Topolojik sıralama, belirli köşe noktalarının diğerlerinden önce gelmesi gereken bağımlılık grafiklerinde uygun yürütme dizilerini belirlemek için geliştirilmiş graf teorisi ve programlama matematiğinden kaynaklanmaktadır. Veritabanı ortamlarında, bu gereksinim ETL iş akışlarının, şema taşıma betiklerinin veya hareketsiz veri dönüşümlerinin yönetilmesi gerektiğinde ortaya çıkar. ANSI SQL özyinelemeli CTE'ler, referans bütünlüğünün hiyerarşik işlemler arasında korunmasını sağlayarak her düğüm için en uzun yol derinliğini hesaplayarak geçerli bir toplu düzey elde etmenin açıklayıcı bir çözümünü sunar.
Ana sorun, benzersiz tanımlayıcılar içeren bir tasks tablosu ve ön koşul ilişkilerini tanımlayan bir dependencies tablosu içeren iki ilişkisel yapıdan oluşur. Geçerli bir sıralama, her görevin tüm bağımlılıklarının listelendiğinden sonra yalnızca görünmesi gerektiğinden, her kenar için A düğümünden B düğümüne kadar rank(A) < rank(B) olan sayısal bir sıraya ihtiyaç duyar. Zorluk, bu sıralamayı hareketli değişkenler veya prosedürel döngü olmadan hesaplamaktadır.
Çözüm, toplu düzeyi, graf üzerinde özyinelemeli olarak yayılmaya devam eden tüm doğrudan öncüllerin maksimum düzeyinin bir fazlası olarak hesaplar. Gelen kenarları olmayan kaynak düğümler sıfır düzeyinde başlatılır. Bu yöntem, en uzun zincirin en erken güvenli yürütme konumunu belirlemesi nedeniyle DAG'leri çoklu miras alma yolları ile doğru bir şekilde işler. Özyinelemeli CTE, bağımlılık grafiği ile iteratif olarak bağlanır ve çocuk göreve göre gruplandırarak maksimum üst düzeyin toplanmasını sağlar.
WITH RECURSIVE topo_levels AS ( -- Temel: Giriş derecesi sıfır olan kaynak düğümleri tanımlayın SELECT t.task_id, 0 AS level, CAST(t.task_id AS VARCHAR(1000)) AS path_trace FROM tasks t WHERE NOT EXISTS ( SELECT 1 FROM dependencies d WHERE d.task_id = t.task_id ) UNION ALL -- Özyinelemeli: Max öncül düzeye göre düzey hesaplayın SELECT d.task_id, MAX(tl.level) + 1, MAX(tl.path_trace) || '->' || CAST(d.task_id AS VARCHAR(1000)) FROM dependencies d INNER JOIN topo_levels tl ON d.depends_on_task_id = tl.task_id WHERE tl.level < 1000 -- Özyineleme güvenliği GROUP BY d.task_id HAVING COUNT(DISTINCT d.depends_on_task_id) = ( -- Bu görev için tüm bağımlılıkların çözüldüğünü doğrulayın SELECT COUNT(*) FROM dependencies d2 WHERE d2.task_id = d.task_id ) ) SELECT task_id, level, path_trace FROM topo_levels ORDER BY level, task_id;
Bir finansal risk yönetim platformu, egzotik opsiyonların volatilite yüzeylerine bağımlı olduğu, bu yüzeylerin ise ham piyasa veri akışlarına bağımlı olduğu 800+ türev fiyatlandırma modelinin gece boyunca yeniden hesaplanmasını gerektiriyordu. Bağımlılıklar altı hiyerarşik seviyeye ulaştıkça mevcut manuel Excel takibi başarısız oldu ve aşağıdaki süreçler tamamlanmadan çalıştığında sık sık hesaplama hataları oluştu. Mühendislik ekibi, bu görevleri dış yönetim altyapısı eklemeden sıralamak için atomik, veritabanı yerel bir çözüm gerekti.
Üç mimari desen değerlendirildi. İlki, güvenli yerel ortam için önemli lisans maliyetleri, ağ gecikmesi ve dış durum yönetimi sunan güçlü izleme ve yeniden deneme mantığı sunan Apache Airflow'u benimsemeyi önerdi. İkincisi, psycopg2 kullanarak bağımlılıkları sorgulayıp görevleri sıralı bir şekilde yürütmek için bir Python prosedürel sürücüsü önerdi; esnek olsa da, bu, ağ parçalanmaları açısından savunmasız ve meta veri havuzuyla işlem tutarlılığı eksik olan kırılgan bir dış bağımlılık yarattı. Üçüncü yaklaşım, görev tanımlamaları ve bağımlılıkların zaten bulunduğu veritabanı içinde tüm yönetim mantığını koruyarak özyinelemeli CTE'ler kullanarak toplu sıralamayı tamamen PostgreSQL içinde uyguladı.
Ekip, ACID uyumluluğunu iş akışı meta verileri ile koruduğu, bağımlılık çözümlemesi için ağ yuvarlak gezintilerini ortadan kaldırdığı ve aynı toplu düzeyleri paylaşan paralel yürütme adaylarını belirlemek için veritabanı optimizasyonunu kullandığı için saf SQL çözümünü seçti. Uygulama sonrasında, gece batch penceresi altı saatten kırk beş dakikaya sıkıştı; önceden manuel sıralama tarafından gizlenen içsel paralellik ortaya çıkarılırken, bağımlılık ile ilgili üretim hataları sonraki altı ay boyunca sıfıra düştü.
Giriş grafiği tesadüfi bir döngü içerdiğinde, ANSI SQL özyinelemeli CTE'lerinin döngüsel grafiklerde sonsuz döngü başlatabileceği veya çalışma zamanı hatalarını atabileceği durumlarda sonsuz özyinelemeye karşı nasıl koruma sağlarsınız?
Adaylar genellikle uygulama katmanında DAG özelliklerinin uygulandığını varsayarlar. Üretim ortamında, yetim dairesel referanslar (örneğin, Görev A, B'ye, B, C'ye ve C, A'ya bağımlıdır) standart özyinelemeli CTE'lerin özyineleme sınırlarını aşmasına veya tüm kaynakları tüketmesine neden olur. Dayanıklı çözüm, özyineleme boyunca bir yol izi dizesi veya dizisi taşımaktır ve ardından mevcut düğümün birikmiş yolda zaten mevcut olduğu satırları hariç tutmak için özyinelemeli üyede filtrelemektir. Alternatif olarak, SQL:2023 CYCLE cümlesini (SEARCH DEPTH FIRST ... CYCLE task_id SET is_cycle USING path) tanıtır; bununla beraber döngüleri otomatik olarak tespit eder ve bir boolean bayrağı ayarlayarak sorgunun başarısız olmaktan ziyade düzgün bir şekilde sona ermesini sağlar.
Özyineleme adımı neden MAX kullanarak toplama yapmalıdır, herhangi bir tek öncül düzeyini sadece bir ekleyerek işlememelidir?
Birçok aday, herhangi bir üst görevle bağ kurup onun düzeyini bir artırmayı önerir, oysa DAG'lerdeki düğümlerin genellikle farklı derinliklerde birçok gelen kenarı bulunmaktadır. D'nin hem A (düzey 0) hem de C'ye (düzey 4) bağımlı olduğunu düşünün. MIN veya keyfi bir bağ kullanmak, D'yi düzey 1'e atanarak C'nin D'den önce tamamlanması gerektiği kuralını ihlal eder. MAX toplamı, D'nin düzeyini doğru bir şekilde ayarlayarak en uzun bağımlılık zincirini dikkate almasını sağlar. Bu ayrım, elmas şeklinde bağımlılıklar veya birleştirici iş akışı desenleri gösteren grafikte doğruluk açısından kritik öneme sahiptir.
Birçok düğüm içeren grafikleri optimize etmek için bu sorguyu nasıl iyileştirirsiniz; standart özyinelemeli CTE yaklaşımı tekrar eden tam tablo taramaları nedeniyle ikinci dereceden performans bozulması sergilediğinde?
Büyük grafikler için, basit yaklaşım, uygun dizinleme stratejileri olmaksızın taban tablolarına karşı tekrar eden bağlardan muzdariptir. Adaylar genellikle özyinelemeli CTE'lerin hem kenar tablosunun ana hem de çocuk sütunları üzerindeki dizinlerden büyük ölçüde faydalandığını göz ardı eder. Dizinlemenin ötesinde, bir optimizasyon da gereksiz kenarları ortadan kaldırmak için ilk önce transitif bir azaltma gerçekleştirmek veya grafiği bağlı bileşenlere ayırarak bağımsız olarak işlemektir. Aşırı durumlarda, SQL'nin temelde ilişkisel cebir için optimize edildiğini göz önünde bulundurarak, doğru mimari karar, grafiği özel bir işleme motoruna (örneğin, GraphX, Neo4j veya NetworkX) dışa aktarmaktır; ancak SQL sınırlamasını anlamak olgun mühendislik yargısını gösterir.