Cost-Based Ranker (P1/3): Cardinality, khi nào CBR vào việc, CBR tính gì

Bài này trả lời một câu hỏi: khi chạy thử không phân định được plan, MongoDB làm gì? Câu trả lời là MongoDB 8.3 chuyển sang ước lượng.

Bài có 3 Part:

• P1 (Part này): Cardinality, khi nào CBR vào việc, CBR tính gì.
• P2: Nguồn ước lượng và ba thí nghiệm.
• P3: CBR và plan cache; biết ranker nào chạy.

Bài Query Planner & Plan Cache kết luận rằng MongoDB không đoán, nó chạy thử. Mỗi candidate plan được làm vài bước, plan nào ra kết quả nhanh nhất thì thắng. Cách này không cần thống kê, và nó chỉ nhìn đoạn đầu.

Nhưng nếu chạy thử xong mà không plan nào ra được kết quả nào thì sao? Với một query trả về 0 document, mọi plan đều có productivity bằng 0. Từ MongoDB 8.3, đây là lúc planner có thể chuyển sang cách thứ hai: ước lượng. Nó đoán mỗi plan sẽ phải đọc bao nhiêu key, bao nhiêu document, quy ra chi phí, rồi chọn plan rẻ nhất. Bộ phận làm việc đó là cost-based ranker (CBR). Con số nó đoán là cardinality.

Bài này mở CBR ra trên MongoDB 8.3.11: khi nào nó được gọi, nó đoán bằng gì, đoán sai bao nhiêu, và một lần đoán sai đủ để chọn plan chậm gấp đôi rồi ghi vào plan cache.

Bài này nằm ở đâu

• Cần biết trước: Query Planner & Plan Cache (candidate plan, trial period, works/score, plan cache với Missing/Inactive/Active, replanning), Index Fundamentals (selectivity, IXSCAN + FETCH)
• Giới thiệu: query cardinality (khác selectivity và relationship cardinality), cardinality estimation, cost model, luật chuyển từ multi-planner sang CBR trên 8.3, query đủ điều kiện, sampling/heuristics/histogram, sai số ước lượng, CBR và plan cache, metrics.query.cbr, costEstimate/cardinalityEstimate/estimatesMetadata, planner dựa trên thống kê của PostgreSQL
• Dẫn tới: Query Execution Engine

Môi trường lab: MongoDB 8.3.11 chạy trong Docker (image mongo:8, standalone), giới hạn 2 CPU, 3 GB RAM, WiredTiger cache 1 GB, máy host Apple M4. Container riêng mongo-lab-14, database lab14. Trong lúc đo, container lab của vài bài khác cũng chạy trên cùng máy host, nên thời gian có nhiễu. Bài báo cáo median và luôn kèm keysExamined/docsExamined, vốn không bị nhiễu. Số nào không đo thì ghi là minh hoạ.

Như các bài trước, mỗi khẳng định quan trọng có nhãn:

• [tài liệu]: tài liệu chính thức của MongoDB mô tả. Có thể dựa vào.
• [quan sát]: đo được trong lab này. Đúng với 8.3.11, nên kiểm lại trên phiên bản của bạn.
• [chi tiết cài đặt]: cách server đang làm hiện nay (tham số nội bộ, không có trong tài liệu). Không phải cam kết API, có thể đổi giữa các bản vá.
• [hình dung]: mô hình đơn giản để dễ nhớ.

Bài này dùng [chi tiết cài đặt] nhiều hơn mọi bài trước, vì tài liệu 8.3 về CBR không công bố luật chuyển giao, kích thước mẫu hay tham số điều khiển nào.

Ý chính

Trên 8.3, planner vẫn bắt đầu bằng chạy thử như trước. Nếu sau một trial ngắn có plan ra kết quả hoặc chạy xong, plan đó thắng như cũ. Nếu không plan nào ra được gì, MongoDB gọi CBR. CBR lấy mẫu vài trăm document, đếm xem bao nhiêu document trong mẫu khớp với từng điều kiện, rồi nhân lên thành ước lượng cardinality: số key, số document đi qua từng stage. Từ đó nó tính chi phí của từng plan và chọn plan rẻ nhất. Plan được chọn vào cùng plan cache như mọi plan khác. Ước lượng tốt cho điều kiện phổ biến, mù với điều kiện hiếm, và có thể lệch hẳn khi dữ liệu nằm thành khối trên đĩa.

Hình dung trước: khi cả hai shipper về tay không

Quay lại công ty giao hàng của bài Query Planner & Plan Cache. Quản lý cử hai shipper chạy thử hai tuyến, ai giao được nhiều kiện hơn trên mỗi km thì thắng.

