github-actions[bot] commented on code in PR #69322: URL: https://github.com/apache/doris/pull/69322#discussion_r4548948253
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,240 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +package org.apache.doris.nereids.stats; + +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.ExprId; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.NullSafeEqual; +import org.apache.doris.nereids.trees.expressions.Slot; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.algebra.Join; + +import com.google.common.hash.Hashing; + +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; + +/** + * Canonical description and fingerprint of the equality conditions of a join, used as the key of + * manually injected join expansion entries ({@code HBO SET EXPANSION}). + * + * <p>The join type and the residual (non equality) conditions take part in the key next to the hash + * (equality) conjuncts, because the injected factor replaces the output rows of the whole join: an + * inner join which matches nothing and a left outer join of the same columns produce very different + * row counts, and a selective residual predicate changes the output by orders of magnitude. The + * shape of both sub trees is still excluded, so one injected entry stays reusable by every query + * which joins the same columns with the same join type and the same residual conditions. + * + * <p>The canonical form is {@code JE{<join type>;EqualTo(...);...}} with the pairs and the residual + * conditions sorted; a pair is rendered by {@link GroupStructInfo#normalizeExpression(Expression)} + * which already sorts the two operands of an equality (equality is commutative), so {@code a = b} + * and {@code b = a} collapse. A residual condition is rendered with its literal in both modes, + * because it decides how many partner rows a row finds ({@code b > c + 1} is not {@code b > c + 2}). + */ +public class HboJoinConditions { + private static final String PREFIX = "JE{"; + private static final String SEP = ";"; + + private HboJoinConditions() { + } + + /** True when the injected expansion of this join type is applicable at all. */ + public static boolean isExpansionApplicable(JoinType joinType) { + // semi / anti / mark style joins can never produce more rows than their left input, and + // asof joins match at most one row per left row, so expansion can not happen there + return joinType == JoinType.INNER_JOIN + || joinType == JoinType.LEFT_OUTER_JOIN + || joinType == JoinType.RIGHT_OUTER_JOIN + || joinType == JoinType.FULL_OUTER_JOIN; + } + + /** + * Canonical string of the conditions of a join, empty when the join has no expansion key at all. + * + * <p>The key describes the <b>equality</b> conditions only: the factor is the fan out of the equi + * join, and the non equality conditions are applied by the estimator on top of it (see + * {@code JoinEstimation}), so a join with a residual predicate uses the factor of its equality pair + * and the residual keeps its own selectivity. The operands have to name the columns of the tables + * themselves: an operand which is not a direct slot of a catalog table (a computed column, an + * aggregate output, a cast) cannot name its table, so such a join has no key. A null safe equality + * ({@code <=>}) is a hash conjunct as well and takes part like a plain equality. + */ + public static Optional<String> canonicalOf(Join join) { + return keyParts(join).map(parts -> PREFIX + String.join(SEP, parts) + "}"); + } + + /** + * The key of the expansion entry of a join: the sha256 of its structural identity, empty when the + * join has no expansion key (see {@link #canonicalOf}). The canonical string is the readable form of + * the same parts: it is printed by EXPLAIN and stored as the struct of the entry, and the key is not + * derived from the text. + */ + public static Optional<String> fingerprintOf(Join join) { + return keyParts(join).map(parts -> { + ShapeKeyWriter key = new ShapeKeyWriter(); + key.tag(0); + for (String part : parts) { + key.text(part); + } + return Hashing.sha256().hashBytes(key.toByteArray()).toString(); + }); + } + + /** + * The identity of a join expansion: its type, the equality pairs, the residual conditions and the + * columns of the tables the join reads. The identity is the same while a group is estimated (its + * children are group references there) and while the chosen plan is printed, because the operands are + * read from the slots themselves. + */ + private static Optional<List<String>> keyParts(Join join) { + Set<String> operands = new TreeSet<>(); + List<String> forward = new ArrayList<>(); + List<String> backward = new ArrayList<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + if (!(conjunct instanceof EqualTo) && !(conjunct instanceof NullSafeEqual)) { + return Optional.empty(); + } + Optional<String> left = operandIdentity(conjunct.child(0)); + Optional<String> right = operandIdentity(conjunct.child(1)); + if (!left.isPresent() || !right.isPresent()) { + return Optional.empty(); + } + operands.add(left.get()); + operands.add(right.get()); + String name = conjunct instanceof NullSafeEqual ? "NullSafeEqual" : "EqualTo"; + if (isCommutative(join.getJoinType())) { + // an inner join has no preserved side: order the pair by identity, which is canonical in + // both orientations, and choose one global orientation of the whole set below + String first = left.get().compareTo(right.get()) <= 0 ? left.get() : right.get(); + String second = first.equals(left.get()) ? right.get() : left.get(); + String pair = name + "(col(" + first + "),col(" + second + "))"; + forward.add(pair); + backward.add(pair); + continue; + } + Integer leftSide = sideOf(join, conjunct.child(0)); + Integer rightSide = sideOf(join, conjunct.child(1)); + // an outer join preserves one side: the operand of the left child is written first. A pair + // which cannot name a side (both operands from one side), or whose two operands are the same + // column, reads the same whichever occurrence is the preserved one, so the join has no key. + if (leftSide == null || rightSide == null || leftSide.equals(rightSide) + || left.get().equals(right.get())) { + return Optional.empty(); + } + forward.add(leftSide == 0 + ? name + "(col(" + left.get() + "),col(" + right.get() + "))" + : name + "(col(" + right.get() + "),col(" + left.get() + "))"); + backward.add(leftSide == 0 + ? name + "(col(" + right.get() + "),col(" + left.get() + "))" + : name + "(col(" + left.get() + "),col(" + right.get() + "))"); + } + if (forward.isEmpty()) { + return Optional.empty(); + } + forward.sort(String::compareTo); + backward.sort(String::compareTo); + // An inner join is commutative, so one global orientation of its two sides is chosen: the pairs are + // ordered by side all together, and the lexicographically smaller orientation is the key. Ordering + // each pair on its own would lose the incidence of a self join (which operands share a column), + // and flipping each pair on its own would lose commutativity. An outer join preserves a side, so + // its orientation is fixed (the operand of the left child first). + List<String> pairs = isCommutative(join.getJoinType()) + && String.join(SEP, backward).compareTo(String.join(SEP, forward)) < 0 + ? backward : forward; + if (pairs.isEmpty()) { + return Optional.empty(); + } + List<String> parts = new ArrayList<>(2 + pairs.size()); + parts.add(String.valueOf(join.getJoinType())); + parts.addAll(pairs); + parts.add("operands:[" + String.join(",", operands) + "]"); + return Optional.of(parts); + } + + /** Whether the operands of an equality are interchangeable without changing the row count. */ + private static boolean isCommutative(JoinType joinType) { + return joinType == JoinType.INNER_JOIN || joinType == JoinType.CROSS_JOIN; + } + + /** The side (0 or 1) of the join a slot is read from, null when it cannot be told. */ + private static Integer sideOf(Join join, Expression operand) { + if (!(operand instanceof SlotReference)) { + return null; + } + ExprId exprId = ((SlotReference) operand).getExprId(); + Plan joinPlan = (Plan) join; + for (int side = 0; side < joinPlan.arity(); side++) { + for (Slot slot : joinPlan.child(side).getOutput()) { + if (slot.getExprId().equals(exprId)) { + return side; + } + } + } + return null; + } + + /** + * The stable identity of the column an operand reads: the table it belongs to and the name of the + * column. The slot carries both, so the identity does not depend on the alias a query gave the + * relation, on the shape of its qualifier or on where the join is described. + */ + // The characters which delimit an operand in the pair text: a quoted column name may contain them, + // and would otherwise forge the boundary between two operands (`EqualTo(col(a),col(b))`). + private static String escapeOperandComponent(String value) { + StringBuilder escaped = new StringBuilder(value.length()); + for (int index = 0; index < value.length(); index++) { + char c = value.charAt(index); + switch (c) { + case '%': + escaped.append("%25"); + break; + case ',': + escaped.append("%2C"); + break; + case '(': + escaped.append("%28"); + break; + case ')': + escaped.append("%29"); + break; + default: + escaped.append(c); + } + } + return escaped.toString(); + } + + private static Optional<String> operandIdentity(Expression operand) { + if (!(operand instanceof SlotReference)) { + return Optional.empty(); + } + SlotReference slot = (SlotReference) operand; + if (!slot.getOriginalTable().isPresent() || !slot.getOriginalColumn().isPresent()) { + return Optional.empty(); + } + return Optional.of(escapeOperandComponent( + HboScanDescriptor.qualifiedNameOf(slot.getOriginalTable().get())) + + "." + escapeOperandComponent(slot.getOriginalColumn().get().getName())); Review Comment: [P2] Preserve VARIANT subpaths in expansion operands The default subpath rewrite turns these supported reduced plans into direct slot equalities: ```text INNER(l.v['a'] = r.v['a'], Scan(l), Scan(r)) INNER(l.v['b'] = r.v['b'], Scan(l), Scan(r)) ``` The extracted slots retain original column `v`, so this return gives both joins the same JE fingerprint. Give each table `{a:1,b:1},{a:1,b:2}` and use supported `ALTER TABLE ... MODIFY COLUMN v SET STATS ('row_count'='2','ndv'='2','num_nulls'='0')`. `StatsCalculator` fetches those known statistics by base name `v`, so both equality estimates are two. A factor of two correctly gives the `a` join four rows, but `applyPinnedJoinExpansion` also applies it to the `b` join, which returns two; the Cartesian cap permits four. Include the counted subpath in the operand identity, or decline such operands. This is separate from the earlier GroupStructInfo subpath fix: this auxiliary expansion lookup still drops the entire path. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboScanDescriptor.java: ########## @@ -0,0 +1,625 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +package org.apache.doris.nereids.stats; + +import org.apache.doris.catalog.DatabaseIf; +import org.apache.doris.catalog.Env; +import org.apache.doris.catalog.OlapTable; +import org.apache.doris.catalog.TableIf; +import org.apache.doris.nereids.trees.plans.algebra.OlapScan; +import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalOlapScan; +import org.apache.doris.rpc.RpcException; +import org.apache.doris.statistics.analysis.TableStatsMeta; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +/** + * The data state of one scan of a hbo struct info: the table it reads, the table visible version, + * the number of rows the scan reads (the sum of the row counts of its selected partitions) and which + * part of the table partitions it selects. + * + * <p>These numbers are the <b>baseline</b> a hbo entry is judged against. The scan token of a + * canonical struct info carries them as an annotation + * ({@code S{db.t,v3,r1000,p1/5}}), so a user copies the state the entry was measured in together + * with the struct info, and the read side compares them with the state of the current query to + * decide whether the injected row count may still be applied (see {@link HboStructFreshness}). + * + * <p>None of these numbers takes part in the fingerprint: + * {@link GroupStructInfo#stripScanBaseline} removes the whole baseline of every scan token before + * the sha256 is taken, so a table which simply keeps growing neither changes the key of an entry nor + * makes it unmatchable; whether the entry may still be applied is a read side decision. + * + * <p>A number which could not be determined is omitted from the token (and parsed back as + * {@link #UNKNOWN}), e.g. the row count of a table whose row count was never reported by any + * backend: such an entry cannot be compared by rows any more and falls back to the version check. + */ +public class HboScanDescriptor { + /** A number which could not be determined; a row count of 0 is a known, meaningful value. */ + public static final long UNKNOWN = -1; + + /** + * Separates the table from the stable ids of the partitions a scan selects inside a scan token. It + * must not contain a comma: the text based reader of a canonical form takes everything before the + * first comma inside {@code S{...}} as the identity of the scan (see + * {@link GroupStructInfo#stripScanBaseline}), so a comma here would move the ids into the baseline + * and the fingerprint of a pasted struct info would no longer match the one of the plan. + */ + static final String PARTITION_IDENTITY_SEPARATOR = ":"; + private static final String PARTITION_IDENTITY_MARK = "#pt"; + private static final String TABLET_IDENTITY_MARK = "#tb"; + private static final String INDEX_IDENTITY_MARK = "#ix"; + private static final String TABLE_IDENTITY_MARK = "#ti"; + private static final String RELATION_IDENTITY_MARK = "#ra"; + + /** + * The qualified name of the table, which is not its identity: {@code DROP TABLE db.t} and the + * creation of another {@code db.t} with the same row count leaves the name, the partitions and the + * version unchanged while the data is unrelated, and an entry pinned for the first table would still + * match. The id of the table is stable for the lifetime of the table (a rename keeps it) and differs + * for every other table, so it is part of the identity. It is {@link #UNKNOWN} for a relation whose + * id is not stable (an external table) or not known. + */ + private final long tableId; + private final String table; + /** + * The alias the query gave this relation ({@code FROM t AS x}), empty when it has none. Two scans of + * one table read the same data, but they are two relation instances: a join predicate which names + * their aliases ({@code x.b < y.b}) is bound to the instances, and the leaves are sorted by their + * text - without the alias the two plans which swap the aliases render the same key although the + * ordered comparison selects a different number of rows. + */ + private final String relationIdentity; + private final long visibleVersion; + private final long scanRows; + private final RowsKind rowsKind; + private final long selectedPartitions; + private final long totalPartitions; + /** + * The partitions this scan selects, as their stable ids in ascending order (empty when it selects + * every partition of the table). The partition *count* alone is not an identity: {@code PARTITION(p1)} + * and {@code PARTITION(p2)} of a table with equally sized partitions produce the same count, the same + * row count and therefore the same key, while they read different data - the ids are what tells them + * apart, and they are stable across renames (a rename keeps the id, so a pinned entry keeps applying). + */ + private final String partitionIdentity; + /** + * The tablets this scan selects explicitly ({@code TABLET(id1, id2)}), ascending, empty when the + * scan reads whole partitions. Like the partition ids they are part of the identity: two tablet + * selections of one partition read different data while they report the same partition count and + * the same row count. + */ + private final String tabletIdentity; + /** + * The index this scan reads when it is not the base index of the table (a rollup), empty otherwise. + * It belongs to the identity as well: an aggregate rollup holds a different number of rows than the + * base index, so an entry recorded for one of them must never be compared with the other - a whole + * table query and a rollup query would otherwise share an entry, and the drift guard would judge the + * rollup's row count against the base index and report the entry as stale. + */ + private final String indexIdentity; + + HboScanDescriptor(String table, long tableId, String relationIdentity, long visibleVersion, + long scanRows, RowsKind rowsKind, long selectedPartitions, long totalPartitions, + String partitionIdentity, String tabletIdentity, String indexIdentity) { + this.table = table; + this.tableId = tableId; + this.relationIdentity = relationIdentity; + this.visibleVersion = visibleVersion; + this.scanRows = scanRows; + this.rowsKind = rowsKind; + this.selectedPartitions = selectedPartitions; + this.totalPartitions = totalPartitions; + this.partitionIdentity = partitionIdentity; + this.tabletIdentity = tabletIdentity; + this.indexIdentity = indexIdentity; + } + + /** + * The name of a table as it is recorded in a scan token. {@code getNameWithFullQualifiers} joins the + * qualifiers and the name with dots, so the table {@code a.b} of the database {@code db} and the + * table {@code b} of the database {@code db.a} serialize identically - and a resolver which takes + * the last dot separated part as the table name would judge the sibling of the recorded table. The + * dots *inside the name* are therefore escaped while the dots which separate the qualifiers are not; + * an ordinary name is unchanged, so no key of an ordinary table moves. + */ + public static String qualifiedNameOf(TableIf table) { + DatabaseIf<?> database = table.getDatabase(); + if (database == null) { + // some kinds of table (a function generated one, for instance) belong to no database + return "null.null." + escapeNamePart(table.getName()); + } + return database.getCatalog().getName() + "." + database.getFullName() + "." + + escapeNamePart(table.getName()); + } + + /** The dots of a table name (and the escape character itself) are escaped. */ + static String escapeNamePart(String name) { + // '#' introduces the partition / tablet / index selector markers of a scan token, so a table name + // which carries one would be truncated to the part before it while the planner summary keeps the + // whole name - the relation key of the entry would then never match the query + return name.replace("%", "%25").replace(".", "%2E").replace("#", "%23") Review Comment: [P2] Escape commas in aliases before rendering scan metadata For the full-table plan `Filter(predicate) -> Scan(t AS alias)` with quoted alias `x,p1/2`, the alias reaches this codec unchanged and produces a token such as `S{internal.db.t#ti:ID#ra:x,p1/2,v2,r1000}`. `parse()` splits on commas, truncates the alias to `x`, and invents a partial-partition baseline (`selected=1,total=2`); a full scan writes no real `p` field to replace it. Pin the advertised key/struct, then insert 10 rows and obtain comparable reported rows at v3/r1010. Query-side `between/stateOf` still applies the pin as DRIFTED, but catalog-side `of()` treats the false partial selection as UNKNOWN. Once the entry has positive age, `HBO DELETE STALE STATISTICS OLDER_THAN 0` therefore removes this usable pin; an ordinary full-table alias remains DRIFTED and is retained. Escape the scan-token comma separator in alias components and cover the descriptor round trip and cleanup behavior. -- 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]
