Sütunlu Motorlar

Önceki ders kümeyi parça parça okuyarak bellek tepesini otuz ikide bire indirdi, ama her parçada kaydın bütün alanlarını çözümledi. Bölge kırılımı üç sütuna bakıyordu; altı sütun okundu, üçü kullanıldı, üçü atıldı. Parçalama tepeyi düşürür, yapılan işi düşürmez.

Bu dersin sorusu odur: aynı cevabı üretmek için kaç değere dokunmak gerekiyor. Ölçü birimi okunan değer sayısıdır ve yanında ikinci bir sayı durur — erişim, yani ayrı bir bitişik alana kaç kez gidildiği. Kaydın alanlarını bitişik tutan düzen ile sütunu bitişik tutan düzen bu iki sayıda birbirinin tersine çalışır; hangisinin ucuz olduğu sorunun ne sorduğuna bağlıdır.

• AB11. Küme kurgudur ve önceki derslerin kümesidir: 3.199 satır, altı sütun, 1.329 abone, üç dönem. Aynı tohumla üretilir ve çıktı koşumdan koşuma aynıdır. Modeldir.
• AB12. İki depo düzeni de bellekte modellenir; ölçülen şey depolama ortamı değil, cevabı üretmek için dokunulan değer sayısıdır. Modeldir.
• AB13. Satır tabanlı düzende bir satıra dokunmak o satırın altı alanını da okumak demektir; alanlar bitişik yazıldığı için tek alan ayrı çekilemez.
• AB14. Sütunlu düzende her sütun ayrı bir dizidir ve her 512 değerlik blok için en küçük ile en büyük değeri tutan bir özet sütunla birlikte saklanır.
• AB15. Erişim, ayrı bir bitişik alana gidiş sayısıdır: baştan sona tarama bir erişim, bir sütunun tek tek konumlarını okumak konum sayısı kadar erişimdir.

İki Düzen

# depo.py — ayni kurgu kume iki duzende tutulur ve her okuma sayilir.
# MODELDIR: gercek bir depo yerine iki yerlesim modellendi; olcu, bir sorgunun
# cevabini uretmek icin kac degere dokunuldugudur. 3199 satir, 1329 abone.
TOHUM = 1246
BOLGE = ("kuzey", "dogu", "merkez", "guney", "bati")
DONEM = (("2024-01", 1329), ("2024-02", 1035), ("2024-03", 835))
YOGUNLUK = (0, 1, 2, 2, 2, 3, 4, 2, 2, 1)   # merkez agirlikli kurgu olcum agi
BASLIK = ("abone_no", "sayac_no", "donem", "bolge", "okuma_m3", "basamak")


def uretec(tohum: int):
    s = tohum & 0xFFFFFFFF

    def sonraki() -> float:
        nonlocal s
        s = (1103515245 * s + 12345) & 0xFFFFFFFF
        return s / 4294967296
    return sonraki


def basamak(o: float) -> str:
    return "0-10" if o <= 10 else "10-25" if o <= 25 else "25-40"


def kayitlar() -> list[tuple]:
    r, k = uretec(TOHUM), []
    for donem, adet in DONEM:
        for i in range(adet):
            o = round(5 + r() * 32.0, 1)
            k.append((10000 + i, f"S-{4000 + i}", donem,
                      BOLGE[YOGUNLUK[i % 10]], o, basamak(o)))
    return k


class SatirDepo:
    """Bir kaydin butun alanlari bitisiktir: bir satira dokunmak o satirin
    butun alanlarini okumak demektir."""

    def __init__(self, k):
        self.k, self.okunan, self.erisim = [tuple(map(str, x)) for x in k], 0, 0

    def tara(self):
        self.erisim += 1                     # bastan sona tek bitisik gecis
        for s in self.k:
            self.okunan += len(BASLIK)
            yield s

    def kayit(self, i: int) -> tuple:
        self.okunan, self.erisim = self.okunan + len(BASLIK), self.erisim + 1
        return self.k[i]


