ทางเข้า — ลำดับของ column, covering index และการไม่ต้องเรียง

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

สูตรที่ตัวเลขทั้งบทเดินตามมีบรรทัดเดียว คือ ต้นทุนของแผน index = k × ความสูงของต้นไม้ + จำนวนใบที่เดินผ่าน โดย k คือจำนวนค่าที่ไม่ซ้ำของ column ที่อยู่หน้า column ที่เราถาม

สิ่งที่ระเบิดในสูตรนั้นคือ k ไม่ใช่ตัวอ่าน และบทนี้วัดผลของมันสามด้าน

ลำดับของคีย์ภายใน index หนึ่งอัน ซึ่งตัดสินว่าคำถามหนึ่งกลายเป็นการอ่านต่อเนื่องครั้งเดียว หรือการลงจากรากซ้ำ k ครั้ง
index ที่ตอบคำถามได้จบที่ใบ โดยไม่ต้องเอาตัวชี้แถวกลับไปเปิด heap อีกรอบ
การอาศัยลำดับที่ index มีอยู่แล้ว แทนการเรียงผลลัพธ์เอง

📦 code ของบทนี้

file ใหม่ของบทนี้คือ qe/paths.py ซึ่งไม่ได้สร้างโครงสร้างใหม่เลยสักอย่าง มัน import qe/fixture.py ของบท 1, qe/heapfile.py ของบท 2 และ qe/bptree.py ของบท 3 มาใช้ตรงๆ

บทนี้ยกมาห้าจุดของ file นั้น ซึ่งเป็นที่ที่ตัวเลขทุกตัวในบทเกิดขึ้นจริง ส่วนที่เหลือของ file เป็นการประกอบคำถามแล้วพิมพ์ผลออกมา รันด้วย python3 qe/paths.py จาก folder ทำงานด้านนอกเหมือนทุกบท

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

ตัวเลขทุกตัวข้างล่างจึงเทียบกันเองได้ แต่เทียบกับราคาของบท 5 ไม่ได้ และแปลงเป็นเวลาไม่ได้

ตัวเลขหน้าที่แตะทั้งบทนับภายใต้เงื่อนไขเดียวกับบทก่อนหน้าด้วย คือยังไม่มี buffer pool ตัวชี้แถวหนึ่งตัวจึงเท่ากับหนึ่งหน้าเสมอ และทุกครั้งที่มีเลข “หน้าไม่ซ้ำ” พิมพ์คู่มา เลขนั้นคือขอบล่างของกรณีที่ cache ได้ทั้งหมด

index ห้าอันที่ต่างกันแค่ลำดับของคีย์

ตารางที่บทนี้ถาม index ห้าอันที่สร้างทับมัน และวิธีที่ code บีบคีย์ร่วมให้เหลือเลขตัวเดียว

ตารางยังเป็นออเดอร์ชุดเดิม 200,000 แถว ที่บท 2 เขียนลง heap file 3,153 หน้า การสแกนทั้งตารางจึงแตะ 3,153 หน้า และเลขนี้เป็นตัวหารของทุกอัตราส่วนในบทนี้

จำนวนค่าที่ไม่ซ้ำของสาม column ที่บทนี้ใช้ต่างกันคนละระดับ คือ status 7 ค่า restaurant 10 ค่า และ customer_id 2,000 ค่า สามตัวนี้คือ k ที่จะโผล่ในสูตรของทุกหัวข้อข้างหน้า

คำว่า access path ในบทนี้หมายถึงวิธีที่แผนหนึ่งเดินเข้าไปหยิบแถว ไม่ใช่ตัวโครงสร้างที่มันเดินผ่าน index หนึ่งอันจึงให้ทางเข้าได้หลายทาง และบทนี้จะวัดทีละทาง

index ทั้งห้าอันสร้างแบบ bulk load คือเรียงคีย์ให้เสร็จก่อนแล้วค่อยใส่ ซึ่งเป็นวิธีเดียวกับที่ CREATE INDEX ทำ

index	หน้า	ขนาด	เทียบ heap	ความสูง
`(status, restaurant)`	493	2,019,328 B	15.64 %	2 ชั้น
`(restaurant, status)`	493	2,019,328 B	15.64 %	2 ชั้น
`(customer_id, restaurant)`	493	2,019,328 B	15.64 %	2 ชั้น
`(restaurant)`	493	2,019,328 B	15.64 %	2 ชั้น
`(placed_at)`	493	2,019,328 B	15.64 %	2 ชั้น

ห้าแถวนี้เท่ากันเป๊ะทุกช่อง ซึ่งเป็นผลของการออกแบบ ไม่ใช่ข้อค้นพบ

def key_sr(row):
    """(status, restaurant) — status อยู่หน้า"""
    return S_OF[row[2]] * NREST + R_OF[row[3]]


def key_rs(row):
    """(restaurant, status) — restaurant อยู่หน้า"""
    return R_OF[row[3]] * NSTATUS + S_OF[row[2]]


