ตัวรหัสของ status ลงเหลือ 3 บิตต่อค่า แล้วการเข้ารหัสที่ตำราจับคู่กับข้อมูลซ้ำๆ ก็แพ้มัน

บทที่ 3 จบลงที่ dictionary encoding ซึ่งแทนค่าด้วยตัวรหัส แล้วเขียนตัวรหัสนั้นลงคลัง บทนี้ถามคำถามถัดไป ตัวรหัสต้องกว้างหนึ่ง byte จริงไหม

status มีค่าที่ไม่ซ้ำเจ็ดค่า และค่าเดิมซ้ำต่อกันเป็นช่วงยาว ตำราจับคู่ข้อมูลรูปนี้กับ run-length encoding และผู้เขียน probe ก็ทำนายว่าทรงนั้นคือคำตอบ

การวัดตอบครึ่งเดียว RLE ชนะทรงที่ใช้ byte เต็มจริง ที่ 190,386 เทียบ 201,740 ไบต์ แต่มันแพ้การนับบิตล้วนๆ ที่ 76,740 ไบต์ บนข้อมูลชุดเดียวกัน

📦 ตัวเลขทุกตัวในบทนี้มาจากคีย์ของตัวเองใน expected/column-store.txt

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

ค่าที่บทนี้พิมพ์มาจากสี่หมวดของผลที่ probe พิมพ์ออกมา สองหมวดที่แบกบทคือ ### 5_bit_packing กับ ### 4_run_length_บน_status ส่วนอีกสองหมวดให้ค่าคนละตัว คือ ### 3_dict_เทียบ_raw ที่คีย์ ค่าที่ไม่ซ้ำมากสุดใน row group เดียว และ ### สนามแข่ง ที่คีย์ แถว · ทุกตารางเขียนชื่อคีย์กำกับไว้

ตัวเลขที่ไม่มีคีย์ บทนี้ไม่พิมพ์ อัตราส่วนระหว่างทรง RLE กับทรง bit packing ไม่มีคีย์ใน scripts/column-store/expected/column-store.txt บทนี้จึงวางไบต์ทั้งสองตัวลงไปแทน

ตัวรหัสไม่จำเป็นต้องกว้างหนึ่ง byte

สองการเข้ารหัสนี้สร้างรายการตัวรหัสชุดเดียวกัน แล้วเลือกความกว้างคนละแบบ

    elif enc in (DICT, BITPACK):
        vs = sorted(set(vals))
        ix = {v: i for i, v in enumerate(vs)}
        codes = [ix[v] for v in vals]
        db = dict_blob(vs, kind)
        if enc == DICT:
            w = 1 if len(vs) <= 256 else (2 if len(vs) <= 65536 else 4)
            fmt = {1: "<B", 2: "<H", 4: "<I"}[w]
            body = b"".join(struct.pack(fmt, c) for c in codes)
            bits = w * 8
            m["fixed_width"] = w
        else:
            bits = bits_for(len(vs))
            body = pack_bits(codes, bits)
            m["fixed_width"] = 0

กิ่งบนคือ dictionary encoding มันเลือก w เป็นจำนวน byte แล้วคูณแปด ความกว้างที่ได้ จึงปัดขึ้นเป็น byte เต็มเสมอ

กิ่งล่างคือ bit packing มันเรียก bits_for แล้วเขียนตัวรหัสต่อกันไปโดยไม่สนขอบของ byte ค่าที่ bits_for คืนมาเรียกว่า bit width และมันมาจากจำนวนค่าที่ไม่ซ้ำใน column chunk ก้อนนั้น

ที่วัด	หมวดในผลของ probe	คีย์	ค่า
`status` · bit packing	`### 5_bit_packing`	`บิตต่อค่า`	3
`status` · dictionary	`### 5_bit_packing`	`บิตต่อค่าของ dict (ไบต์เต็ม)`	8
`restaurant` · bit packing	`### 5_bit_packing`	`บิตต่อค่า`	4
`restaurant` · dictionary	`### 5_bit_packing`	`บิตต่อค่าของ dict (ไบต์เต็ม)`	8

ความกว้างสองค่านี้ตามจำนวนค่าที่ไม่ซ้ำที่บทที่ 3 วัดไว้ คือคีย์ ค่าที่ไม่ซ้ำมากสุดใน row group เดียว ในหมวด ### 3_dict_เทียบ_raw ซึ่งเป็น 7 สำหรับ status และ 10 สำหรับ restaurant

แยกไบต์ของ chunk ออกเป็นตัวรหัสกับ dictionary

