github-actions[bot] commented on code in PR #68480:
URL: https://github.com/apache/doris/pull/68480#discussion_r4091566728
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/model/Histogram.java:
##########
@@ -96,6 +113,18 @@ public static Histogram fromResultRow(ResultRow resultRow) {
}
histogramBuilder.setBuckets(buckets);
+ if (jsonObj.has("mcv_histogram") &&
jsonObj.get("mcv_histogram").isJsonObject()) {
+ JsonObject mcvObj = jsonObj.getAsJsonObject("mcv_histogram");
+ Map<Literal, Float> mcv =
StatisticsUtil.getHotValues(mcvObj.get("mcv").getAsString(), dataType);
Review Comment:
[P1] Decode every MCV entry that was persisted.
`StatisticsUtil.getHotValues` caps parsing with the loader thread's
current/default `hot_value_collect_count`, even though collection may have
stored a larger submitted count. Those discarded keys were excluded from the
residual histogram by the collection SQL, so they disappear from both
representations and their probability mass is reassigned incorrectly.
Deserialization must be driven by the payload, not an unrelated session/global
limit.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/HistogramTask.java:
##########
@@ -69,11 +105,12 @@ public void doExecute() throws Exception {
params.put("colName",
SqlUtils.getIdentSql(String.valueOf(info.colName)));
params.put("sampleRate", getSampleRateFunction());
params.put("maxBucketNum", String.valueOf(info.maxBucketNum));
+ params.put("mcvCount", String.valueOf(getHotValueCollectCount(info)));
- StringSubstitutor stringSubstitutor = new StringSubstitutor(params);
-
StatisticsUtil.execUpdate(stringSubstitutor.replace(ANALYZE_HISTOGRAM_SQL_TEMPLATE_TABLE));
+ StatisticsUtil.execUpdate(buildAnalyzeSql(params,
info.collectMcvHistogram));
Env.getCurrentEnv().getStatisticsCache().refreshHistogramSync(
Review Comment:
[P1] Make completion mean that the new histogram is actually published.
`refreshHistogramSync` ultimately starts an asynchronous Caffeine load and
discards its future; an immediate lookup can still be empty (the cache tests
compensate with a sleep). It also updates only this FE, unlike column-stat
publication, so followers can retain the old value until the 48-hour refresh.
Await the local load and broadcast/invalidate the histogram key on the other
FEs before a `WITH SYNC` analysis returns.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/BaseAnalysisTask.java:
##########
@@ -667,6 +668,13 @@ protected String castToNumeric(String colName) {
}
}
+ // The count the ANALYZE statement was submitted with; the default for a
job written before the
+ // count was kept, whose value is out of reach on this thread.
+ protected static int getHotValueCollectCount(AnalysisInfo info) {
+ return info.hotValueCollectCount > 0 ? info.hotValueCollectCount
Review Comment:
[P2] Preserve an explicit zero separately from legacy absence.
`hot_value_collect_count` accepts 0 and the job persists it, but this sentinel
replaces it with the worker thread's global default. A synchronous job can
therefore collect no MCVs while an asynchronous execution of the same submitted
setting collects the global count. Add presence/version information (or
disallow zero) rather than using `> 0` to distinguish old records.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/AnalysisManager.java:
##########
@@ -457,7 +461,10 @@ public void createTaskForEachColumns(AnalysisInfo jobInfo,
Map<Long, BaseAnalysi
TableIf table = jobInfo.getTable();
for (Pair<String, String> pair : jobColumns) {
AnalysisInfoBuilder colTaskInfoBuilder = new
AnalysisInfoBuilder(jobInfo);
- colTaskInfoBuilder.setAnalysisType(AnalysisType.FUNDAMENTALS);
+ // Per-column tasks are FUNDAMENTALS unless the job asked for a
histogram; INDEX is not a
+ // per-column analysis and is normalized away.
+ colTaskInfoBuilder.setAnalysisType(jobInfo.analysisType ==
AnalysisType.HISTOGRAM
Review Comment:
[P1] Reject or honor every histogram analysis scope before creating these
tasks. Four accepted routes do not produce the requested result: a rollup task
retains its index ID but both HistogramTask templates scan the unqualified
table without forcing that index, so the same scan can be stored under
different index keys; an explicit PARTITION request is retained in AnalysisInfo
but ignored by the SQL and by the storage key; `use.auto.analyzer=true` returns
a FUNDAMENTALS job; and external-table factories return fundamental tasks
although the command accepts HISTOGRAM. Either implement each route end to end
or reject it during validation so a successful ANALYZE cannot silently publish
the wrong scope (or no histogram at all).
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/cache/StatisticsCache.java:
##########
@@ -428,9 +429,18 @@ public ColumnStatistic getColumnStatistics(String colName,
ConnectContext ctx) {
if (shouldReturnUnknownStats(catalogId, schemaId, olapTable, ctx))
{
return ColumnStatistic.UNKNOWN;
}
- return doGetColumnStatistics(
+ ColumnStatistic columnStatistic = doGetColumnStatistics(
catalogId, schemaId, tableId, selectIndexId, colName, ctx
);
+ // the cached column stats object is shared, so attach the
histogram to a copy
+ if (ctx != null &&
ctx.getSessionVariable().isEnableHistogramJoinEstimation()
+ && !columnStatistic.isUnKnown) {
+ Histogram histogram = getHistogram(catalogId, schemaId,
tableId, selectIndexId, colName).orElse(null);
Review Comment:
[P1] Escape the histogram cache key before the loader embeds it in SQL. The
new loader substitutes raw `key.colName` into a quoted literal, whereas the
repository lookup escapes its constructed ID. Legal column names containing a
quote or backslash therefore make automatic histogram attachment fail even
though collection escaped the stored ID. Route this through the same escaping
helper as the repository path.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/HistogramTask.java:
##########
@@ -50,10 +51,45 @@ public class HistogramTask extends BaseAnalysisTask {
+ "FROM "
+ " ${dbName}.${tblName}";
+ // ANALYZE WITH HISTOGRAM + MCV: top-N hot values and residual histogram
in one scan.
+ private static final String ANALYZE_MCV_HISTOGRAM_SQL_TEMPLATE_TABLE =
"INSERT INTO "
+ + "${internalDB}.${histogramStatTbl} "
+ + "WITH src AS (SELECT ${colName} FROM ${dbName}.${tblName}), "
+ + "nn AS (SELECT COUNT(${colName}) AS c FROM src), "
+ + "hot AS (SELECT t.v, t.c FROM (SELECT ${colName} AS v, COUNT(*)
AS c FROM src "
+ + " WHERE ${colName} IS NOT NULL GROUP BY ${colName}) t, nn "
+ + " WHERE t.c / nn.c >= " +
StatisticsUtil.HOT_VALUE_MIN_RATIO_SQL
+ + " ORDER BY t.c DESC LIMIT ${mcvCount}), "
+ + "mcv AS (SELECT GROUP_CONCAT(CONCAT("
Review Comment:
[P1] Make the serialized MCV order deterministic. Ordering the `hot` CTE
chooses the top-N set but does not order rows consumed by `GROUP_CONCAT`; the
aggregate has no internal ORDER BY. The regression expects `hotValues[0]` to be
the hottest item, and nondeterminism also changes which values survive the
current parser cap. Add an explicit aggregate/input ordering with a stable
tie-breaker.
##########
fe/fe-core/src/main/java/org/apache/doris/catalog/InternalSchemaInitializer.java:
##########
@@ -341,6 +341,26 @@ public static void createTbl() throws UserException {
*/
createTable(getStatisticsCreateSql(StatisticConstants.PARTITION_STATISTIC_TBL_NAME,
Lists.newArrayList("catalog_id", "db_id", "tbl_id", "idx_id",
"part_name", "part_id", "col_id")));
+ /**
+ *CREATE TABLE IF NOT EXISTS
`internal`.`__internal_schema`.`histogram_statistics` (
+ * `id` varchar(4096) NOT NULL COMMENT "",
+ * `catalog_id` varchar(1024) NOT NULL COMMENT "",
+ * `db_id` varchar(1024) NOT NULL COMMENT "",
+ * `tbl_id` varchar(1024) NOT NULL COMMENT "",
+ * `idx_id` varchar(1024) NOT NULL COMMENT "",
+ * `col_id` varchar(1024) NOT NULL COMMENT "",
+ * `sample_rate` double NOT NULL COMMENT "",
+ * `buckets` varchar(65533) NOT NULL COMMENT "",
+ * `update_time` datetime NOT NULL COMMENT ""
+ * ) ENGINE = olap
+ * UNIQUE KEY(`id`, `catalog_id`, `db_id`, `tbl_id`, `idx_id`,
`col_id`)
+ * COMMENT "Doris internal statistics table, DO NOT MODIFY IT"
+ * DISTRIBUTED BY HASH(`id`, `catalog_id`, `db_id`, `tbl_id`,
`idx_id`, `col_id`)
+ * BUCKETS 7
+ * PROPERTIES ("replication_num" = "1")
+ */
+
createTable(getStatisticsCreateSql(StatisticConstants.HISTOGRAM_TBL_NAME,
Review Comment:
[P1] Add the new table to the complete statistics cleanup lifecycle. The
explicit table/database/index/column drop-stat paths and `StatisticsCleaner`
enumerate column/partition statistics only, so histogram rows survive
source-object deletion and accumulate indefinitely. They can also collide with
rerun assertions that query by column name. Every lifecycle operation that
removes existing statistics needs the matching histogram deletion.
##########
fe/fe-core/src/main/java/org/apache/doris/catalog/InternalSchemaInitializer.java:
##########
@@ -341,6 +341,26 @@ public static void createTbl() throws UserException {
*/
createTable(getStatisticsCreateSql(StatisticConstants.PARTITION_STATISTIC_TBL_NAME,
Lists.newArrayList("catalog_id", "db_id", "tbl_id", "idx_id",
"part_name", "part_id", "col_id")));
+ /**
+ *CREATE TABLE IF NOT EXISTS
`internal`.`__internal_schema`.`histogram_statistics` (
+ * `id` varchar(4096) NOT NULL COMMENT "",
+ * `catalog_id` varchar(1024) NOT NULL COMMENT "",
+ * `db_id` varchar(1024) NOT NULL COMMENT "",
+ * `tbl_id` varchar(1024) NOT NULL COMMENT "",
+ * `idx_id` varchar(1024) NOT NULL COMMENT "",
+ * `col_id` varchar(1024) NOT NULL COMMENT "",
+ * `sample_rate` double NOT NULL COMMENT "",
+ * `buckets` varchar(65533) NOT NULL COMMENT "",
+ * `update_time` datetime NOT NULL COMMENT ""
+ * ) ENGINE = olap
+ * UNIQUE KEY(`id`, `catalog_id`, `db_id`, `tbl_id`, `idx_id`,
`col_id`)
+ * COMMENT "Doris internal statistics table, DO NOT MODIFY IT"
+ * DISTRIBUTED BY HASH(`id`, `catalog_id`, `db_id`, `tbl_id`,
`idx_id`, `col_id`)
+ * BUCKETS 7
+ * PROPERTIES ("replication_num" = "1")
+ */
+
createTable(getStatisticsCreateSql(StatisticConstants.HISTOGRAM_TBL_NAME,
+ Lists.newArrayList("id", "catalog_id", "db_id", "tbl_id",
"idx_id", "col_id")));
Review Comment:
[P2] Apply the internal statistics replica policy to this table. It is
created with one replica, and the later `modifyTblReplicaCount` calls upgrade
the column, partition, and audit tables to three but omit
`histogram_statistics`. That leaves the newly default-consumed statistics less
durable than every peer internal table.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/HistogramTask.java:
##########
@@ -50,10 +51,45 @@ public class HistogramTask extends BaseAnalysisTask {
+ "FROM "
+ " ${dbName}.${tblName}";
+ // ANALYZE WITH HISTOGRAM + MCV: top-N hot values and residual histogram
in one scan.
+ private static final String ANALYZE_MCV_HISTOGRAM_SQL_TEMPLATE_TABLE =
"INSERT INTO "
+ + "${internalDB}.${histogramStatTbl} "
+ + "WITH src AS (SELECT ${colName} FROM ${dbName}.${tblName}), "
+ + "nn AS (SELECT COUNT(${colName}) AS c FROM src), "
+ + "hot AS (SELECT t.v, t.c FROM (SELECT ${colName} AS v, COUNT(*)
AS c FROM src "
+ + " WHERE ${colName} IS NOT NULL GROUP BY ${colName}) t, nn "
+ + " WHERE t.c / nn.c >= " +
StatisticsUtil.HOT_VALUE_MIN_RATIO_SQL
+ + " ORDER BY t.c DESC LIMIT ${mcvCount}), "
+ + "mcv AS (SELECT GROUP_CONCAT(CONCAT("
+ + " REPLACE(REPLACE(CAST(hot.v AS STRING), ':', '\\\\:'), ';',
'\\\\;'), "
+ + " ' :', ROUND(hot.c / nn.c, 4)), ' ;') AS s FROM hot, nn), "
Review Comment:
[P1] Preserve aggregate probability mass when serializing MCVs. Rounding
every entry to four decimals can create a large systematic error: 3,000 legal
values at ratio 0.00015 serialize as 0.0002, changing hot mass from 0.45 to
0.60, and JoinEstimation treats that rounded sum as exact when assigning
residual mass. Store adequate precision or compensate the residual from exact
aggregate counts.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/model/ColumnStatisticBuilder.java:
##########
@@ -59,6 +60,7 @@ public ColumnStatisticBuilder(ColumnStatistic
columnStatistic) {
this.original = columnStatistic.original;
this.updatedTime = columnStatistic.updatedTime;
this.hotValues = columnStatistic.hotValues;
+ this.histogram = columnStatistic.histogram;
Review Comment:
[P1] Do not implicitly preserve a distribution across value-changing
expressions. Many expression visitors copy a child with this constructor and
update only min/max, so `abs(-1)` still carries histogram/MCV key `-1` although
its output is `1`. A concrete consumer is:
```
Join(x = b.k)
├─ Project(abs(a.k) AS x)
│ └─ Scan A(a.k = -1, histogram at -1)
└─ Scan B(b.k = 1)
```
The default-on join estimator can conclude there is no overlap. Make
preservation opt-in for identity/order-preserving transforms, or
clear/transform both histogram and hot values in every value-changing visitor.
##########
fe/fe-core/src/main/java/org/apache/doris/catalog/InternalSchemaInitializer.java:
##########
@@ -566,6 +586,11 @@ private boolean created() {
return false;
}
+ optionalTable = db.getTable(StatisticConstants.HISTOGRAM_TBL_NAME);
Review Comment:
[P1] Do not publish statistics readiness before this required table exists.
`modifyColumnStatsTblSchema` sets `StatsTableSchemaValid=true` after checking
only the old column table, while this histogram-table check happens later in
the initializer loop; `statsTblAvailable()` also consults only the flag and
column table. During an upgrade, ANALYZE can pass its guard and target a table
that has not been created yet. Include all required tables in the readiness
condition and set the flag only after successful creation/validation.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/analysis/HistogramTask.java:
##########
@@ -50,10 +51,45 @@ public class HistogramTask extends BaseAnalysisTask {
+ "FROM "
+ " ${dbName}.${tblName}";
+ // ANALYZE WITH HISTOGRAM + MCV: top-N hot values and residual histogram
in one scan.
+ private static final String ANALYZE_MCV_HISTOGRAM_SQL_TEMPLATE_TABLE =
"INSERT INTO "
+ + "${internalDB}.${histogramStatTbl} "
+ + "WITH src AS (SELECT ${colName} FROM ${dbName}.${tblName}), "
+ + "nn AS (SELECT COUNT(${colName}) AS c FROM src), "
+ + "hot AS (SELECT t.v, t.c FROM (SELECT ${colName} AS v, COUNT(*)
AS c FROM src "
+ + " WHERE ${colName} IS NOT NULL GROUP BY ${colName}) t, nn "
+ + " WHERE t.c / nn.c >= " +
StatisticsUtil.HOT_VALUE_MIN_RATIO_SQL
+ + " ORDER BY t.c DESC LIMIT ${mcvCount}), "
+ + "mcv AS (SELECT GROUP_CONCAT(CONCAT("
+ + " REPLACE(REPLACE(CAST(hot.v AS STRING), ':', '\\\\:'), ';',
'\\\\;'), "
+ + " ' :', ROUND(hot.c / nn.c, 4)), ' ;') AS s FROM hot, nn), "
+ + "excl AS (SELECT HISTOGRAM(${colName}, ${maxBucketNum}) AS h
FROM src "
+ + " WHERE ${colName} NOT IN (SELECT v FROM hot)), "
+ + "fh AS (SELECT HISTOGRAM(${colName}, ${maxBucketNum}) AS h FROM
src) "
+ + "SELECT "
+ + " CONCAT(${tblId}, '-', ${idxId}, '-', '${colId}') AS id, "
+ + " ${catalogId} AS catalog_id, "
+ + " ${dbId} AS db_id, "
+ + " ${tblId} AS tbl_id, "
+ + " ${idxId} AS idx_id, "
+ + " '${colId}' AS col_id, "
+ + " ${sampleRate} AS sample_rate, "
+ + " JSON_INSERT(fh.h, '$.mcv_histogram', JSON_OBJECT("
Review Comment:
[P1] Keep the combined JSON within the `VARCHAR(65533)` storage contract.
This embeds hot string values in `mcv_histogram` while retaining them in the
full histogram, so previously storable endpoint JSON can overflow after the
default-on MCV section is added (for example, ten multi-KB singleton strings).
Add an encoded-byte budget/truncation policy that preserves probability
invariants, or use a storage type that can hold the documented payload.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -175,6 +179,7 @@ public Statistics visitOr(Or or, EstimationContext context)
{
colBuilder.setMinValue(union.getLow()).setMinExpr(union.getLowExpr())
.setMaxValue(union.getHigh()).setMaxExpr(union.getHighExpr())
.setNdv(union.getDistinctValues());
+ colBuilder.setHistogram(null);
Review Comment:
[P1] Repair all distribution representations for OR, including range
branches. Range visitors never register their slot in `keyColumns`, so `a < 10
OR a > 990` bypasses this block and retains the full 0..1000 histogram;
same-slot equality OR reaches the block but clears only the histogram while the
copied hot map can retain unrelated keys, and cross-slot OR leaves both
distributions untouched. For example:
```
Join(a.k = b.k)
├─ Filter(a.k < 10 OR a.k > 990)
│ └─ Scan A(a.k 0..1000)
└─ Filter(b.k = 500)
└─ Scan B
```
This publishes impossible middle-key mass. Track range keys and either union
compatible branch distributions or clear both histogram and hot values for
every affected slot.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -257,6 +262,11 @@ private Statistics estimateColumnLessThanConstant(LessThan
cp, DataType dataType
}
}
}
+ if (leftStats.histogram != null) {
Review Comment:
[P1] Clear or convert the histogram when temporarily converting VARCHAR
statistics to DATETIME. `tryConvertStringColStatsToDateColStats` copies the
VARCHAR histogram while changing min/max and hot values, then this code
intersects packed-string bucket doubles with datetime-unit bounds. For example:
```
Filter(s < '2025-06-01')
└─ Scan T(s VARCHAR ISO-date histogram)
```
A matching range can appear disjoint. `ExpressionEstimation.castMinMax`
already clears histograms for this domain change; apply the same invariant here
(or transform every bucket exactly).
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -893,6 +952,7 @@ public Statistics visitNot(Not not, EstimationContext
context) {
// 4. not A like XXX
// 5. not array_contains([xx, xx], xx)
colBuilder.setNumNulls(0);
+ colBuilder.setHistogram(originColStats.histogram);
Review Comment:
[P1] Keep distributions invalidated for `NOT LIKE`. LIKE correctly cannot
derive a histogram/hot map, but this complement path restores the original
histogram and, when the child map is null, all original hot values. For example:
```
Join(a.k = b.k)
├─ Filter(NOT(a.k LIKE 'a%'))
│ └─ Scan A(a.k has hot key 'apple')
└─ Scan B(b.k = 'apple')
```
The upper join sees a key the filter removed. Only restore/derive a
distribution for complements whose excluded support is represented exactly.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -1023,6 +1093,7 @@ public boolean isKeySlot(Expression expr) {
private Statistics estimateColumnEqualToColumn(Expression leftExpr,
ColumnStatistic leftStats,
Expression rightExpr, ColumnStatistic rightStats, boolean
keepNull, EstimationContext context) {
ColumnStatisticBuilder intersectBuilder = new
ColumnStatisticBuilder(leftStats);
+ intersectBuilder.setHistogram(null);
Review Comment:
[P1] Recompute or clear conditional hot ratios for column equality. This
clears the histogram, but the branch retains `min(leftRatio,rightRatio)` as if
it were already normalized to the filtered output. With asymmetric marginals, a
realizable result split 50/50 over keys 0 and 1 can be published as
`{0:.1,1:.1}`; `Histogram.fromHotValues` then invents 0.8 residual mass despite
NDV 2. A downstream consumer is:
```
Join(a.k = c.k)
├─ Filter(a.k = b.k)
│ └─ Scan T(asymmetric a/b marginals)
└─ Scan C(c.k = 0)
```
Normalize by the equality selectivity/row count, or invalidate the map.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -841,6 +889,17 @@ public Statistics visitInPredicate(InPredicate
inPredicate, EstimationContext co
selectivity =
newCompareExprStats.getHotValues().values().stream().mapToDouble(x -> x).sum();
}
}
+ if (compareExprStats.histogram != null &&
options.stream().allMatch(Literal.class::isInstance)) {
Review Comment:
[P1] Remove NULL and deduplicate literals before histogram IN arithmetic.
`NullLiteral#getDouble()` contributes numeric zero, `getValuesSelectivity` sums
every option, and the existing deduplication is intentionally skipped for lists
above 200. Thus `IN (NULL, 5)` can acquire key-zero mass and 201 copies of `5`
can saturate selectivity. A downstream case is:
```
Join(a.k = b.k)
├─ Filter(a.k IN (NULL, 5, 5, ...))
│ └─ Scan A
└─ Scan B
```
Normalize SQL-IN semantics before calling the histogram.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java:
##########
@@ -1113,6 +1184,7 @@ private Statistics
estimateColumnLessThanColumn(Expression leftExpr, ColumnStati
.setMinValue(leftRange.getLow())
.setNdv(leftStats.ndv * (leftAlwaysLessThanRightPercent +
leftOverlapPercent))
.setNumNulls(0)
+ .setHistogram(null)
Review Comment:
[P1] Invalidate hot values together with the histogram for column
inequalities. These branches copy the input hot map while narrowing
min/max/NDV, so excluded keys remain visible. For example:
```
Join(a.k = c.k)
├─ Filter(a.k < b.k)
│ └─ Scan T(a.k hot at 100, b.k = 50)
└─ Scan C(c.k = 100)
```
The upper join estimates an impossible match. Filter the hot map against the
derived condition when exact, otherwise clear it.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -595,65 +783,21 @@ private static void
updateJoinConditionColumnStatistics(Statistics inputStats, J
}
if (joinType.isInnerJoin() || joinType.isAsofInnerJoin()) {
ColumnStatisticBuilder builder = new
ColumnStatisticBuilder(leftColStats);
- builder.setNdv(Math.min(leftColStats.ndv, rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- builder.setHotValues(null);
- } else {
- builder.setHotValues(newHotValues);
- }
- }
- updatedCols.put(eqLeft, builder.build());
- updatedCols.put(eqRight, builder.build());
+ mergeJoinKeyStatistics(leftColStats, rightColStats, builder);
+ ColumnStatistic merged = builder.build();
Review Comment:
[P1] Derive ASOF-inner distributions while both input statistics are still
available. The ASOF estimator returns only probe-side column stats; this later
update looks up the absent build expression as UNKNOWN and the one-sided
fallback republishes the probe histogram even when build support reduced the
row count. For example:
```
Join(j.k = C.k)
├─ ASOF_LEFT_INNER(A.k = B.k)
│ ├─ Scan A(k = 0 or 1)
│ └─ Filter(B.k = 0)
└─ Scan C(k = 1)
```
The upper join sees key 1 although the ASOF build excluded it. Condition the
distribution before discarding the build map, or pass both original inputs into
this update.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -54,16 +63,182 @@ public class JoinEstimation {
private static double TRUSTABLE_UNIQ_THRESHOLD = 0.9;
private static double OUTER_JOIN_NULL_SUPPLELMENT_RATIO = 0.1;
+ private static final double MIN_JOIN_KEY_SELECTIVITY = 1e-12;
+
private static boolean shouldDecayRemainingUntrustConditions() {
ConnectContext connectContext = ConnectContext.get();
return connectContext == null || connectContext.getSessionVariable()
== null
||
connectContext.getSessionVariable().isEnableLowConfidenceEqJoinRemainingConditionDecay();
}
+ private static boolean isMcvJoinEstimationEnabled() {
+ ConnectContext ctx = ConnectContext.get();
+ return ctx != null && ctx.getSessionVariable() != null &&
ctx.getSessionVariable().isEnableMcvJoinEstimation();
+ }
+
+ private static boolean isHistogramJoinEstimationEnabled() {
+ ConnectContext ctx = ConnectContext.get();
+ return ctx != null && ctx.getSessionVariable() != null
+ && ctx.getSessionVariable().isEnableHistogramJoinEstimation();
+ }
+
private static void normalizeColumnStatistics(Statistics outputStats,
Statistics inputStats) {
outputStats.normalizeColumnStatistics(inputStats.getRowCount(), false);
}
+ /**
+ * Equi-join key selectivity as sum_v p_L(v) * p_R(v) over hot values and
histogram buckets.
+ * A side without a histogram is treated as one unbounded bucket. When
{@code joinedKeyStats}
+ * is non-null, also fill the join-key column stats for the output.
+ */
+ private static double estimateJoinKeySelectivity(ColumnStatistic
leftColStats, ColumnStatistic rightColStats,
+ ColumnStatisticBuilder joinedKeyStats) {
+ Histogram leftHistogram = getJoinHistogram(leftColStats);
+ Histogram rightHistogram = getJoinHistogram(rightColStats);
+ double leftNdv = Math.max(1, leftColStats.ndv);
+ double rightNdv = Math.max(1, rightColStats.ndv);
+ // Missing histogram: one unbounded bucket; selectivity falls back to
1/max(ndv).
+ Map<Literal, Float> leftHotValues = leftHistogram == null ?
Collections.emptyMap() : leftHistogram.mcv;
+ Map<Literal, Float> rightHotValues = rightHistogram == null ?
Collections.emptyMap() : rightHistogram.mcv;
+ List<Bucket> leftBuckets = leftHistogram == null ?
Collections.singletonList(
+ new Bucket(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
1, 0, leftNdv))
+ : leftHistogram.hasMcv() ? leftHistogram.mcvBuckets :
leftHistogram.buckets;
+ List<Bucket> rightBuckets = rightHistogram == null ?
Collections.singletonList(
+ new Bucket(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
1, 0, rightNdv))
+ : rightHistogram.hasMcv() ? rightHistogram.mcvBuckets :
rightHistogram.buckets;
+ double leftCountToRatio = Math.max(0, 1 -
leftHotValues.values().stream().mapToDouble(r -> r).sum())
+ /
StatsMathUtil.nonZeroDivisor(leftBuckets.stream().mapToDouble(b ->
b.count).sum());
+ double rightCountToRatio = Math.max(0, 1 -
rightHotValues.values().stream().mapToDouble(r -> r).sum())
+ /
StatsMathUtil.nonZeroDivisor(rightBuckets.stream().mapToDouble(b ->
b.count).sum());
+
+ Map<Literal, Double> outputHotValues = new LinkedHashMap<>();
+ double selectivity = 0;
+
+ for (Map.Entry<Literal, Float> entry : leftHotValues.entrySet()) {
+ Literal rightKey = StatisticsUtil.findHotValueKey(rightHotValues,
entry.getKey());
+ double rightRatio = rightKey != null ? rightHotValues.get(rightKey)
+ : rightHistogram != null ?
getBucketValueRatio(rightBuckets, entry.getKey(), rightCountToRatio)
+ : getNdvValueRatio(rightColStats, entry.getKey(),
Math.max(leftNdv, rightNdv));
+ if (rightRatio > 0) {
+ double ratio = entry.getValue() * rightRatio;
+ outputHotValues.put(entry.getKey(), ratio);
+ selectivity += ratio;
+ }
+ }
+ for (Map.Entry<Literal, Float> entry : rightHotValues.entrySet()) {
+ if (StatisticsUtil.findHotValueKey(leftHotValues, entry.getKey())
!= null) {
+ continue;
+ }
+ double leftRatio = leftHistogram != null
+ ? getBucketValueRatio(leftBuckets, entry.getKey(),
leftCountToRatio)
+ : getNdvValueRatio(leftColStats, entry.getKey(),
Math.max(leftNdv, rightNdv));
+ if (leftRatio > 0) {
+ double ratio = entry.getValue() * leftRatio;
+ outputHotValues.put(entry.getKey(), ratio);
+ selectivity += ratio;
+ }
+ }
+ // Bucket-bucket overlap (sorted merge).
+ List<Bucket> outputBuckets = Lists.newArrayList();
+ DataType leftType = leftHistogram == null ? NullType.INSTANCE :
leftHistogram.getDataType();
+ DataType rightType = rightHistogram == null ? NullType.INSTANCE :
rightHistogram.getDataType();
+ int leftIndex = 0;
+ int rightIndex = 0;
+ while (leftIndex < leftBuckets.size() && rightIndex <
rightBuckets.size()) {
Review Comment:
[P1] Exclude the union of both sides' hot keys from residual bucket overlap.
With left `{0:.5,1:.25,2:.25}`/hot 0 and right `{0:.25,1:.5,2:.25}`/hot 1,
hot-to-residual terms add .25, then the 0..2 residual buckets add .125 even
though their only common residual key is 2. The result is .375 instead of .3125:
```
Join(A.k = B.k)
├─ Scan A(hot 0; residual 1,2)
└─ Scan B(hot 1; residual 0,2)
```
Build residual buckets after removing both hot-key sets, or subtract those
cross-hot contributions from the overlap.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -54,16 +63,182 @@ public class JoinEstimation {
private static double TRUSTABLE_UNIQ_THRESHOLD = 0.9;
private static double OUTER_JOIN_NULL_SUPPLELMENT_RATIO = 0.1;
+ private static final double MIN_JOIN_KEY_SELECTIVITY = 1e-12;
+
private static boolean shouldDecayRemainingUntrustConditions() {
ConnectContext connectContext = ConnectContext.get();
return connectContext == null || connectContext.getSessionVariable()
== null
||
connectContext.getSessionVariable().isEnableLowConfidenceEqJoinRemainingConditionDecay();
}
+ private static boolean isMcvJoinEstimationEnabled() {
+ ConnectContext ctx = ConnectContext.get();
+ return ctx != null && ctx.getSessionVariable() != null &&
ctx.getSessionVariable().isEnableMcvJoinEstimation();
+ }
+
+ private static boolean isHistogramJoinEstimationEnabled() {
+ ConnectContext ctx = ConnectContext.get();
+ return ctx != null && ctx.getSessionVariable() != null
+ && ctx.getSessionVariable().isEnableHistogramJoinEstimation();
+ }
+
private static void normalizeColumnStatistics(Statistics outputStats,
Statistics inputStats) {
outputStats.normalizeColumnStatistics(inputStats.getRowCount(), false);
}
+ /**
+ * Equi-join key selectivity as sum_v p_L(v) * p_R(v) over hot values and
histogram buckets.
+ * A side without a histogram is treated as one unbounded bucket. When
{@code joinedKeyStats}
+ * is non-null, also fill the join-key column stats for the output.
+ */
+ private static double estimateJoinKeySelectivity(ColumnStatistic
leftColStats, ColumnStatistic rightColStats,
+ ColumnStatisticBuilder joinedKeyStats) {
+ Histogram leftHistogram = getJoinHistogram(leftColStats);
+ Histogram rightHistogram = getJoinHistogram(rightColStats);
+ double leftNdv = Math.max(1, leftColStats.ndv);
+ double rightNdv = Math.max(1, rightColStats.ndv);
+ // Missing histogram: one unbounded bucket; selectivity falls back to
1/max(ndv).
+ Map<Literal, Float> leftHotValues = leftHistogram == null ?
Collections.emptyMap() : leftHistogram.mcv;
+ Map<Literal, Float> rightHotValues = rightHistogram == null ?
Collections.emptyMap() : rightHistogram.mcv;
+ List<Bucket> leftBuckets = leftHistogram == null ?
Collections.singletonList(
Review Comment:
[P1] Bound a synthesized side by its known min/max instead of making it
infinite. If A has statistics 0..9 but no histogram and B has a histogram at
100..109, this bucket creates overlap and then assigns B's 100..109 output
shape to both keys:
```
Join(j.k = c.k)
├─ Join(A.k = B.k)
│ ├─ Scan A(k 0..9, no histogram)
│ └─ Scan B(k histogram 100..109)
└─ Scan C
```
The first join is empty, yet the chained plan receives a populated
distribution. Use each column's finite bounds (and type) in the fallback bucket.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -595,65 +783,21 @@ private static void
updateJoinConditionColumnStatistics(Statistics inputStats, J
}
if (joinType.isInnerJoin() || joinType.isAsofInnerJoin()) {
ColumnStatisticBuilder builder = new
ColumnStatisticBuilder(leftColStats);
- builder.setNdv(Math.min(leftColStats.ndv, rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- builder.setHotValues(null);
- } else {
- builder.setHotValues(newHotValues);
- }
- }
- updatedCols.put(eqLeft, builder.build());
- updatedCols.put(eqRight, builder.build());
+ mergeJoinKeyStatistics(leftColStats, rightColStats, builder);
+ ColumnStatistic merged = builder.build();
+ updatedCols.put(eqLeft, merged);
+ updatedCols.put(eqRight, merged);
Review Comment:
[P1] Do not write a cast-domain distribution under the raw child slot. For
`CAST(A.s AS DATE)=B.d`, expression estimation clears A's VARCHAR histogram,
then the one-sided merge can build a DATE histogram from B; stripping the Cast
here assigns those DATE buckets to raw `A.s`. A later raw join compares
incompatible encodings:
```
Join(j.s = C.s)
├─ Join(CAST(A.s AS DATE) = B.d)
└─ Scan C(s VARCHAR)
```
Only map merged distributions back when the expression and slot share the
same value domain, otherwise keep them on the expression or clear them.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/StatsCalculator.java:
##########
@@ -1240,7 +1241,21 @@ private ColumnStatistic getColumnStatistic(
builder.merge(pcolStats);
}
}
- return builder.toColumnStatistics();
+ ColumnStatistic columnStatistic = builder.toColumnStatistics();
+ if (connectContext != null
+ &&
connectContext.getSessionVariable().isEnableHistogramJoinEstimation()) {
+ Histogram histogram =
Env.getCurrentEnv().getStatisticsCache().getHistogram(
+ olapTableStatistics.catalogId,
olapTableStatistics.schemaId,
+ olapTableStatistics.tableId,
olapTableStatistics.selectIndexId, colName).orElse(null);
+ if (histogram != null && !histogram.hasCollapsedBuckets())
{
+ // the histogram is table level, the merged column
stats cover the
+ // selected partitions only
+ columnStatistic = new
ColumnStatisticBuilder(columnStatistic).setHistogram(histogram
Review Comment:
[P1] Do not attach a table-level histogram to a proper partition subset.
Min/max clipping cannot remove holes from unselected partitions or repair
partition correlation for non-partition columns, and the fallback path is
broader still. For example:
```
Join(A.k = B.k)
├─ Scan A PARTITION(p1) // table histogram covers p1+p2
└─ Scan B
```
A value present only in p2 remains inside the clipped range and creates a
false join. Collect/key histograms per partition and merge selected partitions,
or omit the histogram whenever scan statistics are partition-scoped.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -595,65 +783,21 @@ private static void
updateJoinConditionColumnStatistics(Statistics inputStats, J
}
if (joinType.isInnerJoin() || joinType.isAsofInnerJoin()) {
ColumnStatisticBuilder builder = new
ColumnStatisticBuilder(leftColStats);
- builder.setNdv(Math.min(leftColStats.ndv, rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- builder.setHotValues(null);
- } else {
- builder.setHotValues(newHotValues);
- }
- }
- updatedCols.put(eqLeft, builder.build());
- updatedCols.put(eqRight, builder.build());
+ mergeJoinKeyStatistics(leftColStats, rightColStats, builder);
+ ColumnStatistic merged = builder.build();
+ updatedCols.put(eqLeft, merged);
+ updatedCols.put(eqRight, merged);
} else if (joinType.isLeftOuterJoin() ||
joinType.isAsofLeftOuterJoin()) {
ColumnStatisticBuilder rightBuilder = new
ColumnStatisticBuilder(rightColStats);
- rightBuilder.setNdv(Math.min(leftColStats.ndv,
rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- rightBuilder.setHotValues(null);
- } else {
- rightBuilder.setHotValues(newHotValues);
- }
- }
+ mergeJoinKeyStatistics(leftColStats, rightColStats,
rightBuilder);
Review Comment:
[P1] Clear or derive preserved-key distributions for every non-inner join.
Semi/anti branches change only NDV, so they can retain keys removed by
existence filtering; outer/ASOF-outer branches leave preserved-side ratios
unchanged even though build multiplicity can reweight them. These stale shapes
feed later joins:
```
Join(j.k = C.k)
├─ LeftSemi/LeftAnti/LeftOuter(A.k = B.k)
└─ Scan C
```
A semi join may remove a key entirely, while an outer join can turn a 1:1
key ratio into 100:1. Establish the same post-join distribution invariant for
semi, anti, left/right/full outer, and ASOF-outer branches.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -595,65 +783,21 @@ private static void
updateJoinConditionColumnStatistics(Statistics inputStats, J
}
if (joinType.isInnerJoin() || joinType.isAsofInnerJoin()) {
ColumnStatisticBuilder builder = new
ColumnStatisticBuilder(leftColStats);
- builder.setNdv(Math.min(leftColStats.ndv, rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- builder.setHotValues(null);
- } else {
- builder.setHotValues(newHotValues);
- }
- }
- updatedCols.put(eqLeft, builder.build());
- updatedCols.put(eqRight, builder.build());
+ mergeJoinKeyStatistics(leftColStats, rightColStats, builder);
+ ColumnStatistic merged = builder.build();
+ updatedCols.put(eqLeft, merged);
Review Comment:
[P1] Intersect distributions for equality conjuncts that share a key instead
of letting the last map write win. Each conjunct is estimated from unchanged
input stats and deferred into `updatedCols`, so predicate order determines the
final support:
```
Join(j.k = C.k)
├─ Join(A.k = B.x AND A.k = B.y)
└─ Scan C(k = 2)
```
If the first equality restricts A.k to `{1}` and the second to `{2}`, the
join is empty but the last assignment can publish `{2}`. Apply each update to
the accumulated statistics or intersect per-expression candidates before
committing them.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/model/Histogram.java:
##########
@@ -172,12 +201,213 @@ public static JsonArray getBucketsJson(List<Bucket>
buckets) {
return bucketsJsonArray;
}
- public double size() {
- if (CollectionUtils.isEmpty(buckets)) {
+ /** Build a histogram from column hot values when stored histogram has no
MCV section. */
+ public static Histogram fromHotValues(ColumnStatistic colStats) {
+ Map<Literal, Float> hotValues =
StatisticsUtil.getHotValuesWithOriginalThreshold(colStats.hotValues,
+ Math.max(1, colStats.ndv));
+ if (hotValues == null) {
+ return null;
+ }
+ if (colStats.histogram != null && !colStats.histogram.hasMcv()) {
+ Histogram withoutHotValues =
colStats.histogram.removeValues(hotValues.keySet());
+ return new Histogram(colStats.histogram.dataType, 0, 0,
Collections.emptyList(), hotValues,
+ withoutHotValues == null ? Collections.emptyList() :
withoutHotValues.buckets);
+ }
+ double hotRatio = hotValues.values().stream().mapToDouble(r ->
r).sum();
+ List<Bucket> buckets = hotRatio >= 1 ? Collections.emptyList() :
Lists.newArrayList(new Bucket(
+ colStats.minValue, colStats.maxValue, 1 - hotRatio, 0,
Math.max(1, colStats.ndv - hotValues.size())));
+ Type dataType = colStats.minExpr != null ? colStats.minExpr.getType()
: Type.NULL;
+ return new Histogram(dataType, 0, 0, Collections.emptyList(),
hotValues, buckets);
+ }
+
+ public boolean hasMcv() {
+ return !mcv.isEmpty();
+ }
+
+ /** True if a multi-ndv bucket collapses to equal bounds (e.g. ints beyond
2^53). */
+ public boolean hasCollapsedBuckets() {
+ for (Bucket bucket : Iterables.concat(buckets, mcvBuckets)) {
+ if (bucket.ndv > 1 && bucket.upper <= bucket.lower) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Restrict histogram to [lower, upper]; open interval when {@code
inclusive} is false. */
+ public Histogram intersectRange(double lower, double upper, boolean
inclusive) {
+ DataType type = getDataType();
+ if (!inclusive) {
+ lower = nextValueAbove(lower, type);
+ upper = nextValueBelow(upper, type);
+ }
+ return rebuild(intersectBuckets(buckets, lower, upper, type),
mcvInRange(lower, upper),
+ intersectBuckets(mcvBuckets, lower, upper, type));
+ }
+
+ private static double nextValueAbove(double value, DataType type) {
Review Comment:
[P1] Carry exact typed strict endpoints instead of advancing encoded
doubles. `Math.nextUp(yyyymmdd)` converts back to the same DATE, and integers
above 2^53 lose adjacency (`2^53 + 1 == 2^53` as double). Thus:
```
Join(f.k = B.k)
├─ Filter(A.k > 9007199254740992)
└─ Scan B(k = 9007199254740992)
```
can retain the excluded boundary; DATE strict predicates have the same
problem. Represent inclusivity separately or use type-aware literal
successor/predecessor operations, including collision checks for singleton
buckets.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/StatsCalculator.java:
##########
@@ -1618,10 +1654,13 @@ public Statistics computeUnion(Union union,
List<Statistics> childStats) {
unionHotValues.entrySet().stream()
.sorted((a, b) -> Float.compare(b.getValue(),
a.getValue()))
.limit(maxHotValueCount)
- .forEach(e -> resultHotValues.put(e.getKey(), (float)
(e.getValue() / unionRowCount)));
+ .forEach(e -> resultHotValues.put(e.getKey(),
+ (float) (e.getValue() / unionNotNullRowCount)));
if (!resultHotValues.isEmpty()) {
colStatsBuilder.setHotValues(resultHotValues);
}
+ // the histograms of the children are not merged
+ colStatsBuilder.setHistogram(null);
Review Comment:
[P1] Apply this distribution invalidation to the other row-changing
operators. UNION clears child histograms here, but EXCEPT, INTERSECT, and
GENERATE copy histogram/hot values even though EXCEPT can remove an entire hot
key and GENERATE can reweight keys by correlated expansion. For example:
```
Join(x.k = B.k)
├─ Except(Scan A, Scan R) // or Generate(A.k, correlated array)
└─ Scan B
```
The upper join consumes support/ratios that no longer describe the output.
Derive them exactly or clear both histogram and hot values in every parallel
operator.
##########
fe/fe-core/src/test/java/org/apache/doris/nereids/stats/StatsCalculatorTest.java:
##########
@@ -366,11 +368,13 @@ public void testHashJoinSkew() {
ColumnStatistic icStatsOut = outputStats.findColumnStatistics(ic);
Assertions.assertEquals(5, icStatsOut.getHotValues().size());
+ // the join key keeps every value skewed on one side that the other
side holds too, so
+ // "1" of ia and "3", "4" of ib join "2" rather than only the values
hot on both sides
ColumnStatistic iaStatsOut = outputStats.findColumnStatistics(ia);
- Assertions.assertEquals(1, iaStatsOut.getHotValues().size());
+ Assertions.assertEquals(4, iaStatsOut.getHotValues().size());
Review Comment:
[P1] Install and restore an enabled `ConnectContext` for this assertion.
`isMcvJoinEstimationEnabled()` requires a thread-local context, but this test
class does not create one here, so production code takes the legacy
intersection path; that path yields one common hot key, not the four asserted
on this line. Without setting the session switch, the changed unit test should
fail rather than exercise the new MCV merge.
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/model/Histogram.java:
##########
@@ -172,12 +201,213 @@ public static JsonArray getBucketsJson(List<Bucket>
buckets) {
return bucketsJsonArray;
}
- public double size() {
- if (CollectionUtils.isEmpty(buckets)) {
+ /** Build a histogram from column hot values when stored histogram has no
MCV section. */
+ public static Histogram fromHotValues(ColumnStatistic colStats) {
+ Map<Literal, Float> hotValues =
StatisticsUtil.getHotValuesWithOriginalThreshold(colStats.hotValues,
+ Math.max(1, colStats.ndv));
+ if (hotValues == null) {
+ return null;
+ }
+ if (colStats.histogram != null && !colStats.histogram.hasMcv()) {
+ Histogram withoutHotValues =
colStats.histogram.removeValues(hotValues.keySet());
+ return new Histogram(colStats.histogram.dataType, 0, 0,
Collections.emptyList(), hotValues,
+ withoutHotValues == null ? Collections.emptyList() :
withoutHotValues.buckets);
+ }
+ double hotRatio = hotValues.values().stream().mapToDouble(r ->
r).sum();
+ List<Bucket> buckets = hotRatio >= 1 ? Collections.emptyList() :
Lists.newArrayList(new Bucket(
+ colStats.minValue, colStats.maxValue, 1 - hotRatio, 0,
Math.max(1, colStats.ndv - hotValues.size())));
+ Type dataType = colStats.minExpr != null ? colStats.minExpr.getType()
: Type.NULL;
+ return new Histogram(dataType, 0, 0, Collections.emptyList(),
hotValues, buckets);
+ }
+
+ public boolean hasMcv() {
+ return !mcv.isEmpty();
+ }
+
+ /** True if a multi-ndv bucket collapses to equal bounds (e.g. ints beyond
2^53). */
+ public boolean hasCollapsedBuckets() {
+ for (Bucket bucket : Iterables.concat(buckets, mcvBuckets)) {
+ if (bucket.ndv > 1 && bucket.upper <= bucket.lower) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /** Restrict histogram to [lower, upper]; open interval when {@code
inclusive} is false. */
+ public Histogram intersectRange(double lower, double upper, boolean
inclusive) {
+ DataType type = getDataType();
+ if (!inclusive) {
+ lower = nextValueAbove(lower, type);
+ upper = nextValueBelow(upper, type);
+ }
+ return rebuild(intersectBuckets(buckets, lower, upper, type),
mcvInRange(lower, upper),
+ intersectBuckets(mcvBuckets, lower, upper, type));
+ }
+
+ private static double nextValueAbove(double value, DataType type) {
+ return type.isIntegralType() ? value + 1 : Math.nextUp(value);
+ }
+
+ private static double nextValueBelow(double value, DataType type) {
+ return type.isIntegralType() ? value - 1 : Math.nextDown(value);
+ }
+
+ private Map<Literal, Float> mcvInRange(double lower, double upper) {
+ Map<Literal, Float> result = Maps.newLinkedHashMap();
+ for (Map.Entry<Literal, Float> entry : mcv.entrySet()) {
+ double value = entry.getKey().getDouble();
+ if (value >= lower && value <= upper) {
+ result.put(entry.getKey(), entry.getValue());
+ }
+ }
+ return result;
+ }
+
+ private static List<Bucket> intersectBuckets(List<Bucket> source, double
lower, double upper, DataType type) {
+ List<Bucket> result = Lists.newArrayList();
+ for (Bucket bucket : source) {
+ double newLower = Math.max(bucket.lower, lower);
+ double newUpper = Math.min(bucket.upper, upper);
+ if (newLower > newUpper) {
+ continue;
+ }
+ double fraction = bucket.coveredFraction(newLower, newUpper, type);
+ result.add(new Bucket(newLower, newUpper, bucket.count * fraction,
0, bucket.ndv * fraction));
+ }
+ return result;
+ }
+
+ /** Drop the given values from MCV/buckets. Null if nothing remains. */
+ public Histogram removeValues(Collection<Literal> values) {
+ Map<Literal, Float> newMcv = Maps.newLinkedHashMap(mcv);
+ List<Bucket> newBuckets = copyBuckets(buckets);
+ List<Bucket> newMcvBuckets = copyBuckets(mcvBuckets);
+ for (Literal value : values) {
+ removeValue(newBuckets, value.getDouble());
+ Literal key = StatisticsUtil.findHotValueKey(newMcv, value);
+ if (key != null) {
+ newMcv.remove(key);
+ } else {
+ removeValue(newMcvBuckets, value.getDouble());
+ }
+ }
+ return rebuild(newBuckets, newMcv, newMcvBuckets);
+ }
+
+ private static List<Bucket> copyBuckets(List<Bucket> source) {
+ List<Bucket> result = Lists.newArrayList();
+ for (Bucket bucket : source) {
+ result.add(new Bucket(bucket.lower, bucket.upper, bucket.count, 0,
bucket.ndv));
+ }
+ return result;
+ }
+
+ private static void removeValue(List<Bucket> buckets, double value) {
+ for (int i = 0; i < buckets.size(); i++) {
+ Bucket bucket = buckets.get(i);
+ if (value < bucket.lower || value > bucket.upper) {
+ continue;
+ }
+ if (bucket.lower == bucket.upper || bucket.ndv <= 1) {
+ buckets.remove(i);
+ } else {
+ bucket.count -= bucket.count / bucket.ndv;
Review Comment:
[P1] Do not leave an excluded interior value inside the bucket bounds. This
decrements count/NDV only; later `getValueSelectivity` and join overlap still
treat every value between the unchanged endpoints as present. For example:
```
Join(a.k = b.k)
├─ Filter(NOT(a.k = 5))
│ └─ Scan A(bucket 1..10)
└─ Scan B(b.k = 5)
```
The upper join assigns positive mass to an impossible value. Split the
bucket around the removed point when the type supports it, or invalidate the
histogram when an exact hole cannot be represented.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -595,65 +783,21 @@ private static void
updateJoinConditionColumnStatistics(Statistics inputStats, J
}
if (joinType.isInnerJoin() || joinType.isAsofInnerJoin()) {
ColumnStatisticBuilder builder = new
ColumnStatisticBuilder(leftColStats);
- builder.setNdv(Math.min(leftColStats.ndv, rightColStats.ndv));
- // update hot values
- if (leftColStats.getHotValues() != null &&
rightColStats.getHotValues() != null) {
- Map<Literal, Float> newHotValues = Maps.newHashMap();
- for (Literal literal :
leftColStats.getHotValues().keySet()) {
- if (rightColStats.getHotValues().containsKey(literal))
{
- newHotValues.put(literal,
Math.min(leftColStats.getHotValues().get(literal),
-
rightColStats.getHotValues().get(literal)));
- }
- }
- if (newHotValues.isEmpty()) {
- builder.setHotValues(null);
- } else {
- builder.setHotValues(newHotValues);
- }
- }
- updatedCols.put(eqLeft, builder.build());
- updatedCols.put(eqRight, builder.build());
+ mergeJoinKeyStatistics(leftColStats, rightColStats, builder);
Review Comment:
[P1] Publish the correct output null mass for both equality modes. The
builder inherits left `numNulls`: for ordinary `=`, those rows were excluded
and the joined keys must have zero nulls; for `<=>`, cardinality includes the
null-null product, but the output records only the left input count instead of
the pair mass. This compounds in chained plans:
```
Join(j.k = C.k) Join(j.k <=> C.k)
├─ Join(A.k = B.k) ├─ Join(A.k <=> B.k)
└─ Scan C └─ Scan C
```
The next selectivity applies an invented non-null reduction in the first
case and can underestimate all-null chains by orders of magnitude in the
second. Pass the predicate mode and derived output cardinality/null-pair count
into the merge.
--
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]