def key_cr(row):
    """(customer_id, restaurant) — column หน้ามีค่าไม่ซ้ำถึง 2,000 ค่า"""
    return (row[1] - 1) * NREST + R_OF[row[3]]


def key_r(row):
    """(restaurant) — index column เดียว ใช้เทียบเรื่อง covering"""
    return R_OF[row[3]]


def key_t(row):
    """(placed_at) — index ของบท 3 เอามาใช้ต่อในหัวข้อการเรียง"""
    return row[4]

คีย์ร่วมของ index สอง column ถูกบีบให้เหลือ uint32 ตัวเดียวที่เรียงตรงกับลำดับของคู่ (column หน้า, column หลัง) เห็นได้จาก key_sr ที่คูณรหัสของ status ด้วยจำนวนร้านก่อนแล้วค่อยบวกรหัสร้าน

การคูณแล้วบวกแบบนั้นเทียบเท่ากับการต่อ byte ของสอง column เข้าด้วยกัน ซึ่งคือสิ่งที่ index จริงทำ ค่าของ column หลังจึงเรียงอยู่ภายในกลุ่มของ column หน้าเสมอ

S_OF กับ R_OF เก็บรหัสตามลำดับที่ประกาศไว้ใน code ลำดับนั้นยืนแทน collation ของ column จริง ไม่ใช่ลำดับพจนานุกรมภาษาไทย

index ห้าอันเท่ากันหมด เพราะของเล่นนี้บีบคีย์ ไม่ใช่เพราะของจริงเป็นแบบนั้น

รายการในใบของทุก index กว้าง 10 B เท่ากันหมด เพราะคีย์ร่วมถูกบีบให้เหลือ uint32 ตัวเดียว ขนาดของ file จึงออกมาเท่ากันทั้งห้าอัน

ของจริงไม่เป็นแบบนี้ index ที่มีสอง column กว้างกว่า index ที่มี column เดียว และคีย์ที่เก็บข้อความจริงกว้างกว่าเลขจำนวนเต็มมาก

ผลดีของการบีบแบบนี้คือความต่างทุกตัวเลขในบทนี้มาจาก ลำดับ ของคีย์ล้วนๆ ไม่มีผลของขนาดปนมาเลย ราคาที่จ่ายคือตัวเลขขนาดของ file ในตารางข้างบนยกไปใช้กับ index ของจริงไม่ได้

prefix ได้ช่วงเดียว suffix ได้ k ช่วง

คำถามเดียวถาม index สองอันที่สลับลำดับกัน แล้วเทียบหน้าที่แตะกับส่วนต่างที่สูตรทำนายได้

คำถามแรกของบทนี้คือ ออเดอร์ของร้าน ครัวคุณแม่ มีกี่แถว การสแกนทั้งตารางตอบว่า 11,934 แถว คิดเป็น 5.97 % ของตาราง และทุกแผนข้างล่างต้องคืนตัวเลขเดียวกันนี้

เงื่อนไข restaurant = 'ครัวคุณแม่' บน index (restaurant, status) แปลงเป็นช่วงคีย์ต่อเนื่องช่วงเดียวได้เสมอ เพราะรหัสร้านคูณอยู่ข้างหน้า ทุกคีย์ของร้านนั้นจึงกองติดกัน

def span(prefix_code, width, lo_code=0, hi_code=None):
    """ช่วงคีย์ของ 'column หน้า = prefix_code' — คือช่วงต่อเนื่องหนึ่งช่วงเสมอ"""
    hi_code = width - 1 if hi_code is None else hi_code
    base = prefix_code * width
    return (base + lo_code, base + hi_code)

บน index (status, restaurant) เงื่อนไขเดียวกันแปลงเป็นช่วงเดียวไม่ได้ เพราะคีย์ของร้านนั้นถูกกระจายไปอยู่ในกลุ่มของ status ทั้ง 7 กลุ่ม แผนจึงต้องอ่าน 7 ช่วง

ราคาของการอ่านหลายช่วงอยู่ในลูปเดียวข้างล่างนี้ ทุกรอบของลูปคือการลงจากรากใหม่หนึ่งครั้ง

def seek_ranges(rd, ranges):
    """เดิน k ช่วงด้วย reader ตัวเดิม คืน (รายการ (key, rid), จำนวนหน้าที่แตะ)"""
    rd.reset()
    out = []
    for lo, hi in ranges:
        out.extend(rd.range(lo, hi))
    return out, rd.reads


def scan_all(rd):
    """สแกน index ทั้งอัน: ลงจากรากครั้งเดียวแล้วเดินโซ่ใบยาวรวด"""
    return seek_ranges(rd, [(0, 0xFFFFFFFF)])

แผน	ช่วงที่ต้องอ่าน	index แตะ	heap แตะ	เทียบสแกน 3,153 หน้า
`(restaurant, status)` — `restaurant` อยู่หน้า	1	31 หน้า	0 หน้า	ถูกกว่า 101.7 เท่า
`(status, restaurant)` — `restaurant` อยู่หลัง	7	43 หน้า	0 หน้า	ถูกกว่า 73.3 เท่า