เมื่อความกว้างลงมาถึงระดับนี้ ส่วนที่เหลือของ chunk ก็อ่านออกได้ว่าใครกินที่

probe แยกไบต์ของทรง bit packing ออกมาให้สองส่วน ส่วนแรกคือตัวรหัสของทุกแถว ส่วนที่สองคือ dictionary ที่แต่ละ row group ถือของตัวเอง

สองส่วนนี้บวกกันแล้วยังไม่เท่ากับไบต์ทั้ง column เพราะทุก chunk เขียนหัวของตัวเองเพิ่มด้วย ตามที่ CHUNK_HDR ใน colstore.py กำหนด

ที่วัด	หมวดในผลของ probe	คีย์	ไบต์
`status` · ส่วนที่เป็นตัวรหัส	`### 5_bit_packing`	`ไบต์ที่เป็นตัวรหัส`	75,000
`status` · ส่วนที่เป็น dictionary	`### 5_bit_packing`	`ไบต์ที่เป็น dictionary`	1,380
`restaurant` · ส่วนที่เป็นตัวรหัส	`### 5_bit_packing`	`ไบต์ที่เป็นตัวรหัส`	100,000
`restaurant` · ส่วนที่เป็น dictionary	`### 5_bit_packing`	`ไบต์ที่เป็น dictionary`	8,320

restaurant จ่ายค่าตัวรหัสมากกว่า status ทั้งที่แถวเท่ากัน เพราะความกว้างของมัน เป็น 4 บิต ไม่ใช่ 3 บิต ความกว้างจึงเป็นค่าที่การเข้ารหัสเลือกให้แต่ละ column chunk ไม่ใช่หนึ่ง byte ตายตัว

RLE บน status ตามที่เก็บอยู่ ชนะ dictionary แต่แพ้ bit packing

ทรงเดียวกับที่ตำราแนะนำ บนข้อมูลที่ตรงเงื่อนไขที่ตำราระบุ แล้วมันยังแพ้

run-length encoding เก็บค่าหนึ่งค่าพร้อมจำนวนครั้งที่มันซ้ำติดกัน ช่วงของค่าที่เหมือนกัน ติดกันหนึ่งช่วงเรียกว่าหนึ่ง run

    elif enc == RLE:
        vs = sorted(set(vals))
        ix = {v: i for i, v in enumerate(vs)}
        db = dict_blob(vs, kind)
        w = 1 if len(vs) <= 256 else (2 if len(vs) <= 65536 else 4)
        fmt = {1: "<B", 2: "<H", 4: "<I"}[w]
        runs = []
        cur = None
        cnt = 0
        for v in vals:
            c = ix[v]
            if c == cur and cnt < 65535:
                cnt += 1
            else:
                if cur is not None:
                    runs.append((cur, cnt))
                cur, cnt = c, 1
        if cur is not None:
            runs.append((cur, cnt))
        body = b"".join(struct.pack(fmt, c) + struct.pack("<H", k) for c, k in runs)

บรรทัดสุดท้ายคือทรงที่ตัดสินทุกอย่าง หนึ่ง run เขียนตัวรหัสหนึ่งตัวตามด้วยจำนวนครั้ง แบบ <H ค่าที่ RLE จ่ายจึงคิดต่อ run ไม่ใช่ต่อแถว

ทรงที่วัด	คีย์ในกลุ่ม `ตามที่เก็บ (เรียงตาม placed_at)`	ไบต์
เก็บสตริงตามที่มันเป็น	`raw`	1,985,792
dictionary encoding · ตัวรหัสไบต์เต็ม	`dict`	201,740
run-length encoding	`rle`	190,386
bit packing	`bitpack`	76,740

ทั้งสี่แถวมาจากหมวด ### 4_run_length_บน_status กลุ่ม ตามที่เก็บ (เรียงตาม placed_at) คือ status ในลำดับที่คลังเก็บมันไว้จริง ไม่ได้เรียงใหม่

คีย์ในกลุ่มเดียวกัน	ค่า
`rle หารด้วย dict`	0.9437
`rle เล็กกว่า dict`	true

ประโยคที่บทนี้หักล้าง

ประโยคที่พบทั่วไปคือ ข้อมูลที่ค่าซ้ำติดกันยาวๆ ให้ใช้ run-length encoding คำทำนายที่ตามมาคือ RLE คือทรงที่เล็กที่สุดของ status

ครึ่งแรกของประโยคจริงตามที่วัดได้ RLE เล็กกว่าทรง dict ตามคีย์ rle เล็กกว่า dict

