เรียงตาม restaurant แล้ว zone map ของ placed_at เหลือข้าม 5 กลุ่ม ไม่ใช่ 0

บทที่ 6 วัดไว้ว่า zone map ตัดกลุ่มทิ้งได้ก็ต่อเมื่อค่าใน column นั้นเดินตามลำดับที่เขียนแถวลงคลัง คำถามถัดไปจึงเขียนตัวมันเองว่า แล้วถ้าเปลี่ยนลำดับที่เขียนล่ะ

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

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

คำทำนายของผู้เขียน probe ก่อนวัดคือ เรียงตาม restaurant แล้ว zone map ของ placed_at จะข้ามได้ 0 กลุ่ม ค่าที่วัดได้คือ 5 กลุ่ม และเหตุผลอยู่ในสองบรรทัดของ Python

📦 ตัวเลขทุกตัวในบทนี้รันเองได้ ไม่ต้องมี Docker และไม่ต้องต่อเน็ต

สั่ง python3 scripts/column-store/probe.py ได้เลย มันใช้ Python 3 กับ standard library ล้วน ไม่ต้องติดตั้งอะไรก่อน และไม่มี container ให้เก็บกวาดทีหลัง

ค่าที่วัดได้ทุกตัวที่บทนี้พิมพ์มีคีย์ของตัวเองอยู่ใน scripts/column-store/expected/column-store.txt และชื่อคีย์นั้นเขียนกำกับไว้ในทุกตาราง ค่าของครึ่งแรกอยู่ในหมวด 7_เรียงแล้วได้อย่างเสียอย่าง ส่วนค่าของครึ่งหลังอยู่ในหมวด 8_ขนาด_row_group

zone map ตัวหนึ่งตื่นขึ้น อีกตัวทรุดลง แต่ไม่ตาย

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

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

ทรงที่วัด	คีย์ในผลของ probe	กลุ่มที่ข้ามได้
เรียงตาม `placed_at` · ถามช่วงเวลา	`เรียงตาม placed_at · กลุ่มที่ข้ามได้เมื่อถามช่วงเวลา`	19
เรียงตาม `restaurant` · ถามช่วงเวลา	`เรียงตาม restaurant · กลุ่มที่ข้ามได้เมื่อถามช่วงเวลา`	5
เรียงตาม `placed_at` · ถามร้าน	`เรียงตาม placed_at · กลุ่มที่ข้ามได้เมื่อถามร้าน`	0
เรียงตาม `restaurant` · ถามร้าน	`เรียงตาม restaurant · กลุ่มที่ข้ามได้เมื่อถามร้าน`	18

ทั้งสี่แถวนับจากคลังที่มี 20 กลุ่มเท่ากัน ตามคีย์ กลุ่มทั้งหมด ในหมวดเดียวกัน

แถวที่สามกับแถวที่สี่คือฝั่งที่ได้มา คำถามที่ถามร้านเคยข้ามไม่ได้เลย แล้วกลายเป็นข้ามได้ 18 จาก 20 กลุ่ม นั่นคือสิ่งที่การเลือก sort key ซื้อมา

แถวที่สองคือฝั่งที่จ่ายไป และมันคือแถวที่หักล้างคำทำนาย 5 ไม่ใช่ 0 zone map ของ placed_at ทรุดลงจริง แต่มันยังทำงานอยู่

sort ของ Python เสถียร เวลาจึงยังเรียงอยู่ข้างในบล็อกของแต่ละร้าน

กลไกที่ทำให้ตัวเลขเป็น 5 แทนที่จะเป็น 0 และ probe อ่านมันออกมาเป็นบูลีนของตัวเอง

การเรียงใหม่ในบทนี้เป็นการเรียกฟังก์ชันเดียว และมันไม่ได้ระบุว่าจะทำอะไรกับแถวที่คีย์เท่ากัน

def order_by(rows, col):
    ix = COL_IX[col]
    return sorted(rows, key=lambda r: r[ix])

sorted ของ Python เป็น stable sort คือแถวที่คีย์เท่ากันยังรักษาลำดับเดิมไว้ แถวของร้านเดียวกันจึงเรียงตามเวลาต่อกันเหมือนเดิม เพราะลำดับเดิมของตารางเรียงตามเวลาอยู่แล้ว

