SEN2104 · 13. hafta · Query Processing and Query Optimization

Sorgu işleme ve optimizasyon: join algoritmaları, denklik kuralları, tahmin

Bir sorgunun hangi adımlardan geçtiği, nested-loop/block/indexed/merge/hash join maliyetlerinin nasıl hesaplandığı ve optimizer'ın sorgu ağacını nasıl yeniden yazdığı.

query processingparsingquery evaluation planquery optimizationblock transferseekexternal sort-mergerunnested-loop joinblock nested-loop joinindexed nested-loop joinmerge joinhash joinbuild inputprobe inputequivalence rulesheuristic optimizationquery treeselectivityV(A, r)join size estimation

Geçen hafta tek bir tablodan seçim yapmanın maliyetini hesapladık. Bu hafta sorgu birden çok tabloyu birleştiriyor. Aynı SQL sorgusu için onlarca farklı çalışma planı olabilir ve aralarında binlerce kat maliyet farkı çıkabilir. Optimizer’ın işi bunlardan ucuz olanı bulmak. Sınavda üç soru tipi var: join maliyeti hesapla, iki planı karşılaştır, sorgu ağacını denklik kurallarıyla yeniden yaz.

Altın kurallar:

Maliyet = blok transferi + seek. Seek sayısını unutma, sorunun yarısı oradan gelir.
Nested-loop türlerinde küçük ilişki dışa konur.
Seçimi ( $\sigma$ ) olabildiğince aşağı it. Join’e giren satır sayısını azaltmak en büyük kazançtır.
Denklik kuralı sonucu değiştirmez. Sadece maliyeti değiştirir.

Sorgu işlemenin adımları

Parsing and translation: SQL’in sözdizimi kontrol edilir, tablo ve sütun isimleri doğrulanır, sorgu ilişkisel cebir ifadesine çevrilir.
Optimization: eşdeğer cebir ifadeleri ve her işlem için algoritmalar düşünülür. Her plan için maliyet tahmin edilir (istatistiklerle), en ucuzu seçilir. Sonuç bir değerlendirme planıdır (query evaluation plan): her düğümünde hangi algoritmanın kullanılacağı yazan bir ağaç.
Evaluation: plan çalıştırılır.

Maliyet ölçüsü: $b$ blok transferi ve $S$ seek için

$\text{maliyet} = b \cdot t_T + S \cdot t_S$

Bu sayfada da $t_T = 0.1$ ms, $t_S = 4$ ms.

Dış sıralama (external sort-merge)

Tablo belleğe sığmıyorsa sıralama iki aşamada olur. $M$ = bellekteki buffer blok sayısı.

Run oluşturma: $M$ bloğu oku, bellekte sırala, run olarak yaz. $\lceil b_r / M \rceil$ run çıkar.
Birleştirme: her geçişte $M - 1$ run birleştirilir (1 blok çıktı için). Geçiş sayısı $\lceil \log_{M-1}(b_r / M) \rceil$ .

$\text{transfer} = b_r \left( 2 \left\lceil \log_{M-1} \frac{b_r}{M} \right\rceil + 1 \right)$

Örnek: $b_r = 400$ , $M = 11$ . Run sayısı $\lceil 400/11 \rceil = 37$ . Her geçişte 10 run birleşir: $37 \to 4 \to 1$ , 2 geçiş. Transfer $400 \cdot (2 \cdot 2 + 1) = 2000$ . Son sonucun diske yazılması sayılmaz, çünkü genelde bir sonraki işleme doğrudan aktarılır.

Join algoritmaları

Gövdedeki örnek: $r$ = takes ( $n_r = 10000$ , $b_r = 400$ ), $s$ = student ( $n_s = 5000$ , $b_s = 100$ ). Join koşulu takes.stu_id = student.stu_id.

Nested-loop join

for each tuple t_r in r:
    for each tuple t_s in s:
        if (t_r, t_s) koşulu sağlıyorsa çıktıya yaz

En kötü durumda (her ilişkiye tek buffer):

$n_r \cdot b_s + b_r \text{ transfer}, \qquad n_r + b_r \text{ seek}$

takes dışta: $10000 \cdot 100 + 400 = 1\,000\,400$ transfer, $10400$ seek. Süre $100040 + 41600 = 141640$ ms, yaklaşık 2.4 dakika. student dışta: $5000 \cdot 400 + 100 = 2\,000\,100$ transfer. Burada dışın tuple sayısı çarpan olduğu için az tuple’lı olan dışta daha iyi.

