Cost-Based Ranker (P2/3): Nguồn ước lượng và ba thí nghiệm

Ở phần trước: khi trial ngắn không ra plan nào, CBR lấy mẫu vài trăm document rồi nhân lên thành ước lượng cardinality. Trial có budget khoảng 10.000 works.

• Cần đọc trước: Cardinality, khi nào CBR vào việc, CBR tính gì
• Dẫn tới: CBR và plan cache; biết ranker nào chạy

Nguồn ước lượng: sampling, heuristics, và chuyện histogram

Sampling: đếm trong mẫu rồi nhân lên

[tài liệu] sampling: MongoDB tính ước lượng trên một mẫu của collection gốc.

[quan sát] Mọi ước lượng Sampling trên collection 1 triệu document là bội số của 2.631,6 = 1.000.000 / 380: mẫu có 380 document. $queryStats xác nhận: 5 lần CBR chạy, nDocsSampled có min = max = 380. Hệ quả: ước lượng chỉ có thể là 0, 2.632, 5.263...; điều kiện khớp dưới khoảng 1/380 (0,26%) thường không có trong mẫu nên được đoán là 0; và điều kiện càng hiếm thì sai số tương đối càng lớn (điều kiện 30% có khoảng 114 document khớp trong mẫu, điều kiện 2,5% chỉ còn 9–10).

[chi tiết cài đặt] Cách lấy mẫu do tham số nội bộ internalQuerySamplingCEMethod quyết định, mặc định "chunk", cùng internalQueryNumChunksForChunkBasedSampling: 10: 380 = 10 chunk × 38 document. Đổi sang "random" thì mẫu thành 384 document, đúng cỡ mẫu cho độ tin cậy 95%, sai số 5% (1,96² × 0,25 / 0,05²), khớp hai tham số samplingConfidenceInterval: "95" và samplingMarginOfError: 5. Không tham số nào trong số này có trong tài liệu.

Sampling đánh giá cả filter trên document trong mẫu. Vì vậy FETCH của Q6 được đoán đúng là 0, và sampling tự nắm được tương quan giữa các field, thứ mà ước lượng theo từng cột riêng lẻ hay bỏ sót.

Heuristics: luật ngón tay cái khi không lấy mẫu được

[tài liệu] heuristics: dùng một bộ quy tắc để xác định selectivity. Chỉ dùng khi sampling thất bại.

[quan sát] Trong lab (ép bằng chế độ nội bộ heuristicCE), heuristics không nhìn dữ liệu:

• Mọi điều kiện bằng trên một index được đoán √n key: 1.000 trên collection 1 triệu document, 774,6 trên collection 600.000 document.
• Mọi điều kiện khoảng ($gte) được đoán 20% collection: 200.000.
• Mỗi điều kiện lọc thêm ở FETCH làm ước lượng nhỏ đi nữa (1.000 → 31,6 với một phép bằng).

tenantId: "t0000" (300.422 đơn) và "t0042" (1.084 đơn) nhận cùng ước lượng 1.000. Thí nghiệm 3 đo hậu quả.

Metadata, code, mixed

[tài liệu] metadata: lấy từ metadata như số document của collection. code: tính trực tiếp (hằng số, biểu thức). mixed: kết hợp nhiều loại. [quan sát] Ở chế độ mặc định, mọi ước lượng trong lab đều là Sampling.

Histogram: có tên, chưa dùng được trên 8.3.11

• serverStatus có metrics.query.cbr.histograms. [tài liệu] Đó là histogram về thời gian và số plan của CBR (micros, numPlans, samplingMicros), không phải histogram dữ liệu.
• $queryStats có bộ đếm metrics.costBasedRanker.cardinalityEstimationMethods.Histogram. [tài liệu] Nó đếm số lần ước lượng dựa trên histogram được dùng. [quan sát] Trong lab, bộ đếm này luôn bằng 0.
• [quan sát] Danh sách nguồn ceSource trong tài liệu explain không có histogram. Thử đặt internalQueryCBRCEMode: "histogramCE" thì server trả lỗi histogramCE not allowed, khác với một giá trị không tồn tại (Enumeration value ... is not a valid value). Tài liệu 8.3 cũng không có lệnh nào để tạo hay xem histogram.

