Skip to content

Commit 1322847

Browse files
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

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎fe/fe-common/src/main/java/org/apache/doris/common/Config.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2332,6 +2332,66 @@ public class Config extends ConfigBase {
23322332
+ "cache entries.")
23332333
public static int hbo_plan_info_cache_num = 1000;
23342334

2335+
/**
2336+
* Threshold of the "extremely small filter estimate" guard used by pinned entries injected with
2337+
* {@code TYPE FILTER_SMALL}: such an entry is only applied while the optimizer's own filter
2338+
* estimate E satisfies {@code E <= 1} or {@code E <= inputRows * hbo_filter_small_ratio}, i.e.
2339+
* while the pathological regime that motivated the injection still holds. Hot mutable.
2340+
*/
2341+
@ConfField(mutable = true, description = "The default setting is 0.001. Relative threshold below which "
2342+
+ "the optimizer's own filter estimate counts as 'extremely small' for HBO FILTER_SMALL "
2343+
+ "pinned entries.")
2344+
public static double hbo_filter_small_ratio = 0.001;
2345+
2346+
/**
2347+
* Tolerance of a hbo entry against data growth. A hbo key no longer contains the visible version
2348+
* or the row count of its tables, so an entry keeps matching while a table grows; the read side
2349+
* applies an entry while the row count of the data it was measured on changed by at most this
2350+
* ratio (|now - recorded| / recorded). Beyond it the entry is not applied and the query falls
2351+
* back to the optimizer estimation. A non-positive value disables the tolerance, i.e. an entry
2352+
* is only applied while the recorded data state is exactly the current one. Hot mutable.
2353+
*/
2354+
@ConfField(mutable = true, description = "The default setting is 0.1. Relative row count change of the data "
2355+
+ "an injected HBO entry was measured on, up to which the entry may still be applied; 0 or "
2356+
+ "less means the recorded data state has to match exactly.")
2357+
public static double hbo_row_count_change_ratio = 0.1;
2358+
2359+
/**
2360+
* Maximum number of manually injected (pinned) hbo statistics entries kept per FE. When the
2361+
* limit is exceeded the least recently used pinned entry is evicted (LRU); pinned entries are
2362+
* otherwise not expired automatically. A non-positive value disables the LRU bound
2363+
* (unbounded), matching the other hbo caches. Takes effect at FE start (not hot-mutable).
2364+
*/
2365+
@ConfField(description = "The default setting is 5000. Maximum number of manually injected "
2366+
+ "(pinned) hbo statistics entries kept per FE; exceeding the limit evicts the least "
2367+
+ "recently used entry; a non-positive value disables the bound (unbounded). Takes "
2368+
+ "effect at FE start (not hot-mutable).")
2369+
public static int hbo_pinned_stats_cache_num = 5000;
2370+
2371+
/**
2372+
* Persist manually injected (pinned) hbo statistics into the internal database table
2373+
* __internal_schema.hbo_statistics, so that they survive FE restarts. In-memory pinned
2374+
* statistics stay authoritative; changes are written through synchronously (best effort)
2375+
* and each FE loads the table in the background at start-up (HboPinnedStatisticsLoader).
2376+
* Persistence applies to SET/DELETE issued
2377+
* while this config is true: entries SET while it is false are not persisted, and entries
2378+
* DELETEd while it is false keep their stored rows. A FE loads the table into memory at most
2379+
* once per process (in the background at start-up, retried until it succeeds), so rows deleted
2380+
* while it is false reappear only for a FE whose one-time load is still pending (e.g. right after
2381+
* FE start). On that load, existing in-memory entries win over the stored
2382+
* snapshot; deletions issued while this config is true during the pending load are honored —
2383+
* rows of theirs that the load sees are best-effort removed from the table again, and they
2384+
* reappear after a FE restart only if that removal also fails. In general, rows whose
2385+
* best-effort removal from the table fails (during or after the one-time load, e.g. because
2386+
* the internal table is temporarily unreachable) reappear after a FE restart; re-issue the
2387+
* DELETE once the table is reachable. A FE never refreshes entries SET by other FEs during
2388+
* its lifetime.
2389+
*/
2390+
@ConfField(mutable = true, description = "The default setting is true. When true, HBO SET/DELETE STATISTICS "
2391+
+ "entries are persisted into __internal_schema.hbo_statistics and reloaded after FE "
2392+
+ "restart.")
2393+
public static boolean hbo_persist_pinned_to_internal_db = true;
2394+
23352395
/**
23362396
* Maximum number of events to poll in each RPC.
23372397
*/

‎fe/fe-core/src/main/java/org/apache/doris/catalog/Env.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2112,6 +2112,10 @@ protected void startNonMasterDaemonThreads() {
21122112
workloadRuntimeStatusMgr.start();
21132113
admissionControl.start();
21142114
splitSourceManager.start();
2115+
2116+
// loads the pinned hbo statistics this FE persisted in the internal database (a no-op when
2117+
// the feature is off); it runs in the background so that no user query pays for the load
2118+
hboPlanStatisticsManager.startPinnedStatisticsLoader();
21152119
}
21162120