En iyi durum: küçük ilişki belleğe tamamen sığıyorsa her ikisi bir kez okunur: $b_r + b_s = 500$ transfer, 2 seek.

Block nested-loop join

Tuple tuple değil, blok blok eşleştir: dışın her bloğu için iç ilişki bir kez taranır.

$b_r \cdot b_s + b_r \text{ transfer}, \qquad 2 b_r \text{ seek}$

takes dışta: $400 \cdot 100 + 400 = 40400$ transfer, 800 seek. student dışta: $100 \cdot 400 + 100 = 40100$ transfer, 200 seek. Bu sefer de küçük ilişki dışta kazanıyor.

$M$ buffer varsa dış ilişkiye $M - 2$ blok ayrılır (bir iç, bir çıktı):

$\left\lceil \frac{b_r}{M-2} \right\rceil b_s + b_r \text{ transfer}, \qquad 2 \left\lceil \frac{b_r}{M-2} \right\rceil \text{ seek}$

$M = 12$ , student dışta: $\lceil 100/10 \rceil = 10$ parça, $10 \cdot 400 + 100 = 4100$ transfer, 20 seek.

Indexed nested-loop join

İç ilişkide join özniteliği üzerinde indeks varsa iç ilişkiyi taramak yerine her dış tuple için indekste arama yapılır. $c$ = bir arama + eşleşeni getirme maliyeti.

$b_r (t_T + t_S) + n_r \cdot c$

takes dışta, student.stu_id üzerinde $h_i = 3$ B+ ağacı: anahtarda eşitlik olduğu için $c = h_i + 1 = 4$ blok erişimi. Erişim sayısı $400 + 10000 \cdot 4 = 40400$ . Her biri seek + transfer olduğundan süre olarak bu, block nested-loop’tan pahalıdır. Indexed nested-loop, dış ilişki küçükken (örneğin önce sıkı bir $\sigma$ uygulanmışsa) parlar.

Merge join

İki ilişki join özniteliğine göre sıralıysa ikisi paralel taranır, bir kez okunur:

$b_r + b_s \text{ transfer}$

Örnekte $400 + 100 = 500$ . Sıralı değillerse önce sıralama maliyeti eklenir. $M = 11$ ile takes sıralaması 2000, student sıralaması ( $\lceil 100/11 \rceil = 10$ run, 1 geçiş) $100 \cdot 3 = 300$ transfer. Toplam $2000 + 300 + 500 = 2800$ . Sadece eşitlik ve doğal join (equi-join) için kullanılır.

Hash join

Bölümleme (partitioning): iki ilişki aynı hash fonksiyonuyla $n_h$ parçaya bölünür. Eşleşebilecek tuple’lar aynı numaralı parçalara düşer.
Her $i$ için $s_i$ belleğe alınır ve bellekte hash tablosu kurulur (build input), sonra $r_i$ okunup bu tabloda aranır (probe input).

Küçük ilişki build input olur; her $s_i$ belleğe sığmalı. Özyinelemeli bölümleme gerekmiyorsa:

$3 (b_r + b_s) \text{ transfer}$

Bölümlemede okuma + yazma $2(b_r + b_s)$ , build/probe aşamasında bir okuma $(b_r + b_s)$ . Örnekte $3 \cdot 500 = 1500$ .

Özet karşılaştırma (takes ⋈ student)

Algoritma	Transfer	Not
Nested-loop, takes dışta	1 000 400	en kötü
Block nested-loop, student dışta	40 100
Block nested-loop, $M = 12$	4 100
Indexed nested-loop, $c = 4$	40 400 erişim	hepsi rastgele
Merge join + iki sıralama	2 800	sonuç sıralı çıkar
Hash join	1 500	eşitlik join’i

TUZAK · formüllerde $n$ mi $b$ mi? Basit nested-loop’ta çarpan dışın tuple sayısı $n_r$ , block nested-loop’ta dışın blok sayısı $b_r$ . Indexed nested-loop’ta yine $n_r$ . Sınavda en sık kayıp puan buradan çıkar.

Denklik kuralları (equivalence rules)

İki cebir ifadesi her veritabanı örneğinde aynı sonucu veriyorsa eşdeğerdir. Optimizer’ın kullandığı başlıca kurallar:

