Sorunun geçmişi
Nested Set Model, 1990'larda Joe Celko tarafından, ağaç yapılarının SQL içinde yinelemeli bağlantılar olmadan temsil edilmesi için kullanılan bir yöntem olarak popüler hale getirildi. Her düğüme sol (lft) ve sağ (rgt) tamsayı sınırları vererek, model, tüm alt ağaçların basit aralık sorguları ile seçilmesine olanak tanır. Ancak standart, aralık bütünlüğü kısıtlamalarını zorlamadığı için, eşzamanlı toplu eklemeler veya miras aktarım hataları, aralıkların kısmen örtüşerek hiyerarşik anlamları bozduğu bozulmalara sıkça yol açmaktadır. Bu soru, hiyerarşilerin, OLAP küpleri veya öneri motorları için güçlendirilmeden önce doğrulanması gereken veri ambarı senaryolarında ortaya çıkmaktadır.
Sorun
Geçerli bir iç içe set içinde, herhangi iki düğüm ya ayrık olmalıdır (a.rgt < b.lft) ya da katı bir kapsama ilişkisi içinde olmalıdır (a.lft < b.lft VE a.rgt > b.rgt). Bir kısmi örtüşme—a.lft < b.lft ama a.rgt b.lft ile b.rgt arasında kalıyorsa—mantıksal bir imkansızlık yaratır; bu durumda bir düğüm hem kardeş hem de soy olarak görünür ve alt ağaç sorgularını bozar. Bu ihlalleri tespit etmek, her aralık çiftini karşılaştırmayı gerektirir ve bu işlem, prosedürel olarak yapıldığında hesaplama açısından maliyetlidir.
Çözüm
Kapsama olmaksızın geçişleri belirlemek için aralık cebirini kullanarak bir kendine katılma gerçekleştiriyoruz. Öznitelik, düğüm anın düğüm bden önce başladığını ve b'nin aralığı içinde sona erdiğini tespit ederek kısmi bir örtüşme olduğunu gösterir.
SELECT a.id AS violating_node_a, b.id AS violating_node_b, a.lft AS a_left, a.rgt AS a_right, b.lft AS b_left, b.rgt AS b_right FROM nested_set a JOIN nested_set b ON a.lft < b.lft -- a, b'den önce başlar AND a.rgt > b.lft -- a, b başlamadan önce sona erer (kesişim) AND a.rgt < b.rgt -- ama a b sona ermeden önce sona erer (kapsama yok) WHERE a.id < b.id; -- Simetrik çoğaltmaları önleyin
Bu sorgu, yasadışı kesişen tüm düğüm çiftlerini döndürür. Okuma-ağırlıklı üretim ortamlarında çalışabilir hale getirmek için (lft, rgt) ve (rgt, lft) üzerinde bileşik indeksler, O(n²) tam tablo taramalarından O(n log n) aralık aramalarına kadar karmaşıklığı azaltır.
Bir perakende ürün sınıflandırmasının, miras alınan bir IBM DB2 sisteminden bir PostgreSQL veri ambarına sıfır-duraklama ile göçü sırasında, mühendislik ekibi, analitik gösterge panosu için hızlı kategori toplama sorgularını desteklemek amacıyla Nested Set Model'i seçti. ETL boru hattı, lft ve rgt değerlerini toplu pencere fonksiyonları kullanarak hesapladı, ancak miras alınan sistemin export API'sindeki yarış koşulları, 147 örtüşen kategori aralığına yol açan bir hata üretti. Bu örtüşmeler, ürünlerin gelir raporlarında iki kat sayılmasına, tahmini satışların %12 oranında şişmesine sebep oldu.
Üç düzeltme stratejisi değerlendirildi.
Strateji 1: Bir gösterici kullanarak prosedürel doğrulama. Bir PL/pgSQL fonksiyonu, her düğümü yinelemeli olarak kontrol ederek, her düğümü daha yüksek lft değerlerine sahip tüm diğer düğümler ile karşılaştırdı. Kavramsal olarak basit olmasına rağmen, bu yaklaşım satır düzeyinde kilitler aldı ve 2.3 milyon kategori üzerinde tamamlanması 38 dakikayı buldu, bu da envanter güncellemeleri için sıkı beş dakikalık tazelik SLA'sını ihlal etti. Kabul edilemez eşzamanlılık bozulması nedeniyle reddedildi.
Strateji 2: Yeniden yapılandırma yoluyla yinelemeli CTE. Tamamen iç içe set modelini terk etmeyi ve bir yan-z listelerden yeni, doğru aralıklar oluşturmak için yeniden inşa etmeyi düşündük. Bu bozmayı onarırdı ama bir tam tablo yazımı ve katalog API'sinin geçici olarak durdurulmasını gerektirirdi, bu da ürün aramasını devre dışı bırakırdı. Ayrıca, belirli bozuk kayıtları denetlemek yerine belirtinin semptomlarını ele alıyordu.
Strateji 3: Küme tabanlı aralık cebiri (ANSI SQL). Kendine katılma sorgusunu, yalnızca standart SQL özniteliklerini kullanarak uyguladık. Aralık sütunları üzerinde B-tree indeksleri kullanarak doğrulama 4.2 saniyede tamamlandı ve 147 düğüm çiftinin tam olarak hangi ihlalleri gerçekleştirdiğini tespit etti. Bu sayede sadece etkilenen alt kategorileri manuel düzeltmeye karantinaya alırken, katalogun geri kalanını canlı tutmayı başardık.
Strateji 3'ü seçtik çünkü yazarları engellemeden ve duraklama gerektirmeden cerrahi bir hassasiyet sağladı. Sonuç, aralık sınırlarının katı üst kümeler oluşturduğu temiz bir sınıflandırmaydı, referans bütünlüğünü restore ederek, sonraki ACID-uyumlu güncellemelerin yeni örtüşmeler yaratamayacağını garanti etti.
Eşleşmekte olan bir geçerli ebeveyn-çocuk kapsama ilişkisi ile geçersiz kısmi örtüşmeyi, join özniteliğini yazarken nasıl ayırt edebilirsiniz?
Adaylar sıkça kesişimi kapsama ile birleştirirler. a.lft < b.lft VE a.rgt > b.lft (sadece kesişimi kontrol eder) yazarlar ve bu ihlalleri tespit ettiklerini yanlış bir şekilde düşünürler. Kritik detay, uç noktanın dışlanabilirliğidir: katı kapsama için, ebeveynin sağ sınırının çocuğun sağ sınırını geçmesi gerekir (a.rgt > b.rgt). Kısmi bir örtüşme, a.lft < b.lft VE a.rgt > b.lft VE a.rgt < b.rgt durumu gerçekleştiğinde meydana gelir. Başlangıç düzeyindeki kullanıcılar genellikle üçüncü koşulu kaçırırlar, bu da sorgunun geçerli ebeveyn-çocuk çiftleri için yanlış olumlu sonuçlar döndürmesine sebep olur. Ayrıca, kendine çiftleri dışlamak (a.id != b.id) ya da simetrik çoğaltmaları ele almak için a.id < b.id uygulamayı unuturlar, bu da gereksiz ihlal raporlarına yol açar.
Bir düğüm, neden örtüşme göstermediği halde yine de kökten yoksun olarak görünebilir ve bunu yalnızca küme işlemleri kullanarak nasıl tespit edersiniz?
Bir yetim düğüm, hiçbir satırın kendi aralık (lft, rgt) kapsamını içermediği durumda vardır; bu, köke bir yolu olmadığı anlamına gelir. Adaylar genellikle NULL ebeveynler aramak için bir LEFT JOIN ile bunu çözmeye çalışırlar, ancak bu, meşru kök düğümünü (ebeveyn olmaması gereken) gerçek yetimlerden ayırt edemez. Doğru yaklaşım, küresel kökü hariç tutarak NOT EXISTS kullanmaktır:
SELECT c.id FROM nested_set c WHERE NOT EXISTS ( SELECT 1 FROM nested_set p WHERE p.lft < c.lft AND p.rgt > c.rgt ) AND c.lft != (SELECT MIN(lft) FROM nested_set);
Başlangıç düzeyindeki kullanıcıların kaçırdığı uç durum, çoklu kök senaryosudur: Eğer tablo yanlışlıkla iki ayrı ağaç içeriyorsa, ikinci en küçük lft değerine sahip düğüm, yalnızca lft minimumunu kontrol ederse, hiçbir ebeveynin varmış gibi görünmesine neden olabilir. Sorgu, tek bir kökü (minimum lft) açıkça tanımlamalı ve onu dışlamalıdır; aksi takdirde, yanlışlıkla ikinci kökü bir yetim olarak işaretler.
Katı ANSI SQL kullanarak, bir düğümün hiyerarşik olarak ilişkili olmayan iki ayrı ata tarafından kapsandığı çoklu ebeveyn ihlalini nasıl tespit edersiniz?
Bu, iki ata arasındaki örtüşme tespitinden farklıdır çünkü iki ata, ayrık (geçerli kardeşler) olabilir, ancak her ikisi de aynı çocuk düğümünü hatalı bir şekilde kapsar. Bu, ağaç özelliğini (tek ebeveyn) ihlal eder ama atalar arasında bir aralık örtüşmesi yaratmaz. Adaylar genellikle tüm atalar üzerinde GROUP BY child_id HAVING COUNT(*) > 1 denemesi yaparlar, ancak bu geçerli bir derin düğümün doğal olarak birçok atası (büyükanne gibi) olduğu için başarısız olur. Çözüm, anlık ebeveyni tanımlamayı gerektirir: çocuğun lft değerinden daha küçük olan ve maksimum lft değerine sahip olan atadır.
SELECT c.id AS child_id FROM nested_set c JOIN nested_set p ON p.lft < c.lft AND p.rgt > c.rgt WHERE NOT EXISTS ( SELECT 1 FROM nested_set p2 WHERE p2.lft > p.lft AND p2.rgt < p.rgt AND p2.lft < c.lft AND p2.rgt > c.rgt ) GROUP BY c.id HAVING COUNT(*) > 1;
Alt sorgu, aday ile çocuk arasındaki herhangi bir ara düğüm bulunmadığını kontrol ederek hemen ebeveynleri filtreler. Başlangıç düzeyindeki kullanıcılar, bu "en yakın atanın" mantığını kaçırırlar; bunun yerine tüm kapsayıcıları sayar ve her derin düğümü yanlış bir ihlal olarak işaretlerler.