31 หน้าของแผนแรกแตกได้เป็นการลงจากราก 1 ครั้งซึ่งกิน 2 หน้า กับการเดินโซ่ใบต่อเนื่องอีก 29 หน้า

43 หน้าของแผนที่สองแตกได้เป็นการลงจากราก 7 ครั้งซึ่งกิน 14 หน้า กับการเดินโซ่ใบอีก 29 หน้าเท่าเดิมเป๊ะ

ในคำถามนี้ใบที่เดินผ่านออกมาเท่ากันที่ 29 หน้าทั้งสองแผน ส่วนต่าง 12 หน้าจึงเป็นค่าลงจากรากล้วนๆ คือ (7 − 1) × ความสูง 2 ชั้น

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

flowchart TD
    Q["คำถามเดียว<br/>ออเดอร์ของร้าน ครัวคุณแม่ มีกี่แถว"]
    Q --> A["index (restaurant, status)<br/>restaurant อยู่หน้า"]
    Q --> B["index (status, restaurant)<br/>restaurant อยู่หลัง"]
    A --> A1["ลงจากราก 1 ครั้ง = 2 หน้า"]
    A1 --> A2["เดินโซ่ใบ 29 หน้า"]
    A2 --> A3["รวม 31 หน้า"]
    B --> B1["ลงจากราก 7 ครั้ง = 14 หน้า"]
    B1 --> B2["เดินโซ่ใบ 29 หน้า เท่ากันในคำถามนี้"]
    B2 --> B3["รวม 43 หน้า"]
    A3 --> D["ส่วนต่าง 12 หน้า<br/>= (7−1) × ความสูง 2 ชั้น"]
    B3 --> D
    D --> E["43 เทียบ 31 = 1.39 เท่า"]

คำบรรยายภาพ: คำถามเดียวกันบน index สองอันที่มี column ชุดเดียวกันแต่สลับลำดับ · ฝั่งซ้าย restaurant อยู่ตัวหน้าจึงได้ช่วงต่อเนื่องช่วงเดียว ลงจากรากครั้งเดียว · ฝั่งขวา restaurant อยู่ข้างหลังจึงต้องลงจากรากซ้ำ 7 ครั้งตามจำนวนค่าของ status · ในคำถามนี้ใบที่เดินผ่านเท่ากันทั้งสองฝั่งที่ 29 หน้า ส่วนต่างจึงเป็นค่าลงจากรากล้วนๆ ซึ่งเป็นผลของข้อมูลชุดนี้ ไม่ใช่กฎ

สลับลำดับที่ k = 7 แพงขึ้น 1.39 เท่า ยังไม่ใช่หน้าผา

สโลแกนที่ว่า prefix ได้ช่วงเดียว ส่วน suffix ได้ k ช่วง เป็นเรื่องจริง แต่คำที่มักตามมาว่า “ผิดลำดับแล้วพัง” ไม่ตรงกับตัวเลขเมื่อ k เล็ก ส่วน k จะใหญ่แค่ไหนถึงพังจริง หัวข้อถัดไปวัดให้ดู

ที่ k = 7 ราคาต่างกัน 1.39 เท่า ซึ่งน้อยกว่าที่สโลแกนชวนให้คิดมาก และแผนที่แพงกว่านั้นก็ยังถูกกว่าการสแกนทั้งตาราง 73.3 เท่าอยู่ดี

สิ่งที่ต้องจำจึงไม่ใช่ “อย่าเอา column ไปไว้ข้างหลัง” แต่เป็นสูตร k × ความสูง + ใบที่เดินผ่าน ซึ่งบอกได้ว่าราคาจะขยับเท่าไรก่อนจะสร้าง index จริง

จุดที่ระเบิดคือ k ไม่ใช่ตัวอ่าน

คำถามเดิมบน index ที่ column หน้ามีค่าไม่ซ้ำ 2,000 ค่า และเงื่อนไขที่ทำให้ k เท่ากับตัวเลขนั้น

คำถามเดิมทุกตัวอักษร บน index (customer_id, restaurant) ซึ่ง column หน้ามีค่าไม่ซ้ำถึง 2,000 ค่า

แผน	ช่วงที่ต้องอ่าน	index แตะ	heap แตะ	เทียบสแกน 3,153 หน้า
`(customer_id, restaurant)` — `restaurant` อยู่หลัง	2,000	4,023 หน้า	0 หน้า	แพงกว่า 1.28 เท่า

4,023 หน้าแตกได้เป็นการลงจากราก 2,000 ครั้งซึ่งกิน 4,000 หน้า กับการเดินใบต่ออีกแค่ 23 หน้า

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

เทียบกับแผน prefix ของหัวข้อก่อน ราคาต่างกัน 129.77 เท่า และแผนนี้แพงกว่าการสแกนทั้งตาราง 1.28 เท่า ทั้งที่มันไม่แตะ heap เลยสักหน้า