Kural	İfade
Seçim kaskadı	$\sigma_{\theta_1 \wedge \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))$
Seçim değişmeli	$\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))$
Projeksiyon kaskadı	$\pi_{L_1}(\pi_{L_2}(E)) = \pi_{L_1}(E)$ , $L_1 \subseteq L_2$ ise
$\sigma$ ve $\times$	$\sigma_{\theta}(E_1 \times E_2) = E_1 \bowtie_{\theta} E_2$
Join değişmeli	$E_1 \bowtie E_2 = E_2 \bowtie E_1$
Join birleşmeli	$(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)$
Seçimi aşağı itme	$\sigma_{\theta}(E_1 \bowtie E_2) = \sigma_{\theta}(E_1) \bowtie E_2$ , $\theta$ sadece $E_1$ ‘in özniteliklerini kullanıyorsa
Projeksiyonu aşağı itme	$\pi_L(E_1 \bowtie_\theta E_2) = \pi_{L_1}(E_1) \bowtie_\theta \pi_{L_2}(E_2)$ , $L_i$ hem $L$ ‘deki hem $\theta$ ‘daki öznitelikleri içermeli
Küme işlemleri	$\cup$ ve $\cap$ değişmeli ve birleşmeli; $\sigma$ bunlara ve $-$ işlemine dağılır

Join değişmeliliği sütun sırasını değiştirir, ama ilişkide sütunlar isimle tanımlandığı için sonuç aynı ilişkidir.

Sezgisel optimizasyon (heuristic optimization)

Tüm planları denemek pahalı. Sezgisel kurallar çoğu durumda iyi plan verir:

Konjonktif seçimleri kaskadla parçala.
Her seçimi ağaçta olabildiğince aşağı it.
En kısıtlayıcı (en az satır bırakan) seçim ve join’i önce yap.
$\sigma$ + $\times$ çiftini $\bowtie$ ‘a çevir. Kartezyen çarpımdan kaç.
Projeksiyonu erken yap, gereksiz sütunları at. Join için gereken sütunları tutmayı unutma.

Örnek: sorgu ağacını dönüştürmek

Örnek üniversite veritabanında: “CS bölümündeki öğrencilerden 3 kredilik bir ders almış olanların adları.” course tablosunda da dept_name olduğu için onu c_dept diye yeniden adlandırıyoruz; yoksa doğal join öğrencinin bölümüyle dersin bölümünü de eşitlemeye çalışır.

Saf çeviri:

$\pi_{name}\big(\sigma_{dept\_name='CS' \wedge credits=3}(\text{student} \bowtie (\text{takes} \bowtie \text{course}))\big)$

Kaskad + seçimi aşağı itme + projeksiyonu erken yapma:

$\pi_{name}\Big(\pi_{stu\_id,\, name}(\sigma_{dept\_name='CS'}(\text{student})) \bowtie \pi_{stu\_id}\big(\text{takes} \bowtie \sigma_{credits=3}(\text{course})\big)\Big)$

ara sonuç boyutları (örnek DB)        saf plan   optimize plan
student ⋈ takes ⋈ course              14         -
σ dept_name='CS'(student)             -          3
σ credits=3(course)                   -          4
takes ⋈ σ(course)                     -          5
sonuç                                 Ada        Ada

İki plan aynı sonucu (sadece Ada) verir. Saf plan önce 14 satırlık bir join üretip sonra eliyor; optimize plan join’e 3 ve 5 satırla giriyor. Gerçek boyutlarda bu fark milyonlarca satırdır.

TUZAK · doğal join ve aynı isimli sütun. Yeniden adlandırmadan student ⋈ takes ⋈ course yazarsan dept_name de eşitlenir ve örnek veritabanında 14 yerine 9 satır çıkar: öğrencinin kendi bölümü dışından aldığı dersler kaybolur. Bu bir optimizasyon değil, yanlış sorgudur.

İstatistikler ve boyut tahmini

Optimizer planın maliyetini tahmin etmek için katalogdaki istatistikleri kullanır: $n_r$ , $b_r$ , $f_r$ , ve $V(A, r)$ , yani $r$ ‘de $A$ ‘nın farklı değer sayısı.

