หน้า (page) — ทำไม "อ่านหนึ่งแถว" ถึงไม่มีอยู่จริง

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

บทนี้ประกอบก้อนนั้นขึ้นมาเองตั้งแต่ byte แรก แล้ววัดว่าข้อเท็จจริงข้อเดียวนี้ทำให้ต้องจ่ายอะไรบ้าง

ทุกอย่างที่เหลือในคอร์สนี้ ตั้งแต่ B+tree ไปจนถึงการเลือกทางเข้า เป็นผลของการที่ชั้นเก็บข้อมูลส่งของมาเป็นก้อน ไม่ใช่ทีละแถว

📦 code ของบทนี้

บทนี้เขียน file ใหม่หนึ่ง file คือ qe/heapfile.py วางไว้ข้างๆ qe/fixture.py ของบทที่แล้ว ส่วนโครงสร้างที่บทนี้ยกมาต้อง import แค่ struct ซึ่งติดมากับภาษาอยู่แล้ว

code block ทุกอันในบทนี้เรียงตามลำดับที่พิมพ์ลง file ได้ตรงๆ ตั้งแต่ block แรกถึง block สุดท้าย

ส่วนที่พิมพ์ตัวเลขทั้งหมดของบทนี้ออกมาคือ block __main__ ท้าย file เดียวกัน ซึ่งบทนี้ไม่ได้ยกมา มันเพิ่ม import อีกสี่ตัวคือ os, random, collections และ fixture ของบทที่แล้ว ทั้งหมดยังเป็น stdlib เหมือนเดิม

แปลว่าพิมพ์ตามเฉพาะ block ในบทนี้แล้วรันจะยังไม่มีอะไรออกมา ผู้อ่านต้องเขียนส่วนวัดผลเองตามหัวข้อที่บทนี้ไล่ไปทีละตาราง แล้วเทียบว่าได้เลขเดียวกันหรือไม่

ชั้นเก็บข้อมูลไม่เคยส่ง “หนึ่งแถว” มาให้

ขนาดของก้อนที่คอร์สนี้ตรึงไว้ ค่าคงที่ทั้งชุดของโมดูล และวิธีแปลงหนึ่งแถวให้เป็น byte

หน่วยที่บทที่แล้วตกลงไว้คืออ่านหนึ่งหน้านับเป็นหนึ่งครั้ง และคอร์สนี้ตรึงขนาดหนึ่งหน้าไว้ที่ 4096 byte ตลอดทั้งแปดบท

ค่าคงที่ทั้งชุดของโมดูลนี้อยู่รวมกันที่หัว file และมันคือกติกาทั้งหมดของรูปแบบข้อมูลที่บทนี้ใช้

"""บท 2 — slotted page + heap file + pager ที่นับหน้าที่อ่าน. stdlib เท่านั้น"""
import struct

PAGE_SIZE = 4096
HEADER = struct.Struct("<HH")      # (nslots, content_start)
SLOT = struct.Struct("<HH")        # (offset, length)  = 4 B
HEADER_SIZE = HEADER.size          # 4
SLOT_SIZE = SLOT.size              # 4
MAX_ROW = PAGE_SIZE - HEADER_SIZE - SLOT_SIZE

STATUS = ["Placed", "Confirmed", "Preparing", "PickedUp",
          "Delivered", "Rejected", "Cancelled"]
FIXED = struct.Struct("<IIBIIH")   # id, customer_id, status, placed_at, satang, len(name)

< ที่ขึ้นต้นทุก format string อ่านว่า little-endian แบบไม่ใส่ padding ระหว่าง field คอร์สนี้บังคับให้ทุก struct ขึ้นต้นด้วยมัน ไม่ใช่เรื่องรสนิยม

ถ้าปล่อยให้เป็นค่าปริยาย Python จะจัด field ให้ตรง word boundary ตามเครื่องที่รัน ขนาดของแถวเดียวกันจะไม่เท่ากันข้ามเครื่อง และ file ที่เขียนบนเครื่องหนึ่งจะอ่านบนอีกเครื่องไม่ได้

