Sorunun cevabı.

Sorunun geçmişi.

Hiyerarşik veri modelleri genellikle ağaç yapıları temsil etmek için komşuluk listeleri veya iç içe setler kullanır. Komşuluk listeleri depolamayı en aza indirirken ve eklemeleri basit hale getirirken, analitik raporlama genellikle "materyalize edilmiş yollar" (örn. "Kök/Kategori/Alt kategori") gerektirir ve bu da önek desenleri kullanarak verimli filtreleme sağlar. SQL:1999'dan önce, bu hiyerarşilerin düzleştirilmesi, prosedürel imleçler veya uygulama tarafı rekursiyonu gerektiriyordu. ANSI SQL standardındaki döngüsel Ortak Tablo İfadelerinin (CTE'ler) tanıtılması, açıklayıcı bir geçiş sağlamış olsa da, derinlik kısıtlamaları ile birlikte belirleyici, sıralı yollar oluşturmak, döngü bitişi ve sıralama kararlılığı ile ilgili karmaşıklıkları beraberinde getiriyor.

Problemin tanımı.

Bir döngüsel komşuluk listesini her bir satırın tam atalar soyunu ayrılmış bir dizi olarak içeren normalleştirilmemiş bir formata dönüştürmeniz gerekiyor (örn. "/A/B/C"). Çözüm üç kısıtlamayı zorunlu kılmalıdır: (1) her seviyedeki kardeşler, yolda lexikografik olarak sıralanmış görünmelidir, (2) geçiş, hatalı veriler üzerinde çoğalan sorguları önlemek için belirlenen maksimum derinliği aşmamalıdır ve (3) uygulama kesinlikle ANSI SQL sözdizimini kullanmalıdır; özel hiyerarşi uzantıları olmamalıdır.

Çözüm.

Çözüm, iki aşamalı bir CTE yaklaşımını kullanır. İlk olarak, döngüsel olmayan bir CTE, her düğümün kardeşleri arasındaki sıralı konumunu bir pencere fonksiyonu kullanarak hesaplar. Bu ön hesaplama gereklidir çünkü ANSI SQL, monoton sonlanmayı sağlamak için CTE'nin döngüsel üyesinde pencere fonksiyonlarına izin vermez. İkinci olarak, bir döngüsel CTE ağacı gezer, düğüm adlarını ve önceden hesaplanmış sıralama anahtarlarını birleştirirken, derinlik sınırını uygular ve WHERE ifadesinde isteğe bağlı döngü tespitini gerçekleştirir.

WITH RECURSIVE 
OrderedNodes AS (
  -- Aşama 1: Kardeşlere belirleyici bir düzen atama
  SELECT 
    node_id, 
    parent_id, 
    node_name,
    ROW_NUMBER() OVER (PARTITION BY parent_id ORDER BY node_name, node_id) AS sibling_order
  FROM taxonomy
),
PathBuilder AS (
  -- Temel üye: Kök düğümleri başlat
  SELECT 
    node_id,
    node_name,
    1 AS depth,
    CAST(node_name AS VARCHAR(1000)) AS materialized_path,
    CAST(sibling_order AS VARCHAR(100)) AS sort_key
  FROM OrderedNodes
  WHERE parent_id IS NULL
  
  UNION ALL
  
  -- Döngüsel üye: Çocukları ekleyin
  SELECT 
    c.node_id,
    c.node_name,
    p.depth + 1,
    p.materialized_path || '/' || c.node_name,
    p.sort_key || '.' || CAST(c.sibling_order AS VARCHAR(100))
  FROM OrderedNodes c
  INNER JOIN PathBuilder p ON c.parent_id = p.node_id
  WHERE p.depth < 5  -- Katı derinlik kısıtlaması
    AND p.materialized_path NOT LIKE '%/' || c.node_name || '%'  -- Döngü koruma
)
SELECT 
  node_id, 
  materialized_path,
  depth
FROM PathBuilder
ORDER BY sort_key;

Hayattan bir durum

Problemin tanımı.

Küresel bir e-ticaret platformu, PostgreSQL veritabanında (ANSI SQL uyumlu modda) 100.000'den fazla kategoriye sahip bir ürün taksonomisi sürdürmektedir. Pazarlama ekibi, tamamen nitelikli kategori yollarını bekleyen bir harici reklam platformu için günlük bir CSV dışa aktarımı gerektiriyor (örn. "Elektronik/Bilgisayarlar/Dizüstü Bilgisayarlar"), her seviyede kesinlikle alfabetik sıralama ile hedef kitle hedeflemesi sağlansın. Mevcut çözüm, N+1 sorgusu yürüten bir Python betiği kullanıyordu ve bu da 20 dakikalık bir çalışma süresine ve sık sık zaman aşımına neden oluyordu.

Düşünülen farklı çözümler.

Çözüm A: Uygulama tarafında önbellekleme ile planlanmış yeniden oluşturma. Ekip, yolları her 6 saatte bir arka planda çalışan bir iş aracılığıyla bir Redis önbelleğinde materyalize etmeyi düşündü. Artıları, basit Python uygulaması ve zirve saatlerinde veritabanı yükünün azaltılmasıydı. Ancak, eksileri büyük veri güncelliği (6 saate kadar), kategoriler yeniden anahtarlandığında önbellek geçersiz kılma karmaşıklığı ve tam ağaç için aşırı bellek tüketimiydi.