ตัวอ่านไม่ได้เปลี่ยนเลยระหว่างสองหัวข้อนี้ มันเป็น seek_ranges ตัวเดิม บน index ที่มีความสูงเท่ากันและกว้างเท่ากัน สิ่งเดียวที่เปลี่ยนคือ k จาก 7 เป็น 2,000

k ไม่ใช่จำนวนค่าที่ เป็นไปได้ ของ column หน้า แต่เป็นจำนวนค่าที่ มีอยู่จริง ในข้อมูล เพราะเอนจินไม่ได้เดาค่าเอง มันถาม index ว่าค่าถัดไปคืออะไร

ในชุดข้อมูลนี้ customer_id มีครบทั้ง 2,000 ค่า ตัวเลขสองตัวจึงบังเอิญเท่ากันพอดี ถ้ามีลูกค้าจำนวนมากที่ไม่เคยสั่งเลย k จะน้อยกว่า 2,000 และราคาจะลดลงตามนั้น

นี่คือเหตุผลตรงๆ ที่เอนจินจริงต้องรู้จำนวนค่าที่ไม่ซ้ำของ column หน้าก่อน จึงจะยอมเลือกแผน k ช่วง

ตัวเลขนั้นไม่ได้ถูกเก็บไว้ตรงๆ แต่หาได้จาก sqlite_stat1 ของบท 4 ซึ่งเก็บจำนวนแถวทั้งหมดคู่กับจำนวนแถวเฉลี่ยต่อคีย์ เอาสองตัวนั้นหารกันก็ได้จำนวนค่าที่ไม่ซ้ำ เช่น idx_status เก็บ 200000 28572 ซึ่งหารกันได้ 7 พอดี

อ่าน index ทั้งอันแล้วกรอง — แผนที่ชนะเฉพาะเมื่อ k ใหญ่

แผนที่สี่บน index อันเดิม ซึ่งเลิก seek ทีละช่วงแล้วอ่านรวดเดียว กับเหตุผลที่มันถูกกว่าแผน 2,000 ช่วงและถูกกว่าการสแกน heap

บน index (customer_id, restaurant) อันเดิมนั้น ยังมีแผนที่สี่ที่เลิกไล่ seek ทีละช่วง คือลงจากรากครั้งเดียว เดินโซ่ใบยาวรวดจนจบ แล้วค่อยกรองเอาเฉพาะรายการที่ตรงกับร้านที่ถาม

นั่นคือสิ่งที่ scan_all ทำ มันเรียก seek_ranges ตัวเดิมด้วยช่วงเดียวที่กว้างคลุมคีย์ทั้งหมด

แผน	ช่วงที่ต้องอ่าน	index แตะ	heap แตะ	เทียบสแกน 3,153 หน้า
สแกน index `(customer_id, restaurant)` ทั้งอันแล้วกรอง	1	492 หน้า	0 หน้า	ถูกกว่า 6.4 เท่า

492 หน้าแตกได้เป็นการลงจากราก 1 ครั้งซึ่งกิน 2 หน้า กับการเดินโซ่ใบอีก 490 หน้า รวมกับใบแรกที่เจอตอนลงจากรากก็คือใบครบทั้ง 491 ใบของต้นไม้

แผนนี้อ่านทุกรายการใน index โดยไม่ข้ามอะไรเลย แต่ยังถูกกว่าการไล่ seek 2,000 ช่วงบน index อันเดียวกัน 8.18 เท่า

การไล่ seek แพงกว่าการอ่านรวดเดียวเพราะมันจ่ายค่าลงจากรากซ้ำ 2,000 ครั้ง ส่วนการอ่านรวดเดียวจ่ายค่านั้นครั้งเดียวแล้วเดินตามโซ่ใบต่อไปเรื่อยๆ

แผนนี้ยังถูกกว่าการสแกน heap ทั้งตาราง 6.4 เท่าด้วย เหตุผลอยู่ที่ความกว้างของหนึ่งรายการ คือรายการในใบกว้าง 10 B ส่วนแถวจริงใน heap เฉลี่ย 59.99 B และเมื่อรวม slot 4 B ที่บท 2 คิดให้ทุกแถวเป็น 63.99 B หารด้วย 10 B ได้ 6.4 พอดี

ผลของความกว้างนั้นคือ index ทั้ง file กิน 493 หน้า เทียบกับ heap 3,153 หน้า หรือ 15.64 % แผนนี้จึงอ่านครบทุกรายการใน index เหมือนที่การสแกนตารางอ่านครบทุกแถว แต่จ่ายหน้าคนละระดับกัน

ราคาที่แผนนี้จ่ายคือ 492 หน้าซึ่งไม่ขึ้นกับสัดส่วนแถวเลย ถามคำถามที่มีคำตอบแถวเดียวก็ยังจ่าย 492 หน้าเท่าเดิม และมันต้องเทียบคีย์ครบทั้ง 200,000 รายการที่อยู่ในใบ

เทียบกับแผน prefix ของหัวข้อแรกที่แตะ 31 หน้า แผนนี้จึงแพงกว่า 15.9 เท่า มันชนะเฉพาะตอนที่ k ใหญ่จนค่าลงจากรากท่วมทุกอย่าง ไม่ใช่ชนะทุกคำถาม

