สถิติ — เดาจำนวนแถวโดยไม่รัน query

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

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

สองคำที่บทนี้ใช้ตลอดคือ selectivity กับ cardinality ตัวแรกคือสัดส่วนของแถวที่ผ่านเงื่อนไข ตัวหลังคือจำนวนค่าที่ไม่ซ้ำกันของ column หนึ่ง และทั้งคู่คือตัวตั้งของทุกการเดาในบทนี้

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

📦 code ของบทนี้

บทนี้เพิ่ม file เดียวคือ qe/stats.py ซึ่ง import fixture ของบท 1 มาใช้ตรงๆ ไม่ต้องมี heap file หรือ B+tree ของบท 2 กับบท 3 ก็รันได้

code ทุกช่วงในบทนี้ตัดมาจาก file เดียวกันนั้น ยกมาเฉพาะช่วงที่บทนี้อธิบาย เรียงตามลำดับที่มันอยู่จริงใน file จึงต้องต่อให้ครบทั้ง file ก่อนถึงจะรันได้

ส่วนที่ไม่ได้ยกมามีฟังก์ชันช่วยพิมพ์ตาราง ตัวช่วยเล็กๆ อย่างมัธยฐานกับการแปลง placed_at เป็นเลขวัน ตัวถอด record format ของ SQLite equi_depth_split ซึ่งเป็น equi-depth อีกแบบที่ยอมผ่าค่า และส่วน __main__ ที่ประกอบทุกอย่างเข้าด้วยกัน

โมดูลนี้เรียก sqlite3 ของ stdlib สร้าง .build/orders.db ขึ้นใหม่ทุกครั้งที่รัน แล้วสั่ง ANALYZE เอง จึงลบ folder .build/ ทิ้งได้ตลอดโดยไม่เสียอะไร

รันจาก folder ทำงานด้านนอกเหมือนบทก่อนหน้า ด้วย python3 qe/stats.py

หน่วยของบทนี้คือความผิดของค่าประมาณ ไม่ใช่ราคาของแผน

นิยามของ q-error code ที่คำนวณมัน และกรณีเดียวที่มันวัดไม่ได้

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

หน่วยนั้นคือ q-error นิยามของมันคือ max(ค่าประมาณ/ของจริง, ของจริง/ค่าประมาณ) ไร้หน่วย และ 1.00 คือแม่นเป๊ะ

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

def qerror(est, act):
    """q-error = max(est/act, act/est) · ยกพื้นทั้งสองฝั่งที่ 1 แถว
    เพราะ optimizer จริงก็ไม่ยอมประมาณต่ำกว่า 1 แถว และของจริง 0 แถวหารไม่ได้"""
    e = max(float(est), 1.0)
    a = max(float(act), 1.0)
    return max(e / a, a / e)

การหารต้องมีตัวหารเสมอ code จึงบังคับค่าต่ำสุดของทั้งสองฝั่งไว้ที่ 1 แถว ซึ่งบทนี้เรียกว่ายกพื้น เหตุผลมีสองชั้น ชั้นแรกคือ optimizer จริงก็ไม่ยอมประมาณต่ำกว่า 1 แถวอยู่แล้ว ชั้นที่สองคือของจริง 0 แถวหารไม่ได้

ผลข้างเคียงของชั้นที่สองต้องบอกไว้ตั้งแต่ตอนนี้ q-error วัดกรณีที่ของจริงเป็น 0 แถวไม่ได้ ตัวเลขที่ออกมาในกรณีนั้นคือผลของการยกพื้น ไม่ใช่ผลของการวัด

กรณีนั้นไม่ใช่กรณีสมมติ หัวข้อ independence จะเจอมันเข้าเต็มๆ

ก่อนจะมีสถิติ ก็ยังต้องมีคนตั้งค่าที่เดาไว้ล่วงหน้า

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

เปเปอร์ที่วางรากของแนวคิด “ประมาณราคาของทุกแผนแล้วเลือกแผนที่ถูกที่สุด” คือ Selinger et al. 1979 ซึ่งบท 1 อ้างถึงไว้แล้วโดยไม่ยกตัวเลข — ตัวเลขอยู่ตรงนี้

TABLE 1 หน้า 26 ของเปเปอร์ กำหนดค่า selectivity ไว้ตามรูปของเงื่อนไข

column = value ได้ 1/ICARD เมื่อมี index อยู่บน column นั้น โดย ICARD คือจำนวนค่าที่ไม่ซ้ำกันใน index ตัวนั้น มิฉะนั้นจึงตกไปใช้ 1/10
column > value ได้ค่าจากการเทียบสัดส่วนของช่วง เมื่อ column เป็นชนิดเลขคณิตและรู้ค่าที่เอามาเทียบตั้งแต่ตอนเลือก access path มิฉะนั้นจึงตกไปใช้ 1/3
column BETWEEN value1 AND value2 ได้ 1/4

ค่า 1/10 กับ 1/3 ไม่ใช่ค่าที่ใช้เสมอ ทั้งคู่เป็นค่าที่ตกไปใช้เมื่อเงื่อนไขข้างต้นไม่ครบ และเปเปอร์เองก็ไม่ได้อ้างว่ามันมีที่มา

