Cevap

Sorunun Tarihçesi

Konteyner yerleştirme ve parti birikimleme sorunu, ilişkisel veritabanlarından önce, operasyon araştırması ve lojistik optimizasyonunda ortaya çıkmıştır. ANSI SQL'da bu sorun, tarihsel olarak, standart küme tabanlı işlemler "sıfırlamalı sürekli toplamlar" olarak referans olamadığı için, PL/SQL veya T-SQL imleçleri gibi prosedürel uzantılar olmadan çözülemezdi. SQL:1999'da rekursif CTE'lerin tanıtılması, yinelemeli birikim için teorik temel sağladı, ancak birçok uygulama başlangıçta büyük veri kümelerinde performans sınırlamaları ile karşılaştı. Modern sorgu optimizasyon araçları, üretim parti kontrolleri ve finansal işlem gruplama için etkili çözümler sağlamak üzere rekursif yürütme planlarını geliştirdi. Bu model, prosedürel algoritmaların deklaratif ANSI SQL mantığına dönüştürülmesinin temel bir testidir.

Sorun

Ağırlık veya değere sahip sıralı bir öğe dizisini işlememiz gerekiyor ve bunları her bir partinin toplamının önceden tanımlanmış kapasiteyi aşmayacak şekilde ardışık partilere atamamız gerekiyor. Bir sonraki öğeyi eklemek eşik değerini aşacaksa, yeni bir parti başlar. Bu, koşullu olarak sıfırlanan bir sürekli toplayıcıyı korumayı gerektirir; bu, ardışık satır işlev toplamalarına bağlı olan basit bir işlem değildir. Çözüm, bireysel kapasiteyi aşan öğeler (hata veya tek öğe taşma partisi) ile boş girişler de dahil olmak üzere uç durumları ele almalıdır ve ANSI SQL içinde, satıcıya özel prosedürel uzantılar olmadan çalışmalıdır.

Çözüm

Sıralı diziyi yinelemeli olarak işleyen bir rekursif CTE kullanıyoruz ve mevcut parti numarasını ve bu partinin birikmiş ağırlığını taşıyoruz. Temel üye, ilk öğeyi parti 1 olarak ve ağırlığını mevcut toplam olarak başlatır. Rekursif üye, bir sonraki ardışık öğeye katılır, ağırlığının kapasiteyi aşıp aşmadığını hesaplar; eğer aşıyorsa, parti numarasını artırır ve toplayıcıyı yeni öğenin ağırlığına sıfırlar, aksine, mevcut partiyi koruyup toplayıcıya ekler. ROW_NUMBER() kullandık, böylece katı bir gezinti sırası kurabiliriz ve sonsuz rekursiyonu önlemek için bir derinlik sayısı üzerinden filtreleriz ya da yalnızca ardışık satırlara katılırız. Son olarak, gerekli olduğu takdirde, belirli parti atamalarını veya birikim sonuçlarını seçiyoruz.

WITH RECURSIVE ordered_items AS (
    SELECT 
        item_id, 
        weight, 
        ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn
    FROM items
),
batch_accumulator AS (
    -- Temel: ilk öğe 1. partide başlar
    SELECT 
        item_id, 
        weight, 
        rn, 
        1 AS batch_number, 
        weight AS current_batch_sum
    FROM ordered_items
    WHERE rn = 1
    
    UNION ALL
    
    -- Rekursif: sonraki öğeyi işle
    SELECT 
        oi.item_id,
        oi.weight,
        oi.rn,
        CASE 
            WHEN ba.current_batch_sum + oi.weight > 100 THEN ba.batch_number + 1 
            ELSE ba.batch_number 
        END AS batch_number,
        CASE 
            WHEN ba.current_batch_sum + oi.weight > 100 THEN oi.weight 
            ELSE ba.current_batch_sum + oi.weight 
        END AS current_batch_sum
    FROM batch_accumulator ba
    JOIN ordered_items oi ON oi.rn = ba.rn + 1
)
SELECT item_id, batch_number, weight
FROM batch_accumulator
ORDER BY rn;

Hayattan bir durum

Konu: E-ticaret karşılama merkezi için depo paketleme otomasyonu.

Sorun Betimlemesi: Otomatik konveyor sistemi siparişleri sırayla işler, ancak bunları 20kg ağırlık sınırı olan nakliye konteynerlerine gruplamak zorundadır. Her siparişin değişken bir ağırlığı vardır. Sistem, hat boyunca öğeler gelirken her nakliye etiketi için hangi konteyner kimliğinin basılacağını bilmelidir, grupları işlemek için duraksamadan. Uygulama katmanı kodu kullanarak yapılan ilk denemeler yüksek trafik dönemlerinde darboğazlar ve yarış koşulları oluşturdu.

Düşünülen Farklı Çözümler:

Çözüm 1: Geçici tablolar ile uygulama katmanı birikimi. Uygulama, öğeleri alır, bir döngüde sürekli toplamları hesaplar ve partileri veritabanına eklerdi. Bu yaklaşım önemli ağ gecikmesi ve işlem yükü getirdi, uygulama sunucusu ve veritabanı arasında birden fazla gidiş-dönüş gerektirdi. Ayrıca, birden fazla paketleme hattı aynı anda çalıştığında eş zamanlılık kontrolünü karmaşıklaştırdı ve tablo kilitlenmesine neden oldu.

Çözüm 2: SUM() OVER (ORDER BY ...) kullanarak saf pencere işlevi yaklaşımı. Bu, sınırsız sürekli toplamı kapasiteye bölümleyerek partiler oluşturmaya çalıştı. Ancak bu, öğeleri sabit pozisyona dayalı olarak atamakta başarısız oldu, bu da partilerin her zaman kapasiteyi aşmasına neden oldu çünkü bireysel öğelerin ağırlıkları farklıydı. Modüler yaklaşım yalnızca sabit boyutlu öğeler için çalışır, bu nedenle değişken ağırlık gereksinimi için uygun değildir.

Çözüm 3: ANSI SQL içinde uygulanan rekursif CTE. Bu çözüm, tüm hesaplamaları sunucu tarafında tek bir sorgu yürütmesinde gerçekleştirerek ağ yükünü ortadan kaldırır. Durumlu birikim ve sıfırlama mantığını doğru bir şekilde ele alır. Her ne kadar bazı veritabanı yapılandırmalarında rekursiyon derinlik sınırlamaları olsa da, depo operasyonel kısıtlamaları (partilerin nadiren 100 öğeyi aşması) bunu aşmayacağından emin oldu. Bu yaklaşım, atomiklik, tutarlılık ve uygulama durumu yönetimini ortadan kaldırması açısından seçildi.

Sonuç: Sorgu, 50.000 öğeyi saatte alt saniye gecikme ile başarıyla işledi, konteyner kimliklerini doğru bir şekilde atadı ve ağırlık kısıtlamalarına saygı gösterdi. Çözüm, yarış koşullarını ortadan kaldırdı ve bir ayrı birikim mikro hizmeti gereksinimini ortadan kaldırarak altyapı maliyetlerini düşürdü.

Adayların Genellikle Göz Ardı Ettiği Noktalar

1. İlk öğeyi, bireysel olarak parti kapasitesini aştığında nasıl düzgün bir şekilde ele alıyorsunuz?

Birçok aday, tüm öğelerin kapasiteye sığacağını varsayıyor. Bireysel bir öğenin ağırlığı parti eşik değerini aşarsa, rekursif mantığın ya bir hata bayrağı koyması ya da onu izolasyon taşma partisine yerleştirmesi gerekir. Doğru uygulama, başlangıç kapasitesini kontrol etmek için temel üyeye bir CASE ifadesi ekler ve rekursif üyeye, oi.weight > capacity olduğunda yeni bir parti zorlamak için bir ifade ekler. Aksi takdirde, sistem aşırı boyutlu öğeleri mevcut partilere eklemeye çalışabilir veya parçaları bölmeye çalışarak sonsuz rekursiyona yol açabilir.

2. Neden rn = rn + 1 üzerinden katılmak sonsuz rekursiyon riskini taşır ve bunu nasıl önlersiniz?

Adaylar sıklıkla oi.rn = ba.rn + 1 kullanır ve katı ardışıklığı varsayıyor, ancak kaynak verilerde boşluklar varsa veya ROW_NUMBER() sıralaması, benzersiz sıralama anahtarları nedeniyle yinelenen ikililer üretirse, katılma döngü oluşturabilir veya satırları atlayabilir. Ayrıca, verilerin sıralama tanımında dairesel referansları varsa, rekursiyon asla sona ermez. Çözüm, sequence_order'un belirleyici ve benzersiz olmasını sağlamak ve her rekursyon seviyesinde artan bir derinlik sayısı sütunu eklemeyi gerektirir; veri bozulması durumunda kaçak sorguları önlemek için CHECK kısıtlaması veya depth < 1000 şartlı ifadesi eklenmelidir.

3. Bu algoritmadaki rekursyon derinliği ve genişliği arasındaki performans etkileri nelerdir?

Junior geliştiriciler genellikle rekursif CTE'leri yinelemeli döngüler olarak değerlendirir, her rekursyon seviyesinin o derinlikteki tüm uygun satırları işlediğini (genişlik öncelikli) anlamadıkları için. rn üzerinde uygun dizinleme olmadan oi.rn = ba.rn + 1 ile JOIN etmenin, iç içe döngü işlemleri olarak karekök olarak ölçekleneceğini gözden kaçırıyorlar. Doğru yaklaşım, dizinlenmiş bir sıralama sütunu sağlamak ve ANSI SQL rekursiyonunun ara sonuçları somutlaştırdığını anlamak; bu, büyük partiler için önemli miktarda bellek tüketebilir. Adayların, milyonlarca satır yerine saf rekursiyon yerine daha küçük parçalar halinde işlem yaparak veya yinelemeli parti işleme ile optimize etmeyi belirtmeleri gerekir.