Kết luận thận trọng: trên 8.3.11, CBR ước lượng bằng sampling, lùi về heuristics khi sampling thất bại. Histogram có dấu vết trong bộ đếm và server, nhưng không dùng được và không có tài liệu. MongoDB 8.3 không có lệnh kiểu ANALYZE.

Thí nghiệm 2: ước lượng sai bao nhiêu?

Cách đo

Ở chế độ chỉ-CBR trong lab, explain một query AND hai điều kiện thì CBR in ước lượng cho IXSCAN của từng index. Mỗi điều kiện lấy 21 lần lập plan (21 mẫu), so median với countDocuments. Hai lượt: chunk (mặc định) và random.

Kết quả thật

                                    chunk (mặc định, mẫu 380)        random (mẫu 384)
Điều kiện          Thật     Sel.    median    min–max         ratio  median    min–max         ratio
tenantId=t0000     300.422  30%     292.105   242.105–339.474  0,97  307.292   265.625–356.771  1,02
createdAt>=30d     287.293  28,7%   284.211   239.474–321.053  0,99  289.063   250.000–333.333  1,01
tenantId=t0001     100.194  10%      97.368    68.421–128.947  0,97  101.563    78.125–119.792  1,01
createdAt>=1d       52.819  5,3%     50.000    36.842–73.684   0,95   52.083    39.063–70.313   0,99
region=KH           25.159  2,5%     21.053     7.895–39.474   0,84   26.042     5.208–46.875   1,04
total>=20M          12.746  1,3%     10.526     2.632–26.316   0,83   13.021     2.604–26.042   1,02
tenantId=t0042       1.084  0,11%         0         0–5.263    0           0         0–5.208   0
status=disputed        478  0,05%         0         0–2.632    0           0         0–2.604   0
total>=70M             125  0,01%         0         0–2.632    0           0         0–2.604   0

Đọc kết quả

[quan sát] Ba vùng rõ rệt:

selectivity    ≥ 5%                  1–5%                   < 0,3%
               │                     │                      │
median         gần đúng (±5%)        đúng trung bình,       0
                                     dao động gấp 5–10 lần
một lần đoán   lệch ~15–20% (ở 30%)  có thể lệch 3–5 lần    0, hoặc "nhảy" lên 2.632–5.263
               tới ~40% (ở 5–10%)

• Điều kiện phổ biến (từ 5% trở lên): median lệch dưới 5%. Từng lần đoán lệch tới khoảng 15–20% ở mức 30%, và tới 30–40% ở mức 5–10% (createdAt 1 ngày: 36.842–73.684 so với 52.819 thật). Đủ tốt để phân biệt 30% với 70%, chưa chắc đủ để phân biệt 5% với 8%.
• Điều kiện vừa (1–5%): trung bình vẫn đúng, từng lần đoán dao động mạnh. total >= 20 triệu có lúc 2.632, có lúc 26.316, thật là 12.746.
• Điều kiện hiếm (dưới khoảng 0,3%): median là 0. Thỉnh thoảng mẫu trúng một document, ước lượng nhảy lên 2.632, gấp 2–20 lần thật.

Thú vị là đoán 0 cho điều kiện hiếm thường dẫn tới quyết định đúng: plan dùng index của điều kiện hiếm thật sự rẻ. Sai về con số nhưng đúng về thứ tự, và CBR chỉ cần thứ tự. Cột chunk có median hơi thấp ở vài dòng (0,83–0,84); 21 lần đo chưa đủ để gọi đó là thiên lệch. Điểm yếu thật của chunk nằm ở thí nghiệm 4.

Thí nghiệm 3: multi-planner và CBR trên cùng query

Cách đo

