join — สี่วิธีจับคู่แถว และความชันของแต่ละวิธี

หกบทที่ผ่านมาถามคำถามกับตารางเดียว บทนี้เพิ่มตารางที่สองเข้ามา แล้วราคาก็ย้ายไปอยู่ที่อื่น

คำตอบของ join ไม่ขึ้นกับว่าเราวนลูปยังไง แต่ราคาขึ้นทั้งหมด สี่วิธีในบทนี้คืนคู่ที่จับได้ชุดเดียวกันเป๊ะ ต่างกันแค่ว่าใครถูกอ่านซ้ำกี่รอบ และอะไรถูกถือไว้ในหน่วยความจำระหว่างวนลูป

บทนี้ยังเป็นที่แรกที่หน่วยเดียวไม่พอ เพราะมีคู่ที่อ่านหน้าเท่ากันเป๊ะแต่ทำงานต่างกันหลายร้อยเท่า อีกสองหน่วยที่บท 1 สัญญาไว้ล่วงหน้าจึงมาเริ่มใช้จริงตรงนี้

📦 code ของบทนี้

file ของบทนี้คือ qe/joins.py ซึ่ง import ของจากสามบทก่อนหน้า คือ fixture ของบท 1, heapfile ของบท 2 และ bptree ของบท 3 ทั้งสาม file นั้นต้องอยู่ใน qe/ ครบก่อน

รันจาก folder ทำงานด้านนอกเหมือนทุกบท คือ python3 qe/joins.py โมดูลจะสร้างตารางกับ index ของตัวเองใหม่ทุกครั้งลงใน .build/ การลบ folder นั้นทั้งอันจึงปลอดภัย

code ในบทนี้ยกมาเป็นช่วงจาก qe/joins.py ไม่ใช่ทั้ง file เพราะโมดูลนี้ยาวเกินกว่าจะแปะทั้งหมดโดยยังอ่านรู้เรื่อง

โจทย์เดียวที่ทั้งบทใช้ และหน่วยที่ใช้วัดมัน

ตารางที่ทั้งบทใช้ ซึ่งเขียนลงหน้า 4096 byte จริง index ที่เตรียมไว้ล่วงหน้า เฉลยที่ใช้ตรวจทั้งสี่วิธี และเหตุผลที่หน่วยเดียวไม่พอกับบทนี้

หน่วยของบทนี้มีสามหน่วย และไม่มีหน่วยเวลาสักหน่วยเดียว

อ่านหนึ่งหน้า 4096 byte เท่ากับ 1 ครั้ง หน่วยเดียวกับที่บท 2 ตกลงไว้
เทียบคีย์หนึ่งคู่ เท่ากับ 1 ครั้ง หยิบคีย์สองตัวมาเทียบกันหนึ่งครั้งนับหนึ่ง
จำนวนแถวที่ต้องถือไว้พร้อมกัน ราคาที่ไม่ได้จ่ายเป็น I/O แต่จ่ายเป็นหน่วยความจำ

สองหน่วยแรกแยกกันโดยตั้งใจ เพราะบทนี้มีคู่ที่อ่านหน้าเท่ากันเป๊ะแต่ทำงานต่างกันหลายร้อยเท่า ถ้ารวมเป็นเลขตัวเดียวจะมองไม่เห็นของชิ้นนั้นเลย

หน่วยของต้นทุนคือค่าอ่านหน้าแบบเรียงหนึ่งหน้า = 1.0 ตามที่บท 5 ตั้งไว้ ส่วนบทนี้รายงานจำนวนหน้าที่อ่านดิบๆ ไม่ได้แปลงเป็นต้นทุนของ cost model

ตารางที่บทนี้ใช้ถูกเขียนลงหน้า slotted-page จริงแบบบท 2 ไม่ใช่รายการที่ลอยอยู่ในหน่วยความจำ

ตาราง	แถว	หน้า	แถวต่อหน้า	บทบาท
`orders`	200,000	3,153	63.4	ตารางหลักของคอร์ส
`customers`	2,000	16	125.0	ตารางที่สอง สร้างจาก seed เดียวกัน
`orders_day`	1,017	17	59.8	ออเดอร์ของวันที่ 90 materialise เป็นตารางจริง

ยังมีตารางที่สี่คือร้าน 10 ร้าน ซึ่งโผล่เฉพาะหัวข้อสุดท้ายเรื่องผลลัพธ์กลางทาง จึงไม่อยู่ในตารางข้างบน

index สามอันถูก bulk load เตรียมไว้ให้ index nested loop ใช้

index	หน้า	ความสูง	รายการ
`customers(id)`	7	2 ชั้น	2,000
`orders_day(customer_id)`	5	2 ชั้น	1,017
`orders(customer_id)`	493	2 ชั้น	200,000

โจทย์หลักคือ orders_day ⋈ customers บนเงื่อนไข orders.customer_id = customers.id

เฉลยคือ 1,017 คู่ ซึ่งคำนวณจากรายการในหน่วยความจำโดยไม่ผ่านวิธีใดเลย ทั้งสี่วิธีต้องได้ตัวเลขนี้ตรงกัน ไม่งั้นการเอาราคามาเทียบกันก็ไม่มีความหมาย

ลูกค้าทุก id ในช่วง 1 ถึง 2,000 มีอยู่จริง ออเดอร์หนึ่งแถวจึงจับคู่ได้ 1 คู่พอดี จำนวนแถวของผลลัพธ์จึงเท่ากับจำนวนแถวของ orders_day เสมอ ไม่ว่าจะให้ตารางไหนเป็นตัวนอก

ขนาดของโจทย์เลือกมาเพราะ nested loop ทีละแถวต้องรันจบได้จริงบนเครื่องของผู้อ่าน ไม่ใช่เพราะมันเป็นขนาดที่พบบ่อยในงานจริง

ตาราง customers ไม่ได้มาจาก fixture.py แต่เป็นข้อมูลของโมดูลนี้เอง

# ── ตารางที่สอง: ลูกค้า 2,000 คน (id เดินตั้งแต่ 1 ถึง N ตรงกับ customer_id ของ orders) ──
CUST_SEED = fixture.SEED + 1      # แยก stream จาก orders แต่ยังล็อกกับ SEED เดิม
CITIES = ["กรุงเทพ", "นนทบุรี", "ปทุมธานี", "สมุทรปราการ",
          "เชียงใหม่", "ขอนแก่น", "ภูเก็ต", "ชลบุรี"]
