Repository navigation
Commit 1322847
committed
[feature](fe) Add history-based optimizer statistics with structural struct-info keys
### What problem does this solve?
The nereids optimizer estimates a plan from catalog statistics alone, so a query whose data distribution
or predicate selectivity the catalog cannot describe (a skewed join key, a selective range, a filter
whose matching rows are known from previous executions) is estimated from heuristics. This change adds
a history-based optimizer (HBO): the statistics a qualifying execution actually observed are published
as learned entries and reused by the next query whose plan is the same, and an administrator can pin a
value for a plan node.
A plan is identified by the struct info of its memo group: a tree description of the node kinds, the
normalized expressions, the scan identities and the children. Two literal modes are keyed - the exact
one and the constant agnostic one which folds the literals of a predicate - and the key is the sha256 of
the structural identity of that tree, not of its printed form, so a table name, an alias or a literal
which carries a character of the printed grammar cannot stand for another field. The scan token records
the table id, the relation alias, the index and the selected partitions, which is what turns a
constant-agnostic key into an entry which is only applied to the same data state.
The read side matches a learned entry by its fingerprint and then validates it against the input table
statistics the entry recorded (rows read per scan) and against the current data state (visible version,
row count, partitions), so a stale or drifted entry is not applied. A published entry carries the
predicates of the scans it measured, the grouping definitions and the join conditions, so two queries
which differ in a predicate the key folds cannot share a count. Manual management is served by
`HBO SET/SHOW/DELETE STATISTICS` (pinned entries), `HBO SET LEARNED STATISTICS` (tests and experts),
`hbo_persist_pinned_to_internal_db` (pinned entries survive a restart) and `SET show_hbo_fingerprint`
(EXPLAIN prints the key and the struct of every node, with the verdict of the pinned and learned
entries). Regression suites cover injection, drift, learned reuse, the legacy configs and persistence.
### Release note
Adds history-based optimizer statistics: learned statistics are published after qualifying executions
and reused by later queries with the same plan, pinned statistics can be managed with `HBO ... STATISTICS`
statements and persisted to `__internal_schema`, and `EXPLAIN` can print the plan key together with the
statistics which were applied.
### Check List (For Author)
- Test: Unit Test + Regression test
- Unit: the `org.apache.doris.nereids.stats` package (struct-info golden corpus: 76 plan cases and
51 text cases, both regenerated and asserted; scan identity, freshness, guards, pinned race,
expansion keys, input merge) plus the HBO command suites, 200 cases pass.
- Regression: a FE rebuilt from this branch runs `query_p0/hbo` to its baseline (19 suites, the 8
`legacy/*` suites fail because the environment does not support them); the injection, drift,
learned, persistence and display suites pass.
- Behavior changed: Yes - the optimizer reuses history for a matched plan, and EXPLAIN can print the
key of a node with `SET show_hbo_fingerprint=true`.
- Does this need documentation: Yes - the HBO statements, the session variables and the internal table
need a manual (the PR body of the squashed change describes the semantics).1 parent dea1b99 commit 1322847
116 files changed
Lines changed: 16383 additions & 463 deletions
File tree
- fe
- fe-common/src/main/java/org/apache/doris/common
- fe-core/src
- main/java/org/apache/doris
- catalog
- common/profile
- nereids
- cost
- memo
- parser
- processor/post/materialize
- rules/rewrite
- stats
- trees
- expressions/functions
- udf
- plans
- commands
- logical
- physical
- util
- qe
- statistics
- hbo
- util
- test
- java/org/apache/doris
- common/profile
- nereids
- stats
- trees/plans/commands
- statistics/hbo
- resources
- fe-sql-parser/src/main/antlr4/org/apache/doris/nereids
- regression-test
- data/query_p0/hbo
- suites/query_p0/hbo
- legacy
Some content is hidden
Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
2332 | 2332 | | |
2333 | 2333 | | |
2334 | 2334 | | |
| 2335 | + | |
| 2336 | + | |
| 2337 | + | |
| 2338 | + | |
| 2339 | + | |
| 2340 | + | |
| 2341 | + | |
| 2342 | + | |
| 2343 | + | |
| 2344 | + | |
| 2345 | + | |
| 2346 | + | |
| 2347 | + | |
| 2348 | + | |
| 2349 | + | |
| 2350 | + | |
| 2351 | + | |
| 2352 | + | |
| 2353 | + | |
| 2354 | + | |
| 2355 | + | |
| 2356 | + | |
| 2357 | + | |
| 2358 | + | |
| 2359 | + | |
| 2360 | + | |
| 2361 | + | |
| 2362 | + | |
| 2363 | + | |
| 2364 | + | |
| 2365 | + | |
| 2366 | + | |
| 2367 | + | |
| 2368 | + | |
| 2369 | + | |
| 2370 | + | |
| 2371 | + | |
| 2372 | + | |
| 2373 | + | |
| 2374 | + | |
| 2375 | + | |
| 2376 | + | |
| 2377 | + | |
| 2378 | + | |
| 2379 | + | |
| 2380 | + | |
| 2381 | + | |
| 2382 | + | |
| 2383 | + | |
| 2384 | + | |
| 2385 | + | |
| 2386 | + | |
| 2387 | + | |
| 2388 | + | |
| 2389 | + | |
| 2390 | + | |
| 2391 | + | |
| 2392 | + | |
| 2393 | + | |
| 2394 | + | |
2335 | 2395 | | |
2336 | 2396 | | |
2337 | 2397 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
2112 | 2112 | | |
2113 | 2113 | | |
2114 | 2114 | | |
| 2115 | + | |
| 2116 | + | |
| 2117 | + | |
| 2118 | + | |
2115 | 2119 | | |
2116 | 2120 | | |
2117 | 2121 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
390 | 390 | | |
391 | 391 | | |
392 | 392 | | |
| 393 | + | |
393 | 394 | | |
394 | 395 | | |
395 | 396 | | |
396 | | - | |
| 397 | + | |
397 | 398 | | |
398 | 399 | | |
399 | 400 | | |
400 | 401 | | |
401 | 402 | | |
402 | 403 | | |
403 | 404 | | |
404 | | - | |
| 405 | + | |
405 | 406 | | |
406 | 407 | | |
407 | 408 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
822 | 822 | | |
823 | 823 | | |
824 | 824 | | |
| 825 | + | |
| 826 | + | |
| 827 | + | |
| 828 | + | |
| 829 | + | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
| 838 | + | |
| 839 | + | |
| 840 | + | |
| 841 | + | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
| 845 | + | |
| 846 | + | |
| 847 | + | |
| 848 | + | |
| 849 | + | |
| 850 | + | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
825 | 855 | | |
826 | 856 | | |
827 | 857 | | |
| |||
835 | 865 | | |
836 | 866 | | |
837 | 867 | | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
| 875 | + | |
| 876 | + | |
| 877 | + | |
| 878 | + | |
838 | 879 | | |
839 | 880 | | |
840 | 881 | | |
| |||
864 | 905 | | |
865 | 906 | | |
866 | 907 | | |
| 908 | + | |
| 909 | + | |
| 910 | + | |
| 911 | + | |
| 912 | + | |
| 913 | + | |
867 | 914 | | |
868 | 915 | | |
869 | 916 | | |
| |||
0 commit comments