MAX_ROW ออกมาเป็น 4088 B จากการลบตรงๆ หน้าเปล่ามี 4096 B แต่ต้องกัน 4 B ให้ header และอีก 4 B ให้ slot ของแถวนั้นเอง แถวที่ใหญ่กว่านี้ลงหน้าเดียวไม่ได้ และของจริงแก้ด้วย overflow page ซึ่งคอร์สนี้ไม่ได้สร้าง

หนึ่งแถวถูกแปลงเป็น byte ด้วยสองฟังก์ชันนี้

def encode(oid, cid, st, rest, ts, satang):
    b = rest.encode()
    return FIXED.pack(oid, cid, STATUS.index(st), ts, satang, len(b)) + b


def decode(buf):
    oid, cid, st, ts, sat, n = FIXED.unpack_from(buf, 0)
    return (oid, cid, STATUS[st], buf[FIXED.size:FIXED.size + n].decode(), ts, sat)

FIXED กินพอดี 19 B ทุกแถว เพราะ < ตัดสิทธิ์ padding ทิ้งไป แถวหนึ่งจึงเป็นส่วนคงที่ 19 B ต่อด้วยชื่อร้านเข้ารหัส UTF-8 ที่ยาวไม่เท่ากัน โดยมี field ขนาด 2 B ตัวสุดท้ายของส่วนคงที่บอกไว้ว่าชื่อยาวกี่ byte

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

slotted page — สองด้านที่โตเข้าหากันในหน้าเดียว

โครงภายในหนึ่งหน้า เหตุผลที่ต้องมี slot directory และเงื่อนไขที่ตัดสินว่าแถวถัดไปลงหน้านี้ได้หรือไม่

slotted page แก้โจทย์ข้อเดียว คือทำอย่างไรให้เก็บแถวที่ยาวไม่เท่ากันลงในก้อนขนาดคงที่ แล้วยังชี้กลับมาที่แถวใดแถวหนึ่งได้

คำตอบคือให้สองอย่างโตเข้าหากันจากคนละด้านของหน้า

header 4 B ที่ต้นหน้า เก็บคู่ (nslots, content_start) คือจำนวน slot ที่ใช้ไปแล้ว กับตำแหน่งที่ข้อมูลแถวเริ่ม
slot directory ต่อจาก header ทันที แต่ละ slot กิน 4 B เก็บคู่ (offset, length) ของหนึ่งแถว และโตจากซ้ายไปขวา
ข้อมูลแถว เริ่มจากท้ายหน้าแล้วโตสวนกลับมาทางซ้าย แถวใหม่ไปวางไว้ซ้ายกว่าแถวก่อนหน้าเสมอ

ที่ว่างจริงของหน้าคือช่องตรงกลางระหว่างปลายของ slot directory กับหัวของข้อมูลแถว และมันหดลงจากทั้งสองด้านทุกครั้งที่แทรกแถว

def new_page():
    p = bytearray(PAGE_SIZE)
    HEADER.pack_into(p, 0, 0, PAGE_SIZE)
    return p


def free_space(page):
    n, cs = HEADER.unpack_from(page, 0)
    return cs - (HEADER_SIZE + n * SLOT_SIZE)


def insert(page, row):
    if len(row) > MAX_ROW:
        raise ValueError(f"แถว {len(row)} B ใหญ่เกินหนึ่งหน้า — ของจริงใช้ overflow page")
    if free_space(page) < len(row) + SLOT_SIZE:
        return None
    n, cs = HEADER.unpack_from(page, 0)
    cs -= len(row)
    page[cs:cs + len(row)] = row
    SLOT.pack_into(page, HEADER_SIZE + n * SLOT_SIZE, cs, len(row))
    HEADER.pack_into(page, 0, n + 1, cs)
    return n

หน้าเปล่าตั้ง content_start ไว้ที่ 4096 ซึ่งเป็นตำแหน่งถัดจาก byte สุดท้ายของหน้า อ่านว่าข้อมูลแถวยังไม่เริ่ม

บรรทัดที่ตัดสินทุกอย่างคือ free_space(page) < len(row) + SLOT_SIZE แถวใหม่ต้องจ่ายค่า slot ของตัวเองด้วย ไม่ใช่แค่ที่วางข้อมูล