TIERS = ["bronze", "silver", "gold"]
TIER_W = [60, 30, 10]
FIRST_NAMES = ["สมชาย", "สมหญิง", "อนันต์", "ปรีชา", "วิภา", "ณัฐพล",
               "กมล", "ธนา", "รัตนา", "สุดา", "ชัยวัฒน์", "พิมล"]

CUST_FIXED = struct.Struct("<IBBH")   # id, city, tier, len(name)  = 8 B

# ── ตารางที่สาม: ร้าน 10 ร้าน (ใช้แค่ในหัวข้อ [6] เรื่องผลลัพธ์กลางทาง) ──
AREAS = ["ในเมือง", "ชานเมือง", "ริมทางด่วน"]


def customers(n=fixture.N_CUSTOMERS, seed=CUST_SEED):
    """แถวของตารางลูกค้า — deterministic เหมือน fixture.rows()"""
    rng = random.Random(seed)
    out = []
    for cid in range(1, n + 1):
        name = f"{rng.choice(FIRST_NAMES)} {cid:04d}"
        out.append((cid, name, rng.randrange(len(CITIES)),
                    rng.choices(range(len(TIERS)), weights=TIER_W)[0]))
    return out


def encode_customer(cid, name, city, tier):
    b = name.encode()
    return CUST_FIXED.pack(cid, city, tier, len(b)) + b

CUST_SEED = fixture.SEED + 1 แยกลำดับตัวสุ่มออกจาก orders แต่ยังล็อกไว้กับ seed เดิม ตารางลูกค้าจึงออกมาเหมือนกันทุกเครื่องด้วยเหตุผลเดียวกับบท 1

บทอื่นที่ต้องใช้ตารางลูกค้าต้อง import customers ตัวนี้ ไม่ใช่สร้างขึ้นมาใหม่เอง ไม่งั้นตัวเลขจะไม่ตรงกันข้ามบท

ขอบเขตของตัวเลขทุกตัวในบทนี้

โจทย์ทั้งบทเป็น join แบบ 1:N ที่ออเดอร์ทุกแถวจับคู่ได้ครบ ส่วนฝั่งลูกค้ามีแถวที่ไม่มีคู่อยู่ด้วย ซึ่งไม่โผล่ในผลเพราะไม่มี outer join และไม่มี many-to-many ตัวเลขที่วัดได้จึงเป็นตัวเลขของรูปแบบนี้รูปแบบเดียว

hash join ที่นี่สมมุติว่าฝั่ง build ใส่หน่วยความจำได้หมด ไม่มีการแบ่ง partition ของจริงที่ฝั่ง build ใหญ่เกินหน่วยความจำต้องแบ่ง partition แล้วจ่ายค่าเขียนกับอ่านกลับเพิ่มอีก

จำนวน bucket ที่ตั้งไว้ 1,024 เป็นค่าที่เราเลือกเอง มันเปลี่ยนจำนวนครั้งที่เทียบคีย์ แต่ไม่เปลี่ยนหน้าที่อ่านเลยสักหน้า

และเหมือนทุกบทที่ผ่านมา ยังไม่มี buffer pool หนึ่ง rid เท่ากับอ่านหนึ่งหน้าเสมอ ตัวเลขหน้าที่อ่านทุกตัวจึงเป็นกรณีที่ cache อะไรไม่ได้เลย

สี่วิธีบนโจทย์เดียวกัน

ผลของทั้งสี่วิธีในสามหน่วย ที่มาของทุกตัวเลขหน้าที่อ่าน และ code ที่ผลิตตัวเลขเหล่านั้น

ตารางนอกคือ orders_day ตารางในคือ customers และทั้งสี่วิธีได้ 1,017 คู่เท่ากันหมด

วิธี	หน้าที่อ่าน	เทียบคีย์	ถือไว้ (แถว)	คู่ที่ได้
nested loop (ทีละแถว)	16,289	2,034,000	1	1,017
block nested loop (B = 8 หน้า)	65	2,034,000	507	1,017
index nested loop	3,070	13,374	1	1,017
hash join	33	2,356	2,000	1,017

ตัวเลขหน้าที่อ่านทุกตัวในตารางนั้นตามที่มาได้ทีละบรรทัด

nested loop เท่ากับ 17 (สแกนตารางนอก) + 1,017 แถว × 16 หน้า = 16,289
block nested loop เท่ากับ 17 + 3 block × 16 หน้า = 65
index nested loop เท่ากับ 17 + 1,017 แถว × (2 หน้า index + 1 หน้า heap) = 3,068 ส่วนที่วัดได้จริงคือ 3,070
hash join เท่ากับ 16 (build จาก customers) + 17 (probe ด้วย orders_day) = 33

ส่วนต่าง 2 หน้าของ index nested loop คือคีย์ที่นั่งอยู่ท้ายใบพอดี ต้องเปิดใบถัดไปดูว่าคีย์ยังซ้ำอยู่หรือหมดแล้ว

nested loop ทีละแถว — เส้นฐานของบท

nested-loop join คือลูปซ้อนสองชั้นที่ตรงไปตรงมาที่สุด หนึ่งแถวของตารางนอกเท่ากับสแกนตารางในทั้งตารางหนึ่งรอบ

def nested_loop(outer, inner):
    """หนึ่งแถวของตารางนอก = สแกนตารางในทั้งตารางหนึ่งรอบ

    ไม่มีอะไรค้างในหน่วยความจำเลย (ถือไว้ทีละแถว) และนั่นคือเหตุผลที่มันแพง:
    ตารางในถูกอ่านซ้ำเท่ากับจำนวนแถวของตารางนอก
    """
    _reset(outer, inner)
    cmps = nres = so = si = 0
    for ob in outer.scan():
        ok, oid = outer.key(ob), outer.rowid(ob)
        for ib in inner.scan():
            cmps += 1
            if inner.key(ib) == ok:
                nres += 1
                so += oid
                si += inner.rowid(ib)
    return Res(_reads(outer, inner), cmps, 1, nres, so, si)

ไม่มีอะไรค้างในหน่วยความจำเลย ถือไว้ทีละแถว และนั่นคือทั้งข้อดีข้อเดียวและเหตุผลที่มันแพง ตารางในถูกอ่านซ้ำ 1,017 รอบ เท่ากับจำนวนแถวของตารางนอกพอดี

block nested loop — เปลี่ยนแค่ว่าใครถูกอ่านซ้ำ

block nested loop เปลี่ยนข้อเดียว คือลูปนอกวนทีละ block ของหน้า ไม่ใช่ทีละแถว

