englefly opened a new pull request, #69322:
URL: https://github.com/apache/doris/pull/69322
# History-based optimizer statistics for the nereids planner
## 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 PR adds a history-based optimizer (HBO):
- **Plan identity.** A plan node 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. The key
is the sha256 of the **structural identity** of that tree (length-prefixed
fields), 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 - the constant agnostic key is then only applied to
the same data state.
- **Read side.** A learned entry is matched by fingerprint and validated
against the input table
statistics it 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.** `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, with
generation-bounded deletions), and `SET show_hbo_fingerprint` prints the
key and the struct of every
node in EXPLAIN together with the verdict of the pinned and learned
entries.
## Release note
- Learned statistics are published after qualifying executions and reused by
later queries with the same
plan; pinned statistics can be managed with the `HBO ... STATISTICS`
statements, 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, 51
text cases, regenerated and asserted), scan identity, freshness,
learned guards, pinned race,
expansion keys, input-table 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.
## Note
This PR is the squashed version of #67549 (one commit per branch tip instead
of the incremental history),
opened with the same tree so the review can be done on a single change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