ถ้าลืม + SLOT_SIZE ไป โปรแกรมจะไม่ error ทันที มันจะยอมรับแถวที่พอดีเป๊ะ แล้ว slot ตัวใหม่จะเขียนทับ byte ต้นๆ ของแถวที่เพิ่งวางไป กว่าจะรู้ตัวคือตอนอ่านกลับแล้วได้ค่าเพี้ยน

insert คืนหมายเลข slot กลับมา ไม่ได้คืน offset และนั่นคือทั้งหมดของเรื่อง record id ซึ่งในคอร์สนี้คือคู่ (หมายเลขหน้า, หมายเลข slot)

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

flowchart LR
    H["header 4 byte<br/>nslots และ content_start"] --> S["slot directory<br/>slot ละ 4 byte<br/>โตจากซ้ายไปขวา"]
    S --> F["ที่ว่างตรงกลาง<br/>หดลงทุกครั้งที่แทรกแถว"]
    F --> D["ข้อมูลแถว<br/>โตจากขวามาซ้าย"]
    S -. "แต่ละ slot เก็บตำแหน่งและความยาวของหนึ่งแถว" .-> D
    R["record id คือคู่ หมายเลขหน้า กับ หมายเลข slot"] --> S

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

การอ่านกลับกับการลบเป็นด้านตรงข้ามของ slot ตัวเดียวกัน

def read_slot(page, slot):
    n, _ = HEADER.unpack_from(page, 0)
    if not 0 <= slot < n:
        raise IndexError(slot)
    off, ln = SLOT.unpack_from(page, HEADER_SIZE + slot * SLOT_SIZE)
    if ln == 0:
        raise KeyError("slot ถูกลบไปแล้ว")
    return bytes(page[off:off + ln])


def nslots(page):
    return HEADER.unpack_from(page, 0)[0]


def delete(page, slot):
    SLOT.pack_into(page, HEADER_SIZE + slot * SLOT_SIZE, 0, 0)

delete ไม่ได้ลบ byte ของแถวทิ้ง มันเขียนค่า (0, 0) ลง slot แล้วปล่อยไว้เท่านั้น

คู่ (0, 0) ปลอดภัยทั้งสองช่อง offset 0 อยู่ในเขต header เสมอจึงไม่มีวันเป็นตำแหน่งจริงของแถว ส่วนความยาว 0 ก็เป็นไปไม่ได้ เพราะลำพังส่วนคงที่ของแถวก็กิน 19 B แล้ว

ตัวที่ read_slot ตรวจจริงคือ field ความยาว มันเทียบ ln == 0 แล้วโยน KeyError ออกมา จึงแยก slot ที่ถูกลบออกจาก slot ที่ยังใช้อยู่ได้ โดยไม่ต้องเพิ่ม field ใหม่เข้าไปในหน้า

ราคาของทางเลือกนี้คือ slot ของแถวที่ถูกลบยังกินที่ 4 B ต่อไป และ byte ของแถวเก่ายังนอนอยู่ในหน้าจนกว่าจะมีการจัดที่ว่างใหม่ heap ของคอร์สนี้เขียนต่อท้ายอย่างเดียวและไม่เคยเรียก delete เลยสักครั้ง ฟังก์ชันนี้จึงมีไว้ให้เห็นรูปร่างของมันเท่านั้น

ขนาดแถวจริง — ชื่อร้านเป็นตัวกำหนด

ตารางขนาดของสิบร้านในข้อมูลตั้งต้น พร้อมช่วงและค่าเฉลี่ยของขนาดแถวทั้งตาราง

ส่วนคงที่ 19 B เท่ากันทุกแถว ส่วนที่ทำให้แถวยาวไม่เท่ากันมีอย่างเดียวคือชื่อร้าน ซึ่งเป็นข้อความไทยเข้ารหัส UTF-8

ชื่อร้าน	ขนาดชื่อ	ขนาดแถว
ครัวสุขใจ	27 B	46 B
ครัวคุณแม่	30 B	49 B
ชาบูบ้านนา	30 B	49 B
ลาบเป็ดอุดร	33 B	52 B
ส้มตำแซ่บนัว	36 B	55 B
พิซซ่าลุงหมี	36 B	55 B
กาแฟดริปซอยเก้า	45 B	64 B
ข้าวหมูแดงเจ๊หมวย	51 B	70 B
ข้าวมันไก่ประตูน้ำ	54 B	73 B
ก๋วยเตี๋ยวเรือรังสิต	60 B	79 B

