Sütunlu Depolama Biçimleri

Önceki ders hesabın çevresindeki eşgüdüm kalemini saydı ve bir aşamanın kaç kalem eklediğini yazdı, ama aşama başladığında bölümlerin ne okuduğunu hiç açmadı. Bir bölüm kendi payını bir dosyadan okur ve o dosyanın düzeni, aynı cevabı üretmek için kaç değere dokunulacağını belirler.

Bu dersin ölçüsü okunan değer sayısıdır ve ölçülen şey bir motor değil bir dosyadır. Ayrım önemlidir: M26/K04’ün başarım konusu aynı ölçü birimini kullanarak okuma yolunu ölçtü — bir motorun süzgeci ne zaman uyguladığı, maddeleştirmeyi ne zaman yaptığı, kümenin hangi sütuna göre sıralandığı. Burada okuma yolu sabittir ve yazma sırası da sabittir; oynayan tek şey dosyanın kendi düzenidir: değerler sütun sınırlarıyla mı ayrılmış, satır kümelerine mi bölünmüş, satır kümesi başlığı var mı ve o başlık ne kadar yer tutuyor.

• OA19. Küme K03–K05’ten devralınır ve kurgudur: 3.199 satır, 1.329 abone, üç dönem, beş bölge, tarife basamakları 10/25/40 m³. Yedi sütunla yazılır ve toplam 22.393 değer eder. Modeldir.
• OA20. Hiçbir dosya biçimi ürünü kullanılmaz; üç düzen bellekte modellenir ve okunan her değer sayılır. Modeldir.
• OA21. Yazma sırası sabittir: dosya kaynağın verdiği abone sırasında yazılır. Sıralama kararının atlamaya etkisi M26/K04’te ölçüldü ve burada tekrarlanmaz.
• OA22. Satır kümesi başlığı sütun başına üç değer taşır: en küçük, en büyük ve satır sayısı. Başlık dosyaya yazılır ve okunması da sayılır.
• OA23. Bir satır kümesi, süzgeç aralığı o kümenin en küçük ile en büyük değeri arasına hiç düşmüyorsa açılmaz.
• OA24. Sorgu sabittir: belirli bir abone aralığındaki toplam tüketim. İki sütun ister ve cevabı 8.869,88 m³’tür.

Üç Düzen, Tek Sorgu

# duzen.py — ayni KURGU kume uc dosya duzeninde yazilir ve tek bir sorgu ucunde
# de kosulur. MODELDIR: hicbir dosya bicimi urunu kullanilmaz; duzenler bellekte
# modellenir ve olcu, cevabi uretmek icin okunan deger sayisidir.
import math

TOHUM, HAM, M32 = 20260218, 1400, 0xFFFFFFFF
BOLGE = [("kuzey", 0.28, 21), ("guney", 0.22, 17), ("dogu", 0.18, 26),
         ("bati", 0.14, 14), ("merkez", 0.18, 23)]
SUTUN = ("abone_no", "bolge", "donem", "hane", "memnuniyet", "tuketim_m3", "basamak")


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