คำทำนายที่ตามมาผิด ทรง rle ได้ 190,386 ไบต์ ส่วนทรง bitpack ได้ 76,740 ไบต์ บน status ชุดเดียวกันและลำดับเดียวกัน การนับบิตล้วนๆ ชนะการเข้ารหัสที่ตำราจับคู่ไว้กับข้อมูลรูปนี้

เหตุผลอยู่ที่จำนวน run เทียบจุดคุ้มทุนของมัน

RLE จ่ายต่อ run ทรงจึงคุ้มก็ต่อเมื่อ run น้อยพอ และที่นี่มันเฉียดเส้นนั้น

flowchart TB
  S["status · 200,000 แถว · ค่าที่ไม่ซ้ำ 7 ค่า"]
  S --> D["dictionary encoding · ตัวรหัสกว้าง 8 บิต · จ่ายต่อแถว · 201,740 ไบต์"]
  S --> R["run-length encoding · จ่ายต่อ run · 190,386 ไบต์"]
  S --> B["bit packing · ตัวรหัสกว้าง 3 บิต · จ่ายต่อแถว · 76,740 ไบต์"]
  R --> R1["จำนวน run ที่วัดได้ · 62,882"]
  R --> R2["จุดคุ้มทุนของ run ที่ 3 ไบต์ต่อ run · 66,666"]

คำบรรยายภาพ: สามทรงบน status ชุดเดียวกัน กิ่งกลางจ่ายต่อ run ส่วนอีกสองกิ่งจ่ายต่อแถว สองใบล่างคือค่าที่ตัดสินกิ่งกลาง คือจำนวน run ที่วัดได้ เทียบจุดคุ้มทุนที่ทรงนี้ต้องอยู่ใต้มัน

ที่วัด	คีย์ในกลุ่ม `ตามที่เก็บ (เรียงตาม placed_at)`	ค่า
จำนวน run ของทั้ง column	`จำนวน run`	62,882
จำนวน run ของ row group ก้อนแรก	`run ต่อ row group`	3046
เส้นที่ทรงนี้ต้องอยู่ใต้	`จุดคุ้มทุนของ run (ไบต์ต่อ run = 3)`	66,666

62,882 อยู่ใต้ 66,666 แค่นิดเดียว RLE จึงชนะทรง dict แบบเฉียดฉิว ตามคีย์ rle หารด้วย dict ที่ 0.9437

ส่วน bit packing ไม่มีค่าใช้จ่ายต่อ run เลย มันจ่ายความกว้างเท่าเดิมทุกแถว เส้นจุดคุ้มทุนของ RLE จึงไม่ใช่เส้นที่ bit packing ต้องข้าม

เรียงตาม status แล้ว run ยุบ แต่ bit packing ก็เล็กลงด้วย

ตรงนี้คือที่ที่การอ่านผิดเกิดง่ายที่สุด เพราะการเรียงช่วยทั้งสองทรง ไม่ใช่ช่วยเฉพาะ RLE

probe สร้างคลังใบที่สองจากแถวชุดเดิม โดยเรียงตาม status ก่อนเขียน แล้ววัดทั้งสี่ทรงซ้ำ ผลอยู่ในกลุ่ม เรียงตาม status แล้ว ของหมวดเดียวกัน

คีย์	`ตามที่เก็บ (เรียงตาม placed_at)`	`เรียงตาม status แล้ว`
`จำนวน run`	62,882	26
`run ต่อ row group` ก้อนแรก	3046	1
`rle`	190,386 ไบต์	772 ไบต์
`bitpack`	76,740 ไบต์	29,444 ไบต์
`dict`	201,740 ไบต์	200,694 ไบต์
`rle หารด้วย dict`	0.9437	0.0038

คีย์ของหมวด	ค่า
`จำนวน run ลดลงกี่เท่าเมื่อเรียง`	2418.5

RLE ได้ประโยชน์มากที่สุดจากการเรียง นั่นคือข้อที่คาดไว้ได้ และตัวเลขก็ยืนยัน

ข้อที่คาดไว้ไม่ได้อยู่ที่แถว bitpack ทรงที่ไม่มีแนวคิดเรื่อง run อยู่ในตัวเลย ก็ลงจาก 76,740 เหลือ 29,444 ไบต์ในการเรียงชุดเดียวกัน

ทำไม bit packing ถึงเล็กลงทั้งที่มันไม่รู้จัก run