อักษรไทยหนึ่งตัวกิน 3 B ใน UTF-8 ชื่อที่คนอ่านว่ายาวกว่ากันไม่กี่พยางค์จึงต่างกันหลายสิบ byte

ทั้งตาราง 200,000 แถวได้แถวเล็กสุด 46 B ใหญ่สุด 79 B และเฉลี่ย 59.99 B

ถ้านับค่า slot 4 B ที่แต่ละแถวต้องจ่ายเข้าไปด้วย ค่าเฉลี่ยขยับเป็น 63.99 B ตัวเลขตัวหลังนี่แหละที่กำหนดว่าหนึ่งหน้าใส่ได้กี่แถว

เขียน 200,000 แถวลง heap file

ตัวอ่านหน้าที่นับจำนวนครั้งไว้เอง วิธีปิดหน้าเดิมแล้วเปิดหน้าใหม่ และรูปร่างของ file ที่ได้ออกมา

heap file คือ file ที่เก็บแถวเรียงตามลำดับที่เขียนเข้าไป ไม่ได้เรียงตามคีย์ใดๆ ทั้งสิ้น

ก่อนจะเขียนได้ต้องมีตัวอ่านเขียนหน้าก่อน และตัวนี้คือเครื่องวัดของทั้งคอร์ส

class Pager:
    def __init__(self, path, mode="r+b"):
        self.f = open(path, mode)
        self.reads = 0

    def read_page(self, pageno):
        self.f.seek(pageno * PAGE_SIZE)
        self.reads += 1
        return bytearray(self.f.read(PAGE_SIZE))

    def write_page(self, pageno, page):
        self.f.seek(pageno * PAGE_SIZE)
        self.f.write(page)

    def page_count(self):
        self.f.seek(0, 2)
        return self.f.tell() // PAGE_SIZE

self.reads คือหน่วยที่บทที่แล้วตกลงไว้ ในรูปของตัวแปรจริงหนึ่งตัว ทุกครั้งที่มีใครขอหนึ่งหน้า ตัวเลขนี้เพิ่มหนึ่ง

Pager.reads ไม่ใช่จำนวน I/O ที่ลงไปถึงตัว disk

มันนับจำนวนครั้งที่มีการเรียกอ่านหนึ่งหน้าเท่านั้น file ขนาด 12.9 MB นี้อยู่ใน page cache ของ OS แทบทั้งหมด การอ่านส่วนใหญ่จึงไม่ได้ลงไปถึงตัว disk เลย

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

Pager ตัวนี้ยังไม่มี buffer pool ด้วย ขอหน้าเดิมซ้ำสิบครั้งก็นับสิบครั้ง ตัวชี้แถวหนึ่งตัวจึงเท่ากับหนึ่งหน้าเสมอ

การเขียนทั้งตารางคือการวนแทรกจนหน้าเต็ม แล้วปิดหน้าเดิมเปิดหน้าใหม่

def build_heap(path, rows):
    """คืน dict: oid -> rid=(pageno, slot)"""
    pg = Pager(path, "w+b")
    page, pno, rid = new_page(), 0, {}
    for r in rows:
        row = encode(*r)
        s = insert(page, row)
        if s is None:
            pg.write_page(pno, page)
            page, pno = new_page(), pno + 1
            s = insert(page, row)
        rid[r[0]] = (pno, s)
    pg.write_page(pno, page)
    pg.f.flush()
    return pg, rid

if s is None เป็นบรรทัดที่ควรหยุดอ่านสักครู่ เพราะเขียนเป็น if not s ก็ผ่านสายตาคนรีวิวได้ง่ายมาก

insert คืนหมายเลข slot และแถวแรกของหน้าได้หมายเลข 0 เสมอ ซึ่ง Python ตีความว่าเป็นเท็จ เงื่อนไขที่เขียนผิดจึงเข้าใจว่าแถวแรกสุดของทั้ง file ใส่ไม่ลง มันปิดหน้าแรกทั้งที่มีอยู่แถวเดียว แล้วเขียนแถวนั้นซ้ำลงหน้าถัดไป