probe ไม่ได้เชื่อเอกสารของ Python มันวัดข้อนี้จากแถวจริงแล้วเก็บผลไว้เป็นคีย์ของตัวเอง

    ixr, ixt = COL_IX["restaurant"], COL_IX["placed_at"]
    blocks_in_time_order = all(
        rows_by_rest[i][ixr] != rows_by_rest[i + 1][ixr]
        or rows_by_rest[i][ixt] <= rows_by_rest[i + 1][ixt]
        for i in range(len(rows_by_rest) - 1))

ทรงที่วัด	คีย์ในผลของ probe	ค่า
เวลายังเรียงอยู่ในบล็อกของแต่ละร้าน	`บล็อกของแต่ละร้านยังเรียงตามเวลาอยู่ (sort เสถียร)`	true
กลุ่มที่มีร้านเดียวล้วนหลังเรียงตามร้าน	`row group ที่มีร้านเดียวล้วน (เรียงตามร้าน)`	11

11 จาก 20 กลุ่มถือแถวของร้านเดียวล้วน กลุ่มเหล่านั้นจึงเป็นบล็อกที่เรียงตามเวลาทั้งก้อน และช่วง min ถึง max ของ placed_at ในกลุ่มนั้นเป็นช่วงเวลาที่ต่อเนื่อง ไม่ใช่ช่วงที่กินทั้งตาราง

คำทำนายที่บทนี้หักล้าง

คำทำนายที่เขียนไว้ก่อนวัดคือ เปลี่ยน sort key แล้ว zone map ของ column เดิมจะข้ามได้ 0 กลุ่ม เพราะทุกกลุ่มจะกินช่วงเวลาเกือบทั้งตารางเหมือนกันหมด

ค่าที่วัดได้คือ 5 ตามคีย์ เรียงตาม restaurant · กลุ่มที่ข้ามได้เมื่อถามช่วงเวลา

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

flowchart TB
  T["ตารางออเดอร์ใบเดิม · 20 row group เท่ากันทั้งสองฝั่ง"]
  T --> A["เรียงตาม placed_at · ลำดับที่เสาข้อมูลใช้อยู่"]
  T --> B["เรียงตาม restaurant · sort เสถียร เวลาจึงยังเรียงอยู่ในบล็อกของแต่ละร้าน"]
  A --> A1["ถามช่วงเวลา · ข้าม 19 กลุ่ม"]
  A --> A2["ถามร้าน · ข้าม 0 กลุ่ม"]
  B --> B1["ถามช่วงเวลา · ข้าม 5 กลุ่ม"]
  B --> B2["ถามร้าน · ข้าม 18 กลุ่ม"]

คำบรรยายภาพ: กิ่งซ้ายกับกิ่งขวาเป็นตารางใบเดียวกันและจำนวนกลุ่มเท่ากัน ต่างกันที่ลำดับ ที่เขียนแถวลงคลังอย่างเดียว ใบล่างทั้งสี่ใบคือกลุ่มที่ zone map ตัดทิ้งได้ และคู่ 19 กับ 5 บนคำถามช่วงเวลา เทียบกับคู่ 0 กับ 18 บนคำถามร้าน คือสิ่งที่บอกว่าการเรียงเป็นการย้าย ไม่ใช่การเพิ่ม

ราคาของการเรียงจ่ายที่ column ที่ไม่ได้ใช้เรียง

ตัวเลขที่เป็นไบต์สี่คู่ และสามคู่ในนั้นบวมขึ้นทั้งที่ไม่มีใครแตะการเข้ารหัสของมัน

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