def block_nested_loop(outer, inner, block_pages):
    """อ่านตารางนอกทีละ block_pages หน้า เก็บไว้ในแรม แล้วสแกนตารางในหนึ่งรอบต่อบล็อก

    เปลี่ยนแค่ "ใครถูกอ่านซ้ำ" — ตารางในถูกอ่านซ้ำเท่ากับจำนวนบล็อก ไม่ใช่จำนวนแถว
    จำนวนครั้งที่เทียบคีย์ยังเท่าเดิมทุกประการ: |นอก| x |ใน|
    """
    _reset(outer, inner)
    cmps = nres = so = si = 0
    mem = 0
    for start in range(0, outer.npages, block_pages):
        block = []
        for pno in range(start, min(start + block_pages, outer.npages)):
            page = outer.pager.read_page(pno)
            for s in range(nslots(page)):
                b = read_slot(page, s)
                block.append((outer.key(b), outer.rowid(b)))
        mem = max(mem, len(block))
        for ib in inner.scan():
            ik, iid = inner.key(ib), inner.rowid(ib)
            for ok, oid in block:
                cmps += 1
                if ok == ik:
                    nres += 1
                    so += oid
                    si += iid
    return Res(_reads(outer, inner), cmps, mem, nres, so, si)

ตารางในถูกอ่านซ้ำเท่ากับจำนวน block คือ 3 รอบ ไม่ใช่ 1,017 รอบ หน้าที่อ่านจึงลดจาก 16,289 เหลือ 65 หรือต่างกัน 250.6 เท่า

จำนวนครั้งที่เทียบคีย์ไม่ขยับเลยสักครั้ง อยู่ที่ 2,034,000 ครั้งเท่ากันทั้งคู่ ซึ่งเท่ากับ 1,017 × 2,000 พอดี block แก้ที่ I/O ล้วน ไม่แตะ CPU

ราคาที่จ่ายแทนคือ 507 แถวที่ต้องถือไว้พร้อมกัน เทียบกับ 1 แถวของวิธีแรก

index nested loop — เลิกสแกนตารางใน แล้วถาม index แทน

index nested loop ไม่สแกนตารางในอีกต่อไป แต่ถาม index ของตารางในทีละแถวนอก โดยต้องมี index อยู่ก่อนบน column ที่ใช้ join

def index_probe(rd, key):
    """ลงจากรากถึงใบแล้วเก็บ rid ทุกตัวที่คีย์ตรง — คืน (rids, จำนวนครั้งที่เทียบคีย์)

    เขียนซ้ำแทนที่จะเรียก rd.range() ของบท 3 เพราะบทนี้ต้องนับ "ครั้งที่เทียบคีย์"
    ด้วย ไม่ใช่แค่หน้าที่อ่าน (การค้นทวิภาคในโหนดก็คือการเทียบคีย์เหมือนกัน)
    """
    pno, cmps = rd.root, 0
    while True:
        page = rd.pager.read_page(pno)
        is_leaf, n, nxt = header(page)
        if is_leaf:
            break
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            cmps += 1
            if inner_key(page, mid) < key:
                lo = mid + 1
            else:
                hi = mid
        pno = inner_child(page, lo)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        cmps += 1
        if leaf_key(page, mid) < key:
            lo = mid + 1
        else:
            hi = mid
    out, i = [], lo
    while True:
        while i < n:
            cmps += 1
            if leaf_key(page, i) != key:
                return out, cmps
            out.append(leaf_rid(page, i))
            i += 1
        if nxt == NO_NEXT:
            return out, cmps
        page = rd.pager.read_page(nxt)
        _, n, nxt = header(page)
        i = 0

index_probe เขียนขึ้นใหม่แทนการเรียกฟังก์ชันของบท 3 เพราะบทนี้ต้องนับครั้งที่เทียบคีย์ด้วย ไม่ใช่แค่หน้าที่อ่าน การค้นแบบ binary search ภายในหนึ่งหน้าก็คือการเทียบคีย์เหมือนกัน

การวางตัวนับไว้ใน joins.py แทนการไปเพิ่มใน bptree.py ทำให้ของที่ถูกวัดไม่เปลี่ยนรูป ตัวเลขหน้าที่อ่านของบท 3 จึงยังเทียบกับบทนี้ได้ตรงๆ

ผลคือเทียบคีย์ 13,374 ครั้ง หรือ 13.2 ครั้งต่อหนึ่งแถวนอก น้อยกว่า nested loop 152 เท่า เพราะมันไม่ต้องไล่เทียบแถวนอกหนึ่งแถวกับแถวในทั้ง 2,000 แถว

13.2 ครั้งที่เหลือคือการค้นแบบ binary search ใน node ที่เดินผ่าน ซึ่งส่วนใหญ่ยังเป็นการเทียบกับคีย์ที่ไม่ตรง ราคาของมันโตแบบ log ตามจำนวนแถวใน ไม่ใช่แบบเชิงเส้น

ราคาที่จ่ายอยู่ที่หน้าที่อ่าน 3,070 หน้า เพราะทุกแถวนอกต้องเดินลงจากรากใหม่ทุกครั้ง

hash join — อ่านสองตารางคนละรอบเดียว

hash join สร้างตาราง hash จากตารางในไว้ในหน่วยความจำก่อน แล้วเอาแถวของตารางนอกมาค้น

HASH_C = 2654435761
"""ค่าคงที่ทองของ Knuth (ราว 2^32 หารด้วยอัตราส่วนทอง)

ใช้สูตรตายตัวแทน hash() ของ Python เพราะ hash() ของสตริงขึ้นกับ PYTHONHASHSEED
และคอร์สนี้ต้องรันซ้ำได้ stdout เท่าเดิมเป๊ะ
"""


def hbucket(k, nbuckets):
    """คีย์ -> หมายเลขถัง (เลื่อนบิตทิ้งก่อนเพื่อให้บิตสูงมามีส่วนในการกระจาย)"""
    return ((k * HASH_C) >> 11) % nbuckets


def hash_join(outer, inner, nbuckets):
    """สร้างตารางแฮชจากตารางใน (build) แล้วยิงตารางนอกเข้าไปหา (probe)

    ทั้งสองตารางถูกอ่านคนละหนึ่งรอบพอดี ไม่มีการอ่านซ้ำ — ราคาของ I/O จึงต่ำสุด
    ราคาที่จ่ายแทนคือหน่วยความจำ: ทุกแถวของฝั่ง build ต้องอยู่ในแรมพร้อมกัน
    """
    _reset(outer, inner)
    buckets = [[] for _ in range(nbuckets)]
    for ib in inner.scan():
        k = inner.key(ib)
        buckets[hbucket(k, nbuckets)].append((k, inner.rowid(ib)))
    cmps = nres = so = si = 0
    for ob in outer.scan():
        ok, oid = outer.key(ob), outer.rowid(ob)
        for bk, bid in buckets[hbucket(ok, nbuckets)]:
            cmps += 1
            if bk == ok:
                nres += 1
                so += oid
                si += bid
    return Res(_reads(outer, inner), cmps, inner.nrows, nres, so, si)