สิ่งที่ทำให้บั๊กนี้เงียบคือมันเกิดครั้งเดียวจบ s ตัวใหม่ที่ได้หลังเปิดหน้าไม่ถูกทดสอบซ้ำ แถวถัดไปได้หมายเลข slot 1 ซึ่งเป็นจริง เงื่อนไขจึงไม่เข้าอีกเลยทั้ง file ส่วนตอนที่หน้าเต็มจริง insert คืน None ซึ่งเป็นเท็จอยู่แล้ว พฤติกรรมตรงนั้นยังถูก

ผลคือ heap ที่เกินมาหนึ่งหน้า และเดินอ่านกลับได้แถวเกินมาหนึ่งแถว ไม่มี exception ไม่มี stack trace มีแต่ตัวนับที่เกินไปทีละหนึ่ง กับการตรวจ histogram สถานะท้ายบทที่จะไม่ตรงกับของ fixture.py อยู่หนึ่งแถว

รันจาก folder ทำงานด้านนอกเหมือนบทที่แล้ว

python3 qe/heapfile.py

สองค่าที่ต้องตรงก่อนอย่างอื่นคือจำนวนหน้า 3,153 หน้า กับแถวที่อ่านกลับมาได้ 200,000 แถว ถ้าสองค่านี้ตรง ตัวเลขที่เหลือทั้งบทจะตรงตามไปด้วย

เดินอ่านกลับทั้ง file แล้ววัดรูปร่างของมันได้แบบนี้

ค่า	ผลที่วัดได้
จำนวนหน้าทั้งหมด	3,153 หน้า
ขนาด file	12,914,688 B
แถวที่อ่านกลับมาได้	200,000 แถว
แถวต่อหน้า เฉลี่ย	63.43 แถว
แถวต่อหน้า น้อยสุด / มากสุด (ไม่นับหน้าสุดท้าย)	58 / 68 แถว
หน้าสุดท้าย	36 แถว
ที่ว่างที่เหลือในหน้าที่เขียนเต็มแล้ว	น้อยสุด 0 B / มากสุด 82 B / เฉลี่ย 32.50 B

แถวต่อหน้าแกว่งจาก 58 ถึง 68 ไม่ได้แกว่งเพราะอัลกอริทึมการแพ็กฉลาดบ้างไม่ฉลาดบ้าง อัลกอริทึมนี้ไม่มีทางเลือกอะไรเลย มันแทรกไปเรื่อยๆ จนใส่ไม่ลง

มันแกว่งเพราะชื่อร้านยาว 27 ถึง 60 byte ล้วนๆ หน้าที่บังเอิญได้ร้านชื่อสั้นมาเยอะก็ใส่ได้ 68 แถว หน้าที่ได้ร้านชื่อยาวก็ได้ 58 แถว

flowchart TD
    A["แถวถัดไปที่ต้องเขียน"] --> B{"ที่ว่างในหน้าปัจจุบัน<br/>พอสำหรับแถวบวกอีก 4 byte ไหม"}
    B -- "พอ" --> C["แทรกลงหน้าปัจจุบัน<br/>เพิ่มจำนวน slot ขึ้นหนึ่ง<br/>เลื่อนจุดเริ่มข้อมูลไปทางซ้าย"]
    C --> A
    B -- "ไม่พอ" --> D["เขียนหน้าปัจจุบันลง heap file<br/>ที่ว่างที่เหลือกลายเป็นหางหน้า"]
    D --> E["เปิดหน้าใหม่ แล้วแทรกแถวเดิมลงไป"]
    E --> A

คำบรรยายภาพ: เส้นทางของหนึ่งแถวตอนถูกเขียนลง heap file · เงื่อนไขที่ตัดสินมีข้อเดียวคือที่ว่างพอสำหรับตัวแถวบวกค่า slot อีก 4 byte หรือไม่ · ถ้าไม่พอ หน้าปัจจุบันถูกเขียนลง file ทั้งที่ยังเหลือที่ว่างอยู่ และที่ว่างก้อนนั้นคือหางหน้าที่บทนี้วัดสัดส่วนของมันในหัวข้อถัดไป

fill factor 99.19 % — overhead อยู่ที่แถว ไม่ใช่ที่หางหน้า

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