ทรงที่วัด	คีย์ในผลของ probe	ไบต์
`placed_at` · delta · เรียงตามเวลา	`placed_at ไบต์ · delta · เรียงตามเวลา`	491,610
`placed_at` · delta · เรียงตามร้าน	`placed_at ไบต์ · delta · เรียงตามร้าน`	585,360
`id` · delta · เรียงตามเวลา	`id ไบต์ · delta · เรียงตามเวลา`	350,360
`id` · delta · เรียงตามร้าน	`id ไบต์ · delta · เรียงตามร้าน`	434,110
`placed_at` · bit packing · เรียงตามเวลา	`placed_at ไบต์ · bitpack · เรียงตามเวลา`	1,138,004
`placed_at` · bit packing · เรียงตามร้าน	`placed_at ไบต์ · bitpack · เรียงตามร้าน`	1,149,184
`restaurant` · bit packing · เรียงตามเวลา	`restaurant ไบต์ · bitpack · เรียงตามเวลา`	108,680
`restaurant` · bit packing · เรียงตามร้าน	`restaurant ไบต์ · bitpack · เรียงตามร้าน`	26,657

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

delta ของหมวดนี้คือแบบ frame of reference ตามชื่อที่ colstore.py:42 ตั้งไว้ คือเก็บส่วนต่าง จากค่าที่น้อยที่สุดของกลุ่ม id ในลำดับเดิมที่ตกอยู่ในกลุ่มเดียวกันจึงเป็นช่วงที่ต่อเนื่อง และระยะจากค่าน้อยสุดถึงค่ามากสุดแคบ พอเรียงใหม่ตามร้าน id ในกลุ่มเดียวกันกระจายทั้งตาราง ระยะนั้นกว้างขึ้น และตัวรหัสก็กว้างตาม

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

คลังใบเดียวจ่ายทั้งสองอย่างพร้อมกันไม่ได้ ถ้าอยากได้ 26,657 ไบต์ของแถวสุดท้าย ต้องรับ 585,360 ไบต์ของแถวที่สองไปด้วย

🔁 การเรียงในบทที่ 4 ไม่ใช่การเรียงในบทนี้

บทที่ 4 เรียงตาม status แล้ววัดผลที่เกิดกับ status เอง ส่วนบทนี้เรียงตาม restaurant แล้ววัดผลที่เกิดกับ column ที่ไม่ได้ถูกใช้เรียง

สองบทจึงตอบคนละคำถาม บทที่ 4 ตอบว่าการเรียงให้อะไรกับ sort key และบทนี้ตอบว่ามันเก็บเงิน ที่ไหน

ครึ่งหลัง — ขนาดของ row group ไม่มีจุดต่ำสุดตรงกลาง

ตะแกรงห้าค่าในหมวด 8_ขนาด_row_group และเส้นของฝั่ง query ที่ขึ้นตลอด

ขนาดของก้อนเป็นค่าตั้งที่ผู้สร้างคลังเลือกเอง คำทำนายที่สมเหตุสมผลคือมันมีค่าที่ดีที่สุด อยู่ตรงกลาง เพราะก้อนเล็กเกินไปก็มี metadata เยอะ ก้อนใหญ่เกินไปก็ตัดทิ้งไม่ได้

probe กวาดห้าค่าโดยเปลี่ยนขนาดก้อนอย่างเดียว ทุกอย่างที่เหลือเหมือนเดิมหมด

    sweep = {}
    for rg in SWEEP:
        st = build(f"sweep-{rg}", rows, rg, all_enc(BITPACK))
        z = zone_query(st, "placed_at", DAY_LO, DAY_HI, extra=("total",))
        pp, _ = point_read(st, one_i)

ฝั่งของ query วัดห้าอย่าง ทุกอย่างอ่านจากคีย์ของตัวเองในตะแกรงเดียวกัน

แถวต่อก้อน	`row group`	`กลุ่มที่ข้าม`	`แถวที่สแกน`	`หน้าที่แตะ_column เงื่อนไข`	`หน้าที่แตะ_สอง column`	`หน้าที่แตะเมื่อหยิบหนึ่งแถวทั้งแถว`
500	400	397	1,500	3	5	7
2,000	100	99	2,000	3	6	15
10,000	20	19	10,000	15	29	42
25,000	8	7	25,000	37	72	86
50,000	4	3	50,000	74	142	154

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

เหตุผลตรงไปตรงมา ก้อนเล็กแปลว่าหน่วยที่ตัดทิ้งได้เล็กลง คำถามวันเดียวจึงลากแถวที่ไม่เกี่ยวข้อง ติดมาน้อยลง คือ 1,500 แถวที่ก้อนละ 500 เทียบ 50,000 แถวที่ก้อนละ 50,000