เปเปอร์เขียนกำกับค่า 1/10 ไว้เองว่า “There is no significance to this number” (ตัวเลขนี้ไม่มีนัยสำคัญอะไรเป็นพิเศษ) ส่วนค่า 1/3 มาจากสมมุติฐานที่เขียนไว้ว่า “We hypothesize that few queries use predicates that are satisfied by more than half the tuples.” (เราตั้งสมมุติฐานว่ามี query ไม่กี่ข้อที่ใช้เงื่อนไขซึ่งแถวเกินครึ่งตารางผ่านได้)

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

uniformity — ตัวประมาณทั้งตัวคือ n หารด้วยจำนวนค่าที่ไม่ซ้ำ

ข้อสมมติแรก code ที่คำนวณมัน และผลของมันบนสาม column ที่กระจายไม่เหมือนกันในตารางเดียวกัน

uniformity assumption บอกว่าทุกค่าที่ต่างกันของ column หนึ่งมีจำนวนแถวเท่ากัน ค่าประมาณของทุกค่าจึงเป็นตัวเลขตัวเดียวกันหมด คือ n หารด้วยจำนวนค่าที่ไม่ซ้ำ

สถิติที่ต้องเก็บมีแค่สองตัว คือจำนวนแถวทั้งตารางกับ cardinality ของแต่ละ column นี่คือเหตุผลที่มันเป็นตัวประมาณที่ทุกเอนจินมี มันแทบไม่มีราคา

def uniformity(rows, col, name, show=None):
    """ประมาณ count(col = v) ด้วย n/distinct ทุกค่าเท่ากันหมด แล้วเทียบของจริง"""
    n = len(rows)
    cnt = collections.Counter(r[col] for r in rows)
    est = n / len(cnt)
    qs = {v: qerror(est, a) for v, a in cnt.items()}
    worst = min(qs, key=lambda v: (-qs[v], str(v)))     # tie-break ด้วยชื่อ เพื่อให้ deterministic

ตัวประมาณทั้งตัวอยู่ที่ est = n / len(cnt) บรรทัดเดียว ที่เหลือคือการนับของจริงมาเทียบเพื่อรายงานผล

status — column ที่เบ้หนัก

status มีค่าที่ไม่ซ้ำกัน 7 ค่า ค่าประมาณจึงเป็น 28,571.43 แถวเท่ากันทุกค่า ส่วนของจริงห่างกันหลายร้อยเท่า

ค่า	ของจริง	q-error
Delivered	163,733	5.73
Cancelled	21,131	1.35
Rejected	13,165	2.17
PickedUp	806	35.45
Preparing	583	49.01
Confirmed	383	74.60
Placed	199	143.58

แย่สุดคือ 143.58 ที่ Placed ซึ่งมีของจริง 199 แถว มัธยฐานอยู่ที่ 35.45 และมี 6 ค่าจาก 7 ค่าที่พลาดเกิน 2 เท่า

ทิศทางของความพลาดอ่านออกจากตารางได้ตรงๆ ว่ามันพังตรงค่าที่หายาก ไม่ใช่ค่าที่เยอะ Delivered ที่กินตาราง 81.87 % พลาดไป 5.73 เท่า ส่วน Placed ที่มี 199 แถวพลาดไป 143.58 เท่า

ค่าที่แม่นที่สุดคือ Cancelled ที่ 1.35 เพราะจำนวนแถวจริงของมันบังเอิญใกล้ค่าเฉลี่ยที่สุด ไม่ใช่เพราะตัวประมาณรู้อะไรเกี่ยวกับมันเป็นพิเศษ

restaurant กับ customer_id — ข้อสมมติเดิม ผลคนละอย่าง

restaurant มี 10 ค่า ค่าประมาณเท่ากันหมดที่ 20,000.00 แถว แย่สุดคือ 1.68 ที่ ครัวคุณแม่ ซึ่งมีของจริง 11,934 แถว มัธยฐาน 1.26 และไม่มีค่าไหนพลาดเกิน 2 เท่าเลยสักค่า

customer_id มี 2,000 ค่า ค่าประมาณเท่ากันหมดที่ 100.00 แถว แย่สุดคือ 1.37 มัธยฐาน 1.07 และพลาดเกิน 2 เท่า 0 ค่าจาก 2,000 ค่า

สาม column นี้อยู่ในตารางเดียวกัน ผ่านตัวประมาณตัวเดียวกัน แล้วได้ผลคนละขนาด แย่สุด 143.58 บน status เทียบกับแย่สุด 1.37 บน customer_id

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

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

independence — คูณสัดส่วนสองตัวเข้าด้วยกันแล้วเชื่อผลลัพธ์

ข้อสมมติที่สอง ผลของมันบนคู่ status กับ restaurant ทั้ง 70 คู่ และคู่ที่มันสร้างแถวขึ้นมาเอง

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

independence assumption อุดช่องนั้นด้วยการบอกว่ารู้ค่าของ column หนึ่งแล้วไม่ได้บอกอะไรเกี่ยวกับอีก column ค่าประมาณของสองเงื่อนไขจึงเป็น sel(X) คูณ sel(Y) คูณ n

def independence(rows, st_cnt, rs_cnt):
    """ประมาณ status=X AND restaurant=Y ด้วย sel(X)*sel(Y) แล้วเทียบของจริง"""
    n = len(rows)
    joint = collections.Counter((r[2], r[3]) for r in rows)
    recs = []
    for s, r in itertools.product(sorted(st_cnt), sorted(rs_cnt)):
        act = joint.get((s, r), 0)
        est = n * (st_cnt[s] / n) * (rs_cnt[r] / n)
        recs.append((qerror(est, act), s, r, act, est))
    recs.sort(key=lambda t: (-t[0], t[1], t[2]))
    return joint, recs