class SutunDepo:
    """Her sutun ayri bir dizidir: yalniz istenen sutun, hatta o sutunun yalniz
    istenen konumlari okunabilir. Blok ozeti sutunla birlikte saklanir."""
    BLOK = 512

    def __init__(self, k):
        self.s = {ad: [str(x[j]) for x in k] for j, ad in enumerate(BASLIK)}
        self.okunan, self.erisim, self.n = 0, 0, len(k)
        self.ozet = {ad: [(min(v[i:i + self.BLOK]), max(v[i:i + self.BLOK]))
                          for i in range(0, len(v), self.BLOK)]
                     for ad, v in self.s.items()}

    def tumu(self, ad: str) -> list:
        self.okunan, self.erisim = self.okunan + self.n, self.erisim + 1
        return self.s[ad]

    def konumlar(self, ad: str, yerler: list) -> list:
        self.okunan += len(yerler)           # dagitik erisim: her konum ayri
        self.erisim += len(yerler)
        return [self.s[ad][i] for i in yerler]

    def kayit(self, i: int) -> tuple:
        self.okunan += len(BASLIK)           # alti sutuna alti ayri gidis
        self.erisim += len(BASLIK)
        return tuple(self.s[ad][i] for ad in BASLIK)


k0 = kayitlar()
sd, cd = SatirDepo(k0), SutunDepo(k0)
print(f"tohum {TOHUM}; {len(k0)} satir, {len(BASLIK)} sutun, "
      f"{len(k0) * len(BASLIK)} deger")
print(f"blok boyutu {SutunDepo.BLOK}, donem sutununda "
      f"{len(cd.ozet['donem'])} blok ozeti")
print("ilk kayit:", sd.kayit(0))

tohum 1246; 3199 satir, 6 sutun, 19194 deger
blok boyutu 512, donem sutununda 7 blok ozeti
ilk kayit: ('10000', 'S-4000', '2024-01', 'kuzey', '9.4', '0-10')

Sayı kümenin sınırını çiziyor: altı sütun ve 3.199 satır, toplam 19.194 değer. Satır tabanlı düzen bu değerleri kayıt kayıt bitişik tutar; ilk kaydın altı alanı yan yanadır. Sütunlu düzen aynı değerleri altı ayrı diziye yayar ve her dizinin yedi bloğu için bir özet tutar. Kümenin içeriği aynı, yerleşimi farklıdır.

Aynı Soru, Dört Okuma Yolu

# sorgu.py — tek bir soru dort yolla cevaplanir: "verilen donemde bolge basina
# toplam okuma". Cevap dort yolda da ayni; degisen sey okunan deger ve ayri
# bitisik alana gidis sayisi olan erisimdir.
def satir_yolu(d: SatirDepo, hedef: str) -> dict:
    t = {}
    for s in d.tara():                       # kaydin alti alani da gelir
        if s[2] == hedef:
            t[s[3]] = round(t.get(s[3], 0.0) + float(s[4]), 1)
    return t


def sutun_erken(d: SutunDepo, hedef: str) -> dict:       # uc sutun bastan sona
    donem, bolge, okuma = d.tumu("donem"), d.tumu("bolge"), d.tumu("okuma_m3")
    return topla([(bolge[i], okuma[i]) for i, v in enumerate(donem) if v == hedef])


def sutun_gec(d: SutunDepo, hedef: str) -> dict:         # once suzgec, sonra konum
    yerler = [i for i, v in enumerate(d.tumu("donem")) if v == hedef]
    return topla(list(zip(d.konumlar("bolge", yerler),
                          d.konumlar("okuma_m3", yerler))))