แล้วราคาไปโผล่ที่ขนาดของคลัง

ตัวเลขฝั่งเก็บสี่ตัวจากตะแกรงเดียวกัน และมันเดินสวนทางกับตารางข้างบนทุกแถว

แถวต่อก้อน	`ไบต์ทั้งคลัง`	`หน้าทั้งคลัง`	`ไบต์ที่เป็น dictionary`	`ไบต์ metadata (footer)`
500	4,406,245	1,079	3,289,565	106,448
2,000	4,224,327	1,034	2,938,527	26,648
10,000	4,038,792	989	2,536,632	5,368
25,000	3,982,336	974	2,406,472	2,176
50,000	3,977,860	973	2,327,428	1,112

ตัวที่โตคือ dictionary ทุกก้อนถือ dictionary ใบของตัวเอง ก้อนละ 500 แถวจึงคัดลอกรายการ ค่าที่ไม่ซ้ำซ้ำใหม่ 400 รอบ ตามคีย์ row group ของแถวแรก

ไบต์ที่เป็น dictionary ที่ 3,289,565 ในแถวแรก เทียบกับ 2,327,428 ในแถวสุดท้าย คือส่วนที่ผู้อ่านบทที่ 3 คาดไว้ได้ เพราะบทนั้นวัดไว้แล้วว่าขอบเขตของกลุ่มเป็นตัวตัดสิน

ค่าของคีย์ ไบต์ metadata (footer) สองปลายของตะแกรง และกลไกที่ทำให้มันโต

metadata ท้ายคลังที่ถือ min กับ max และตำแหน่งของทุก column chunk เรียกว่า footer มันคือที่ที่ zone map อยู่จริง และเป็นสิ่งที่ query ต้องอ่านก่อนตัดสินใจข้ามกลุ่มไหน

def footer_bytes(kind, metas):
    """ไบต์ของ footer ถ้าเขียนลง file จริง · off,len,n,ndict,nruns u32 + bits,enc u8 + min,max"""
    total = 0
    for m in metas:
        total += 4 * 5 + 1 + 1                       # off,len,n,ndict,nruns + bits + enc

column ที่เป็นจำนวนเต็มสี่ตัว จ่าย metadata เท่ากันทุกก้อน ไม่ว่าข้างในก้อนนั้นจะมีกี่แถว ส่วนสอง column ที่เป็นสตริงจ่ายไม่เท่ากัน เพราะ colstore.py:295 บวกความยาวของ ค่า min กับ max เข้าไปด้วย · จำนวนก้อนจึงเป็นตัวคูณที่เกือบตรง ไม่ใช่ตรงเป๊ะ

ไบต์ metadata (footer) อ่านได้ 1,112 ที่ก้อนละ 50,000 แถว และ 106,448 ที่ก้อนละ 500 แถว ในตะแกรงเดียวกัน

นี่คือของที่ตำราเรียกว่าราคาของก้อนเล็ก และมันมีจริง แต่มันไม่ได้ทำให้เกิดจุดต่ำสุดตรงกลาง เพราะฝั่ง query ก็ดีขึ้นเรื่อยๆ ในทิศเดียวกันจนสุดตะแกรง

คำถามที่ถูก ไม่ใช่ขนาดไหนดีที่สุด แต่เป็นจะจ่ายที่ตัววัดไหน

คีย์สามตัวปิดท้ายหมวด 8_ขนาด_row_group และตัวที่สามเป็นบูลีนที่ตอบคำถามของบทนี้ตรงๆ

probe ไม่ปล่อยให้ผู้อ่านสรุปเอง มันเลือกผู้ชนะของแต่ละตัววัดแล้วเก็บไว้เป็นคีย์

คำถาม	คีย์ในผลของ probe	ค่า
ขนาดที่ query เลือกสรรอ่านน้อยที่สุด	`row group ที่ query เลือกสรร อ่านน้อยที่สุด`	500
ขนาดที่คลังทั้งใบเล็กที่สุด	`row group ที่คลังเล็กที่สุด`	50000
สองอันนี้เป็นอันเดียวกันไหม	`สองอันนี้เป็นอันเดียวกัน`	false

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