Hôm nay có một kiểu đơn lạ: "giao cho khách lớn nhất, ở quận 1, bằng xe tải lạnh". Công ty không có xe tải lạnh, nên không kiện nào giao được. Hết giờ thử, hai shipper về tay không, "kiện trên mỗi km" đều bằng 0. Nhưng vẫn phải chọn một tuyến, vì muốn chắc chắn "không có kiện nào" thì vẫn phải đi hết một tuyến.

Quản lý đổi cách. Anh vào kho, rút ngẫu nhiên 380 phiếu giao hàng, đếm xem bao nhiêu phiếu thuộc "khách lớn nhất", bao nhiêu phiếu ở "quận 1". Từ đó anh đoán: tuyến theo khách sẽ phải ghé khoảng 300.000 điểm, tuyến theo quận khoảng 500.000 điểm. Anh chọn tuyến ít điểm hơn.

Hai chi tiết sẽ quay lại suốt bài:

• 380 phiếu thì không thấy được thứ hiếm. Một khách chỉ có 0,1% số phiếu thường không có mặt trong mẫu. Quản lý sẽ đoán "khách này có 0 phiếu".
• Cách rút phiếu quan trọng. Nếu anh rút 10 xấp, mỗi xấp 38 phiếu liền nhau, và một khách lớn được nhập kho một lần nên nằm gọn trong vài xấp, thì rút trúng hay trượt mấy xấp đó làm ước lượng nhảy vọt.

Đời thực                                  MongoDB
────────────────────────────────────      ─────────────────────────────────────────
hai shipper chạy thử                      multi-planner, trial ngắn
cả hai về tay không                       không plan nào ra kết quả, không plan nào EOF
rút 380 phiếu trong kho                   sampling (lấy mẫu document)
"tuyến này khoảng 300.000 điểm"           cardinalityEstimate của IXSCAN
quy số điểm ra tiền xăng                  cost model → costEstimate
chọn tuyến rẻ nhất                        CBR chọn plan có costEstimate thấp nhất
rút 10 xấp liền nhau                      chunk sampling (cách lấy mẫu mặc định trên 8.3.11)

[hình dung] Con số 380 và chuyện "10 xấp" là quan sát trong lab, không phải hằng số được tài liệu công bố.

Ba nghĩa của chữ "cardinality", và selectivity

Chữ "cardinality" xuất hiện ở ba chỗ trong series, và lẫn chúng là nhầm lẫn phổ biến nhất khi đọc về CBR.

Hai khái niệm đầu dính nhau: cardinality ≈ selectivity × số document. Nhưng cardinality là của một stage trong một plan: IXSCAN và FETCH phía trên có cardinality khác nhau vì FETCH còn lọc thêm, nên explain ghi cardinalityEstimate theo từng stage. Relationship cardinality là chuyện schema, không liên quan tới planner.

Cardinality estimation (CE) là việc đoán query cardinality trước khi chạy, phần khó nhất của CBR.

Mental model: đường đi của một query trên 8.3

find(filter)
   │
   ▼
tra plan cache ── Active ──► dùng plan đã cache (CBR không tham gia)
   │
   │ Missing / Inactive
   ▼
sinh candidate plans (≥ 2)
   │
   ▼
trial ngắn: ~10.000 works chia đều cho các plan
   │
   ├── có plan ra kết quả hoặc chạy hết (EOF) ──► multi-planner chọn như cũ
   │
   └── không plan nào ra gì
            │
            ▼
       CBR: lấy mẫu ~380 document
            │
            ▼
       cardinalityEstimate cho từng stage
            │
            ▼
       costEstimate cho từng plan → chọn plan rẻ nhất
            │
            ▼
plan thắng ──► ghi vào plan cache (cùng một cache, cùng luật Inactive/Active)

Các con số ~10.000 works và ~380 document là [quan sát] trong lab, đo ở các phần sau. Hai ý cần giữ suốt bài: CBR là phương án dự phòng, đại đa số query trên 8.3 không chạm tới nó; và CBR chỉ đổi cách chọn plan, còn cách chạy và cách nhớ plan vẫn như cũ.

Setup và dataset

Dữ liệu phải lệch thì ước lượng mới đáng bàn.

MongoDB version : 8.3.11 (mongo:8, standalone)
Hardware        : Apple M4 host; container 2 CPU, 3 GB RAM
Configuration   : --wiredTigerCacheSizeGB 1, mọi tham số planner để mặc định
Dataset         : lab14.orders, 1.000.000 document, avgObjSize 145 byte
                  145,2 MB chưa nén, 41,3 MB trên đĩa