Cùng năm query, chạy dưới bốn chế độ của tham số nội bộ internalQueryCBRCEMode. [chi tiết cài đặt] Tham số này không có trong tài liệu. Giá trị server chấp nhận trong lab: automaticCE (mặc định), samplingCE, heuristicCE, exactCE. Đặt bằng setParameter và chỉ dùng trong lab:

// CHỈ TRONG LAB. Tham số nội bộ, không có trong tài liệu, có thể đổi hoặc biến mất ở bản vá sau.
db.adminCommand({ setParameter: 1, internalQueryCBRCEMode: "samplingCE" });
// ... đo ...
db.adminCommand({ setParameter: 1, internalQueryCBRCEMode: "automaticCE" });  // trả về mặc định

• automaticCE: mặc định, multi-planner trước, CBR dự phòng.
• samplingCE: CBR với sampling cho mọi query đủ điều kiện, bỏ qua trial.
• heuristicCE: CBR chỉ với heuristics.
• exactCE: CBR với số đếm chính xác. Dùng làm "đáp án".

Kết quả thật

Thời gian CBR tự báo trong metrics.query.cbr.micros cho mỗi lần lập plan:

samplingCE   209–290 µs   (trong đó lấy mẫu 156–213 µs)
heuristicCE   10–16 µs
exactCE      44.195–406.858 µs   (44 ms đến 407 ms: đếm thật = chạy thật)

Đọc kết quả

[quan sát]

1. Trên dữ liệu này, sampling CBR và multi-planner đồng ý ở mọi query. Khi khoảng cách giữa hai plan lớn (ở đây gấp 8 lần trở lên), sai số của mẫu 380 document không đủ để đảo thứ tự.
2. Heuristics sai ba trên bốn query có kết quả, và mỗi lần sai chậm hơn 3–40 lần. Không phải vì heuristics "dở". Nó đoán mọi phép bằng như nhau, nên trên dữ liệu lệch, việc chọn giữa t0000 (30%) và disputed (0,05%) chỉ còn là chuyện tie-break. Đây là lý do tài liệu nói heuristics chỉ là đường lùi khi sampling thất bại.
3. Đếm chính xác thì luôn đúng, nhưng mất 44–407 ms chỉ để chọn plan, lâu hơn cả chạy query. Ước lượng tồn tại vì đếm thật quá đắt.
4. Multi-planner tự nó không cần ước lượng cho bốn query đầu: trial ngắn đã đủ phân định. CBR chỉ có việc ở Q6.

Chạy thử là "đo thật trên đoạn đầu", chính xác khi đo được. CBR là "đoán trên toàn cục", dùng khi đo không ra gì. Kết hợp hai cái giữ hành vi cũ cho hầu hết query.

Thí nghiệm 4: khi ước lượng sai và CBR chọn plan chậm hơn

Ở lab14.orders, các đơn được chèn theo thứ tự ngẫu nhiên. Mọi giá trị đều rải đều trên đĩa, nên 10 chunk liền nhau vẫn là một mẫu đại diện. Ngoài đời thì không phải lúc nào cũng vậy.

Kịch bản: một khách hàng lớn được import một lần

Một hệ thống SaaS có 300 tenant nhỏ. Rồi một khách lớn chuyển sang, toàn bộ lịch sử đơn hàng của họ được import một lần. Các document của khách này nằm liền nhau ở cuối collection.

// lab14.imported: 600.000 đơn
//   330.000 đơn đầu: 300 tenant nhỏ, chèn ngẫu nhiên
//   270.000 đơn cuối: tenant "tBULK", chèn liền một khối (45% collection)
// region "HN" rải đều 20% trên toàn collection: 120.376 đơn
db.imported.createIndex({ tenantId: 1 });
db.imported.createIndex({ region: 1 });

// không có đơn nào qua kênh "fax": query trả 0 document, CBR sẽ được gọi
const q = { tenantId: "tBULK", region: "HN", channel: "fax" };

Đáp án đúng là region_1: 120.376 key thay vì 270.000.

hint region_1   : keys 120.376  docs 120.376  median 54 ms  (7 lần: 51–64)
hint tenantId_1 : keys 270.000  docs 270.000  median 108 ms (7 lần: 106–120)