ถ้าปริมาณที่เก็บเป็นข้อจำกัด ก้อนใหญ่คือคำตอบ และคุณจ่ายด้วยหน้าที่แตะทุกคำถาม
ถ้าคำถามเลือกสรรและต้องแตะหน้าน้อย ก้อนเล็กคือคำตอบ และคุณจ่ายด้วย dictionary ที่ถูกคัดลอกซ้ำ กับ footer ที่โตขึ้น

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

คำถามที่บทนี้ทิ้งไว้

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

ช่องสุดท้ายของตารางฝั่ง query คือ หน้าที่แตะเมื่อหยิบหนึ่งแถวทั้งแถว และมันขยับจาก 7 ถึง 154 ตลอดตะแกรง

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

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

Python — Sorting Techniques (เข้าถึง 2026-09-10) — ที่มาของข้อที่ว่า sorted รักษาลำดับเดิมของแถวที่คีย์เท่ากัน · probe ไม่ได้เชื่อข้อนี้เฉยๆ มันวัดจากแถวจริงที่ probe.py:412 แล้วเก็บผลเป็นคีย์
Apache Parquet — Metadata (เข้าถึง 2026-09-10) — ที่มาของกลไกที่ว่า min กับ max ของทุก column chunk อยู่ใน metadata ท้ายคลัง · ColumnMetaData ถือ Statistics ที่มี min_value กับ max_value · ดึงหน้า File Format มาอ่านแล้วไม่มีคำว่า statistics min_value หรือ max_value เลย เพื่อให้ข้ามทั้งก้อนได้โดยไม่ต้องอ่านข้างใน · อ้างในฐานะรูปแบบ ไม่ใช่ในฐานะของที่วัด และ คลังของคอร์สนี้ไม่ใช่ Parquet
ตัวเลขทุกตัวในบทนี้มาจาก python3 scripts/column-store/probe.py ซึ่งสร้างคลังขึ้นใหม่ ทุกรอบจาก fixture.py ของคอร์สที่ 26 · ค่าที่ตรึงไว้อยู่ที่ scripts/column-store/expected/column-store.txt หมวด 7_เรียงแล้วได้อย่างเสียอย่าง และหมวด 8_ขนาด_row_group
ทรงของการเรียงอยู่ที่ scripts/column-store/colstore.py บรรทัดที่ 466 และทรงของ footer อยู่ที่บรรทัดที่ 287 · คอร์สนี้ไม่แก้อะไรใน scripts/query-engine/qe/ แม้แต่ byte เดียว

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

ข้อ 1 / 3

เรียงตารางใหม่ตาม restaurant แล้ว คำถามช่วงเวลาข้าม row group ได้กี่กลุ่ม

เรียง​ตาม restaurant แล้ว zone map ของ placed_at เหลือ​ข้าม 5 กลุ่ม ไม่ใช่ 0

zone map ตัว​หนึ่ง​ตื่น​ขึ้น อีก​ตัว​ทรุด​ลง แต่​ไม่​ตาย

sort ของ Python เสถียร เวลา​จึง​ยัง​เรียง​อยู่​ข้าง​ใน​บล็อก​ของ​แต่ละ​ร้าน

ราคา​ของ​การ​เรียง​จ่าย​ที่ column ที่​ไม่​ได้​ใช้​เรียง

ครึ่ง​หลัง — ขนาด​ของ row group ไม่มี​จุด​ต่ำ​สุด​ตรง​กลาง

แล้ว​ราคา​ไป​โผล่​ที่​ขนาด​ของ​คลัง

footer เป็น​ราคา​ที่​มอง​ไม่​เห็น จน​กระทั่ง​ก้อน​เล็ก​ลง

คำถาม​ที่​ถูก ไม่ใช่​ขนาด​ไหน​ดี​ที่สุด แต่​เป็น​จะ​จ่าย​ที่​ตัว​วัด​ไหน

คำถาม​ที่​บท​นี้​ทิ้ง​ไว้