ไม่มีลำดับไหนดีกว่าลอยๆ

คำถามที่ระบุ column อีกตัวบน index สองอันเดิม แล้วผู้ชนะสลับข้าง

คำถามที่สองกลับด้าน คือ ออเดอร์สถานะ Rejected มีกี่แถว คำตอบคือ 13,165 แถว คิดเป็น 6.58 % ของตาราง

แผน	ช่วงที่ต้องอ่าน	index แตะ
`(status, restaurant)` — `status` อยู่หน้า	1	34 หน้า
`(restaurant, status)` — `status` อยู่หลัง	10	54 หน้า

index สองอันนี้คืออันเดิมสองอันจากคำถามแรก ไม่ได้สร้างใหม่และไม่ได้แก้อะไรเลย เปลี่ยนแค่ว่าคำถามระบุ column ไหน แล้วผู้ชนะสลับข้างทันที

k ของแผนที่สองเป็น 10 คราวนี้ ไม่ใช่ 7 เพราะ column ที่อยู่หน้ากลายเป็น restaurant ซึ่งมี 10 ค่า สูตรตัวเดิม เปลี่ยนแค่ว่าใครอยู่หน้า

แต่ส่วนต่างจริงคือ 54 − 34 = 20 หน้า ขณะที่ค่าลงจากรากอธิบายได้ 18 หน้า คือ (10 − 1) × 2 อีก 2 หน้าที่เหลือคือใบหัวท้ายของช่วงที่ถูกอ่านซ้ำ ซึ่งคือเหตุผลที่ใบที่เดินผ่านของแผน k ช่วงเป็นขอบล่าง

ลำดับของคีย์จึงไม่ใช่คุณสมบัติของ index อย่างเดียว มันเป็นคุณสมบัติของคู่ระหว่าง index กับคำถาม การถามว่า (status, restaurant) หรือ (restaurant, status) ดีกว่ากันโดยไม่บอกคำถาม จึงตอบไม่ได้

covering index — index ที่ตอบได้จบที่ใบ

คำถามสองข้อคนละปลายของสัดส่วนแถว เทียบแผนที่จบที่ใบกับแผนที่ต้องตามตัวชี้กลับไปเปิดแถว

covering index คือ index ที่มีทุก column ที่คำถามขอ แผนจึงตอบจบได้ที่ใบ ไม่ต้องเอาตัวชี้แถวไปเปิด heap อีกรอบ

คำถามที่สามคือ ของร้าน ครัวคุณแม่ แต่ละสถานะมีกี่แถว ซึ่งขอสอง column คือ restaurant กับ status

แผน	index แตะ	heap แตะ	รวม
covering — index `(restaurant, status)`	31 หน้า	0 หน้า	31 หน้า
non-covering — index `(restaurant)` แล้วเปิดแถวจริง	31 หน้า	11,934 หน้า	11,965 หน้า
สแกน heap ทั้งตาราง	—	3,153 หน้า	3,153 หน้า

ทั้งสองแผนแตะ index เท่ากันคือ 31 หน้า ส่วนต่างทั้งหมดอยู่ที่ heap และมันเกิดขึ้นในสองฟังก์ชันข้างล่างนี้

def fetch_rows(pager, rids):
    """ตามตัวชี้กลับไปหยิบแถวจริงจาก heap — หนึ่ง rid = อ่านหนึ่งหน้า (ไม่มี cache)"""
    pager.reads = 0
    got = [decode(read_row(pager, rid)) for rid in rids]
    return got, pager.reads, len({p for p, _ in rids})


def touch_rows(pager, rids):
    """เหมือน fetch_rows แต่ไม่เก็บผล ใช้ตอนสนใจแค่ 'แตะกี่หน้า' กับชุดที่ใหญ่มาก"""
    pager.reads = 0
    for rid in rids:
        read_row(pager, rid)
    return pager.reads, len({p for p, _ in rids})

ลูปนั้นเรียก read_row ทีละตัวชี้ ไม่มีอะไรจำหน้าที่เพิ่งอ่านไว้ ตัวชี้ 11,934 ตัวจึงกลายเป็นการอ่าน 11,934 หน้าตรงๆ

หน้าไม่ซ้ำจริงมี 3,079 หน้า ซึ่งเป็นขอบล่างของกรณีที่ cache ได้ทั้งหมด ของจริงอยู่ระหว่าง 3,079 กับ 11,934

covering แตะ 31 หน้า ส่วน non-covering แตะ 11,965 หน้า ต่างกัน 11,934 หน้า คิดเป็นราคา 386.0 เท่า

แต่ประเด็นที่แรงกว่าคือแผน non-covering แพงกว่าการอ่านทั้งตารางทิ้ง 3.79 เท่า ทั้งที่มันเอาแถวมาแค่ 5.97 %