HASH_C ไม่ได้เลือกมาลอยๆ การใช้ hash() ของ Python กับสตริงให้ผลไม่เท่ากันข้ามการรันเพราะขึ้นกับ PYTHONHASHSEED ซึ่งขัดกับสัญญาเรื่องการรันซ้ำแล้วได้เลขเดิมของทั้งคอร์ส

ตาราง hash 1,024 bucket กับคีย์ 2,000 ตัว ใช้จริง 963 bucket ยาวที่สุด 3 รายการ และเฉลี่ย 1.95 รายการต่อ bucket เมื่อหารด้วย bucket ทั้ง 1,024 ใบ ไม่ใช่หารด้วยเฉพาะใบที่ถูกใช้

จำนวนครั้งที่เทียบคีย์จึงเป็น 2,356 ครั้ง หรือ 2.32 ครั้งต่อหนึ่ง probe ไม่ใช่ 1.00 พอดี เพราะ bucket หนึ่งใบมีคีย์ที่ไม่ตรงปนอยู่ด้วย นี่คือราคาของการชนกัน

hash join อ่านน้อยที่สุดคือ 33 หน้า แลกกับการถือ 2,000 แถวไว้ในหน่วยความจำพร้อมกัน ส่วนอีกสามวิธีถือไว้ระหว่าง 1 ถึง 507 แถว

flowchart LR
    Q["โจทย์เดียวกัน<br/>ตารางนอก 1,017 แถว 17 หน้า<br/>ตารางใน 2,000 แถว 16 หน้า"]
    Q --> A1["nested loop ทีละแถว<br/>วนตารางในใหม่ทุกแถวนอก รวม 1,017 รอบ"]
    A1 --> A2["อ่าน 16,289 หน้า<br/>เทียบคีย์ 2,034,000 ครั้ง<br/>ถือไว้ 1 แถว"]
    Q --> B1["block nested loop<br/>วนตารางในใหม่ทุก block รวม 3 รอบ"]
    B1 --> B2["อ่าน 65 หน้า<br/>เทียบคีย์ 2,034,000 ครั้ง<br/>ถือไว้ 507 แถว"]
    Q --> C1["index nested loop<br/>ถาม index ของตารางในทีละแถวนอก"]
    C1 --> C2["อ่าน 3,070 หน้า<br/>เทียบคีย์ 13,374 ครั้ง<br/>ถือไว้ 1 แถว"]
    Q --> D1["hash join<br/>อ่านสองตารางคนละรอบเดียว"]
    D1 --> D2["อ่าน 33 หน้า<br/>เทียบคีย์ 2,356 ครั้ง<br/>ถือไว้ 2,000 แถว"]

คำบรรยายภาพ: โจทย์เดียวกันและคำตอบชุดเดียวกัน ต่างกันแค่รูปแบบการวนลูป · เส้นบนสุดวนตารางในใหม่ทุกแถวนอก เส้นถัดมาวนใหม่ทุก block เส้นที่สามแทนการสแกนด้วยการถาม index และเส้นล่างสุดอ่านแต่ละตารางรอบเดียวจบ · ตัวเลขสามบรรทัดในกล่องขวาคือสามหน่วยของบทนี้ ซึ่งไม่ได้เรียงลำดับเหมือนกันทั้งสามหน่วย

ขนาดของ block และคู่ที่พิสูจน์ว่าหน่วยเดียวไม่พอ

ผลของการขยาย block จาก 1 หน้าถึง 32 หน้า สูตรที่อธิบายทั้งแถว จุดที่ผลของ block ตัน และคู่ที่อ่านหน้าเท่ากันเป๊ะแต่เทียบคีย์ต่างกันหลายร้อยเท่า

ตารางนอกมี 17 หน้า ตารางในมี 16 หน้า เมื่อขยับ block ทีละขั้น ตัวเลขทั้งสามหน่วยขยับคนละทิศ

block (หน้า)	จำนวน block	หน้าที่อ่าน	เทียบคีย์	ถือไว้ (แถว)
1	17	289	2,034,000	67
2	9	161	2,034,000	129
4	5	97	2,034,000	256
8	3	65	2,034,000	507
16	2	49	2,034,000	1,006
32	1	33	2,034,000	1,017

แถวแรกคือแถวที่ได้เยอะที่สุด แค่เปลี่ยนจากวนทีละแถวเป็นวนทีละหน้า หน้าที่อ่านก็ลงจาก 16,289 เหลือ 289 หรือถูกลง 56 เท่า ทั้งที่เทียบคีย์เท่าเดิมทุกครั้ง

ส่วนการขยาย block ต่อจากนั้นทั้งหมด จาก 1 หน้าไปถึง 32 หน้า พา 289 หน้าลงมาที่ 33 หน้า หรือถูกลงอีก 8.8 เท่า น้อยกว่าก้าวแรกก้าวเดียวที่ถูกลง 56 เท่า

แต่ปลายทางของก้าวหลังไม่ใช่ของแถม มันคือจุดที่หน้าที่อ่านของ block nested loop ไปชนกับ hash join พอดี ซึ่งเป็นคู่ที่ Callout ท้ายหัวข้อนี้ยกมาเทียบ

สูตรที่ตัวเลขทั้งแถวเชื่อฟังคือ หน้าที่อ่าน = P_นอก + ⌈P_นอก / B⌉ × P_ใน ผลของ B จึงตันที่ B = P_นอก = 17 หน้า เพิ่ม block ต่อจากนั้นไม่ได้อะไรอีก

สูตรนี้ใช้ B ตรงๆ ไม่ใช่ B−2 เพราะ Pager ของคอร์สนี้ยังไม่มี buffer pool จึงไม่ต้องกันหน้าไว้ให้ตารางในกับ output ตัวเลขที่ได้จึงต่างจากตัวอย่างของ CMU ที่อ้างไว้ท้ายบทด้วยเหตุนี้

ราคาของ block ที่ใหญ่ขึ้นอ่านได้จาก column ขวาสุด แถวที่ต้องถือไว้พร้อมกันโตจาก 67 เป็น 1,017 แถว ซึ่งก็คือทั้งตารางนอก