Cách đo

Lập plan 200 lần (explain("queryPlanner"), mỗi lần một mẫu mới), đếm plan nào thắng, ghi lại ước lượng cho tenantId: "tBULK" mỗi khi nó có mặt. Làm với chunk (mặc định) rồi với random (tham số nội bộ, chỉ trong lab).

Kết quả thật

chunk (mặc định)   CBR gọi 200 lần, numPlansTiedCostEstimation +4
                   thắng: region_1 185 lần, tenantId_1 15 lần (7,5%)  ← sai
                   ước lượng tBULK (khi bị loại):
                     120.000 ×11 | 180.000 ×39 | 240.000 ×41 | 300.000 ×46
                     360.000 ×33 | 420.000 ×13 | 480.000 ×2
                   thời gian CBR trung bình 215 µs/lần (lấy mẫu 158 µs)

random             CBR gọi 200 lần, không hoà
                   thắng: region_1 200 lần, tenantId_1 0 lần
                   ước lượng tBULK: 231.250 – 307.813, tập trung quanh 270.000
                   thời gian CBR trung bình 649 µs/lần (lấy mẫu 578 µs)

Đọc kết quả

Nhìn cột ước lượng của chunk: mọi giá trị đều là bội số của 60.000. 60.000 là đúng 1/10 của 600.000. Mỗi chunk 38 document hoặc nằm trọn trong khối tBULK, hoặc nằm trọn ngoài nó, nên mỗi chunk đóng góp "0%" hoặc "10%" cho ước lượng. Ước lượng chỉ có 11 giá trị có thể (0, 60.000, ..., 600.000), và nó phụ thuộc vào việc bao nhiêu trong 10 chunk rơi vào nửa cuối collection.

collection trên đĩa (thứ tự chèn)
[ 300 tenant nhỏ ........ 330.000 ......][ tBULK tBULK tBULK ... 270.000 ...]
   ▲      ▲        ▲     ▲                  ▲         ▲            ▲
   chunk  chunk    chunk chunk              chunk     chunk        chunk
   → 7 chunk ngoài khối, 3 chunk trong khối → ước lượng tBULK = 3/10 × 600.000 = 180.000

Thật: 270.000. Nếu chỉ 1–2 chunk rơi vào khối: ước lượng 60.000–120.000, ngang hoặc
thấp hơn ước lượng cho HN (thật 120.376) → CBR có thể chọn tenantId_1 → 270.000 key, chậm gấp đôi.

[quan sát] Với chunk, CBR chọn sai 15 trên 200 lần (7,5%), và mỗi lần sai query chậm gấp đôi (108 ms so với 54 ms). Với random, mẫu gồm 384 document rời rạc nên khối liền nhau không làm lệch ước lượng: 0 lần sai, đổi lại thời gian lấy mẫu gấp khoảng 3,7 lần (578 µs so với 158 µs).

[chi tiết cài đặt] Việc "chunk" là các đoạn document liền nhau theo thứ tự lưu trữ là suy ra từ chính các con số ước lượng (bước 60.000 đúng bằng 1/10 collection), không phải từ tài liệu. Nó khớp với tên tham số và với dữ liệu, nhưng có thể đổi giữa các phiên bản.

Bài học không phải "chunk sampling dở": nó rẻ hơn nhiều lần và đúng trên dữ liệu rải đều. Bài học là ước lượng bằng mẫu có điểm mù phụ thuộc bố cục vật lý của dữ liệu: import hàng loạt, backfill, dữ liệu migrate. Chạy thử thì không có điểm mù kiểu này, nhưng như bài Query Planner & Plan Cache đã cho thấy, chạy thử có điểm mù riêng: nó chỉ nhìn đoạn đầu.

Cột mốc: Bạn đã biết sampling, heuristics và histogram lấy ước lượng từ đâu, và đo được một lần CBR chọn sai plan ra sao. Tiếp theo: CBR và plan cache; biết ranker nào chạy.

Hỏi & đáp