flowchart LR
    Q["คำถาม<br/>ร้าน ครัวคุณแม่ แต่ละสถานะมีกี่แถว"]
    Q --> C1["เดิน index (restaurant, status)<br/>31 หน้า"]
    Q --> N1["เดิน index (restaurant)<br/>31 หน้า"]
    C1 --> C2["คีย์มีทั้งชื่อร้านและสถานะ<br/>ตอบจบที่ใบ"]
    C2 --> C3["รวม 31 หน้า"]
    N1 --> N2["คีย์ไม่มีสถานะ<br/>ต้องเปิดแถวจริง 11,934 ครั้ง"]
    N2 --> N3["แตะ heap 11,934 หน้า<br/>หน้าไม่ซ้ำจริง 3,079 หน้า"]
    N3 --> N4["รวม 11,965 หน้า"]
    C3 --> V{"อ่านตัวเลขสองคู่"}
    N4 --> V
    V --> V1["covering ถูกกว่า non-covering 386.0 เท่า"]
    V --> V2["non-covering แพงกว่าสแกนทั้งตาราง 3.79 เท่า"]

คำบรรยายภาพ: สองเส้นทางของคำถามเดียวกัน · เส้นบนใช้ index ที่มีทั้งสอง column ที่คำถามขอ จึงจบที่ใบและไม่แตะ heap เลย · เส้นล่างใช้ index ที่รู้แค่ว่าแถวอยู่ตรงไหน จึงต้องเอาตัวชี้ไปเปิดแถวจริงทีละแถว · ลูกศรกลับไปหา heap ในเส้นล่างมี 11,934 เส้น วาดไว้เป็นสัญลักษณ์เส้นเดียว

ปลายอีกด้านของสัดส่วนแถวให้ผลคนละแบบ คำถามที่สี่คือ สถานะ Placed มาจากร้านไหนบ้าง อย่างละกี่แถว ซึ่งมีคำตอบ 199 แถว คิดเป็น 0.10 % ของตาราง

แผน	หน้าที่แตะ
covering — index `(status, restaurant)`	2 หน้า
non-covering — เดิน index แล้วเปิดแถวจริง	index 2 + heap 199 = 201 หน้า (heap ไม่ซ้ำ 190 หน้า)
สแกน heap ทั้งตาราง	3,153 หน้า

ที่สัดส่วนแถวต่ำขนาดนี้ แผน non-covering ยังชนะการสแกนอยู่ 15.7 เท่า แต่ covering ยังถูกกว่า non-covering อีก 100 เท่า

กติกาที่ตัดสินคือหนึ่งตัวชี้แถวเท่ากับหนึ่งหน้า จุดตัดจึงเป็นของแผนนั้น ไม่ใช่ของตาราง

ค่าคงที่ที่ตัดสินทั้งหมดนี้มีตัวเดียว คือการตามตัวชี้กลับไปหยิบแถวเท่ากับ 1 หน้าต่อ 1 แถว

แผน non-covering ที่ตัวชี้แถวกระจายจึงแพงกว่าการสแกนทั้งตารางทันทีที่ผลลัพธ์เกิน 3,153 แถว หรือ 1.58 % ของตาราง

เลข 1.58 % นี้เป็นเลขเดียวกับจุดคุ้มทุนที่บท 2 วัดไว้ ไม่ใช่ความบังเอิญ ทั้งสองบทเดินมาจากข้อเท็จจริงข้อเดียวกันคนละทาง คือหนึ่งตัวชี้แถวเท่ากับหนึ่งหน้า

แต่ตัวเลขนี้เป็นของแผนที่ตัวชี้แถวกระจาย และวัดด้วยหน้าที่แตะดิบๆ ที่ไม่มี buffer pool บท 5 วัดจุดตัดของ index ที่ไม่ cluster ด้วย cost model แล้วได้ 394 แถว หรือ 0.197 % ส่วน index ที่ cluster ได้ 185,094 แถว หรือ 92.55 %

จุดตัดจึงเป็นตัวเลขของ index ตัวนั้นเสมอ ไม่ใช่ของตาราง คำถามที่หกข้างล่างหยิบครบทั้ง 200,000 แถวแต่แตะหน้าไม่ซ้ำแค่ 3,153 หน้า เพราะ index (placed_at) เรียงตรงกับลำดับของ heap พอดี

ราคาของ covering ที่ไม่ได้อยู่ในตารางไหนในบทนี้ คือทุก column ที่ใส่เพิ่มเข้าไปทำให้รายการในใบกว้างขึ้น ใบเก็บได้น้อยลง และ index ทั้งอันโตขึ้น ของเล่นชุดนี้วัดราคานั้นไม่ได้เพราะมันบีบคีย์เป็น uint32 หมดแล้ว

sort avoidance — ฟรีเมื่อ index ครอบคลุม แลกเมื่อไม่ครอบคลุม

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

sort avoidance คือการอาศัยลำดับที่ index มีอยู่แล้ว เพื่อไม่ต้องเรียงผลลัพธ์เอง ลำดับนั้นเป็นของที่ติดมากับโครงสร้าง ไม่ใช่สิ่งที่ต้องคำนวณ

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