def sutun_blok(d: SutunDepo, hedef: str) -> tuple[dict, int]:
    ozet, yerler, atlanan = d.ozet["donem"], [], 0
    d.okunan, d.erisim = d.okunan + 2 * len(ozet), d.erisim + 1
    for bi, (enk, enb) in enumerate(ozet):
        if not enk <= hedef <= enb:          # blok ozeti hedefi kapsamiyor
            atlanan += 1
            continue
        bas = bi * d.BLOK
        dilim = d.s["donem"][bas:bas + d.BLOK]
        d.okunan, d.erisim = d.okunan + len(dilim), d.erisim + 1
        yerler += [bas + i for i, v in enumerate(dilim) if v == hedef]
    return topla(list(zip(d.konumlar("bolge", yerler),
                          d.konumlar("okuma_m3", yerler)))), atlanan


def topla(ciftler: list) -> dict:
    t = {}
    for b, o in ciftler:
        t[b] = round(t.get(b, 0.0) + float(o), 1)
    return t


def kos(yol: str, kume: list, hedef: str) -> tuple:
    if yol == "satir tabanli tarama":
        d = SatirDepo(kume)
        t = satir_yolu(d, hedef)
    else:
        d = SutunDepo(kume)
        t = (sutun_erken(d, hedef) if "erken" in yol else
             sutun_gec(d, hedef) if "gec" in yol else sutun_blok(d, hedef)[0])
    return d, t


YOLLAR = ("satir tabanli tarama", "sutunlu, erken maddelestirme",
          "sutunlu, gec maddelestirme", "sutunlu, blok atlamali")
G = (30, 14, 9, 9, 11, 12)
y = lambda h: "".join(str(v).rjust(G[j]) if j else str(v).ljust(G[0])
                      for j, v in enumerate(h))
print(y(["okuma yolu", "okunan deger", "oran", "erisim", "merkez m3", "toplam m3"]))
taban = 0
for yol in YOLLAR:
    d, t = kos(yol, k0, "2024-03")
    taban = taban or d.okunan
    print(y([yol, d.okunan, f"{taban / d.okunan:.1f}x", d.erisim, t["merkez"],
             round(sum(t.values()), 1)]))
print(f"blok atlamali yolda 7 blogun {sutun_blok(SutunDepo(k0), '2024-03')[1]} tanesi "
      f"hic acilmadi; 2024-03 doneminde 835 satir var")

okuma yolu                      okunan deger     oran   erisim  merkez m3   toplam m3
satir tabanli tarama                   19194     1.0x        1     8752.6     17307.2
sutunlu, erken maddelestirme            9597     2.0x        3     8752.6     17307.2
sutunlu, gec maddelestirme              4869     3.9x     1671     8752.6     17307.2
sutunlu, blok atlamali                  2835     6.8x     1674     8752.6     17307.2
blok atlamali yolda 7 blogun 4 tanesi hic acilmadi; 2024-03 doneminde 835 satir var

Dört yol da aynı cevabı veriyor: merkez bölgesinde 8.752,6 m³, toplamda 17.307,2 m³. Okunan değer 19.194’ten 2.835’e iniyor — 6,8 kat. Kazanç tek bir kalemden gelmiyor, üç ayrı kararın üstüste binmesinden geliyor ve tablonun her satırı bir kararı ekliyor.

Ölçünün okunan değer olması bir kolaylık değil, karşılaştırmayı taşınabilir kılan seçimdir. Aynı dört yolun süresi çalışılan makineye, o anki yüke ve ara belleğin durumuna göre koşumdan koşuma değişir; okunan değer sayısı yerleşimden ve sorudan türer ve her koşumda aynı çıkar. Bir yolun diğerinden kaç kat ucuz olduğu bu birimde savunulabilir bir cümledir.

Birinci karar sütun seçimidir. Soru üç sütun soruyor; satır tabanlı düzen altısını da getiriyor, çünkü kaydın alanları bitişik. Sütunlu düzen üçünü okuyor ve okunan değer yarıya iniyor. Bu, ürün değil yerleşim farkıdır: sütunu bitişik tutan her yapı aynı kazancı verir.

