Sorunun yanıtı.

Sorunun geçmişi.

Kadane'nin Algoritması, 1984 yılında Jay Kadane tarafından formüle edilen en büyük alt dizi problemini dinamik programlama ile çözmektedir; mevcut konumda sona eren maksimum toplamı ve karşılaşılan küresel maksimumu takip eder. Bu zorunlu modeli açıklayıcı ANSI SQL'ye çevirmek, Yinelemeli CTE'ler aracılığıyla sıralı yinelemeyi simüle etmeyi gerektirir; çünkü standart pencere işlevleri, önceki satırların hesaplanmış sonuçlarına karşılıklı olarak bağımlı olan çalıştırma toplamlarını ifade edemez. Bu sorun, bir adayın küme tabanlı işlem kısıtlamaları içinde karmaşık algoritmik mantığı uygulama yeteneğini test eder.

Sorun.

Sıralı sayısal gözlemlerden oluşan bir tablodan (örneğin, günlük kar/zarar) en yüksek toplamı üreten tek bir ardışık satır bloğunu tanımlamak amacı vardır. Basit bir çalışan toplamın aksine, optimal alt dizi herhangi bir keyfi noktada başlayıp sona erebilir ve her satırda mevcut alt diziyi uzatma veya yenisini başlatma kararı, hemen önceki alt dizinin biriktirilmiş toplamına bağlıdır—bu, basit toplamayı yasaklayan bir yinelemeli tanım oluşturur.

Çözüm.

İlk satırı, hem current_max_ending_here hem de global_max_so_far olarak değeri ile başlatarak bir Yinelemeli CTE kullanıyoruz. Yinelemeli üye, sıralama anahtarı kullanarak bir sonraki satırı birleştirir, yeni current_max'ı GREATEST(current_value, previous_current_max + current_value) olarak hesaplar ve global_max'ı GREATEST(previous_global_max, new_current_max) olarak günceller. Son bir toplama, tüm yinelemelerde maksimum global_max'ı seçer. Bu yaklaşım, her bölüm için O(n) zamanında çalışırken tamamen küme tabanlı kalır.

WITH RECURSIVE numbered AS (
    SELECT 
        partition_id,
        observation_date,
        value,
        ROW_NUMBER() OVER (PARTITION BY partition_id ORDER BY observation_date) AS rn
    FROM daily_returns
),
kadane AS (
    -- Bağlantı: her bölüm için ilk satırı başlatma
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- Yinelemeli adım: durumu ileriye taşımak
    SELECT 
        n.partition_id,
        n.rn,
        n.value,
        GREATEST(n.value, k.current_max_ending_here + n.value) AS current_max_ending_here,
        GREATEST(k.global_max_so_far, GREATEST(n.value, k.current_max_ending_here + n.value)) AS global_max_so_far
    FROM kadane k
    JOIN numbered n 
        ON k.partition_id = n.partition_id 
        AND n.rn = k.rn + 1
)
SELECT partition_id, MAX(global_max_so_far) AS maximum_subarray_sum
FROM kadane
GROUP BY partition_id;

Hayatta bir durum

Bir nicel ticaret masası, bir momentum stratejisi için optimum tarihsel pencereyi tanımlamak zorundaydı—özellikle her varlık sınıfı için en yüksek kümülatif getiriyi sağlayan ticaret günlerinin ardışık dizisini. Veri seti, hisse sembolüne göre bölümlere ayrılmış milyonlarca günlük P&L kaydı içeriyordu ve araştırma ekibi, binlerce menkul kıymet arasında anlık analiz yapmak için alt saniye gecikme gereksinimi duyuyordu.

İlk konsept kanıtı, tüm olası başlangıç ve bitiş tarihlerini üretmek için tabloyu kendisiyle çapraz birleştiren bir brüt kuvvet kendi kendine birleştirme yaklaşımını kullandı ve ardından bunlar arasındaki toplamı topladı. Bu Yinelemeli CTE gerektirmese de ve kavramsal olarak basit olsa da, O(n²) karmaşıklığı, yürütme saatlerce sürdükten sonra sorgu zaman aşımına neden olarak, aşırı CPU ve I/O tüketimi nedeniyle üretim ölçeğinde analiz için uygulanabilir olmaktan çıkardı.