บท 1 ประกาศหน่วยที่สองไว้ว่าจะเพิ่มเข้ามาตอนบท join หัวข้อนี้หยิบมาใช้ก่อน เพราะการเลี่ยงการเรียงวัดด้วยหน้าที่แตะอย่างเดียวแล้วสรุปผิด

คำถามที่ห้าคือ 20 ออเดอร์แรกสุด เขียนเป็น ORDER BY placed_at LIMIT 20

แผน	หน้าที่แตะ	แถวที่ถือไว้พร้อมกัน
index `(placed_at)` แล้วหยุดกลางคัน	22 หน้า	20
สแกน heap แล้วเก็บ 20 อันดับแรก	3,153 หน้า	20
สแกน heap แล้วเรียงทั้งชุด	3,153 หน้า	200,000

22 หน้าของแผนแรกคือ index 2 หน้ากับ heap 20 หน้า มันหยุดได้ทันทีที่ครบ 20 แถว เพราะเดินตามลำดับคีย์อยู่แล้ว

การหยุดกลางคันนั้นเป็นของจริงใน code ไม่ใช่การกรองทีหลัง ลูปข้างล่างเช็ก len(out) < limit ทุกรอบทั้งชั้นนอกและชั้นใน

def scan_ordered(rd, limit):
    """เดินตามลำดับคีย์จากซ้ายสุด แล้วหยุดทันทีที่ได้ครบ limit

    ใช้ _descend ของ reader ตรง ๆ เพราะ range() ไม่มีทางหยุดกลางคัน
    ซึ่งประเด็นของหัวข้อ [3] คือ "หยุดกลางคันได้" นั่นแหละ
    """
    rd.reset()
    pno, page = rd._descend(0)
    out, i = [], 0
    while len(out) < limit:
        _, n, nxt = header(page)
        while i < n and len(out) < limit:
            out.append((leaf_key(page, i), leaf_rid(page, i)))
            i += 1
        if len(out) >= limit or nxt == NO_NEXT:
            break
        page, i = rd.pager.read_page(nxt), 0
    return out, rd.reads

แผนที่สองต้องอ่านครบทั้ง 3,153 หน้าก่อนถึงจะรู้ว่าใครอยู่ใน 20 อันดับแรก มันถือแถวไว้ 20 แถวเท่ากัน แต่จ่ายหน้ามากกว่า 143 เท่า

LIMIT ตัดงานได้จริงเฉพาะตอนที่ลำดับมาจาก index ถ้าลำดับต้องคำนวณเอง LIMIT ไม่ได้ลดงานที่ต้องทำก่อนหน้านั้นเลยสักหน้า

คำถามที่หกถอด LIMIT ออก เหลือ ORDER BY placed_at ทั้งตาราง แล้วผลกลับด้านทันที

แผน	หน้าที่แตะ	แถวที่ถือไว้พร้อมกัน
index `(placed_at)` แล้วตามไปหยิบแถวทีละแถว	200,492 หน้า	1
สแกน heap แล้วเรียงทั้งชุด	3,153 หน้า	200,000

200,492 หน้าคือ index 492 หน้ากับ heap 200,000 หน้า แผนนี้เลี่ยงการเรียงได้จริง ผลไหลออกทีละแถว แต่จ่ายหน้าเพิ่ม 63.6 เท่า

สิ่งที่แลกมาคือหน่วยความจำ จาก 200,000 แถวที่ต้องถือไว้พร้อมกันเหลือ 1 แถว เมื่อ index ตอบไม่จบที่ใบและไม่มี LIMIT มาตัดงาน การเลี่ยงการเรียงคือการย้ายราคาจากหน่วยหนึ่งไปอีกหน่วยหนึ่ง ไม่ใช่การชนะ

ตัวเลขของคำถามนี้เป็นกรณีดีที่สุด ไม่ใช่กรณีทั่วไป

แถวชุดนี้เรียงตาม placed_at มาตั้งแต่ qe/fixture.py ของบท 1 heap จึงถูกเขียนเรียงตามนั้นไปด้วย การเดินตาม index (placed_at) จึงไล่หน้าไปข้างหน้าเรื่อยๆ ไม่กระโดดกลับ หน้าไม่ซ้ำจึงมีแค่ 3,153 หน้า

ถ้ามี cache พอเก็บทั้ง file แผนนี้จะเหลือราว 3,645 หน้า แทนที่จะเป็น 200,492 หน้า

ถ้าเปลี่ยนไปถามด้วย column ที่ไม่ได้เรียงอยู่แล้ว ตัวเลขจะไม่สวยแบบนี้ บท 3 วัดไว้ว่าคำถาม customer_id = 995 ได้ 97 แถวที่กระจายอยู่บน 93 หน้า หรือ 0.96 หน้าต่อหนึ่งแถว ซึ่งแทบไม่มีอะไรให้ cache ช่วยเลย

คำถามที่เจ็ดผสมสองเรื่องเข้าด้วยกัน คือ ออเดอร์ของร้าน ครัวคุณแม่ เรียงตาม status