21172121
private void transferToNonMaster(FrontendNodeType newType) {

‎fe/fe-core/src/main/java/org/apache/doris/common/profile/Profile.java‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -390,18 +390,19 @@ public void publishHboPlanStatistics(String queryId, List<TPlanNodeRuntimeStatsI
390390
Map<Integer, PhysicalPlan> idToPlanMap = planInfoProvider.getIdToPlanMap(queryId);
391391
Map<PhysicalPlan, Integer> planToIdMap = planInfoProvider.getPlanToIdMap(queryId);
392392
Map<RelationId, Set<Expression>> scanToFilterMap = planInfoProvider.getScanToFilterMap(queryId);
393+
Map<Integer, String> nodeFingerprints = planInfoProvider.getNodeIdToFingerprintMap(queryId);
393394

394395
if (!idToPlanMap.isEmpty() && idToPlanMap.size() == planToIdMap.size()) {
395396
Map<PlanNodeAndHash, PlanStatisticsWithInputInfo> curPlanStatistics = HboUtils.genPlanStatisticsMap(
396-
idToPlanMap, planToIdMap, scanToFilterMap, curPlanNodeRuntimeStats);
397+
idToPlanMap, planToIdMap, scanToFilterMap, curPlanNodeRuntimeStats, nodeFingerprints);
397398
Map<PlanNodeAndHash, RecentRunsPlanStatistics> recentRunsPlanStatisticsMap =
398399
hboPlanStatisticsProvider.getHboPlanStats(
399400
curPlanStatistics.keySet().stream().collect(Collectors.toList()));
400401

401402
// update plan statistics
402403
Map<PlanNodeAndHash, RecentRunsPlanStatistics> newPlanStatistics = curPlanStatistics.entrySet().stream()
403404
.filter(entry -> entry.getKey().getHash().isPresent()
404-
&& entry.getValue().getInputTableInfo().getInputTableStatistics().isPresent())
405+
&& entry.getValue().getInputTableInfo().hasInputTables())
405406
.collect(Collectors.toMap(
406407
Map.Entry::getKey,
407408
entry -> {

‎fe/fe-core/src/main/java/org/apache/doris/common/profile/RuntimeProfile.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -822,6 +822,36 @@ public void write(DataOutput output) throws IOException {
822822
Text.writeString(output, GsonUtils.GSON.toJson(this));
823823
}
824824

825+
/** The rows a scan read, as its nested counter profiles report them (see the caller). */
826+
private void fillInputRowsFromChildProfiles(TPlanNodeRuntimeStatsItem item) {
827+
if (item.getInputRows() != 0) {
828+
return;
829+
}
830+
childLock.readLock().lock();
831+
try {
832+
for (Pair<RuntimeProfile, Boolean> pair : childList) {
833+
RuntimeProfile child = pair.first;
834+
if (!"CustomCounters".equals(child.getName()) && !"Scanner".equals(child.getName())) {
835+
continue;
836+
}
837+
for (Map.Entry<String, Counter> entry : child.counterMap.entrySet()) {
838+
if (!(entry.getValue() instanceof AggCounter)) {
839+
continue;
840+
}
841+
String counterName = entry.getKey();
842+
if ("RowsRead".equals(counterName) || "ScanRows".equals(counterName)) {
843+
item.setInputRows(((AggCounter) entry.getValue()).sum.getValue());
844+
if (item.getInputRows() != 0) {
845+
return;
846+
}
847+
}
848+
}
849+
}
850+
} finally {
851+
childLock.readLock().unlock();
852+
}
853+
}
854+
825855
private TPlanNodeRuntimeStatsItem toTPlanNodeRuntimeStatsItem() {
826856
TPlanNodeRuntimeStatsItem item = new TPlanNodeRuntimeStatsItem();
827857
item.setNodeId(this.nodeId());
@@ -835,6 +865,17 @@ private TPlanNodeRuntimeStatsItem toTPlanNodeRuntimeStatsItem() {
835865
case "RowsProduced":
836866
item.setOutputRows(value.sum.getValue());
837867
break;
868+
case "RowsRead":
869+
case "ScanRows":
870+
// a scan operator reports the rows it read under these names; a learned entry has
871+
// to record the rows a scan read, and "InputRows" is only registered for sink
872+
// operators, so a scan which records zero here would be judged stale on the next
873+
// identical query (the learned comparison reads the recorded scan rows). The
874+
// case of "InputRows" below wins when a node reports both.
875+
if (item.getInputRows() == 0) {
876+
item.setInputRows(value.sum.getValue());
877+
}
878+
break;
838879
case "InputRows":
839880
item.setInputRows(value.sum.getValue());
840881
if (isBuildSinkOperator) {
@@ -864,6 +905,12 @@ private TPlanNodeRuntimeStatsItem toTPlanNodeRuntimeStatsItem() {
864905
}
865906
}
866907

908+
// a scan operator registers the rows it read on its "CustomCounters" child profile
909+
// (`ADD_COUNTER(custom_profile(), "ScanRows", ...)`), while the operator node itself reports
910+
// none: without them the published learned entry records zero rows for its input table, and the
911+
// freshness comparison has nothing to compare
912+
fillInputRowsFromChildProfiles(item);
913+
867914
// Handle runtime profile structure
868915
/*
869916
- RuntimeFilterInfo: sum 0, avg 0, max 0, min 0

0 commit comments

Comments
 (0)