Alternatif bir yaklaşım, Python ile birlikte psycopg2 kullanarak bir prosedürlü işaretçi ile satırları yinelemeyi ve akışkan değişkenleri korumayı gerektirdi. Bu, sezgisel zorunlu mantık sağladı ve kolay hata ayıklama sundu, ancak veri transferi aşamasını azaltmak için ekibin veri tabanında hesaplama gereksinimlerini ihlal etti ve işaretçi tabanlı işleme, gidiş-dönüş gecikmesi ve küme tabanlı optimizasyon eksikliği nedeniyle zayıf performans sergiledi.

Kadane'nin Algoritmasını simüle eden Yinelemeli CTE uygulaması seçildi. Bu çözüm, her bölümü tek bir doğrusal geçişte işledi, her yineleme seviyesinde yalnızca iki skalar değer sakladı ve veritabanı motorunun yinelemeli sorgular için yerel optimizasyonunu kullandı. Tüm veri seti boyunca istenen milisaniye seviyesindeki yanıt sürelerine ulaşırken, tamamen açıklayıcı kalmayı başardı.

Uygulama, 400ms içinde beş binden fazla menkul kıymet için maksimum kârlı süreleri belirlemeyi başardı. DBA ekibi, benzer "en iyi pencere" analizleri, risk metrik hesaplamaları ve oynaklık kümeleme tespiti dahil olmak üzere bu modeli benimsedi.

Adayların genellikle kaçırdığı noktalar

Yinelemeli CTE negatif değerler içeren partisyonlarla nasıl başa çıkıyor ve başlangıçta kullanılan bağlantı satırı seçimi neden hatalı bir şekilde sıfır dönüşünü engelliyor?

Birçok aday, bağlantı üyesinde current_max ve global_max'ı sıfıra başlatmaktadır ki bu, algoritmanın tüm negatif diziler için sıfır döndürmesine yol açar (yanlış bir biçimde boş bir alt dizinin optimum olduğunu ileri sürerek). Doğru yaklaşım, her bölümde her iki toplamı da ilk satırın gerçek değeriyle başlatmaktır. Bu, [-5, -2, -8] gibi bir dizide sorgunun doğru bir şekilde -2 döndürmesini sağlar, bu da alt dizinin en az bir eleman içermesi koşuluna uyar. Bu kenar durumunu dikkate almamanın sonucunda, sadece kayıpları içeren dönemlerde sessiz mantıksal hatalar ortaya çıkar.

Maksimum alt dizinin gerçekten başlangıç ve bitiş sınırlarını (belirli satırları) alabilir misiniz, yalnızca toplam değerini değil, sadece ANSI SQL kullanarak?

Evet, ama yinelemeli CTE'yi meta verileri takip edecek şekilde genişletmeyi gerektirir. İki ek sütunu, current_start_rn (şu anki aday alt dizinin başlangıç indeksi) ve best_start_rn/best_end_rn (küresel maksimumun sınırları) ile ileri taşımak zorundasınız. Yinelemeli üyede, mevcut değer yalnızca genişletilmiş toplamdan yüksekse, current_start_rn'yi mevcut row_num olarak ayarlayın; aksi takdirde, onu önceki satırdan alın. global_max_so_far güncellendiğinde, mevcut row_num'u best_end_rn ve current_start_rn'yi best_start_rn olarak kaydedin. Bu, Yinelemeli CTE'lerin yalnızca skaler toplama değil, karmaşık durum nesnelerini de koruyabileceğini gösterir, böylece en iyi pencerenin yerini yeniden inşa etme imkanını sunar.

Bu problem neden standart pencere fonksiyonları gibi SUM() OVER veya MAX() OVER kullanılarak çözülemez ve hangi özel SQL standardı, pencere tabanlı bir yaklaşımı engeller?

Standart pencere fonksiyonları, statik olarak tanımlanmış çerçeveler (örneğin, ROWS BETWEEN) üzerinden toplamları hesaplar. Maksimum alt dizi problemi, mevcut satırı dahil etme kararının önceki satırın toplamının sonucuna bağlı olduğu bir çalışan toplamı gerektirir—özellikle, bu önceki toplam olumlu mu. Bu, karşılıklı bağımlılık veya yineleme oluşturur ve pencere fonksiyonlarının ifade edemeyeceği bir durumdur çünkü bir sonuç kümesindeki hemen önceki satırın pencere fonksiyonunun çıktısını referans alma yeteneğinden yoksundurlar. Yinelemeli CTE'ler gereklidir çünkü bir yinelemenin çıktısının bir sonraki için girdi olarak hizmet etmesine olanak tanır, böylece açıklayıcı paradigmanın içinde satır bazında durum birikimli hesaplamayı mümkün kılar.