แผน	หน้าที่แตะ	แถวที่ถือไว้พร้อมกัน
index `(restaurant, status)` — ลำดับตรงกับที่ขอ	31 หน้า	1
index `(status, restaurant)` — 7 ช่วง เดินตามลำดับ `status`	43 หน้า	1
index `(restaurant)` — index ไม่รู้จัก `status`	31 + 11,934 หน้า	11,934

แผนที่สามต้องหยิบแถวให้ครบทั้ง 11,934 แถวก่อนถึงจะเรียงได้ เพราะ index ที่มันใช้ไม่มี status อยู่ในคีย์เลย

แผน 7 ช่วงยังคืนผลเรียงตาม status และถือไว้แค่ 1 แถวเหมือนแผนแรก เพราะเราเดินช่วงตามลำดับของ column ที่อยู่หน้าอยู่แล้ว

สองแผนบนเป็น covering ด้วย การเลี่ยงการเรียงในคำถามนี้จึงชนะทั้งสองหน่วยจริง คือ 31 หน้ากับถือไว้ 1 แถว เหนือแผนที่สามซึ่งจ่าย 11,965 หน้าและถือไว้ 11,934 แถว เหมือนที่คำถามที่ห้าชนะทั้งสองหน่วยเพราะ LIMIT ตัดงานให้

กติกาที่แม่นกว่า “k ช่วงทำลายลำดับ” จึงเป็น k ช่วงรักษาลำดับของ column ที่อยู่หน้า ไม่ใช่ของ column ที่อยู่หลัง

เงื่อนไขที่ทำให้ตัวเลขทั้งบทออกมาแบบนี้

ข้อจำกัดสี่ข้อของของเล่นชุดนี้ที่ต้องอ่านคู่กับทุกตัวเลขข้างบน และสิ่งที่บทหน้าทำต่อ

ไม่มี buffer pool ตัวชี้แถวหนึ่งตัวเท่ากับหนึ่งหน้าเสมอ เลข 11,934 กับ 200,000 หน้าจึงเป็นขอบบนของกรณีที่ cache อะไรไม่ได้เลย ส่วนเลข 3,079 กับ 3,153 ที่พิมพ์คู่มาคือขอบล่าง
index ทุกอัน bulk load ใบจึงเต็มเกือบ 100 % เหมือนตอน CREATE INDEX เสร็จใหม่ๆ หลังตารางถูกแก้ไปสักพัก ใบจะเต็มราว 70 % และทุกจำนวนหน้าในบทนี้จะโตราว 1.4 เท่า
คีย์ร่วมถูกบีบเป็น uint32 index ห้าอันจึงกว้างเท่ากันหมด ความต่างทุกตัวในบทนี้เป็นผลของลำดับล้วนๆ ซึ่งเป็นข้อดีของการทดลอง แต่แปลว่าตัวเลขขนาดของ file ยกไปใช้กับของจริงไม่ได้
ลำดับของค่ามาจาก code S_OF กับ R_OF ตรึงลำดับไว้ตามที่ประกาศใน qe/fixture.py และ qe/heapfile.py มันยืนแทน collation ของ column จริง ไม่ใช่ลำดับพจนานุกรมภาษาไทย

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

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

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

Query Planning — SQLite (ตรวจ 2026-08-11) — เอกสารทางการที่อธิบายเงื่อนไขที่ทำให้ index ตอบคำถามได้เองโดยไม่ต้องกลับไปเปิดแถวจริง และเงื่อนไขที่ทำให้ planner ยอมอ่าน index หลายช่วงแทนช่วงเดียว ส่วนตัวเลขทั้งหมดในบทนี้เป็นของโครงสร้างที่คอร์สนี้สร้างเอง ไม่ใช่ของ SQLite

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

ข้อ 1 / 3

คำถามเดียวกันคือ ออเดอร์ของร้าน ครัวคุณแม่ มีกี่แถว บน index (restaurant, status) แตะ 31 หน้า ส่วนบน index (status, restaurant) แตะ 43 หน้า ส่วนต่าง 12 หน้ามาจากอะไร

ทาง​เข้า — ลำดับ​ของ column, covering index และ​การ​ไม่​ต้อง​เรียง

index ห้า​อัน​ที่​ต่าง​กัน​แค่​ลำดับ​ของ​คีย์

prefix ได้​ช่วง​เดียว suffix ได้ k ช่วง

จุด​ที่​ระเบิด​คือ k ไม่ใช่​ตัว​อ่าน

อ่าน index ทั้ง​อัน​แล้วก​รอง — แผนที่​ชนะ​เฉพาะ​เมื่อ k ใหญ่

ไม่มี​ลำดับ​ไหน​ดี​กว่า​ลอยๆ

covering index — index ที่​ตอบ​ได้​จบ​ที่​ใบ

sort avoidance — ฟรี​เมื่อ index ครอบคลุม แลก​เมื่อ​ไม่​ครอบคลุม

เงื่อนไข​ที่​ทำให้​ตัวเลข​ทั้ง​บท​ออก​มา​แบบ​นี้