fill factor ของ heap นี้คือ 12,810,514 B ที่ถูกใช้จริง จาก 12,914,688 B ทั้ง file คิดเป็น 99.19 %

ตัวเลขตัวเดียวแบบนี้ไม่บอกอะไรเลยว่าอีก 0.81 % หายไปไหน และตรงนั้นคือส่วนที่น่าสนใจ

ส่วน	สัดส่วนของทั้ง file
ข้อมูลแถว	92.90 %
slot directory และ header	6.29 %
หางหน้าที่ใส่แถวถัดไปไม่ลง	0.81 %

หางหน้าคือสิ่งที่คนคาดว่าจะเสียมากที่สุด เพราะมันเห็นภาพง่าย ปิดหน้าทิ้งทั้งที่ยังเหลือที่ว่าง คูณด้วย 3,153 หน้า

แต่มันเป็นก้อนที่เล็กที่สุดในสามส่วน แค่ 0.81 % เพราะแถวเฉลี่ย 59.99 B เล็กเมื่อเทียบกับหน้า 4096 B หางที่เหลือของหน้าที่เขียนเต็มแล้วจึงเฉลี่ยแค่ 32.50 B

สิ่งที่กินจริงคือ slot directory ซึ่งคิด 4 B ต่อแถว รวมกับ header อีกหน้าละ 4 B ได้ 6.29 % ของทั้ง file แพงกว่าหางหน้าเกือบ 8 เท่า

overhead ของ heap เป็นค่าต่อแถว ไม่ใช่ค่าต่อหน้า

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

ผลวัดบอกตรงข้าม 0.81 % อยู่ที่ขอบของหน้า ส่วน 6.29 % อยู่ที่ slot ที่ทุกแถวต้องจ่าย บวก header อีกหน้าละ 4 B ซึ่งเป็นก้อนที่เล็กกว่ามาก

ผลตามมาคือการลด overhead ของ heap ต้องไปลดที่ขนาดของ slot หรือจำนวนแถว ไม่ใช่ที่การจัดหน้าให้เต็มขึ้น และมันจะกลับมาอีกครั้งตอนบท 3 ตอนคิดว่ารายการหนึ่งรายการในใบของ B+tree ควรใหญ่แค่ไหน

โครงสร้างทั้งหมดนี้มีราคาที่วัดได้ ถ้าเทแถวดิบต่อกันโดยไม่แบ่งหน้าเลย 200,000 แถวจะใช้ 2,930 หน้า

heap ใช้ 3,153 หน้า มากกว่ากัน 223 หน้า คิดเป็น 7.61 % และสิ่งที่ได้กลับมาคือความสามารถอย่างเดียว คือระบุตำแหน่งของแถวใดแถวหนึ่งแล้วกระโดดไปอ่านได้เลย

การเทแถวดิบต่อกันไม่ใช่ทางเลือกจริง

ในกองที่เทต่อกันไม่มี header ไม่มี slot และไม่มีขอบเขตของหน้า การจะรู้ว่าแถวที่ต้องการเริ่มที่ byte ไหนต้องไล่อ่านจาก byte แรกของ file มาเรื่อยๆ

แปลว่ามันตอบได้แค่คำถามเดียวคืออ่านทั้งตาราง และตอบคำถาม “ขอแถวนี้แถวเดียว” ไม่ได้เลย

การเทียบนี้จึงมีไว้ตีราคาโครงสร้างเท่านั้น ไม่ได้เสนอว่ามันเป็นทางเลือกที่ใช้แทนกันได้

อ่านเรียง เทียบ หยิบด้วย record id

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

หน่วยของหัวข้อนี้คือข้อตกลงของบทที่แล้ว อ่านหนึ่งหน้านับเป็นหนึ่งครั้ง และหน้าที่อ่านเรียงกับหน้าที่หยิบแบบสุ่มถูกนับเท่ากันทั้งคู่

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

การอ่านสองแบบใช้ Pager ตัวเดียวกันและนับด้วยตัวแปร reads ตัวเดียวกัน ต่างกันแค่ลำดับของหน้าที่ขอ

การอ่าน	หน้าที่แตะ	แถวที่ได้	หน้าที่แตะต่อหนึ่งแถว
เรียงทั้งตาราง	3,153	200,000	0.01577
หยิบสุ่มด้วย record id	1,000	1,000	1.00000