อ่านเท่ากันเป๊ะ 33 หน้า แต่เทียบคีย์ต่างกัน 863 เท่า

เมื่อ block ใหญ่พอจะใส่ตารางนอกได้ทั้งตาราง block nested loop อ่าน 33 หน้า เท่ากับ hash join พอดี

แต่เทียบคีย์ต่างกัน 863 เท่า คือ 2,034,000 ครั้ง เทียบกับ 2,356 ครั้ง เพราะ block nested loop ยังเทียบทุกแถวนอกกับทุกแถวใน ส่วน hash join เทียบเฉพาะแถวที่ตกลงมาใน bucket เดียวกัน

ถ้าบทนี้รายงานหน่วยเดียวคือหน้าที่อ่าน ข้อสรุปที่ได้จะเป็น “สองวิธีนี้เท่ากัน” ซึ่งผิด และนี่คือคู่ที่ทำให้ต้องแยกสองหน่วยออกจากกันตั้งแต่ต้นบท

สลับลำดับ — ตารางไหนเป็นตัวนอก

ผลของการสลับว่าตารางไหนเป็นตัวนอก วัดด้วยสามหน่วยแยกกัน บนวิธีเดิมทั้งสี่วิธีและโจทย์เดิม

join order ที่สองตารางมีให้เลือกแค่สองทาง คือให้ orders_day เป็นตัวนอก หรือให้ customers เป็นตัวนอก ทั้งสองทางให้คำตอบตรงกันทุกครั้ง

หน่วยแรก หน้าที่อ่าน

วิธี	นอก = `orders_day`	นอก = `customers`	ต่างกัน
nested loop (ทีละแถว)	16,289	34,016	2.09 เท่า
block nested loop (B = 8 หน้า)	65	50	1.30 เท่า
index nested loop	3,070	5,037	1.64 เท่า
hash join	33	33	1.00 เท่า

หน่วยที่สอง ครั้งที่เทียบคีย์

วิธี	นอก = `orders_day`	นอก = `customers`	ต่างกัน
nested loop (ทีละแถว)	2,034,000	2,034,000	1.00 เท่า
block nested loop (B = 8 หน้า)	2,034,000	2,034,000	1.00 เท่า
index nested loop	13,374	23,731	1.77 เท่า
hash join	2,356	2,356	1.00 เท่า

หน่วยที่สาม แถวที่ต้องถือไว้พร้อมกัน

วิธี	นอก = `orders_day`	นอก = `customers`	ต่างกัน
nested loop (ทีละแถว)	1	1	1.00 เท่า
block nested loop (B = 8 หน้า)	507	1,036	2.04 เท่า
index nested loop	1	1	1.00 เท่า
hash join	2,000	1,017	1.97 เท่า

nested loop กับ block nested loop เทียบคีย์เท่ากันเป๊ะทั้งสองทาง เพราะ 1,017 คูณ 2,000 กับ 2,000 คูณ 1,017 ให้ผลเท่ากัน ที่ต่างกันคือหน้าที่อ่าน และต่างแค่ 2.09 เท่ากับ 1.30 เท่า

hash join อ่าน 33 หน้าเท่ากันเป๊ะทั้งสองทาง เพราะยังไงก็อ่านแต่ละตารางรอบเดียว ลำดับของมันจึงไม่ได้ไปโผล่ที่ I/O

สิ่งที่ลำดับของ hash join เปลี่ยนคือหน่วยความจำ 2,000 แถว เทียบกับ 1,017 แถว หรือ 1.97 เท่า คำถามจริงของมันคือฝั่ง build ใส่หน่วยความจำได้ไหม ไม่ใช่ว่าอ่านกี่หน้า

ที่สองตารางนี้ส่วนต่าง 1.97 เท่ายังไม่เจ็บ แต่ที่โจทย์เต็มตารางในหัวข้อถัดไป สองทางต่างกัน 100 เท่า คือ 2,000 แถวถ้า build จาก customers และ 200,000 แถวถ้า build จาก orders

index nested loop สลับข้างไม่ได้ฟรี เพราะต้องมี index อีกอันอยู่ก่อนบนอีกฝั่ง ทางที่ index อยู่ฝั่ง customers อ่าน 3,070 หน้า ส่วนทางกลับอ่าน 5,037 หน้า

ทางกลับแพงกว่าเพราะต้อง probe 2,000 ครั้งตามจำนวนแถวนอก ทั้งที่ได้คู่กลับมาเท่าเดิม 1,017 คู่

ผลของวิธี เทียบกับผลของลำดับ ที่ 2 ตาราง

อัตราส่วนสูงสุดต่อต่ำสุดของทั้งสองปัจจัยบนโจทย์เดียวกัน และข้อจำกัดของตัวเลขที่ได้

ตัวเลขสองชุดจากสองหัวข้อที่แล้ว วางเทียบกันตรงๆ ได้แบบนี้

ปัจจัย	หน่วย	อัตราส่วน สูงสุด/ต่ำสุด
วิธี ทั้งสี่ตัว	หน้าที่อ่าน	493.6 เท่า (16,289 / 33)
วิธี เฉพาะสามตัวที่ใช้จริง	หน้าที่อ่าน	93.0 เท่า (3,070 / 33)
วิธี ทั้งสี่ตัว	เทียบคีย์	863 เท่า (2,034,000 / 2,356)
วิธี เฉพาะสามตัวที่ใช้จริง	เทียบคีย์	863 เท่า เท่ากัน เพราะตัวที่แพงที่สุดคือ block nested loop ซึ่งอยู่ในทั้งสองชุด
วิธี ทั้งสี่ตัว	แถวที่ถือไว้	2,000 เท่า (2,000 / 1)
ลำดับ	หน้าที่อ่าน	1.00 ถึง 2.09 เท่า
ลำดับ	เทียบคีย์	1.00 ถึง 1.77 เท่า
ลำดับ	แถวที่ถือไว้	1.00 ถึง 2.04 เท่า

แถวที่เขียนว่าเฉพาะสามตัวที่ใช้จริงคือแถวที่ตัด nested loop ทีละแถวออก เพราะไม่มีเอนจินไหนเลือกมันเป็นแผนหลักกับตารางขนาดนี้ และทุกครั้งที่ยกตัวคูณของวิธีมาพูด ต้องบอกด้วยว่านับมันหรือไม่นับ ไม่งั้นตัวเลขจะดูขัดกันเอง