İfade	Tahmini satır sayısı
$\sigma_{A = v}(r)$	$n_r / V(A, r)$
$\sigma_{A \le v}(r)$	$n_r \cdot \frac{v - \min(A)}{\max(A) - \min(A)}$
$\sigma_{\theta_1 \wedge \theta_2}(r)$	$n_r \cdot \frac{s_1}{n_r} \cdot \frac{s_2}{n_r}$ (bağımsızlık varsayımı)
$r \bowtie s$ , ortak öznitelik $s$ ‘nin anahtarı	$\le n_r$ ; yabancı anahtarsa tam $n_r$
$r \bowtie s$ , ortak öznitelik anahtar değil	$\min\left(\frac{n_r n_s}{V(A,s)}, \frac{n_r n_s}{V(A,r)}\right)$

Örnek: $n = 5000$ öğrenci, $V(dept\_name) = 20$ . dept_name = 'CS' tahmini $250$ . tot_cred 0 ile 240 arasında ise tot_cred <= 60 tahmini $5000 \cdot 60/240 = 1250$ . İkisi birden: $5000 \cdot 0.05 \cdot 0.25 = 62.5$ , yani yaklaşık 63 satır.

Tahmin bir varsayımdır. Örnek veritabanımızda student 7 satır ve COUNT(DISTINCT dept_name) = 3 (NULL sayılmaz). Tahmin $7/3 \approx 2.33$ , gerçekte CS’de 3 öğrenci var. Dağılım eşit değilse tahmin sapar; gerçek sistemler bu yüzden histogram tutar.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
Nested-loop’ta $b_r \cdot b_s$	Tuple tabanlıda $n_r \cdot b_s + b_r$ ; $b_r \cdot b_s$ block nested-loop
Büyük ilişki dışta olsun	Nested-loop türlerinde küçük ilişki dışta
Seek’i atlamak	NLJ’de $n_r + b_r$ , BNLJ’de $2b_r$ seek; seek transferden 40 kat pahalı
$M$ bufferın hepsi dış ilişkiye	$M - 2$ : bir blok iç ilişki, bir blok çıktı
Dış sıralamada geçiş sayısı $\log_M$	Birleştirmede $M - 1$ yol: $\lceil \log_{M-1}(b_r/M) \rceil$
Merge join her zaman $b_r + b_s$	Sadece zaten sıralıysa; değilse sıralama maliyeti eklenir
Hash join’de büyük ilişki build input	Küçük ilişki build input, parçaları belleğe sığmalı
Seçimi join’in istediğin koluna indir	Sadece koşuldaki tüm öznitelikler o kolda varsa
Projeksiyonu erken yaparken join sütununu at	Join özniteliği üst seviyede gerekiyorsa tutulmalı
$\min$ yerine $\max$ ile join tahmini	Daha sıkı olan küçük değer: büyük $V$ ‘ye böl

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Put the steps of query processing in the correct order: optimization, parsing and translation, evaluation.

Cevabı göster

parsing and translation, optimization, evaluation

Önce SQL sözdizimi kontrol edilir ve ilişkisel cebir ifadesine çevrilir (parsing and translation).
Sonra optimizer eşdeğer planlar arasından tahmini en ucuzunu seçer (optimization).
En son evaluation engine seçilen planı çalıştırır ve sonucu döndürür.

Soru 2orta

Relation $r$ has $n_r = 6000$ tuples in $b_r = 300$ blocks; $s$ has $n_s = 1500$ tuples in $b_s = 60$ blocks. Using a simple (tuple) nested-loop join with $r$ as the outer relation and only one buffer block per relation (worst case), give the number of block transfers and seeks.

Cevabı göster

360300 transfers, 6300 seeks

Dış ilişkinin her tuple'ı için iç ilişkinin tamamı okunur: $n_r \cdot b_s = 6000 \cdot 60 = 360000$ .
Dış ilişkinin kendisi bir kez okunur: $+ b_r = 300$ . Toplam 360300 transfer.
Seek: her dış tuple için iç ilişkiye bir seek ( $n_r$ ) ve dış ilişkinin her bloğu için bir seek ( $b_r$ ): $6000 + 300 = 6300$ .

Soru 3orta

Same $r$ ( $b_r = 300$ ) and $s$ ( $b_s = 60$ ). For a block nested-loop join (worst case, one buffer block each), compute the block transfers with $r$ as outer and with $s$ as outer. Which should be the outer relation?

Cevabı göster

r outer: 18300, s outer: 18060; s should be outer

