github-actions[bot] commented on code in PR #67549: URL: https://github.com/apache/doris/pull/67549#discussion_r4245156358
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,100 @@ +// 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.Expression; +import org.apache.doris.nereids.trees.expressions.NullSafeEqual; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.algebra.Join; + +import com.google.common.hash.Hashing; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; + +/** + * 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. The residual conditions are rendered constant agnostically, like the + * rest of the join keys. + */ +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 equality conditions, empty when the join has no equality condition + * (e.g. a cross join). A null safe equality ({@code <=>}) is a hash conjunct as well, so it + * takes part in the canonical like a plain equality. + */ + public static Optional<String> canonicalOf(Join join) { + List<String> pairs = new ArrayList<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + if (conjunct instanceof EqualTo || conjunct instanceof NullSafeEqual) { + pairs.add(GroupStructInfo.normalizeExpression(conjunct)); + } + } + if (pairs.isEmpty()) { + return Optional.empty(); + } + pairs.sort(String::compareTo); + List<String> residuals = new ArrayList<>(); + for (Expression conjunct : join.getOtherJoinConjuncts()) { + residuals.add(GroupStructInfo.normalizeExpression(conjunct, Review Comment: [P2] Preserve literals in residual predicates for JOIN_EXPANSION keys. `canonicalOf` normalizes every non-equality join conjunct with `NO_LITERAL`, so `t.a=u.a AND t.b>u.b+1` and `t.a=u.a AND t.b>u.b+1000` generate the same JE fingerprint. `applyPinnedJoinExpansion` uses the matched factor to replace the entire join output estimate, including the residual's effect, and can give both joins the same inflated count and join order despite very different selectivity. Include residual constants in this key, or apply the factor before estimating residual selectivity. The prior fix added residual predicates to the key; this remaining collision is between different values of an included residual. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,100 @@ +// 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.Expression; +import org.apache.doris.nereids.trees.expressions.NullSafeEqual; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.algebra.Join; + +import com.google.common.hash.Hashing; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; + +/** + * 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. The residual conditions are rendered constant agnostically, like the + * rest of the join keys. + */ +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 equality conditions, empty when the join has no equality condition + * (e.g. a cross join). A null safe equality ({@code <=>}) is a hash conjunct as well, so it + * takes part in the canonical like a plain equality. + */ + public static Optional<String> canonicalOf(Join join) { + List<String> pairs = new ArrayList<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + if (conjunct instanceof EqualTo || conjunct instanceof NullSafeEqual) { + pairs.add(GroupStructInfo.normalizeExpression(conjunct)); + } + } + if (pairs.isEmpty()) { + return Optional.empty(); + } + pairs.sort(String::compareTo); + List<String> residuals = new ArrayList<>(); + for (Expression conjunct : join.getOtherJoinConjuncts()) { + residuals.add(GroupStructInfo.normalizeExpression(conjunct, + GroupStructInfo.LiteralMode.NO_LITERAL)); + } + residuals.sort(String::compareTo); + StringBuilder canonical = new StringBuilder(PREFIX).append(join.getJoinType()); Review Comment: [P2] Include the preserved relation in outer-join expansion keys. `A LEFT JOIN B ON A.k=B.k` and `B LEFT JOIN A ON B.k=A.k` both retain `LEFT_OUTER_JOIN`, and `normalizeExpression` sorts the equality operands, so this method gives them the same JE fingerprint. If A has 1,000 rows and B has 10 disjoint rows, the first join yields 1,000 and the second 10; a factor of 1 pinned for the first makes `applyPinnedJoinExpansion` estimate 1,000 for the second. Encode which child is preserved, or normalize child swapping together with the outer join type. The prior join-type fix does not separate two LEFT joins that preserve different relations. ########## regression-test/suites/query_p0/hbo/hbo_persist_internal_db_test.groovy: ########## @@ -0,0 +1,90 @@ +// 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. + +suite("hbo_persist_internal_db_test", "nonConcurrent") { + // Persistence of pinned hbo statistics into __internal_schema.hbo_statistics is gated by + // Config.hbo_persist_pinned_to_internal_db (hot-mutable, true by default). The config is pinned + // to true for this suite and restored afterwards, so that the row level effect of SET/DELETE is + // asserted whatever the cluster is configured with. The in-memory pinned entry is authoritative: + // SET writes through synchronously and DELETE removes the row again. + // The load side (a FE reading the table back at start-up, and the tombstone handling of a DELETE + // racing that load) is not covered here: it needs a FE restart, and it is exercised by the + // background loader (HboPinnedStatisticsLoader) instead of by a statement. + def prevPersist = (sql """ ADMIN SHOW FRONTEND CONFIG LIKE 'hbo_persist_pinned_to_internal_db'; """)[0][1].toString() + // a pinned entry must carry the struct info its fingerprint was computed from, so the pair + // below is self consistent: the fingerprint is the sha256 of the canonical without the data + // state of its scans, with the literals folded because the entry is stored constant agnostically + // (sha256 of "F{EqualTo(col(internal.hbo_test.hbo_persist_t.a),lit(*))}(S{internal.hbo_test.hbo_persist_t})"). + // The root is a filter, not a scan: pinned row counts are looked up at filter, join and + // aggregation nodes, so an entry keyed by a scan token could never be applied. + def structCanonical = "F{EqualTo(col(internal.hbo_test.hbo_persist_t.a),lit(1:INT))}" + + "(S{internal.hbo_test.hbo_persist_t,v1})" + def fingerprint = "d6fbc16dff64c7607cb0c016e8471a390f1a124531ce29f146fa998889d5e028" + def tableName = "__internal_schema.hbo_statistics" + try { + sql """ ADMIN SET FRONTEND CONFIG ("hbo_persist_pinned_to_internal_db" = "true"); """ + try { + // SET persists the pinned entry (including its stats type) into the internal table + sql """ HBO SET STATISTICS VALUE=123456 TYPE=EXACT FINGERPRINT='${fingerprint}' STRUCT='${structCanonical}'; """ + qt_set_persisted """ SELECT fingerprint, row_count, stats_type, literal_mode, struct_info + FROM ${tableName} WHERE fingerprint = '${fingerprint}'; """ + + // DELETE removes the row from the internal table + sql """ HBO DELETE STATISTICS FINGERPRINT='${fingerprint}'; """ + qt_delete_cleared """ SELECT fingerprint, row_count, stats_type, literal_mode, struct_info + FROM ${tableName} WHERE fingerprint = '${fingerprint}'; """ + + // a join expansion entry is the same kind of entry as a pinned row count - it lives in + // the same table and is distinguished by stats_type, but its value column carries the + // fan-out factor and its key is the join condition fingerprint + def condCanonical = "JE{INNER_JOIN;EqualTo(col(internal.hbo_test.x.a),col(internal.hbo_test.y.a))}" + def condFingerprint = java.security.MessageDigest.getInstance("SHA-256") + .digest(condCanonical.getBytes("UTF-8")).encodeHex().toString() + sql """ HBO SET STATISTICS VALUE=1000 TYPE=JOIN_EXPANSION FINGERPRINT='${condFingerprint}' STRUCT='${condCanonical}'; """ + qt_set_expansion """ SELECT stats_type, expansion, struct_info FROM ${tableName} + WHERE fingerprint = '${condFingerprint}'; """ + + // the unified list reports it with its own type and the factor as its value + def expansionRows = sql """ HBO SHOW PINNED STATISTICS LIKE 'JE{%'; """ + assertEquals(1, expansionRows.size(), expansionRows.toString()) + assertEquals("join_expansion", expansionRows[0][3].toString()) + assertEquals("1000x", expansionRows[0][4].toString()) + assertEquals(condCanonical, expansionRows[0][5].toString()) + // a condition keyed entry is always constant agnostic and has no data state + assertEquals("no_literal", expansionRows[0][2].toString()) + assertEquals("-", expansionRows[0][7].toString()) + + // a stale clean up never removes an expansion entry: it carries no table version, so + // even OLDER_THAN (which removes unresolvable entries) has to leave it alone + sql """ HBO DELETE STALE STATISTICS; """ + sql """ HBO DELETE STALE STATISTICS OLDER_THAN 0; """ + qt_expansion_kept """ SELECT stats_type, expansion FROM ${tableName} + WHERE fingerprint = '${condFingerprint}'; """ + + sql """ HBO DELETE STATISTICS FINGERPRINT='${condFingerprint}'; """ + qt_expansion_deleted """ SELECT stats_type, expansion FROM ${tableName} + WHERE fingerprint = '${condFingerprint}'; """ + } finally { + // cleanup runs while the config is still on, so a failure between SET and the DELETE + // above cannot leave a persisted row behind + sql """ HBO DELETE STATISTICS FINGERPRINT='${fingerprint}'; """ Review Comment: [P3] Clean up the expansion pin when this suite fails. After the JOIN_EXPANSION `SET`, any failed query or assertion before line 78 jumps here, but this `finally` deletes only the earlier row-count fingerprint. The expansion entry then remains in the FE cache and `__internal_schema.hbo_statistics`, affecting later tests and restarts. Keep `condFingerprint` in scope and delete it here as well. -- 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]