ข้อสรุปที่วัดได้คือ ที่ 2 ตาราง วิธีวนลูปมีผลมากกว่าลำดับ 45 เท่า เมื่อนับจากหน้าที่อ่านและตัด nested loop ทีละแถวออก ถ้านับมันด้วย ตัวคูณจะเป็น 236 เท่า

ตัวเลขนี้มีข้อจำกัดสองข้อที่ต้องพูดพร้อมกัน มันวัดที่ 2 ตารางเท่านั้น และมันวัดใน model ที่คิดเงินเฉพาะหน้าที่อ่านกับครั้งที่เทียบคีย์

ราคาตัวจริงของลำดับอยู่ที่ขนาดของผลลัพธ์กลางทาง ซึ่ง model นี้ไม่คิดเงินให้เลย และมันโตตามจำนวนตารางที่ join หัวข้อสุดท้ายของบทวัดของชิ้นนั้นแยกต่างหาก

ผู้ชนะสลับข้างเมื่อฝั่งไหนเป็นตัวนอก

ผลบนโจทย์เต็มตาราง เหตุผลที่สองแถวล่างของตารางไม่ได้รันจริง และโจทย์ปลายอีกด้านที่ผู้ชนะสลับกัน

โจทย์เดิมแต่เปลี่ยนตารางนอกเป็น orders ทั้ง 200,000 แถว join กับ customers 2,000 แถว

วิธี	หน้าที่อ่าน	เทียบคีย์	ถือไว้ (แถว)	สถานะ
hash join	3,169	461,121	2,000	วัดจริง
index nested loop	603,956	2,626,392	1	วัดจริง
block nested loop (B = 8)	9,473	400,000,000	507	จากสูตร ไม่ได้รัน
nested loop (ทีละแถว)	3,203,153	400,000,000	1	จากสูตร ไม่ได้รัน

สองแถวล่างไม่ได้รันจริง เพราะ 400,000,000 ครั้งที่เทียบคีย์คือของที่ไม่คุ้มจะรอให้จบบนเครื่องของผู้อ่าน ตัวเลขของมันมาจากสูตรในหัวข้อที่แล้วตรงๆ

เหตุผลที่ฐานข้อมูลไม่เลือกสองแบบนี้เมื่อตารางใหญ่ไม่ใช่เหตุผลเดียวกัน nested loop ทีละแถวแพงทั้งสองหน่วย ส่วน block nested loop อ่านแค่ 9,473 หน้า ถูกกว่า index nested loop ด้วยซ้ำ แต่ยังเทียบคีย์ 400,000,000 ครั้ง ซึ่งเป็นหน่วยที่ hash join ชนะมัน

hash join ถูกกว่า index nested loop 191 เท่า คือ 3,169 หน้า เทียบกับ 603,956 หน้า

ที่มาของ 603,956 คือ index nested loop ถาม index customers(id) แล้วจ่ายค่าเดินลงจากรากใหม่ทุกแถวนอก 200,000 ครั้ง × (2 + 1) หน้า บวกสแกน orders อีก 3,153 หน้า รวมเป็น 603,153 ส่วนที่วัดได้เกินมา 803 หน้าคือคีย์ที่นั่งท้ายใบ ด้วยเหตุผลเดียวกับหัวข้อแรก

ส่วน hash join อ่านสองตารางคนละรอบเดียวจบ จำนวนแถวนอกจึงไม่ทำให้ I/O โตเลย

ตัวเลข 191 เท่าเป็นขอบบน ไม่ใช่ค่ากลาง

Pager ของคอร์สนี้ยังไม่มี buffer pool ทุกครั้งที่ต้องการหน้าหนึ่งคือเรียกอ่านใหม่ แม้เพิ่งอ่านหน้าเดียวกันไปเมื่อครู่

index customers(id) ทั้งอันมีแค่ 7 หน้า ของจริงที่มี buffer pool มันจะค้างอยู่ใน cache ทั้งอันตั้งแต่แถวนอกแถวแรก ค่าเดินลงจากรากของแถวนอกที่เหลือทั้งหมดจึงแทบไม่ต้องแตะ disk เลย

603,956 หน้าจึงเป็นกรณีแย่ที่สุดที่ cache อะไรไม่ได้เลย และ 191 เท่าเป็นขอบบนของช่องว่าง ไม่ใช่ตัวเลขที่จะเห็นบนฐานข้อมูลจริง

ปลายอีกด้านของโจทย์ให้ผลกลับทาง คือถามหาออเดอร์ทั้งหมดของลูกค้า id 1 ถึง 10 ซึ่งได้คำตอบ 1,021 คู่

index nested loop คราวนี้ถาม index orders(customer_id) แทน อ่าน 1,059 หน้า แยกเป็น 16 หน้าสแกน customers บวก index 22 หน้า บวก heap 1,021 หน้า และเทียบคีย์ 1,209 ครั้ง
hash join อ่าน 3,169 หน้า แยกเป็น build 16 หน้า บวก probe 3,153 หน้า ตัวกรองไม่ช่วยเลยเพราะยังต้องสแกน orders ทั้งตารางมา probe อยู่ดี

index nested loop จึงถูกกว่า 3.0 เท่าที่โจทย์นี้ ทั้งที่แพ้ 191 เท่าที่โจทย์เต็มตาราง

สองโจทย์นี้เปลี่ยนพร้อมกันสองอย่าง คือฝั่งที่เป็นตารางนอกสลับข้าง จาก orders 200,000 แถว มาเป็น customers ที่กรองเหลือ 10 แถว และ index ที่ถูก probe ก็สลับตาม จาก customers(id) 7 หน้า มาเป็น orders(customer_id) 493 หน้า

ราคาของ index nested loop โตตามจำนวนแถวของฝั่งที่เป็นตัวนอก คำถามว่าวิธีไหนดีที่สุดจึงตอบไม่ได้ถ้าไม่บอกขนาดของทั้งสองข้างมาด้วย

ทำไมลำดับถึงกลายเป็นเรื่องใหญ่เมื่อจำนวนตารางเพิ่ม

ผลลัพธ์กลางทางของ join สามตาราง ผลของการกรองก่อน ราคาที่ model นี้มองไม่เห็น และจำนวนลำดับที่ต้องเลือกเมื่อตารางเพิ่ม

คำถามใหม่ใช้สามตาราง คือออเดอร์ของวันที่ 90 ที่ลูกค้าระดับ gold สั่งจากร้านครัวคุณแม่ โดยขอชื่อลูกค้ากับทำเลของร้านมาด้วย

เงื่อนไข join มีสองข้อ คือ orders.customer_id = customers.id กับ orders.restaurant = restaurants.name