İkinci karar sıradır. Erken maddeleştirme üç sütunu da baştan sona okur; geç maddeleştirme önce süzgeç sütununu okur, eşleşen 835 konumu bulur ve diğer iki sütundan yalnız o konumları alır. Okunan değer 9.597’den 4.869’a iner. Bedeli erişim sütunundadır: üç erişim yerine 1.671 erişim, çünkü artık bitişik bir dizi değil dağınık konumlar okunuyor.

Üçüncü karar blok özetidir. Dönem sütunu 512’lik yedi bloğa ayrılmış ve her blok için en küçük ile en büyük değer saklanmıştı. Hedef dönem bir bloğun aralığına düşmüyorsa o blok hiç açılmaz; yedi bloğun dördü açılmadı ve okunan değer 4.869’dan 2.835’e indi. Blok özeti okumaya on dört değer ekledi, karşılığında 2.048 değer okumaktan kurtardı.

Kazanç Neye Bağlı

# kumelenme.py — blok atlama verinin o sutuna gore kumelenmis olmasina baglidir.
# Ayni kume abone sirasina gore yazildiginda her blok ucu donemi de tasir,
# hicbir ozet disarida kalmaz ve atlama kazanci sifirlanir.
abone_sirali = sorted(k0, key=lambda x: (x[0], x[2]))
r = uretec(99)                                  # gorunur tohumlu kendi uretecimiz
karisik = [x for _, x in sorted((r(), x) for x in k0)]
G2 = (20, 14, 14, 10, 12)
y2 = lambda h: "".join(str(v).rjust(G2[j]) if j else str(v).ljust(G2[0])
                       for j, v in enumerate(h))
print(y2(["kume duzeni", "atlanan blok", "okunan deger", "erisim", "toplam m3"]))
for ad, kume in [("donem sirali", k0), ("abone sirali", abone_sirali),
                 ("karisik (tohum 99)", karisik)]:
    d = SutunDepo(kume)
    t, atlanan = sutun_blok(d, "2024-03")
    print(y2([ad, f"{atlanan}/{len(d.ozet['donem'])}", d.okunan, d.erisim,
              round(sum(t.values()), 1)]))

# Suzgecin seciciligi hangi yolun ucuz oldugunu belirler. Formuller olculen
# yollarin kendisinden okunur: erken yol uc sutunu bastan sona okur, gec yol
# suzgec sutununu okur ve kalan m konumu iki sutundan tek tek toplar.
n = len(k0)
G3 = (22, 14, 13, 13, 12)
y3 = lambda h: "".join(str(v).rjust(G3[j]) if j else str(v).ljust(G3[0])
                       for j, v in enumerate(h))
print(y3(["eslesen satir", "okunan erken", "okunan gec", "erisim gec", "gec kazanc"]))
for m in (835, 1329, 2691):
    print(y3([f"{m} ({100 * m // n} yuzde)", 3 * n, n + 2 * m, 1 + 2 * m,
              f"{(3 * n) / (n + 2 * m):.2f}x"]))
d = SutunDepo(k0)
sutun_gec(d, "2024-03")
print(f"olculen gec yol 835 satirda {d.okunan} deger ve {d.erisim} erisim; formul "
      f"{n + 2 * 835} ve {1 + 2 * 835}")

# Ters yon: bir kaydin tamamini getirmek.
ORNEK = list(range(0, n, 320))
sd2, cd2 = SatirDepo(k0), SutunDepo(k0)
for i in ORNEK:
    sd2.kayit(i)
    cd2.kayit(i)
print(f"{len(ORNEK)} kaydin tamami: satir tabanli {sd2.okunan} deger / {sd2.erisim} "
      f"erisim, sutunlu {cd2.okunan} deger / {cd2.erisim} erisim")

kume duzeni           atlanan blok  okunan deger    erisim   toplam m3
donem sirali                   4/7          2835      1674     17307.2
abone sirali                   2/7          4244      1676     17307.2
karisik (tohum 99)             0/7          4883      1678     17307.2
eslesen satir           okunan erken   okunan gec   erisim gec  gec kazanc
835 (26 yuzde)                  9597         4869         1671       1.97x
1329 (41 yuzde)                 9597         5857         2659       1.64x
2691 (84 yuzde)                 9597         8581         5383       1.12x
olculen gec yol 835 satirda 4869 deger ve 1671 erisim; formul 4869 ve 1671
10 kaydin tamami: satir tabanli 60 deger / 10 erisim, sutunlu 60 deger / 60 erisim