ความกว้างของ bit packing เป็นค่าต่อ row group ตามที่หัวข้อแรกวางไว้ มันมาจากจำนวน ค่าที่ไม่ซ้ำใน column chunk ก้อนนั้น ไม่ใช่ของทั้ง column

เรียงตาม status แล้ว ก้อนหนึ่งจึงถือค่าที่ไม่ซ้ำน้อยลง และความกว้างของก้อนนั้นก็ลดตาม

การอ่านที่ผิดคือ “การเรียงเป็นของที่ RLE ได้ประโยชน์อยู่ทรงเดียว” ตัวเลขที่วัดได้บอกว่า การเรียงเป็นสิ่งที่ทั้งสองทรงกินได้ และหลังเรียงแล้วทรงที่เล็กที่สุดก็ยังเปลี่ยนมือได้ ตามคีย์ rle ที่ 772 ไบต์ เทียบคีย์ bitpack ที่ 29,444 ไบต์

ราคาของการเรียง บทนี้ยังไม่ได้จ่าย

ตารางเรียงได้ลำดับเดียว และบทนี้วัดเฉพาะฝั่งที่ได้ ยังไม่ได้วัดฝั่งที่เสีย

ตัวเลขในหัวข้อที่แล้วเป็นตัวเลขของ status ตัวเดียว การเรียงใหม่ตามค่าของ column หนึ่ง เปลี่ยนขนาดของ column ตัวอื่นด้วย และบทนี้ไม่ได้วัดข้อนั้น

🔁 บทที่ต่อจากตรงนี้

บทที่ 3 — dictionary ที่ทำให้ใหญ่ขึ้น วางทรง dict ที่บทนี้ใช้เป็นเส้นเทียบ และวัดว่ามันจ่ายคืนที่ column ไหนบ้าง
บทที่ 7 — เรียงเพื่อ column หนึ่ง คือจ่ายให้อีก column วัดราคาที่การเรียงเรียกเก็บที่ column ซึ่งไม่ได้ถูกใช้เรียง · แต่มันเรียงตาม restaurant ไม่ใช่เรียงตาม status ของบทนี้ กลไกเดียวกัน คนละ sort key · ราคาของการเรียงตาม status ไม่มีทรงไหนใน probe วัดไว้

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

Apache Parquet — Encodings (เข้าถึง 2026-09-10) — หน้านี้ระบุว่าความกว้างของตัวรหัสถูก เก็บ ไว้หนึ่ง byte · มันไม่ได้บอกว่า ความกว้างนั้นคำนวณมาจากจำนวนสมาชิกของ dictionary ซึ่งเป็นสิ่งที่ colstore.py:50 ทำ · และรูปแบบนี้พับ bit packing ไว้ใน RLE hybrid ของมันเอง ส่วนการแยกสองอย่างออกจากกัน เป็นของคอร์สนี้ เพื่อให้วัดทีละอย่างได้
ตัวเลขทุกตัวในบทนี้มาจาก python3 scripts/column-store/probe.py หมวด ### 5_bit_packing หมวด ### 4_run_length_บน_status หมวด ### 3_dict_เทียบ_raw และหมวด ### สนามแข่ง · ค่าที่ตรึงไว้อยู่ที่ scripts/column-store/expected/column-store.txt
fence สองอันในบทนี้ยกมาจาก scripts/column-store/colstore.py บรรทัดที่ 155 และ 176 · คลังที่ probe วัดคือคลังที่ colstore.py เขียน ไม่ใช่ Parquet

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

ข้อ 1 / 3

ตัวรหัสของ status กว้างกี่บิตต่อค่า ในทรง bit packing เทียบกับทรง dictionary

ตัว​รหัส​ของ status ลง​เหลือ 3 บิต​ต่อ​ค่า แล้ว​การ​เข้า​รหัส​ที่​ตำรา​จับ​คู่​กับ​ข้อ​มูล​ซ้ำๆ ก็​แพ้​มัน

ตัว​รหัส​ไม่​จำเป็น​ต้อง​กว้าง​หนึ่ง byte

แยก​ไบต์​ของ chunk ออก​เป็น​ตัว​รหัส​กับ dictionary

RLE บน status ตาม​ที่​เก็บ​อยู่ ชนะ dictionary แต่​แพ้ bit packing

เหตุผล​อยู่​ที่​จำนวน run เทียบ​จุด​คุ้ม​ทุน​ของ​มัน

เรียง​ตาม status แล้ว run ยุบ แต่ bit packing ก็​เล็ก​ลง​ด้วย

ราคา​ของ​การ​เรียง บท​นี้​ยัง​ไม่​ได้​จ่าย