การอ่านเรียงหยิบได้เฉลี่ย 63.43 แถวต่อหนึ่งหน้าที่แตะ ส่วนการหยิบด้วย record id ยกหน้ามาทั้งหน้าเพื่อแถวเดียว

0.50 % ของแถว จ่ายไป 31.72 % ของราคาการอ่านทั้งตาราง

1,000 แถวที่หยิบมาคิดเป็น 0.50 % ของตาราง

1,000 หน้าที่จ่ายไปคิดเป็น 31.72 % ของราคาการอ่านทั้งตาราง

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

ตัวเลข 1,000 หน้าเป็นขอบบนของกรณีที่ cache อะไรไม่ได้เลย เพราะ Pager ยังไม่มี buffer pool

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

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

อีกอย่างที่ค่า 1.00000 ไม่ได้คิดราคาให้คือการรู้ว่า record id ของแถวที่ต้องการคืออะไร บทนี้ได้มันมาฟรีจาก dict ที่ build_heap คืนกลับมา ซึ่งลอยอยู่ในหน่วยความจำล้วนๆ และเป็นราคาที่บทหน้าต้องจ่ายจริง

สองแบบนี้ไม่ได้มีแบบไหนถูกกว่าเสมอ มันมีจุดที่ราคาเท่ากัน

ภายใต้ขอบบนเดียวกันนี้ คือหนึ่งหน้าต่อหนึ่งแถว จุดนั้นอยู่ที่ 3,153 แถว หรือ 1.58 % ของตาราง หยิบน้อยกว่านั้นการไล่ตาม record id ถูกกว่า มากกว่านั้นการอ่านทั้งตารางถูกกว่า ถ้าคิด cache เข้าไปด้วย จุดนี้จะขยับสูงขึ้น

1.58 % ต่ำกว่าที่คนส่วนใหญ่เดามาก และเหตุผลอยู่ในตารางข้างบนแล้ว คือหน้าที่แตะต่อหนึ่งแถวของการหยิบด้วย record id คือ 1.00000 ขณะที่ของการอ่านเรียงคือ 0.01577

คำถามเดียว กับ 3,153 หน้าที่ต้องอ่าน

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

ถามคำถามที่ใครก็ถาม ร้านครัวคุณแม่มีกี่ออเดอร์

คำตอบคือ 11,934 ออเดอร์ คิดเป็น 5.97 % ของตาราง และวิธีเดียวที่ heap ตอบได้คืออ่านทั้ง 3,153 หน้าแล้วนับ

ราคานี้ไม่ขึ้นกับคำตอบเลย ถ้าคำตอบมีแถวเดียวก็ 3,153 หน้า ถ้ามีสองแสนแถวก็ 3,153 หน้า เพราะ heap เก็บแถวเรียงตามลำดับที่เขียนเข้าไป ไม่ได้เรียงตามชื่อร้าน

คำถามที่ตามมาทันทีคือ ถ้ารู้ล่วงหน้าว่าหน้าไหนไม่มีคำตอบ จะประหยัดได้เท่าไร

ค่า	ผลที่วัดได้
หน้าที่ต้องแตะ	3,153 หน้า
หน้าที่มีคำตอบอยู่จริง	3,079 หน้า (97.65 % ของ file)
หน้าที่อ่านมาแล้วทิ้งเปล่า	74 หน้า

แถวของร้านเดียวที่กินแค่ 5.97 % ของตาราง กระจายอยู่บน 97.65 % ของหน้า เพราะแถวถูกเขียนเรียงตามเวลาที่ออเดอร์เข้ามา ไม่ได้เขียนแยกตามร้าน

การกรองระดับหน้าจึงตัดงานทิ้งได้ 74 หน้าจาก 3,153 หน้า ซึ่งแทบไม่ต่างจากไม่กรองเลย

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

ก่อนจะไปต่อ มีการตรวจหนึ่งอย่างที่ต้องผ่านก่อน คือจำนวนแถวรายสถานะที่นับได้จากการเดิน heap ต้องตรงกับที่ fixture.py พิมพ์ออกมาทุกค่า

status	จำนวนแถวที่นับได้จาก heap
Placed	199
Confirmed	383
Preparing	583
PickedUp	806
Delivered	163,733
Rejected	13,165
Cancelled	21,131

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