Formül: $b_{\text{dış}} \cdot b_{\text{iç}} + b_{\text{dış}}$ transfer, $2 b_{\text{dış}}$ seek. $r$ dış: $300 \cdot 60 + 300 = 18300$ transfer, 600 seek. $s$ dış: $60 \cdot 300 + 60 = 18060$ transfer, 120 seek.
Çarpım kısmı aynı, fark ikinci terimde ve seek sayısında. Küçük ilişki dışta olmalı: $s$ .

Soru 4orta

Block nested-loop join of $r$ ( $b_r = 300$ ) and $s$ ( $b_s = 60$ ) with $M = 22$ memory buffers, $s$ as outer. Give block transfers and seeks.

Cevabı göster

960 transfers, 6 seeks

$M - 2 = 20$ blok dış ilişkiye ayrılır (1 blok iç ilişki, 1 blok çıktı).
Dış ilişki $\lceil 60/20 \rceil = 3$ parçada okunur. Her parça için iç ilişki bir kez taranır.
Transfer: $3 \cdot 300 + 60 = 960$ . Seek: $2 \cdot 3 = 6$ .
Tek bufferlı versiyondaki 18060 transfer 960'a indi.

Soru 5zor

Indexed nested-loop join: $r$ ( $n_r = 6000$ , $b_r = 300$ ) is the outer relation and $s$ has a B+ tree index on the join attribute. Each index lookup plus fetching the matching tuple costs $c = 3$ block accesses. What is the total number of block accesses? If instead $s$ ( $n_s = 1500$ , $b_s = 60$ ) is outer and $r$ has an index with the same $c$ , what is the cost?

Cevabı göster

18300; 4560

Formül: $b_{\text{dış}} + n_{\text{dış}} \cdot c$ . $r$ dış: $300 + 6000 \cdot 3 = 18300$ . $s$ dış: $60 + 1500 \cdot 3 = 4560$ .
Indexed nested-loop'ta dış ilişkinin tuple sayısı belirleyici. Az tuple'lı ilişkiyi dışa koymak ucuz.

Soru 6orta

Both $r$ ( $b_r = 300$ ) and $s$ ( $b_s = 60$ ) are already sorted on the join attribute. How many block transfers does a merge join need (ignore the output)?

Cevabı göster

360