ข้อที่ต้องจำคือ customers กับ restaurants ไม่มีเงื่อนไขต่อกันเองเลย ลำดับที่เอาสองตารางนี้มาชนกันก่อนจึงสร้าง cross product ขึ้นมาเองโดยไม่มีใครสั่ง

flowchart TD
    S["ตารางฐานก่อนกรอง<br/>ออเดอร์ของวัน 1,017 แถว · ลูกค้า 2,000 แถว · ร้าน 10 แถว"]
    S --> L1["ลำดับ ออเดอร์ ต่อ ลูกค้า ต่อ ร้าน"]
    S --> R1["ลำดับ ลูกค้า ต่อ ร้าน ต่อ ออเดอร์"]
    L1 --> L2["ขั้นที่ 1 สองตารางมีเงื่อนไขต่อกัน<br/>ได้ของกลางทาง 1,017 แถว"]
    L2 --> L3["ขั้นที่ 2 ได้ 1,017 แถว<br/>ของกลางทางใหญ่สุด 1,017 แถว"]
    R1 --> R2["ขั้นที่ 1 ลูกค้ากับร้านไม่มีเงื่อนไขต่อกัน<br/>ได้ cross product 20,000 แถว"]
    R2 --> R3["ขั้นที่ 2 ได้ 1,017 แถว<br/>ของกลางทางใหญ่สุด 20,000 แถว"]
    L3 --> E["ผลสุดท้ายเป็นชุดเดียวกันเป๊ะทั้งสองลำดับ<br/>ต่างกันแค่ราคา 19.7 เท่า"]
    R3 --> E

คำบรรยายภาพ: สองลำดับของ join สามตารางที่ให้คำตอบชุดเดียวกันเป๊ะ · เส้นซ้ายเริ่มจากคู่ที่มีเงื่อนไขต่อกัน ของกลางทางจึงไม่โตเกิน 1,017 แถว · เส้นขวาเริ่มจากลูกค้ากับร้านซึ่งไม่มีเงื่อนไขต่อกันเลย ผลของขั้นแรกจึงเป็น cross product 2,000 × 10 = 20,000 แถว · ลำดับไม่เปลี่ยนคำตอบ มันเปลี่ยนแค่ราคา

หกลำดับที่เป็นไปได้ถูกวัดสองครั้ง ครั้งแรกกรองที่ตารางฐานก่อนแล้วค่อย join ครั้งที่สอง join ให้ครบก่อนแล้วค่อยกรองตอนท้าย

หลังกรองที่ตารางฐาน เหลือออเดอร์ของวัน 1,017 แถว ลูกค้าระดับ gold 209 คน และร้านเป้าหมาย 1 ร้าน ตัวเลขในตารางข้างล่างสืบกลับมาที่สามจำนวนนี้ได้ทุกตัว

แบบที่วัด	ลำดับที่ดีที่สุด	ลำดับที่แย่ที่สุด	ต่างกัน
กรองก่อน (predicate pushdown)	ออเดอร์ ต่อ ร้าน ต่อ ลูกค้า สร้างของกลางทาง 62 แถว	ลูกค้า ต่อ ร้าน ต่อ ออเดอร์ สร้าง 209 แถว	3.4 เท่า
ไม่กรองก่อน	ออเดอร์ ต่อ ลูกค้า ต่อ ร้าน สร้างของกลางทาง 1,017 แถว	ลูกค้า ต่อ ร้าน ต่อ ออเดอร์ สร้าง 20,000 แถว	19.7 เท่า

ทุกลำดับในทั้งสองแบบให้ผลสุดท้ายเป็นชุดเดียวกันเป๊ะ ลำดับไม่เปลี่ยนคำตอบ มันเปลี่ยนแค่ราคา

การกรองที่ตารางฐานก่อนยุบโทษของลำดับที่แย่ลงจาก 19.7 เท่าเหลือ 3.4 เท่า นี่คือเหตุผลที่ predicate pushdown เป็นการแปลง query ที่ทุกฐานข้อมูลทำก่อนจะเริ่มเลือกลำดับด้วยซ้ำ

def rel_join(a, b):
    """ต่อสองผลลัพธ์กลางทางเข้าด้วยกัน คืนแถวที่ได้

    ถ้าสองข้างไม่มีเงื่อนไขร่วม (เช่น customers กับ restaurants) ผลคือ cross product
    ซึ่งเป็นสิ่งที่ลำดับที่แย่ทำให้เกิดขึ้นเอง โดยไม่มีใครสั่ง
    """
    if not a or not b:
        return []
    sa, sb = _present(a[0]), _present(b[0])
    if ("o" in sa) == ("o" in sb):
        return [_merge(x, y) for x in a for y in b]
    oside, other = (a, b) if "o" in sa else (b, a)
    tags = sorted(_present(other[0]) & {"c", "r"})
    if not tags:
        return [_merge(x, y) for x in a for y in b]
    idx = collections.defaultdict(list)
    for y in other:
        idx[tuple(y[1][0] if t == "c" else y[2][1] for t in tags)].append(y)
    out = []
    for x in oside:
        for y in idx.get(tuple(x[0][OCOL[t]] for t in tags), ()):
            out.append(_merge(x, y))
    return out


def orderings(n):
    """จำนวนลำดับที่เป็นไปได้: แบบ left-deep = n! · ทุกทรงรวม bushy = (2(n-1))!/(n-1)!"""
    return math.factorial(n), math.factorial(2 * (n - 1)) // math.factorial(n - 1)

ราคาที่ model ของบทนี้มองไม่เห็น

ของกลางทางในหัวข้อนี้อยู่ในหน่วยความจำล้วน ราคาของมันจึงเป็น 0 ในหน่วยที่หัวข้อก่อนหน้าใช้ ซึ่งเป็นการโกงที่ต้องรู้ตัว

ถ้าเอาของกลางทางไป materialise ลง disk จริง ที่ 59.8 แถวต่อหน้า ผลจะเป็นแบบนี้

1,017 แถว เท่ากับ 17 หน้า เขียนแล้วอ่านกลับอีกรอบ เท่ากับ 34 ครั้งที่แตะ disk
20,000 แถว เท่ากับ 335 หน้า เขียนแล้วอ่านกลับอีกรอบ เท่ากับ 670 ครั้งที่แตะ disk

59.8 แถวต่อหน้าเป็นความหนาแน่นของแถวออเดอร์ล้วน ส่วนแถวกลางทางต่อออเดอร์กับลูกค้าเข้าด้วยกันแล้ว จึงกว้างกว่าและลงหน้าได้น้อยกว่า 17 หน้ากับ 335 หน้าจึงเป็นขอบล่างของราคาจริง