Çözüm B: Döngüsel CTE kullanan veritabanı görünümü. Bu yaklaşım, ANSI SQL döngüsel CTE modelini kullanarak talep üzerine yollar hesaplayan bir görünüm oluşturur. Artıları, veri tazeliği garantisi (gerçek zamanlı sonuçlar), tek doğru kaynak ve veritabanının sorgu optimize edicisinden yararlanma. Eksileri, veritabanı sunucusundaki CPU yoğunluğu ve veriler döngüsel referanslar içeriyorsa sonsuz döngü riski idi (örn. bir kategori kazara kendi soyundan birine bağlandığında).

Çözüm C: Tetikleyici ile bakımı yapılan materyalize sütun. Bu, tabloya materialized_path sütunu ekler ve ekleme, güncelleme veya silme işlemleri sırasında tetikleyiciler aracılığıyla güncellerdi. Artıları, son derece hızlı okuma performansı (basit dizin taraması). Eksileri, önemli yazma yükü, alt ağaç taşımaları veya yeniden adlandırmaları yönetmek için karmaşık tetikleyici mantığı ve kardeş isimleri değiştiğinde lexikografik sıralama kısıtlamasını korumada zorluklardı.

Seçilen çözüm ve sonuç.

Ekip, Çözüm B (Döngüsel CTE Görünümü) seçti çünkü okuma-ağır çalışma yükü (100:1 okuma-yazma oranı) tetikleyicilerin bakım yükü olmadan talep üzerine hesaplamadan faydalandı. Döngü riskini azaltmak için, WHERE ifadesinde LIKE desen kontrolünü uyguladılar ve iş kurallarına dayalı olarak 5 seviyelik bir derinlik sınırlaması eklediler. Ayrıca, ana CTE’de pencere fonksiyonu sıralamasını optimize etmek için (parent_id, node_name) üzerinde bir bileşik dizin oluşturdular. Sonuç olarak, dışa aktarma süresi 20 dakikadan 8 saniyeye düştü ve uygulama aşamasında eski verilerde 3 döngüsel referansı tespit edip izole etti.

Adayların sıkça atladığı noktalar

Neden aggrege veya pencere fonksiyonları bir CTE'nin döngüsel üyesinde yer alamaz ve bu, kardeş sıralamasını nasıl etkiler?

ANSI SQL standartları, döngüsel üyenin, döngü sorgusunun monoton ve bir denge noktasına ulaşacağına dair garanti sağlamak için aggrege fonksiyonları (örn. SUM) veya pencere fonksiyonları (örn. ROW_NUMBER) içermesini kısıtlar. Pencere fonksiyonları, tüm çalışma setini materyalize etmeyi ve bölmeyi gerektirir ki bu da döngüsel bitiş için gereken akışsal anlamı ihlal edebilir ve belirsizlik yaratabilir. Sonuç olarak, döngü içinde dinamik olarak kardeş sıralamasını hesaplayamazsınız. Doğru yaklaşım, sıralı pozisyonları önceden bir döngüsel olmayan CTE'de hesaplamak (çözümde gösterildiği gibi) ve ardından bu hesaplanan sütunu döngüsel birleşimde referans almaktır. Adaylar genellikle ROW_NUMBER() ifadesini doğrudan döngüsel SELECT listesine yerleştirme girişiminde bulunur, bu da sözdizimi hatalarına veya öngörülemez yürütme planlarına yol açar.

Döngüsel referansları sahiplenmeden nasıl yönetirsiniz ve PostgreSQL'in CYCLE ifadesi gibi özel döngü tespit sözdizimi kullanmadan?

Saf ANSI SQL, yerleşik bir CYCLE tespit mekanizması sağlamaz (SQL:2023'te CYCLE ve SEARCH ifadeleri tanıtılmıştır; ancak henüz yaygın olarak uygulanmamıştır). Sonsuz döngüyü önlemek için, ziyaret edilen düğümleri manuel olarak takip etmelisiniz. Standart taşınabilir teknik, ziyaret edilen düğüm ID'lerinin ayrılmış bir dizgisini (veya destekleniyorsa bir dizi) biriktirmek ve mevcut node_id'nin o biriktiricide zaten mevcut olup olmadığını kontrol etmektir. WHERE p.materialized_path NOT LIKE '%/' || c.node_id || '%' gibi bir öngörü kullanmak, döngüleri etkili bir şekilde temizler; ancak bu yöntem, dize uzunluğu taşmasını önlemek için makul derinlik sınırlamaları varsayar. Alternatif olarak, daha büyük veri setleri için bir bit dizesi veya hashlenmiş yol kullanabilirsiniz.

İki kardeş düğümü aynı isimleri paylaşırken belirleyici sıralamanın neyi garanti eder ve toplam sıralama neden materyalize edilmiş yollar için kritik önemde?

Belirlilik, kardeşler arasında toplam bir sıralama oluşturmaya dayanır. Eğer pencere fonksiyonu yalnızca ORDER BY node_name kullanıyorsa ve iki kardeş aynı isme sahipse, veritabanı bunları herhangi bir sırayla döndürebilir (uygulama tanımına bağlı), bu da farklı sorgu çalıştırmaları veya veritabanı sürümleri arasında belirsiz yol dizgileriyle sonuçlanır. Bu belirsizlik, sorgu sonuçlarının önbelleğe alınmasını kırar, test etmeyi karmaşıklaştırır ve alt sistemlerde "sarsılan" verilere neden olabilir. Çözüm, ORDER BY node_name, node_id ifadesine tipik olarak bir benzersiz eşitlikçi eklemektir. Bu, her kardeşin benzersiz bir sıralı konuma sahip olmasını garanti eder, bu da materyalize edilmiş yolun ve yardımcı sort_key'in yeniden üretilebilir ve istikrarlı olmasını sağlar.