İki sıralı ilişki aynı anda birer kez taranır: $b_r + b_s = 300 + 60 = 360$ transfer.
Join değerinde çok sayıda tekrar yoksa (aynı değerli tuple'lar belleğe sığıyorsa) ek okuma olmaz.

Soru 7zor

External sort-merge of a relation with $b_r = 300$ blocks using $M = 7$ buffer blocks. How many initial runs are created, how many merge passes are needed, and what is the total number of block transfers (do not count writing the final result)?

Cevabı göster

43 runs, 3 passes, 2100 transfers

Başlangıç run sayısı: $\lceil b_r / M \rceil = \lceil 300/7 \rceil = 43$ .
Her geçişte $M - 1 = 6$ run birleşir. Geçiş sayısı $\lceil \log_6 43 \rceil$ ; $\log_6 43 \approx 2.10$ , yani 3 (43 → 8 → 2 → 1).
Transfer: $b_r (2 \lceil \log_{M-1}(b_r/M) \rceil + 1) = 300 \cdot (2 \cdot 3 + 1) = 2100$ .
Run oluşturma 1 okuma + 1 yazma, her geçiş 1 okuma + 1 yazma, son geçişin yazması sayılmaz.

Soru 8orta

For $r$ ( $b_r = 300$ ) and $s$ ( $b_s = 60$ ), both unsorted, compare a hash join (no recursive partitioning, ignore partially filled blocks) with sort + merge join where sorting $r$ costs 2100 and sorting $s$ costs 300 transfers. Which is cheaper?

Cevabı göster

hash 1080 vs sort-merge 2760: hash join

Hash join: iki ilişki bölümlenirken okunup yazılır ( $2(b_r + b_s)$ ), sonra build/probe aşamasında bir kez daha okunur ( $b_r + b_s$ ): $3 \cdot (300 + 60) = 1080$ .
Sort-merge: $2100 + 300 + (300 + 60) = 2760$ .
Hash join daha ucuz. Ama sonucun join anahtarına göre sıralı istenmesi gibi durumlarda merge join avantaj kazanabilir.

Soru 9kolay

Relation instructor has $n = 6000$ tuples and $V(\text{dept\_name}, \text{instructor}) = 40$ . Estimate the size of $\sigma_{dept\_name = 'EE'}(\text{instructor})$ . Also estimate $\sigma_{salary \le 30}$ (salary in thousands) if salaries range uniformly from 10 to 90.

Cevabı göster

150; 1500

Eşitlik: değerlerin eşit dağıldığı varsayılır, $n_r / V(A, r) = 6000 / 40 = 150$ .
Karşılaştırma: $n_r \cdot \frac{v - \min(A)}{\max(A) - \min(A)} = 6000 \cdot \frac{30 - 10}{90 - 10} = 6000 \cdot 0.25 = 1500$ .

Soru 10orta

takes has 6000 tuples and student has 1500 tuples. takes.stu_id is a foreign key referencing the primary key student.stu_id (NOT NULL). Estimate the size of $\text{takes} \bowtie \text{student}$ .

Cevabı göster

6000

Ortak öznitelik student için anahtar ve takes.stu_id yabancı anahtar. Her takes tuple'ı tam olarak bir student tuple'ıyla eşleşir.
Sonuç tam olarak $n_{takes} = 6000$ tuple. Genel kural: ortak öznitelik $s$ 'nin anahtarıysa join en fazla $n_r$ tuple verir.

Soru 11orta

On the sample university database, rewrite $\sigma_{dept\_name = 'EE'}(\text{student} \bowtie \text{takes})$ by pushing the selection down. How many tuples does the result have?

Cevabı göster

σ_dept_name='EE'(student) ⋈ takes; 3 tuples

dept_name sadece student'ta var, bu yüzden seçim join'in student koluna inebilir: $\sigma_{dept\_name='EE'}(\text{student}) \bowtie \text{takes}$ .
EE öğrencileri: S3 (Cem) ve S6 (Firat). S6 hiç ders almamış. S3'ün üç kaydı var: EE210, MA101, CS101.
Sonuç 3 tuple. Join'e 7 yerine 2 student tuple'ı girer.

Soru 12zor

$r(A, B)$ has 1000 tuples, $s(B, C)$ has 3000 tuples, $V(B, r) = 100$ and $V(B, s) = 200$ . $B$ is not a key of either relation. Estimate the size of $r \bowtie s$ .

Cevabı göster

15000

İki tahmin: $\frac{n_r n_s}{V(B, s)} = \frac{3 \cdot 10^6}{200} = 15000$ ve $\frac{n_r n_s}{V(B, r)} = \frac{3 \cdot 10^6}{100} = 30000$ .
Küçük olanı (daha sıkı tahmin) alınır: $\min = 15000$ . Bu, büyük $V$ değerine bölmek demek.

Doğrulama: Tüm join, dış sıralama ve boyut tahmini sayıları node ile formüllerden hesaplandı; denklik kuralları (kaskad, seçimi aşağı itme, join değişme/birleşme) ve sorgu ağacı dönüşümü örnek üniversite DB'sinde hem ilişkisel cebir (JS küme işlemleri) hem node:sqlite ile çalıştırılıp sonuçların aynı olduğu kontrol edildi (verify/SEN2104/13.mjs).

Deftere not kartı

adımlar: parse+translate → optimize (plan seç) → evaluate maliyet: b transfer * t_T + S seek * t_S (CPU ihmal) NLJ: n_r*b_s + b_r transfer, n_r + b_r seek (küçük bellekte: b_r + b_s) BNLJ: b_r*b_s + b_r transfer, 2b_r seek M buffer: ceil(b_r/(M-2))*b_s + b_r INLJ: b_r + n_r*c (dışın TUPLE sayısı önemli) merge (sıralı): b_r + b_s + sıralama maliyeti dış sıralama: run = ceil(b/M), geçiş = ceil(log_{M-1}(b/M)), transfer b(2*geçiş+1) hash join: 3(b_r + b_s), küçük ilişki build input σ_{A=v}: n_r/V(A,r) σ_{A<=v}: n_r(v-min)/(max-min) join: ortak öznitelik s'nin anahtarı → <= n_r; FK ise = n_r genel: min(n_r n_s / V(A,s), n_r n_s / V(A,r)) sezgisel: σ'yı aşağı it, π'yi erken yap, en seçici σ ve join önce, × yerine ⋈