บรรทัดที่ทำงานจริงคือ est = n * (st_cnt[s] / n) * (rs_cnt[r] / n) ข้อสมมติที่ดังที่สุดในวงการเขียนได้ในบรรทัดเดียว

status 7 ค่า คูณ restaurant 10 ร้าน ได้ 70 คู่ที่เป็นไปได้ ในข้อมูลจริงมีอยู่ 69 คู่ อีก 1 คู่ไม่มีแถวเลยสักแถว

ภาพรวมดูดี มัธยฐาน q-error ของทั้ง 70 คู่อยู่ที่ 1.09 และมี 11 คู่ที่พลาดเกิน 2 เท่า ปัญหาของ independence ไม่ได้อยู่ที่ค่ากลาง มันอยู่ที่หาง

status	restaurant	ของจริง	ประมาณ	q-error
Rejected	ครัวสุขใจ	0	1,565.6	1565.58
Rejected	ครัวคุณแม่	8,126	785.6	10.34
Delivered	ครัวคุณแม่	2,426	9,769.9	4.03

อีก 7 คู่ที่เหลือในสิบอันดับแรกเป็น Rejected คู่กับร้านอื่น q-error อยู่ในช่วง 2.03 ถึง 2.29 ทั้งเจ็ดคู่ และทุกคู่ประมาณเกินจริง

สองคู่ที่พลาดหนักรองลงมาเป็นร้านเดียวกัน คือ ครัวคุณแม่ ที่บท 1 ตั้งน้ำหนัก Rejected ไว้สูงกว่าร้านอื่นมากใน MIX ร้านนี้ปฏิเสธออเดอร์บ่อยกว่าค่าเฉลี่ยของตารางมาก

ผลคือ independence ประมาณ Rejected ของร้านนี้ต่ำไป 10.34 เท่า และประมาณ Delivered ของร้านเดียวกันเกินไป 4.03 เท่า ความผิดสองข้อนี้เป็นความผิดข้อเดียวกันมองจากคนละด้าน

คู่ที่ไม่มีอยู่จริง — ความผิดที่ q-error บอกไม่ครบ

คู่ Rejected × ครัวสุขใจ มีของจริง 0 แถว แต่ independence ยืนยันว่ามี 1,565.6 แถว

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

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

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

🔁 ที่มาของคู่นี้อยู่ใน บทที่ 1 — สี่จุดใน qe/fixture.py ที่ต้องอ่านให้ออก

histogram — เก็บรูปร่างของ column ไว้ แทนค่าเฉลี่ยตัวเดียว

ตัวประมาณตัวที่สาม สองวิธีแบ่ง bucket และการทดสอบสามแบบบนข้อมูลชุดเดียวกัน กับคุณสมบัติที่ตำราท่องกันซึ่งจริงแค่ครึ่งเดียว

histogram แก้ปัญหาของ uniformity ด้วยการเลิกใช้ค่าเฉลี่ยตัวเดียวทั้ง column แล้วหั่นช่วงของค่าออกเป็น bucket เก็บจำนวนแถวของแต่ละ bucket ไว้แทน

บทนี้ทำ histogram บน placed_at แต่แปลงเป็นเลขวันก่อน จึงเหลือค่าที่ต่างกัน 180 ค่า ไม่ใช่ 196,891 ค่าระดับวินาทีที่บท 1 นับไว้

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

ค่าที่เป็นไปได้คือวัน 0 ถึง 179 รวม 180 วันที่มีข้อมูล ตั้ง B = 15 bucket ได้เป้าหมาย n/B = 13,333.33 แถวต่อ bucket

วันที่หนักที่สุดคือวัน 140 ซึ่งมี 17,603 แถว คิดเป็น 8.80 % ของทั้งตาราง นี่คือวันโปรโมชันที่บท 1 ฝังไว้ในข้อมูล

equi-width — แบ่งให้แต่ละช่วงกว้างเท่ากัน