İlk tablo dersin gizlenen kararıdır. Blok atlama bir yapı özelliği gibi görünür, oysa kümenin o sütuna göre kümelenmiş olmasına bağlıdır. Aynı küme abone sırasında yazıldığında her bloğun içine üç dönem birden karışır, özetler hedefi kapsar ve yedi bloğun yalnız ikisi atlanır; karışık sırada hiçbiri atlanmaz. Okunan değer 2.835’ten 4.244’e, oradan 4.883’e çıkar ve altı buçuk katlık kazanç dört kata iner. Üç koşumda da toplam 17.307,2 m³ çıkar; kararın oynattığı sayı cevap değil, cevabı üretmek için okunan değerdir. Kümeyi hangi sütuna göre sıralayacağı sorusu bir yerleşim kararıdır ve sorgu yazılırken görünmez.

İkinci tablo geç maddeleştirmenin sınırını çiziyor. Süzgeç 835 satır bıraktığında geç yol erken yola göre 1,97 kat az değer okur; 2.691 satır bıraktığında kazanç 1,12 kata iner ve dağınık erişim 1.671’den 5.383’e çıkar. Seçicilik düştükçe konum listesi büyür, dağınık okuma bitişik okumaya yaklaşır ve öne alınan süzgeç ödemesini karşılamaz. Formüller ölçülen yolların kendisinden okunur ve 835 satırlık satır ölçülen değerle birebir tutuyor: 4.869 değer, 1.671 erişim.

Son satır ters yönü ölçüyor. On kaydın tamamını getirmek iki düzende de 60 değer okur, ama satır tabanlı düzen bunu 10 erişimle, sütunlu düzen 60 erişimle yapar. Sütunlu yerleşim az sütunu çok satırda okuyan sorularda kazanır, çok sütunu az satırda okuyan sorularda kaybeder. Yerleşim bir kolaylık tercihi değil, hangi sorunun ucuza cevaplanacağının kararıdır.

Özet

• Aynı soru dört yolla cevaplandı ve dördü de merkez için 8.752,6 m³, toplamda 17.307,2 m³ verdi; değişen tek şey okunan değer sayısıdır.
• Satır tabanlı tarama 19.194 değer okur; sütunlu düzen gereken üç sütunla 9.597, süzgeci öne alarak 4.869, blok atlayarak 2.835 değer okur — 6,8 kat.
• Geç maddeleştirme okunan değeri düşürür ama erişimi üçten 1.671’e çıkarır; kazanç seçiciliğe bağlıdır ve eşleşen satır 2.691’e çıktığında 1,12 kata iner.
• Blok atlama kümelenmeye bağlıdır: dönem sıralı kümede yedi bloğun dördü, abone sıralı kümede ikisi, karışık kümede hiçbiri atlanmaz ve okunan değer 2.835’ten 4.883’e çıkar.
• Tek bir kaydın tamamını getirmek satır tabanlı düzende 10 erişim, sütunlu düzende 60 erişimdir; yerleşim kazancı sorunun yönüne göre işaret değiştirir.

Sonraki Adım

Bu ders okunan değeri altı buçuk kat düşürdü, ama bütün hesap hâlâ tek bir yerde yapıldı. Küme büyüdükçe o tek yerin sınırı gelir: okunan değer altıda birine inse de 3.199 satır 3,2 milyar satır olduğunda tek bir makinenin okuyacağı değer yine sığmaz. Sonraki ders işi birden çok bölüme dağıtır ve dağıtmanın kendi kalemini ölçer — bölümleme, veri taşıma ve eşgüdüm hesaba kaç birim ekliyor, hangi iş boyutunda bu kalem kazanca dönüşüyor.