สิ่งที่ 99.19 % ไม่ได้บอก

เงื่อนไขที่ทำให้ fill factor ของบทนี้สูงขนาดนี้ และข้อจำกัดที่ทำให้ต้องมีบทถัดไป

99.19 % เป็นค่าของ heap ที่เขียนต่อท้ายอย่างเดียว ไม่เคยลบและไม่เคยแก้แถวสักครั้ง

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

ตัวเลขที่วงสนทนามักยกมาคือหน้าเต็มราวๆ 70 % ซึ่งเป็นค่าหลังผ่านการใช้งานมาแล้ว ทั้งสองตัวเลขจริงพร้อมกันได้ เพราะมันวัดคนละช่วงชีวิตของ file เดียวกัน

ทุกตัวเลขในบทนี้จึงติดเงื่อนไขเดียวกันหมด คือเป็นตัวเลขของข้อมูลชุดนี้ บน heap ที่ยังไม่เคยถูกลบหรือแก้ และวัดโดยไม่มี buffer pool

สิ่งที่ยกไปใช้ต่อได้คือวิธีวัดกับข้อสรุปเชิงโครงสร้าง เช่น overhead อยู่ที่แถว หรือจุดคุ้มทุนของการไล่หยิบด้วย record id ต่ำกว่าที่คนเดา ไม่ใช่ตัวเลข 99.19 % หรือ 1.58 % ที่ยกไปแปะกับตารางอื่นได้ทันที

สิ่งที่ขาดคือโครงสร้างที่ชี้ลงถึงแถวได้ตรงๆ โดยไม่ต้องอ่านทั้งตารางก่อน และมันต้องอยู่บนหน้าขนาด 4096 byte แบบเดียวกันนี้ ไม่ใช่ dict ที่ลอยอยู่ในหน่วยความจำซึ่งจะหายไปพร้อม process

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

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

The SQLite Database File Format (ตรวจ 2026-08-11) — รูปแบบ file ของจริงที่จัดหน้าด้วยแนวคิดเดียวกับที่บทนี้สร้าง คือ cell pointer array ที่โตจากต้นหน้า กับเนื้อข้อมูลที่โตสวนกลับมาจากท้ายหน้า ส่วนขนาดหน้า 4096 byte ที่คอร์สนี้ใช้ตรงกับค่าปริยายของ SQLite พอดี บท capstone จึงวางหน่วยของสองฝั่งทาบกันได้
Alex Petrov, Database Internals, O’Reilly 2019, ISBN 978-1-492-04034-7 — บทที่ 3 File Formats ว่าด้วย slotted page กับการจัดที่ว่างในหน้า เป็นการอ่านต่อสำหรับเรื่องที่บทนี้ตัดออก เช่น overflow page และการจัดที่ว่างใหม่หลังลบแถว

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

ข้อ 1 / 3

heap file ของบทนี้มี fill factor 99.19 % ถ้าแยกเนื้อที่ส่วนที่ไม่ใช่ข้อมูลแถวออกเป็นสองก้อน คือหางหน้าที่ใส่แถวถัดไปไม่ลง กับ slot directory ที่คิด 4 B ต่อแถว บวก header ของทุกหน้า ก้อนไหนกินที่มากกว่ากัน

หน้า (page) — ทำไม "อ่าน​หนึ่ง​แถว" ถึง​ไม่มี​อยู่​จริง

ชั้น​เก็บ​ข้อมูล​ไม่​เคย​ส่ง “หนึ่ง​แถว” มา​ให้

slotted page — สอง​ด้าน​ที่​โต​เข้าหา​กัน​ใน​หน้า​เดียว

ขนาด​แถว​จริง — ชื่อ​ร้าน​เป็น​ตัว​กำหนด

เขียน 200,000 แถว​ลง heap file

fill factor 99.19 % — overhead อยู่​ที่​แถว ไม่ใช่​ที่​หาง​หน้า

อ่าน​เรียง เทียบ หยิบ​ด้วย record id

คำถาม​เดียว กับ 3,153 หน้าที่​ต้อง​อ่าน

สิ่ง​ที่ 99.19 % ไม่​ได้​บอก