def equi_width(days, b):
    """แบ่งโดเมนวันเป็น b ช่วงกว้างเท่ากัน — ขอบง่าย แต่จำนวนแถวต่อ bucket คุมไม่ได้"""
    width = DAYS // b
    out = []
    for i in range(b):
        lo, hi = i * width, (i + 1) * width - 1
        out.append([lo, hi, 0, hi - lo + 1])
    for d in days:
        out[min(int(d) // width, b - 1)][2] += 1
    return [tuple(x) for x in out]

bucket	ช่วงวัน	แถว	ส่วนแบ่ง
0	0-11	838	0.42 %
1	12-23	2,520	1.26 %
2	24-35	4,073	2.04 %
3	36-47	5,760	2.88 %
4	48-59	7,466	3.73 %
5	60-71	9,051	4.53 %
6	72-83	10,678	5.34 %
7	84-95	12,427	6.21 %
8	96-107	13,830	6.92 %
9	108-119	15,661	7.83 %
10	120-131	17,301	8.65 %
11	132-143	34,618	17.31 %
12	144-155	20,405	10.20 %
13	156-167	21,827	10.91 %
14	168-179	23,545	11.77 %

ขอบของทุก bucket คำนวณได้จากเลขวันตรงๆ ไม่ต้องเก็บอะไรเพิ่ม นั่นคือข้อดีทั้งหมดของวิธีนี้

ราคาของมันอยู่ที่ bucket 11 ซึ่งกิน 34,618 แถว หรือ 17.31 % ของตาราง เพราะวันโปรโมชันตกอยู่ในช่วง 132-143 พอดี วิธีนี้คุมความกว้างของช่วงได้ แต่คุมจำนวนแถวต่อ bucket ไม่ได้เลย

equi-depth — แบ่งให้จำนวนแถวของแต่ละ bucket ใกล้เคียงกัน

def equi_depth_atomic(sorted_days, b):
    """equi-depth แบบห้ามผ่าค่าเดียวกันข้าม bucket (กติกาที่ฐานข้อมูลจริงใช้
    เพราะ bucket ต้องตอบคำถาม 'ค่า v มีกี่แถว' ได้)
    ปิด bucket ที่จุดซึ่ง 'ใกล้โควตาที่สุด' ไม่ใช่จุดแรกที่เกินโควตา"""
    n = len(sorted_days)
    runs = sorted(collections.Counter(sorted_days).items())
    out, i, left = [], 0, n
    while i < len(runs):
        left_buckets = b - len(out)
        if left_buckets <= 1:
            seg = runs[i:]                       # bucket สุดท้ายรับที่เหลือทั้งหมด
            out.append((seg[0][0], seg[-1][0], sum(c for _, c in seg), len(seg)))
            break
        target = left / left_buckets
        bound = max(i + 1, len(runs) - (left_buckets - 1))   # ต้องเหลือ run ให้ bucket ที่ยังไม่เปิด
        cnt, nd, j = 0, 0, i
        while j < bound:
            c = runs[j][1]
            if cnt and abs(cnt - target) <= abs(cnt + c - target):
                break
            cnt, nd, j = cnt + c, nd + 1, j + 1
        out.append((runs[i][0], runs[j - 1][0], cnt, nd))
        left -= cnt
        i = j
    return out

ต้องบอกไว้ตรงนี้ว่า equi_depth_atomic เป็น greedy ที่เขียนขึ้นเองสำหรับคอร์สนี้ ไม่ใช่อัลกอริทึมของ PostgreSQL หรือของ SQLite

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

bucket	ช่วงวัน	แถว	ค่าที่ต่างกัน	ส่วนแบ่ง
0	0-47	13,191	48	6.60 %
1	48-67	13,383	20	6.69 %
2	68-82	12,879	15	6.44 %
3	83-95	13,360	13	6.68 %
4	96-107	13,830	12	6.92 %
5	108-117	12,959	10	6.48 %
6	118-127	14,032	10	7.02 %
7	128-136	13,445	9	6.72 %
8	137-139	4,767	3	2.38 %
9	140-140	17,603	1	8.80 %
10	141-149	14,811	9	7.41 %
11	150-157	13,867	8	6.93 %
12	158-165	14,445	8	7.22 %
13	166-172	13,440	7	6.72 %
14	173-179	13,988	7	6.99 %

ความต่างที่เห็นชัดที่สุดอยู่ที่ bucket 9 ซึ่งมีวัน 140 อยู่วันเดียว และ bucket 0 ซึ่งกวาดวัน 0 ถึง 47 รวม 48 วันเข้ามาอยู่ด้วยกัน

การอ่านค่าออกจาก histogram ทำแบบเดียวกันทั้งสองแบบ

def est_from(hist, d):
    """ประมาณ count(day = d) จาก histogram: กระจายแถวใน bucket ให้ทุกค่าเท่ากัน"""
    los = [h[0] for h in hist]
    i = bisect.bisect_right(los, d) - 1
    lo, hi, cnt, nd = hist[max(i, 0)]
    return cnt / nd

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

flowchart TB
    subgraph W["equi-width — แบ่ง 180 วันเป็น 15 ช่วงกว้างเท่ากัน"]
        direction LR
        W10["bucket 10<br/>วัน 120-131<br/>17,301 แถว"] --> W11["bucket 11<br/>วัน 132-143<br/>34,618 แถว"] --> W12["bucket 12<br/>วัน 144-155<br/>20,405 แถว"]
    end
    subgraph D["equi-depth — ห้ามผ่าค่าเดียวกันข้าม bucket"]
        direction LR
        D8["bucket 8<br/>วัน 137-139<br/>4,767 แถว"] --> D9["bucket 9<br/>วัน 140 วันเดียว<br/>17,603 แถว"] --> D10["bucket 10<br/>วัน 141-149<br/>14,811 แถว"]
    end
    W --> NW["วันโปรโมชันจมรวมกับอีกสิบเอ็ดวัน<br/>ถามว่าวัน 140 มีกี่แถว ได้ q-error 6.10"]
    D --> ND["วันโปรโมชันได้ bucket ของตัวเอง<br/>ถามว่าวัน 140 มีกี่แถว ได้ q-error 1.00"]

คำบรรยายภาพ: สาม bucket กลางของแต่ละวิธี วางบนค่าชุดเดียวกันคือเลขวันของ placed_at · equi-width บังคับให้ทุกช่วงกว้างเท่ากัน วันโปรโมชันจึงตกไปรวมกับวันอื่นใน bucket 11 · equi-depth เลือกขอบเองเพื่อคุมจำนวนแถว วัน 140 จึงได้ bucket ของตัวเองที่ bucket 9 · ตัวเลข q-error ใต้ภาพคือผลของการถามว่าวัน 140 มีกี่แถว ด้วย histogram แต่ละแบบ

คุณสมบัติที่ตำราท่องกัน จริงแค่ครึ่งเดียว

ประโยคที่ได้ยินบ่อยคือ equi-depth การันตีว่า bucket ที่ใหญ่ที่สุดจะมีแถวเท่ากับ n/B ไม่ว่าข้อมูลจะรูปร่างไหน โมดูลนี้ทดสอบมันบนข้อมูลชุดเดียวกันสามแบบ

วิธีแบ่ง	bucket ใหญ่สุด	เทียบกับ n/B
equi-depth ที่ยอมผ่าค่าเดียวข้าม bucket	13,334 แถว	1.0000 เท่า
equi-depth ที่ห้ามผ่าค่า	17,603 แถว	1.3202 เท่า
equi-width	34,618 แถว	2.5963 เท่า

แบบที่ทำให้คุณสมบัตินี้เป็นจริงคือแบบที่ยอมให้ค่าเดียวถูกผ่าไปอยู่มากกว่าหนึ่ง bucket ซึ่งอยู่ใน qe/stats.py ชื่อ equi_depth_split และเป็นช่วงที่บทนี้ไม่ได้ยกมา ราคาของมันคือ 14 วันที่ถูกผ่า

histogram แบบนั้นตอบคำถาม “วัน d มีกี่แถว” ตรงๆ ไม่ได้ ต้องรวมข้าม bucket ก่อน ซึ่งเป็นเหตุผลที่ฐานข้อมูลจริงไม่ใช้กติกาแบบนั้น

พอบังคับกติกาที่ฐานข้อมูลจริงใช้ คือห้ามผ่าค่า ค่าเดียวที่หนักเกินเป้าหมายก็ทำลายการันตีทันที วัน 140 มี 17,603 แถวอยู่ในค่าเดียว ผ่าไม่ได้ bucket ที่รับมันจึงใหญ่กว่าเป้าหมาย 1.3202 เท่า

สิ่งที่พูดได้แน่ๆ จึงเป็นประโยคที่อ่อนกว่านั้น คือ ค่าที่หนักที่สุดในข้อมูลเป็นพื้นของ bucket ที่ใหญ่ที่สุดเสมอ ผ่าค่าไม่ได้ก็ลงไปต่ำกว่าค่านั้นไม่ได้ ที่ B = 15 พื้นนี้คือ 17,603 แถว และ bucket ใหญ่สุดก็ลงมาอยู่ที่พื้นพอดี

เมื่อพื้นสูงกว่าเป้าหมาย การันตี n/B ก็เป็นไปไม่ได้ตั้งแต่ต้นด้วยเลขคณิตล้วนๆ แต่การดัน n/B ให้สูงกว่าพื้นด้วยการลด B ก็ไม่ได้แปลว่าการันตีจะกลับมา เพราะกติกาห้ามผ่าค่ายังบังคับให้วันข้างเคียงถูกยุบเข้า bucket เดียวกันอยู่ดี

equi-depth ไม่ได้ชนะทุกจุด

เอา histogram ทั้งสองแบบไปประมาณจำนวนแถวของทั้ง 180 วัน แล้ววัด q-error ทุกวัน ได้ผลแบบนี้

histogram	q-error แย่สุด	มัธยฐาน	วันที่พลาดเกิน 2 เท่า
equi-width	13.97	1.05	4/180
equi-depth (ห้ามผ่าค่า)	54.96	1.04	13/180

ตรงจุดที่เป็นโจทย์ตั้งต้น equi-depth ชนะขาด ถามว่าวัน 140 มีกี่แถว มันได้ q-error 1.00 ส่วน equi-width ได้ 6.10

แต่เมื่อดูทั้ง 180 วัน มันแย่กว่าทั้งค่าแย่สุด และจำนวนวันที่พลาดเกิน 2 เท่าซึ่งมากกว่าสามเท่าตัว

จุดที่มันแพ้คือหางที่ข้อมูลบาง วัน 0 มีของจริง 5 แถว equi-width ประมาณ 69.8 แถว ส่วน equi-depth ประมาณ 274.8 แถว เพราะมันยุบวันเงียบๆ หลายสิบวันเข้ามาอยู่ bucket เดียวกัน

equi-depth คุมจำนวนแถวต่อ bucket ได้ แต่ไม่ได้คุมความคล้ายกันของค่าที่อยู่ใน bucket เดียวกัน ความแม่นตรง spike จึงถูกแลกมาด้วยความแม่นตรงหาง

SQLite เก็บสถิติอะไรไว้จริง

ผลของ ANALYZE บนตารางชุดเดียวกัน รูปแบบของ stat1 สิ่งที่ index ร่วมให้มาแทน และชั้นที่สองที่ชื่อ stat4

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

def build_db(rows):
    """สร้าง orders.db ใหม่ทุกครั้งจาก fixture แล้วสั่ง ANALYZE ให้ SQLite เก็บสถิติเอง"""
    os.makedirs(BUILD, exist_ok=True)
    if os.path.exists(DB_PATH):
        os.remove(DB_PATH)
    con = sqlite3.connect(DB_PATH)
    con.execute("CREATE TABLE orders(id INTEGER PRIMARY KEY, customer_id INTEGER,"
                " status TEXT, restaurant TEXT, placed_at INTEGER, total_satang INTEGER)")
    con.executemany("INSERT INTO orders VALUES (?,?,?,?,?,?)", rows)
    for sql in ("CREATE INDEX idx_status ON orders(status)",
                "CREATE INDEX idx_restaurant ON orders(restaurant)",
                "CREATE INDEX idx_status_rest ON orders(status, restaurant)",
                "CREATE INDEX idx_placed_at ON orders(placed_at)",
                "CREATE INDEX idx_customer ON orders(customer_id)"):
        con.execute(sql)
    con.commit()
    con.execute("ANALYZE")
    con.commit()
    return con

ANALYZE เดิน index ทุกตัวแล้วเขียนผลลง sqlite_stat1 หนึ่งบรรทัดต่อหนึ่ง index

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

index	stat ที่ SQLite เขียน	n/distinct ที่เราคำนวณเอง
`idx_customer`	`200000 100`	100.00
`idx_placed_at`	`200000 1`	1.02
`idx_restaurant`	`200000 20000`	20,000.00
`idx_status`	`200000 28572`	28,571.43
`idx_status_rest`	`200000 28572 2899`	2,898.55

สองหลักนี้เกาะกันทุกแถว ค่าที่ SQLite เขียนคือจำนวนเต็มที่อยู่ติดกับ n หารด้วยจำนวนค่าที่ไม่ซ้ำที่เราคำนวณเองเสมอ แปลว่า stat1 คือ uniformity assumption ในหัวข้อก่อนหน้า เขียนลง disk

แถวที่ต้องอ่านแยกคือ idx_placed_at ซึ่งได้ 1 ทั้งที่ของจริงคือ 1.02 ตัวเลขนี้ไม่ได้มาจากการปัดตามปกติ แต่มาจากกฎพิเศษที่ ANALYZE ใช้บีบค่าของ column ที่เกือบไม่ซ้ำลงมาเหลือ 1 column แบบนั้นจึงหน้าตาเหมือนไม่ซ้ำเลยในสายตา optimizer

index ร่วมให้สถิติร่วม แต่ไม่ได้แปลว่าเดาดีขึ้น

index บน (status, restaurant) ทำให้มีตัวเลขตัวที่สามคือ 2,899 แถวต่อหนึ่งคู่ ซึ่งเป็นสถิติของคู่จริงๆ ไม่ต้องคูณ selectivity อีกแล้ว independence หายไปจากสมการทั้งข้อ

ค่าที่เราคำนวณเองคือ 2,898.55 ซึ่งก็คือ n หารด้วยจำนวนคู่ที่มีอยู่จริงในข้อมูล

แต่สิ่งที่เข้ามาแทน independence คือ uniformity บนคู่ และมันพังคนละที่

ตัวประมาณ	q-error แย่สุด	มัธยฐาน	คู่ที่พลาดเกิน 2 เท่า
sel(X) คูณ sel(Y)	1565.58	1.09	11/70
ตัวเลขต่อคู่จาก index ร่วม	2899.00	35.81	60/70

ค่าแย่สุดของตัวประมาณทั้งสองตัวมาจากคู่เดียวกัน คือคู่ที่ของจริงเป็น 0 แถว ทั้งคู่จึงเป็นตัวเลขที่ผ่านการยกพื้นมาแล้ว ไม่ใช่การวัด ส่วนมัธยฐานกับจำนวนคู่ที่พลาดเกิน 2 เท่าเป็นตัวเลขที่เทียบกันได้ตรงๆ

คู่	ของจริง	sel คูณ sel	q-error	ต่อคู่	q-error
Rejected × ครัวสุขใจ	0	1,565.6	1565.58	2,899	2899.00
Rejected × ครัวคุณแม่	8,126	785.6	10.34	2,899	2.80
Delivered × ครัวคุณแม่	2,426	9,769.9	4.03	2,899	1.19
Rejected × ส้มตำแซ่บนัว	926	2,122.6	2.29	2,899	3.13
Rejected × ข้าวมันไก่ประตูน้ำ	834	1,856.8	2.23	2,899	3.48

ผลรวมสวนความคาดหมาย การมีสถิติร่วมทำให้ดีขึ้น 2 คู่ และแย่ลง 68 คู่จาก 70 คู่

ที่ดีขึ้นคือคู่ที่ผิดปกติจริงๆ Rejected × ครัวคุณแม่ ตกจาก 10.34 เหลือ 2.80 เพราะตัวเลขต่อคู่ไม่ได้ตั้งอยู่บนสัดส่วนของ Rejected ทั้งตารางที่ร้านนี้ไม่ทำตาม

ที่แย่ลงเพราะมันเป็นเลขตัวเดียวใช้กับทุกคู่เท่ากันหมด มันทิ้งความต่างระหว่าง Delivered ที่กินตาราง 81.87 % กับ Placed ที่มี 0.10 % ไปทั้งดุ้น ส่วน independence อย่างน้อยยังใช้สัดส่วนราย column อยู่

ประโยคที่ถูกจากตารางนี้คือ ตัวประมาณที่ใช้ stat1 อย่างเดียวแย่กว่า ไม่ใช่ “SQLite ประมาณแย่กว่า” — ตัวประมาณที่เอาตัวเลขต่อคู่ไปใช้กับทุกคู่เป็นสิ่งที่เราประกอบขึ้นเองจากสิ่งที่ stat1 มี ไม่ใช่วิธีที่ SQLite ใช้จริง

และหัวข้อถัดไปคือเหตุผลว่าทำไมมันถึงไม่ใช่

sqlite_stat4 — ชั้นที่สองที่เก็บจำนวนแถวจริง ไม่ใช่ค่าเฉลี่ย

build ของ SQLite ที่ใช้วัดบทนี้คอมไพล์ด้วย SQLITE_ENABLE_STAT4 จึงมีตาราง sqlite_stat4 เพิ่มมาอีกตาราง มันเก็บ nEq คือจำนวนแถวจริงของค่าที่ถูกเก็บไว้เป็นตัวอย่าง

def stat4(con, idx, ncols):
    """คืน {ค่าที่ถูกเก็บเป็นตัวอย่าง: nEq} ของ index หนึ่ง
    nEq คือจำนวนแถวจริงของค่านั้น ไม่ใช่ค่าเฉลี่ย — นี่คือ histogram ตัวจริงของ SQLite"""
    out = {}
    for neq, sample in con.execute(
            "SELECT neq, sample FROM sqlite_stat4 WHERE idx = ? ORDER BY rowid", (idx,)):
        out[tuple(sample_cols(sample, ncols))] = int(neq.split()[ncols - 1])
    return out

ค่าตัวอย่างถูกเก็บเป็น blob ตามรูปแบบ record ของ SQLite การอ่านมันออกมาจึงต้องถอดรูปแบบนั้นเอง ซึ่ง qe/stats.py ทำด้วย stdlib ล้วนผ่านฟังก์ชัน varint กับ sample_cols ที่ไม่ได้ยกมาแสดงตรงนี้เพราะยาว

ANALYZE เก็บตัวอย่างไว้ 97 แถวสำหรับ 5 index รวมกัน

index	จำนวนตัวอย่าง
`idx_customer`	24
`idx_placed_at`	24
`idx_restaurant`	11
`idx_status`	14
`idx_status_rest`	24

ตัวอย่างนับเป็นแถวใน sqlite_stat4 ไม่ใช่จำนวนค่าที่ต่างกัน ค่าเดียวกันจึงติดตัวอย่างได้มากกว่าหนึ่งครั้ง ตัวอย่าง 14 แถวของ idx_status เป็นค่าที่ต่างกันเพียง 7 ค่า

idx_status ติดตัวอย่างครบทั้ง 7 ค่าจาก 7 ค่า และ nEq ตรงกับของจริงทุกค่า q-error จึงเป็น 1.00 ทั้งเจ็ดค่า ความเบ้ที่ทำให้ uniformity พลาดไป 143.58 เท่า หายไปหมดตรงนี้

idx_status_rest ติดตัวอย่าง 24 คู่จาก 69 คู่ที่มีจริง และทั้ง 24 คู่ nEq ตรงของจริงเป๊ะ คู่ Rejected × ครัวคุณแม่ ได้ nEq เท่ากับ 8,126 ซึ่งเท่ากับของจริง

คู่ที่ไม่ติดตัวอย่างตกกลับไปใช้ค่าเฉลี่ยของ stat1 เหมือนเดิม และคู่ Rejected × ครัวสุขใจ ไม่มีทางติดตัวอย่างได้เลย เพราะไม่มี entry อยู่ใน index ให้สุ่มเจอ มันจึงตกไปใช้ตัวเลข 2,899 ต่อคู่

การเก็บตัวอย่างแก้ความเบ้ได้ แต่แก้คู่ที่ไม่มีอยู่จริงไม่ได้

stat4 ลบความผิดพลาดที่เกิดจากความเบ้ออกได้จริงสำหรับค่าที่ติดตัวอย่าง จาก 143.58 เท่าเหลือ 1.00 บน status ทั้ง 7 ค่า

ราคาของมันคือสถิติที่ต้องเก็บเพิ่มและงานที่ ANALYZE ต้องทำเพิ่ม ไม่ใช่ของฟรี และ build ที่ไม่ได้เปิด SQLITE_ENABLE_STAT4 จะมีแค่ stat1 ผลของหัวข้อนี้ก็จะต่างออกไปทั้งหัวข้อ

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

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

ตัวเลขของ SQLite ในหัวข้อนี้วัดจาก 3.53.4 ซึ่งเป็นตัวที่มากับ Python ของเครื่องที่ใช้วัด ส่วนคำอธิบายรูปแบบของ stat1 อ้างจากซอร์ส 3.51.0

สิ่งที่บทนี้ส่งต่อให้บทถัดไป

สรุปว่าตัวประมาณสามแบบพังตรงไหนกันบ้าง และค่าประมาณพวกนี้จะถูกเอาไปใช้ทำอะไรต่อ

ตัวประมาณสามแบบในบทนี้พังคนละแบบ และไม่มีแบบไหนพังตลอดเวลา

uniformity พลาดหนักตรงค่าที่หายากของ column ที่เบ้ และแม่นมากบน column ที่กระจายเท่ากัน ทั้งสองอย่างเกิดในตารางเดียวกัน
independence ให้ค่ากลางที่ดี แต่พังหนักที่สุดกับคู่ที่ไม่มีอยู่จริง ซึ่งเป็นความผิดที่การเก็บตัวอย่างช่วยไม่ได้
histogram แลกความแม่นตรงจุดที่ข้อมูลหนา กับความแม่นตรงหางที่ข้อมูลบาง และการเลือกวิธีแบ่ง bucket คือการเลือกว่าจะยอมพลาดตรงไหน

flowchart TD
    Q["เงื่อนไขบน column เดียว"] --> U["uniformity<br/>n หารด้วยจำนวนค่าที่ไม่ซ้ำ"]
    Q --> H["histogram<br/>แถวใน bucket หารด้วยจำนวนค่าที่ต่างกันใน bucket"]
    P["เงื่อนไขบนสอง column พร้อมกัน"] --> I["independence<br/>sel ของ X คูณ sel ของ Y คูณ n"]
    U --> UQ["status แย่สุด 143.58<br/>customer_id แย่สุด 1.37"]
    H --> HQ["equi-width แย่สุด 13.97<br/>equi-depth แย่สุด 54.96"]
    I --> IQ["แย่สุด 1565.58 ที่คู่ซึ่งของจริง 0 แถว<br/>เลขจากการยกพื้น ไม่ใช่ผลวัด<br/>มัธยฐาน 1.09"]
    UQ --> R["จำนวนแถวที่ประมาณได้"]
    HQ --> R
    IQ --> R
    R --> C["ส่งต่อให้บทถัดไปเอาไปคิดราคาของแผน"]

คำบรรยายภาพ: ทางเดินของค่าประมาณหนึ่งค่า จากเงื่อนไขไปจนถึงจำนวนแถวที่ planner เชื่อ · เงื่อนไขบน column เดียวเลือกได้ระหว่าง uniformity กับ histogram ส่วนเงื่อนไขบนสอง column พร้อมกันใช้การคูณ selectivity · กล่องที่ติดตัวเลขคือ q-error ที่บทนี้วัดได้ของแต่ละเส้นทาง · ทุกเส้นทางไปจบที่จำนวนแถวประมาณตัวเดียว ซึ่งบทถัดไปเอาไปคิดราคา

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

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

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

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

Access Path Selection in a Relational Database Management System — Selinger et al., Proc. 1979 ACM SIGMOD, หน้า 23–34 (ตรวจ PDF แล้ว 2026-08-11) — TABLE 1 หน้า 26 คือที่มาของค่า 1/ICARD, 1/10, 1/3 และ 1/4 พร้อมเงื่อนไขของแต่ละค่า และเป็นที่มาของสองประโยคที่ยกมาตรงตัวในหัวข้อที่สองของบทนี้
SQLite File Format — หัวข้อ The sqlite_stat1 table (ตรวจ 2026-08-11) — รูปแบบของ stat ที่ ANALYZE เขียน ตรวจคู่กับซอร์ส src/analyze.c บรรทัด 20 และ 41–65 ของ SQLite 3.51.0 ส่วนผลที่วัดได้ในบทนี้มาจาก SQLite 3.53.4 ที่มากับ Python ของเครื่องที่ใช้วัด

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

ข้อ 1 / 3

uniformity ประมาณ status พลาดไป 143.58 เท่าที่ค่า Placed แต่ประมาณ customer_id พลาดแค่ 1.37 เท่าเป็นอย่างมาก ทั้งที่เป็นตารางเดียวกันและตัวประมาณตัวเดียวกัน อธิบายผลนี้อย่างไรจึงตรง

สถิติ — เดา​จำนวน​แถว​โดย​ไม่​รัน query

หน่วย​ของ​บท​นี้​คือ​ความ​ผิด​ของ​ค่า​ประมาณ ไม่ใช่​ราคา​ของ​แผน

ก่อน​จะ​มี​สถิติ ก็​ยัง​ต้อง​มี​คน​ตั้ง​ค่าที่​เดา​ไว้​ล่วงหน้า

uniformity — ตัว​ประมาณ​ทั้ง​ตัว​คือ n หาร​ด้วย​จำนวน​ค่าที่​ไม่​ซ้ำ

status — column ที่​เบ้​หนัก

restaurant กับ customer_id — ข้อ​สมมติ​เดิม ผล​คนละ​อย่าง

independence — คูณ​สัดส่วน​สอง​ตัว​เข้า​ด้วย​กัน​แล้ว​เชื่อ​ผลลัพธ์

histogram — เก็บ​รูปร่าง​ของ column ไว้ แทน​ค่า​เฉลี่ย​ตัว​เดียว

equi-width — แบ่ง​ให้​แต่ละ​ช่วง​กว้าง​เท่า​กัน

equi-depth — แบ่ง​ให้​จำนวน​แถว​ของ​แต่ละ bucket ใกล้​เคียง​กัน

คุณสมบัติ​ที่​ตำรา​ท่อง​กัน จริง​แค่​ครึ่ง​เดียว

equi-depth ไม่​ได้​ชนะ​ทุก​จุด

SQLite เก็บ​สถิติ​อะไร​ไว้​จริง

index ร่วม​ให้​สถิติ​ร่วม แต่​ไม่​ได้​แปล​ว่า​เดา​ดี​ขึ้น

sqlite_stat4 — ชั้น​ที่​สอง​ที่​เก็บ​จำนวน​แถว​จริง ไม่ใช่​ค่า​เฉลี่ย

สิ่ง​ที่​บท​นี้​ส่ง​ต่อ​ให้​บท​ถัด​ไป