def ayrik(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


def basamak(v):
    return "0-10" if v <= 10 else "10-25" if v <= 25 else "25-40" if v <= 40 else "40 ustu"


KUME = []
for i in range(HAM):
    r = uretec(TOHUM + i)
    b = BOLGE[ayrik(r(), [x[1] for x in BOLGE])]
    hane = 1 + ayrik(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    memnun = 1 + ayrik(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() < 0.046:
        continue
    no, q = 10001 + i, uretec(TOHUM + 7000 + 10001 + i)
    for d in range(ayrik(q(), [0.05, 0.12, 0.21, 0.62])):
        v = 0.0 if q() < 0.038 else math.floor(
            b[2] * math.exp((q() + q() + q() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100
        KUME.append((no, b[0], d + 1, hane, memnun, v, basamak(v)))
        q()

N, S = len(KUME), len(SUTUN)
ALT, UST = 10601, 10800          # sorgu: bu abone araligindaki toplam tuketim
sec = [s for s in KUME if ALT <= s[0] <= UST]
print(f"tohum {TOHUM}; {N} satir, {S} sutun, {N * S} deger")
print(f"dosya kaynagin verdigi sirada yazildi: abone {min(s[0] for s in KUME)} - "
      f"{max(s[0] for s in KUME)}")
print(f"sorgu araligi {ALT}-{UST}: {len(sec)} satir eslesir, dogru cevap "
      f"{sum(s[5] for s in sec):.2f} m3")

tohum 20260218; 3199 satir, 7 sutun, 22393 deger
dosya kaynagin verdigi sirada yazildi: abone 10001 - 11399
sorgu araligi 10601-10800: 453 satir eslesir, dogru cevap 8869.88 m3

Kümenin sınırı 22.393 değer. Sorgu bu değerlerin 453 satırını ilgilendiriyor ve iki sütununu istiyor; yani cevabın gerçekten ihtiyaç duyduğu değer 906 tane. Aradaki oran bu dersin bütün tablolarının çerçevesidir: bir düzen ne kadar iyiyse okunan değer o 906’ya o kadar yaklaşır ve hiçbir düzen onun altına inemez.

# okuma.py — ayni sorgu uc duzende kosulur. Olcu: okunan deger sayisi.
# D1 satir sirali duz duzen, D2 sutun sinirli tek satir kumesi,
# D3 satir kumeli ve baslikli sutunlu duzen.
ISTENEN = ("abone_no", "tuketim_m3")
SUZGEC, BASLIK_DEGERI = "abone_no", 3      # en kucuk, en buyuk, satir sayisi


def kumeler(r):
    return [KUME[i:i + r] for i in range(0, N, r)]


def d1():
    return N * S, N, "satirin butun alanlari bitisik"


def d2():
    return N * len(ISTENEN), N, "yalniz istenen sutunlar"


def d3(r, hepsi=False):
    g = kumeler(r)
    baslik = BASLIK_DEGERI * len(g) * (S if hepsi else 1)
    acilan = [k for k in g if not (max(x[0] for x in k) < ALT
                                   or min(x[0] for x in k) > UST)]
    veri = sum(len(k) for k in acilan) * len(ISTENEN)
    return baslik + veri, sum(len(k) for k in acilan), len(g) - len(acilan)


print(f"sorgu {len(ISTENEN)} sutun istiyor: {', '.join(ISTENEN)}; "
      f"baslik satir kumesi basina {BASLIK_DEGERI} deger")
print(f"{'duzen':<40}{'okunan deger':>14}{'okunan satir':>14}{'oran':>8}")
t1, s1, _ = d1()
t2, s2, _ = d2()
t3, s3, atlanan = d3(512)
print(f"{'D1 satir sirali duz duzen':<40}{t1:>14}{s1:>14}{t1 / t1:>7.2f}x")
print(f"{'D2 sutun sinirli, tek satir kumesi':<40}{t2:>14}{s2:>14}{t1 / t2:>7.2f}x")
print(f"{'D3 satir kumeli (512) ve baslikli':<40}{t3:>14}{s3:>14}{t1 / t3:>7.2f}x")
print(f"D3'te {len(kumeler(512))} satir kumesinin {atlanan} tanesi hic acilmadi")

sorgu 2 sutun istiyor: abone_no, tuketim_m3; baslik satir kumesi basina 3 deger
duzen                                     okunan deger  okunan satir    oran
D1 satir sirali duz duzen                        22393          3199   1.00x
D2 sutun sinirli, tek satir kumesi                6398          3199   3.50x
D3 satir kumeli (512) ve baslikli                 2069          1024  10.82x
D3'te 7 satir kumesinin 5 tanesi hic acilmadi

Üç düzen aynı cevabı veriyor ve okunan değer 22.393’ten 2.069’a iniyor — 10,82 kat. Kazanç iki ayrı düzen özelliğinden gelir ve tablonun her satırı birini ekliyor.

Birinci özellik sütun sınırıdır. Satır sıralı düz düzende bir satırın yedi alanı yan yana yazılmıştır; iki alan okumak için yedisini de geçmek gerekir. Sütun sınırı çekilmiş bir dosyada her sütun kendi bitişik alanındadır ve yalnız iki tanesi okunur: 22.393 değer 6.398’e iner. Bu kazanç bir sorgudan ya da bir motordan değil, dosyanın nasıl yazıldığından gelir.

İkinci özellik satır kümesi ile başlıktır. Dosya 512 satırlık yedi kümeye bölünmüş ve her kümenin abone sütunu için en küçük, en büyük ve satır sayısı yazılmış. Sorgu aralığı bir kümenin sınırlarına hiç değmiyorsa o küme açılmıyor; yedi kümenin beşi açılmadı ve okunan satır 3.199’dan 1.024’e indi. Başlık okumanın bedeli 21 değer, karşılığında kurtardığı 4.350 değer.

Üçüncü sütun atlamanın kalan payını gösteriyor. Sorgu 453 satır istiyor, açılan satır 1.024; aradaki 571 satır okunuyor ve süzgeç onları teker teker eliyor. Sebep atlamanın satır kümesi tanesinde olmasıdır: bir küme aralığa bir satırla bile değiyorsa tümüyle açılır. Atlamanın inceliği satır kümesi boyutuyla belirlenir ve bu, bir sonraki bölümün konusudur.

Satır Kümesi Boyutu Bir Yazma Kararı

# satir_kumesi.py — satir kumesi boyutu bir YAZMA karari. Kucuk satir kumesi
# ince atlama ve cok baslik, buyuk satir kumesi kaba atlama ve az baslik verir.
# Yazma sirasi sabittir: kaynagin verdigi abone sirasi.
print(f"{'satir kumesi':<14}{'kume':>6}{'baslik':>8}{'atlanan':>9}"
      f"{'acilan satir':>14}{'veri':>7}{'toplam':>8}{'oran':>8}{'tum baslik':>12}")
en_iyi = None
for r in (32, 64, 128, 256, 512, 1024, 3199):
    g = kumeler(r)
    toplam, acilan, atlanan = d3(r)
    tumu = d3(r, True)[0]
    baslik = BASLIK_DEGERI * len(g)
    print(f"{r:<14}{len(g):>6}{baslik:>8}{atlanan:>9}{acilan:>14}"
          f"{acilan * len(ISTENEN):>7}{toplam:>8}{t1 / toplam:>7.2f}x{tumu:>12}")
    if en_iyi is None or toplam < en_iyi[1]:
        en_iyi = (r, toplam)
tum = min(((r, d3(r, True)[0]) for r in (32, 64, 128, 256, 512, 1024, 3199)),
          key=lambda x: x[1])
print(f"yalniz suzgec sutununun basligi okunursa en iyi satir kumesi boyutu "
      f"{en_iyi[0]}: {en_iyi[1]} deger, {t1 / en_iyi[1]:.2f} kat")
print(f"butun sutunlarin basligi okunursa en iyi boyut {tum[0]}: {tum[1]} deger, "
      f"{t1 / tum[1]:.2f} kat; ayni dosya, iki okuma karari, iki ayri en iyi")

# Kazanc, sorgunun kac sutun istedigine baglidir.
print(f"{'istenen sutun':<15}{'D1':>8}{'D2':>8}{'D2 oran':>10}"
      f"{'D3 (128)':>10}{'D3 oran':>10}")
for k in (1, 2, 3, 5, 7):
    ISTENEN = SUTUN[:k]
    a, _, _ = d2()
    b = d3(128)[0]
    print(f"{k:<15}{t1:>8}{a:>8}{t1 / a:>9.2f}x{b:>10}{t1 / b:>9.2f}x")
ISTENEN = ("abone_no", "tuketim_m3")

satir kumesi    kume  baslik  atlanan  acilan satir   veri  toplam    oran  tum baslik
32               100     300       85           480    960    1260  17.77x        3060
64                50     150       42           512   1024    1174  19.07x        2074
128               25      75       20           640   1280    1355  16.53x        1805
256               13      39       10           768   1536    1575  14.22x        1809
512                7      21        5          1024   2048    2069  10.82x        2195
1024               4      12        3          1024   2048    2060  10.87x        2132
3199               1       3        0          3199   6398    6401   3.50x        6419
yalniz suzgec sutununun basligi okunursa en iyi satir kumesi boyutu 64: 1174 deger, 19.07 kat
butun sutunlarin basligi okunursa en iyi boyut 128: 1805 deger, 12.41 kat; ayni dosya, iki okuma karari, iki ayri en iyi
istenen sutun        D1      D2   D2 oran  D3 (128)   D3 oran
1                 22393    3199     7.00x       715    31.32x
2                 22393    6398     3.50x      1355    16.53x
3                 22393    9597     2.33x      1995    11.22x
5                 22393   15995     1.40x      3275     6.84x
7                 22393   22393     1.00x      4555     4.92x

İlk tablo dersin gizlenen kararıdır. Satır kümesi boyutu bir dosya yazılırken seçilir, sorgu yazılırken değil, ve iki yönde de bedeli vardır. Küçük kümede atlama incelir — 32 satırlık kümede yüz kümenin 85’i atlanıyor ve yalnız 480 satır açılıyor — ama başlık 300 değer okutuyor, veri payının neredeyse üçte biri. Büyük kümede başlık ucuzlar, 3.199 satırlık tek kümede yalnız üç değer, ama atlanacak hiçbir şey kalmaz ve okuma 6.401 değere çıkar.

En az değer okutan boyut 64 satırdır: 1.174 değer ve 22.393’e göre 19,07 kat. Tablonun tepesi keskin değildir — 32 ile 128 arasındaki bütün boyutlar 16 katın üstünde kalır — ama uçlar pahalıdır ve iki uç iki ayrı sebeple pahalıdır. Bu tabloda ölçülen şeyin bir motor davranışı olmadığını tekrar yazmak gerekiyor: yazma sırası yedi satırda da aynıdır, sorgu aynıdır, okuma yolu aynıdır. Değişen tek şey dosyaya kaç satırda bir başlık yazıldığıdır.

Tavanın nerede olduğunu da yazmak gerekiyor. Cevabın gerçekten ihtiyaç duyduğu değer 906’ydı; en iyi düzen 1.174 değer okuyor, yani ulaşılabilir en iyiye 1,30 kat uzakta. Kalan fark iki kalemden oluşuyor: 150 değerlik başlık ve süzgeci geçemeyen 59 satırın 118 değeri. Bu iki kalem hiçbir satır kümesi boyutunda birlikte sıfırlanmaz, çünkü biri boyutla büyür diğeri boyutla küçülür. Bir dosya düzeninin işi sorgunun ihtiyacını sıfır bedelle karşılamak değil, iki kalemin toplamını en küçük tutan boyutu bulmaktır.

Son sütun ikinci kararı ekliyor. Bazı düzenlerde okuyucu yalnız süzgeç sütununun başlığını çeker, bazılarında satır kümesinin bütün sütun başlıkları tek blok halinde durur ve birlikte okunur. İkinci durumda başlık yedi kat pahalıdır ve en iyi boyut 64’ten 128’e taşınır: 1.805 değer, 12,41 kat. Aynı dosya, iki savunulabilir okuma kararı, iki ayrı en iyi boyut. Bir düzenin “en iyi satır kümesi boyutu” diye tek bir sayısı yoktur; hangi başlığın okunduğu yazılmadan o sayı üretilemez.

İkinci tablo kazancın sorguya bağlı olduğunu gösteriyor. Sütun sınırının kazancı istenen sütun sayısıyla erir ve yedi sütunun hepsi istendiğinde 1,00 kata iner: bütün sütunları okuyan bir sorgu için sütunlu düzen düz düzenden farksızdır. Satır kümesi atlaması ise erimez, çünkü satır atlamak sütun seçmekten bağımsızdır; aynı satırda oran 4,92 katta kalır. Sütun sınırı okunmayacak sütunu atlatır, satır kümesi başlığı okunmayacak satırı; ikisinin kazancı çarpılır ve biri sıfırlandığında diğeri sürer.

Bu ayrım bir dosya düzeni seçilirken hangi sorunun sorulacağını belirler. Az sütun okuyup çok satır tarayan sorgular sütun sınırından kazanır; belirli bir aralığı okuyan sorgular satır kümesi başlığından. İkisini de yapmayan bir sorgu — bütün sütunları ve bütün satırları isteyen bir dışa aktarım — hiçbir düzenden kazanmaz: sütun sınırı 1,00 kat verir, atlanacak satır kümesi bulunmaz ve okuma başlıkların değeri kadar düz düzenin üstüne çıkar. Düzen kararı sorgudan önce verilir ve hangi sorgunun ucuza cevaplanacağını o karar belirler.

Özet

• Kurgu kümenin 3.199 satırı ve 7 sütunu 22.393 değer eder; sorgunun gerçekten ihtiyaç duyduğu değer 453 satırın iki sütunu, yani 906’dır.
• Aynı sorgu satır sıralı düz düzende 22.393, sütun sınırlı düzende 6.398, satır kümeli ve başlıklı düzende 2.069 değer okur; yedi satır kümesinin beşi hiç açılmaz ve kazanç 10,82 kattır.
• Satır kümesi boyutunun iki yönlü bedeli vardır: 32 satırlık kümede başlık 300 değer okutur, 3.199 satırlık tek kümede hiçbir şey atlanmaz; en az değer okutan boyut 64’tür ve 1.174 değerle 19,07 kat verir.
• Hangi başlıkların okunduğu ikinci karardır: bütün sütun başlıkları okunduğunda en iyi boyut 128’e taşınır ve kazanç 12,41 kata iner.
• Sütun sınırının kazancı istenen sütun sayısıyla erir ve yedi sütunlu sorguda 1,00 kata iner; satır kümesi atlaması aynı sorguda 4,92 kat vermeyi sürdürür.

Sonraki Adım

Dört ders dağıtımın kalemlerini tek tek saydı: taşınan kayıt, eşgüdüm kalemi, okunan değer. Üçü de azaltılabilir kalemlerdi ve her birinde bir karar bulundu. Geriye azaltılamayan bir pay kalıyor. Bir işin bölünemeyen kısmı yüzde kaçsa, kaç birim eklenirse eklensin hızlanma bir tavanın üstüne çıkamaz. Sonraki ders bu tavanı birim sayısını artırarak basar ve dağıtımın ne zaman gereksiz olduğunu sayıyla yazar; aynı ders kursu ve M26 müfredatını kapatır.