หน่วยหน้าที่อ่านของหัวข้อก่อนหน้าคิดเงินให้ตารางฐานเท่านั้น ตัวคูณของลำดับที่วัดได้ 1.00 ถึง 2.09 เท่าจึงเป็นตัวเลขของ model ที่มองข้ามของชิ้นนี้ไป

เหตุผลสุดท้ายที่ลำดับกลายเป็นปัญหาใหญ่คือจำนวนทางที่ต้องเลือก ซึ่งไม่ได้โตแบบเชิงเส้น

ตาราง	left-deep (n!)	ทุกทรงรวม bushy
2	2	2
3	6	12
4	24	120
10	3,628,800	17,643,225,600

ที่ 2 ตารางมีให้เลือกแค่ 2 ทาง และในหน่วยหน้าที่อ่านเราวัดแล้วว่าสองทางนั้นต่างกันไม่เกิน 2.09 เท่า ตัวคูณของลำดับจึงเล็กเฉพาะในหน่วยที่ model นี้คิดเงิน

ในหน่วยแถวที่ต้องถือไว้พร้อมกัน สองทางเดียวกันนี้ต่างกัน 1.97 เท่าที่โจทย์สองตารางของบท และต่างกันถึง 100 เท่าที่โจทย์เต็มตาราง เพราะฝั่ง build ของ hash join สลับจาก 2,000 แถวเป็น 200,000 แถว ซึ่งเป็นหน่วยที่ตัดสินว่ามันทำได้หรือไม่ได้เลย

ที่ 10 ตารางมี 3,628,800 ทาง และของกลางทางคูณกันไปเรื่อยๆ ตามความยาวของลำดับ ตัวคูณของลำดับจึงไม่ใช่ค่าคงที่ มันโตตามจำนวน join

ส่วนตัวคูณของวิธีวนลูปอยู่ที่รูปแบบการวนลูปล้วนๆ และเห็นผลตั้งแต่ 2 ตาราง นี่คือเหตุผลที่บทนี้จัดลำดับความสำคัญแบบที่จัด

บท 8 จะเอาของที่เจ็ดบทก่อนหน้าสะสมไว้ ทั้งทางเข้า ราคา และวิธี join ไปเทียบกับสิ่งที่ sqlite3 เลือกจริงบนข้อมูลชุดเดียวกัน แล้วอธิบายทุกจุดที่ไม่ตรงว่าย้อนกลับไปที่บทไหน

🔗 อ้างอิงต้นทางของบทนี้

CMU 15-445/645 Fall 2022, lecture #11 Join Algorithms (ตรวจ 2026-08-11) — ตัวอย่างที่คำนวณเสร็จแล้วบนโจทย์คนละขนาดกับของเรา คือ R มี M = 1,000 หน้า (100,000 แถว) และ S มี N = 500 หน้า (40,000 แถว) นับเป็นครั้งที่ต้องอ่านหน้าตามหน่วยของคอร์สนี้ได้ตามนี้ (หน้า 22, 24, 49, 82 และตารางสรุปหน้า 85)
- nested loop แบบ naive M + (m·N) = 50,001,000 ครั้ง
- block nested loop แบบยังไม่คิด buffer M + (M·N) = 501,000 ครั้ง
- sort-merge = 7,500 ครั้ง ซึ่งเป็นวิธีที่ห้องเรียนนั้นสอนแต่บทนี้ไม่ได้สร้าง
- hash 3·(M+N) = 4,500 ครั้ง
CMU 15-445/645 Fall 2025, lecture #12 (ตรวจ 2026-08-11) — ใช้เฉพาะตอนอ้างสูตรของ block nested loop ที่มี buffer เข้ามาเกี่ยว คือ M + (⌈M/(B−2)⌉ · N) ซึ่งที่ B = 102 ให้ 6,000 ครั้งเมื่อ R เป็นตารางนอก และ 5,500 ครั้งเมื่อสลับข้าง
ตารางสรุปของรุ่น Fall 2025 เขียนสูตรไว้แบบหนึ่งแต่ใส่ตัวอย่างเป็นค่าของกรณีที่สลับตารางนอกแล้ว ตัวอย่างที่คำนวณเสร็จของบทนี้จึงหยิบมาจากรุ่น Fall 2022 ซึ่งสอดคล้องกันทุกช่อง แล้วใช้รุ่น Fall 2025 เฉพาะตอนอ้างสูตร เพราะสองรุ่นใช้สูตรของ block nested loop คนละตัว
Martin Kleppmann, Designing Data-Intensive Applications บทที่ 10 (ISBN 978-1449373320, 2017) — การอ่านต่อสำหรับ join ฝั่งประมวลผลเป็นชุด ซึ่งอธิบายว่ารูปแบบการวนลูปเดียวกันนี้ถูกยกไปวางบนหลายเครื่องอย่างไร

เช็กความเข้าใจ — บทที่ 7

ข้อ 1 / 3

block nested loop ที่ block ใหญ่พอจะใส่ตารางนอกได้ทั้งตาราง อ่าน 33 หน้า เท่ากับ hash join พอดี ข้อสรุปที่ถูกต้องคืออะไร

join — สี่​วิธี​จับ​คู่​แถว และ​ความ​ชัน​ของ​แต่ละ​วิธี

โจทย์​เดียว​ที่​ทั้ง​บท​ใช้ และ​หน่วย​ที่​ใช้​วัด​มัน

สี่​วิธี​บน​โจทย์​เดียวกัน

nested loop ที​ละ​แถว — เส้น​ฐาน​ของ​บท

block nested loop — เปลี่ยน​แค่​ว่า​ใคร​ถูก​อ่าน​ซ้ำ

index nested loop — เลิก​สแกน​ตาราง​ใน แล้ว​ถาม index แทน

hash join — อ่าน​สอง​ตาราง​คนละ​รอบ​เดียว

ขนาด​ของ block และ​คู่​ที่​พิสูจน์​ว่า​หน่วย​เดียว​ไม่​พอ

สลับ​ลำดับ — ตาราง​ไหน​เป็น​ตัว​นอก

ผล​ของ​วิธี เทียบ​กับ​ผล​ของ​ลำดับ ที่ 2 ตาราง

ผู้​ชนะ​สลับ​ข้าง​เมื่อ​ฝั่ง​ไหน​เป็น​ตัว​นอก

ทำไม​ลำดับ​ถึง​กลาย​เป็น​เรื่อง​ใหญ่​เมื่อ​จำนวน​ตาราง​เพิ่ม