Indexes         : _id_ (10,5 MB), tenantId_1 (7,1 MB), status_1 (5,0 MB),
                  createdAt_1 (11,7 MB), total_1 (5,7 MB), region_1 (5,1 MB)

// trích gen.js: PRNG mulberry32 seed 14, 100 lần insertMany x 10.000 document
docs.push({
  tenantId: tenant(rnd()),          // t0000 30%, t0001 10%, t0002 5%, 497 tenant còn lại chia đều
  userId:   "u" + String(Math.floor(rnd() * 5000)).padStart(5, "0"),
  status:   status(rnd()),          // 70% completed, 10% cancelled, 10% pending, ~9,95% refunded, 0,05% disputed
  region:   region(rnd()),          // HCM 50%, HN 30%, 8 vùng khác chia 20%
  channel:  t === "t0000" ? "b2b"   // tenant lớn nhất CHỈ bán b2b: hai field tương quan hoàn toàn
                          : (rnd() < 0.6 ? "web" : "app"),
  createdAt: new Date(END - Math.floor(Math.pow(rnd(), 2) * 365 * DAY)),  // dồn về gần đây
  total:    Math.round(Math.exp(rnd() * rnd() * 9)) * 10000                // đuôi dài: đa số nhỏ, vài đơn rất lớn
});

Phân bố thật, đếm bằng countDocuments:

tenantId : t0000 300.422 | t0001 100.194 | t0002 50.191 | mỗi tenant nhỏ ~1.100 (t0042: 1.084)
status   : completed 699.223 | refunded 100.142 | pending 100.085 | cancelled 100.072 | disputed 478
region   : HCM 500.348 | HN 299.159 | mỗi vùng nhỏ ~25.000 (KH: 25.159)
channel  : web 419.565 | b2b 300.422 (toàn bộ là t0000) | app 280.013
createdAt: 1 ngày gần nhất 52.819 | 30 ngày 287.293
total    : >= 20 triệu 12.746 | >= 70 triệu 125 | lớn nhất 80.930.000

Field channel không có index. { tenantId: "t0000", channel: "web" } không bao giờ khớp vì tenant đó chỉ bán b2b: đúng kiểu query trả 0 document mà multi-planner bó tay.

Khi nào multi-planner giao việc cho CBR

Tài liệu nói gì

[tài liệu] Từ MongoDB 8.3, cơ chế chọn plan mặc định cho các query đủ điều kiện là multi-planning có CBR làm dự phòng. Trong một trial ngắn, multi-planner cố tìm một plan trả được kết quả. Nếu không tìm được, MongoDB áp một bộ quy tắc để quyết định tiếp tục multi-planning hay để CBR đánh giá từng node bằng hàm chi phí và ước lượng cardinality, rồi chọn plan có tổng chi phí thấp nhất. Hiện tại MongoDB chỉ gọi CBR cho một lượng nhỏ query. Cả hai cơ chế ghi plan thắng vào cùng plan cache.

Tài liệu không liệt kê "bộ quy tắc" đó, cũng không định nghĩa "query đủ điều kiện". Phần còn lại là đo.

Thí nghiệm 1: trial ngắn dài bao nhiêu?

Query trả về 0 document, có hai candidate: createdAt_1 với một khoảng thời gian chứa đúng k key, và tenantId_1 với 300.422 key. Cho k tăng dần rồi xem bộ đếm metrics.query.cbr.count trong serverStatus có nhích không.

const x = db.orders.find({}, { createdAt: 1 }).sort({ createdAt: -1 }).skip(k - 1).limit(1).next().createdAt;
db.orders.find({ tenantId: "t0000", channel: "web", createdAt: { $gte: x } }).explain("allPlansExecution");

k (key của createdAt_1)   CBR được gọi   works trong trial
2.000                      không          createdAt_1 2.001 (EOF), tenantId_1 2.001
4.900                      không          createdAt_1 4.901 (EOF), tenantId_1 4.901
5.100                      có             tenantId_1 dừng ở 5.000; createdAt_1 chưa xong
8.000 / 20.000 / 100.000   có             tenantId_1 dừng ở 5.000

Với ba candidate, mỗi plan dừng ở 3.333 works. Với bốn candidate, 2.500.

[quan sát] Trial ngắn có budget (số works tối đa được phép dùng) khoảng 10.000 works, chia đều cho các candidate. Nếu trong budget đó có plan chạy hết (EOF) hoặc trả được kết quả, multi-planner tự quyết như trước. Chỉ khi mọi plan đều chưa ra gì và chưa xong, CBR mới được gọi. Trong cả bốn lần CBR được gọi ở trên, nó chọn createdAt_1, đúng plan rẻ hơn.

[chi tiết cài đặt] Con số 10.000 khớp với tham số nội bộ internalQueryPlanEvaluationWorks (giá trị 10000 trong lab). Luật "chỉ gọi CBR khi trial không ra kết quả" khớp với giá trị của tham số automaticCEPlanRankingStrategy: "CBRForNoMultiplanningResults". Cả hai không có trong trang tham số của tài liệu.

Trên thực tế, query gặp CBR là query có từ hai candidate, mà không candidate nào tìm được kết quả đầu tiên trong vài nghìn works: kiểm tra tồn tại ("có đơn nào như thế này không?"), điều kiện mâu thuẫn do dữ liệu tương quan, tìm kiếm không có kết quả.

Query nào đủ điều kiện

Để xem CBR có thể xử lý dạng query nào, lab tạm chuyển sang chế độ "CBR cho mọi query" (tham số nội bộ internalQueryCBRCEMode: "samplingCE", nói ở thí nghiệm 3, chỉ dùng trong lab) rồi xem cbr.count có tăng không.

[quan sát] Kiểm lại ở chế độ mặc định với filter trả 0 document: find, find + sort, aggregate $match + $sort + $limit đều làm cbr.count tăng 1; aggregate $match + $group thì không. Trong lab, CBR đi cùng classic engine, pipeline chạy SBE không có ước lượng nào.

CBR tính gì: từ cardinality tới cost

Query Q6 trả về 0 document vì t0000 không có đơn web:

db.orders.find({ tenantId: "t0000", status: "completed", channel: "web" }).explain("queryPlanner");

cbr: count +1, choseWinningPlan +1, numPlans +2, micros 480, samplingMicros 359
win : FETCH <- IXSCAN(tenantId_1)
rej : FETCH <- IXSCAN(status_1)
rej : FETCH{card=0 cost=1446.97 ce=Sampling} <- IXSCAN(status_1){card=684210.5 cost=298.01 ce=Sampling}
exec: nReturned 0, keys 300.422, docs 300.422, 137 ms

[tài liệu] Các trường ước lượng mới từ 8.3.3:

• cardinalityEstimate: số document hoặc key mà stage ước lượng sẽ trả ra. IXSCAN status_1 được đoán 684.210 key (thật: 699.223). FETCH phía trên đoán 0 document (thật: 0), vì trong mẫu không document nào vừa completed vừa t0000 vừa web.
• costEstimate: chi phí theo đơn vị trừu tượng, không phải mili giây. CBR chọn plan có costEstimate cấp cao nhất thấp nhất. IXSCAN có thêm numKeysEstimate.
• estimatesMetadata.ceSource: nguồn ước lượng. Tài liệu liệt kê sampling, heuristics, mixed, metadata, code; output thật viết "Sampling".

status_1 xuất hiện hai lần trong rejectedPlans. [quan sát] Lần đầu là candidate của trial ngắn, không có ước lượng; lần sau là candidate CBR đã định giá. Plan thắng thì không mang ước lượng trong explain ở chế độ mặc định, dù chính CBR chọn nó.

Cost tỉ lệ với cardinality. [quan sát] Trong mọi output của lab, cost của IXSCAN xấp xỉ cardinality × 0,000436, cost của FETCH (tính cả IXSCAN bên dưới) gấp khoảng 4,9 lần cost của IXSCAN đó: mô hình chi phí ở đây chủ yếu là "đọc bao nhiêu key, fetch bao nhiêu document". Hệ số cụ thể không được công bố. Điều đáng nhớ: sai cardinality thì sai cost theo đúng tỉ lệ đó.

                cardinality ước lượng     ×  hệ số chi phí   =  costEstimate
IXSCAN status_1    684.210 key                (mỗi key)           298
FETCH              ← 684.210 lần fetch        (mỗi document)      1.447   ← plan này bị loại
FETCH ← IXSCAN tenantId_1  321.053 key       ...                 679     ← plan thắng

(Dòng tenantId_1 lấy từ một lần chạy cùng query ở chế độ chỉ-CBR trong lab, vì explain mặc định không in ước lượng của plan thắng.)

[quan sát] Ở lab của bài Query Planner & Plan Cache (mongo-lab-08, database lab08), một query tương tự ước lượng 715.789 key completed (thật 700.317), chạy lại ra 694.737: mỗi lần lập plan là một mẫu mới.

Cột mốc: Bạn đã có thể phân biệt ba nghĩa của cardinality, nói khi nào multi-planner gọi CBR, và giải thích cost tỉ lệ với cardinality ra sao. Tiếp theo: Nguồn ước lượng và ba thí nghiệm.

Hỏi & đáp