github-actions[bot] commented on code in PR #69871:
URL: https://github.com/apache/doris/pull/69871#discussion_r4638057021
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/cost/CostModel.java:
##########
@@ -120,36 +123,47 @@ public Cost visitPhysicalOlapScan(PhysicalOlapScan
physicalOlapScan, PlanContext
OlapTable table = physicalOlapScan.getTable();
Statistics statistics = context.getStatisticsWithCheck();
double rows = statistics.getRowCount();
+ Optional<UseMvHint> useMvHint = getUseMvHint();
+ if (useMvHint.isPresent()) {
+ // USE_MV forces the hinted materialized view, so the hinted
materialized view is scanned
+ // with zero cost and the other relations are charged with a tiny
extra cost, which makes
+ // the hinted materialized view the cheapest one during the whole
optimization.
+ // UseMvHintPlanner.chooseBestPlanConsideringUseMv() validates the
final plan afterwards.
+ if (isHintedMaterialization(useMvHint.get(), physicalOlapScan)) {
+ return Cost.ofCpu(context.getCostWeight(), 0);
+ }
+ return Cost.ofCpu(context.getCostWeight(), rows +
NON_USE_MV_SCAN_PENALTY);
Review Comment:
[P2] Do not bias ordinary planning for an unusable USE_MV hint
This early return charges `rows + 1` to every non-hinted OLAP scan and skips
the existing aggregate-index bonus whenever any valid USE_MV hint is present.
For an unmatched or rewrite-ineligible hint such as `USE_MV(no_such_mv)`,
`chooseBestPlanConsideringRequiredUseMv` falls back to ordinary selection, but
normal costing still sees the penalty and can choose a slower base index. Apply
the bias only when a usable hinted materialization will actually be enforced;
otherwise preserve the existing cost calculation.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/UseMvHintPlanner.java:
##########
@@ -0,0 +1,933 @@
+// 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;
+
+import org.apache.doris.catalog.MTMV;
+import org.apache.doris.catalog.OlapTable;
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.cost.Cost;
+import org.apache.doris.nereids.cost.CostCalculator;
+import org.apache.doris.nereids.exceptions.AnalysisException;
+import org.apache.doris.nereids.hint.Hint;
+import org.apache.doris.nereids.hint.UseMvHint;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ChildOutputPropertyDeriver;
+import org.apache.doris.nereids.properties.DistributionSpec;
+import org.apache.doris.nereids.properties.DistributionSpecGather;
+import org.apache.doris.nereids.properties.DistributionSpecHash;
+import org.apache.doris.nereids.properties.DistributionSpecHash.ShuffleType;
+import org.apache.doris.nereids.properties.OrderSpec;
+import org.apache.doris.nereids.properties.PhysicalProperties;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.SortPhase;
+import org.apache.doris.nereids.trees.plans.physical.AbstractPhysicalJoin;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalCatalogRelation;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalDistribute;
+import
org.apache.doris.nereids.trees.plans.physical.PhysicalLazyMaterializeOlapScan;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalOlapScan;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalPlan;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalQuickSort;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalRelation;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalSetOperation;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalSink;
+import org.apache.doris.nereids.trees.plans.visitor.DefaultPlanVisitor;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+
+/**
+ * Choose the physical plan which satisfies the USE_MV hint as a hard
constraint, and report the
+ * materializations which the final plan actually uses.
+ * <p>
+ * A hinted materialization is required only once: several hinted
materializations are usually
+ * alternatives of each other, and a materialization which several children of
a join can reach does not
+ * have to be produced by every one of them. The selection picks the cheapest
plan which contains at least
+ * one of the reachable materializations and synthesizes the enforcers which
the replaced relations need,
+ * the rest of the plan selection stays the cost based one of {@link
NereidsPlanner}.
+ */
+public final class UseMvHintPlanner {
+ private UseMvHintPlanner() {
+ }
+
+ /**
+ * Choose the best plan which contains at least one of the USE_MV hinted
materializations.
+ *
+ * @return the chosen plan together with its estimated cost, or null when
there is no materialization
+ * to enforce, the caller then keeps its regular plan selection
+ */
+ public static PlanWithCost chooseBestPlanConsideringRequiredUseMv(Group
rootGroup,
+ PhysicalProperties physicalProperties, CascadesContext
cascadesContext)
+ throws AnalysisException {
+ StatementContext stmtCtx = cascadesContext.getStatementContext();
+ Set<List<String>> requiredUseMvIdentifiers =
computeRequiredUseMvIdentifiers(stmtCtx);
+ if (requiredUseMvIdentifiers.isEmpty()) {
+ return null;
+ }
+ Map<Group, Set<List<String>>> mvReachableCache = new HashMap<>();
+ computeReachableMvIdentifiers(rootGroup, mvReachableCache,
requiredUseMvIdentifiers);
+ Set<List<String>> rootReachable = mvReachableCache.get(rootGroup);
+ // Drop the required MVs which the rewrite can not produce, and mark
them as UnUsed,
+ // USE_MV is best-effort and should not fail the query.
+ requiredUseMvIdentifiers = dropUnreachableUseMvIdentifiers(stmtCtx,
requiredUseMvIdentifiers,
+ rootReachable == null ? ImmutableSet.of() : rootReachable);
+ if (requiredUseMvIdentifiers.isEmpty()) {
+ return null;
+ }
+ PlanWithCost chosenPlan =
chooseBestPlanWithRequiredMaterializations(rootGroup,
+ physicalProperties, requiredUseMvIdentifiers,
mvReachableCache, cascadesContext);
+ if (chosenPlan == null) {
+ // No materialization can be produced together with the required
properties, fall back to
+ // the cost based plan instead of failing the query.
+ markUseMvNotChosen(stmtCtx, requiredUseMvIdentifiers);
+ return chooseBestPlanWithCost(rootGroup, physicalProperties,
cascadesContext);
+ }
+ return enforceOutputProperties(chosenPlan, physicalProperties,
rootGroup, cascadesContext);
+ }
+
+ /**
+ * Choose the best physical plan considering USE_MV hint as a hard
constraint.
+ * If USE_MV hint is present with rewrite-success MVs, the returned plan
must
+ * contain those MVs. Otherwise, falls back to standard cost-based
selection.
+ *
+ * @param rootGroup the root memo group
+ * @param physicalProperties required physical properties
+ * @param cascadesContext the cascades context
+ * @return physical plan respecting USE_MV hard constraint
+ */
+ public static PhysicalPlan chooseBestPlanConsideringUseMv(Group rootGroup,
+ PhysicalProperties physicalProperties, CascadesContext
cascadesContext)
+ throws AnalysisException {
+ PlanWithCost chosenPlan =
chooseBestPlanConsideringRequiredUseMv(rootGroup, physicalProperties,
+ cascadesContext);
+ if (chosenPlan == null) {
+ return NereidsPlanner.chooseBestPlan(rootGroup,
physicalProperties, cascadesContext);
+ }
+ return chosenPlan.plan;
+ }
+
+ /**
+ * Compute the set of USE_MV hint qualifiers that successfully rewrote.
+ * Marks USE_MV hint parameters that did NOT rewrite-success as UnUsed.
+ */
+ private static Set<List<String>>
computeRequiredUseMvIdentifiers(StatementContext statementContext) {
+ Optional<UseMvHint> useMvHint =
statementContext.getUseMvHint("USE_MV");
+ if (!useMvHint.isPresent()) {
+ return ImmutableSet.of();
+ }
+ Set<List<String>> useMvQualifiers =
useMvHint.get().getUseMvTableColumnMap().keySet();
+ Set<List<String>> rewrittenSuccessSet =
statementContext.getMaterializationRewrittenSuccessSet();
+ Set<List<String>> required = new HashSet<>(useMvQualifiers);
+ required.retainAll(rewrittenSuccessSet);
+ // Mark USE_MV qualifiers that did not rewrite-success as UnUsed
+ Set<List<String>> notRewritten = new HashSet<>(useMvQualifiers);
+ notRewritten.removeAll(rewrittenSuccessSet);
+ for (List<String> qualifier : notRewritten) {
+ // Update hint map to mark as not-chosen (false) with failure
reason
+ useMvHint.get().getUseMvTableColumnMap().put(qualifier, false);
+ }
+ if (!notRewritten.isEmpty()) {
+ // If some USE_MV hints failed to rewrite, set status to UNUSED
with reason
+ useMvHint.get().setStatus(Hint.HintStatus.UNUSED);
+ useMvHint.get().setErrorMessage("MV(s) not rewrite-success after
CBO: " + notRewritten);
+ }
+ return required;
+ }
+
+ /**
+ * Extract the MV qualifier(s) from a scan plan if it matches a required
USE_MV identifier.
+ * Returns the set of MV qualifiers this plan represents.
+ */
+ private static Set<List<String>> getScanMvIdentifiers(Plan plan,
+ Set<List<String>> requiredUseMvIdentifiers) {
+ Set<List<String>> result = new HashSet<>();
+ if (plan instanceof PhysicalOlapScan) {
+ PhysicalOlapScan scan = (PhysicalOlapScan) plan;
+ OlapTable table = scan.getTable();
+ if (table.getBaseIndexId() != scan.getSelectedIndexId()) {
+ List<String> qualifier = new ArrayList<>();
+ qualifier.add(table.getDatabase().getCatalog().getName());
+ qualifier.add(table.getDatabase().getFullName());
+ qualifier.add(table.getName());
+
qualifier.add(table.getIndexNameById(scan.getSelectedIndexId()));
+ if (requiredUseMvIdentifiers.contains(qualifier)) {
+ result.add(qualifier);
+ }
+ }
+ }
+ if (plan instanceof PhysicalCatalogRelation) {
+ PhysicalCatalogRelation rel = (PhysicalCatalogRelation) plan;
+ if (rel.getTable() instanceof MTMV) {
+ List<String> qualifier = rel.getTable().getFullQualifiers();
+ if (requiredUseMvIdentifiers.contains(qualifier)) {
+ result.add(qualifier);
+ }
+ }
+ // Also check for sync MV via OlapScan (PhysicalOlapScan is a
PhysicalCatalogRelation)
+ if (rel instanceof PhysicalOlapScan) {
+ PhysicalOlapScan scan = (PhysicalOlapScan) rel;
+ OlapTable table = scan.getTable();
+ if (table.getBaseIndexId() != scan.getSelectedIndexId()) {
+ List<String> qualifier = new ArrayList<>();
+ qualifier.add(table.getDatabase().getCatalog().getName());
+ qualifier.add(table.getDatabase().getFullName());
+ qualifier.add(table.getName());
+
qualifier.add(table.getIndexNameById(scan.getSelectedIndexId()));
+ if (requiredUseMvIdentifiers.contains(qualifier)) {
+ result.add(qualifier);
+ }
+ }
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Memoized bottom-up DFS: compute all MV identifiers reachable from this
group's subtree
+ * through physical GroupExpressions (including enforcers).
+ */
+ private static void computeReachableMvIdentifiers(Group group,
+ Map<Group, Set<List<String>>> cache, Set<List<String>>
requiredUseMvIdentifiers) {
+ if (cache.containsKey(group)) {
+ return;
+ }
+ Set<List<String>> reachable = new HashSet<>();
+ // Put in cache BEFORE recursing to break cycles
+ cache.put(group, reachable);
+
+ for (GroupExpression ge : group.getPhysicalExpressions()) {
+ Set<List<String>> geReachable = getScanMvIdentifiers(ge.getPlan(),
requiredUseMvIdentifiers);
+ for (Group child : ge.children()) {
+ computeReachableMvIdentifiers(child, cache,
requiredUseMvIdentifiers);
+ geReachable.addAll(cache.get(child));
+ }
+ reachable.addAll(geReachable);
+ }
+ for (GroupExpression enforcer : group.getEnforcers().values()) {
+ Set<List<String>> enforcerReachable = new HashSet<>();
+ for (Group child : enforcer.children()) {
+ computeReachableMvIdentifiers(child, cache,
requiredUseMvIdentifiers);
+ enforcerReachable.addAll(cache.get(child));
+ }
+ reachable.addAll(enforcerReachable);
+ }
+ }
+
+ /**
+ * Drop the required USE_MV identifiers which are not reachable in the
memo, and mark them
+ * as not chosen in the hint. USE_MV is a best-effort hint: when the
materialized view can not
+ * be produced by the rewrite, for example the query aggregations can not
be answered by the
+ * materialized view, the query is planned without this hint instead of
failing.
+ *
+ * @return the required USE_MV identifiers which are reachable, or an
empty set if all are dropped
+ */
+ private static Set<List<String>>
dropUnreachableUseMvIdentifiers(StatementContext statementContext,
+ Set<List<String>> requiredUseMvIdentifiers, Set<List<String>>
reachableUseMvIdentifiers) {
+ Set<List<String>> reachableRequired = new
HashSet<>(requiredUseMvIdentifiers);
+ reachableRequired.retainAll(reachableUseMvIdentifiers);
+ if (reachableRequired.size() == requiredUseMvIdentifiers.size()) {
+ return requiredUseMvIdentifiers;
+ }
+ Set<List<String>> unreachable = new
HashSet<>(requiredUseMvIdentifiers);
+ unreachable.removeAll(reachableUseMvIdentifiers);
+ Optional<UseMvHint> useMvHint =
statementContext.getUseMvHint("USE_MV");
+ if (useMvHint.isPresent()) {
+ useMvHint.get().setStatus(Hint.HintStatus.UNUSED);
+ useMvHint.get().setErrorMessage("MV(s) not found in memo after
rewrite: " + unreachable);
+ for (List<String> qualifier : unreachable) {
+ useMvHint.get().getUseMvTableColumnMap().put(qualifier, false);
+ }
+ }
+ return reachableRequired;
+ }
+
+ /**
+ * Mark the USE_MV qualifiers which are not chosen in the final plan, so
that the hint is reported
+ * as UnUsed together with the reason.
+ */
+ private static void markUseMvNotChosen(StatementContext statementContext,
+ Set<List<String>> notChosenQualifiers) {
+ Optional<UseMvHint> useMvHint =
statementContext.getUseMvHint("USE_MV");
+ if (!useMvHint.isPresent()) {
+ return;
+ }
+ useMvHint.get().setStatus(Hint.HintStatus.UNUSED);
+ useMvHint.get().setErrorMessage("MV(s) can not be chosen with the
required properties: "
+ + notChosenQualifiers);
+ for (List<String> qualifier : notChosenQualifiers) {
+ useMvHint.get().getUseMvTableColumnMap().put(qualifier, false);
+ }
+ }
+
+ /**
+ * Enforce the required output properties on the selected plan, the
selected materialization can
+ * provide other properties than the costed plan which it replaced.
+ */
+ private static PlanWithCost enforceOutputProperties(PlanWithCost
selectedPlan,
+ PhysicalProperties requiredProperties, Group group,
CascadesContext cascadesContext) {
+ if (selectedPlan.plan instanceof PhysicalSink
+ ||
providesProperties(selectedPlan.plan.getPhysicalProperties(),
requiredProperties)) {
+ // A sink is the root of the plan and its child is already
required to provide the
+ // properties, an enforcer above it would be meaningless.
+ return selectedPlan;
+ }
+ return enforceProperties(selectedPlan, requiredProperties, false,
group, cascadesContext);
+ }
+
+ /**
+ * Choose the cost based plan of the group together with its estimated
cost.
+ */
+ private static PlanWithCost chooseBestPlanWithCost(Group rootGroup,
PhysicalProperties physicalProperties,
+ CascadesContext cascadesContext) throws AnalysisException {
+ PhysicalPlan physicalPlan = NereidsPlanner.chooseBestPlan(rootGroup,
physicalProperties, cascadesContext);
+ double planCost = rootGroup.getLowestCostPlan(physicalProperties)
+ .map(costAndPlan -> costAndPlan.first.getValue()).orElse(0.0);
+ return new PlanWithCost(physicalPlan, planCost);
+ }
+
+ /**
+ * Choose the cheapest physical plan which contains at least one of the
required materializations.
+ * <p>
+ * At each group, picks the cheapest physical GroupExpression which can
produce one of the remaining
+ * required materializations, then assigns the materializations which its
children still have to produce
+ * to a single child each and recurses. A materialization is not required
from every child which could
+ * reach it, see {@link #assignRequiredMaterializations}.
+ *
+ * @return the chosen plan together with its estimated cost, or null if no
materialization can be
+ * produced together with the required properties
+ */
+ private static PlanWithCost chooseBestPlanWithRequiredMaterializations(
+ Group group, PhysicalProperties properties,
+ Set<List<String>> remaining, Map<Group, Set<List<String>>>
reachableCache,
+ CascadesContext cascadesContext) {
+ Set<List<String>> requiredMvs = new HashSet<>(remaining);
+ if (requiredMvs.isEmpty()) {
+ return chooseBestPlanWithCost(group, properties, cascadesContext);
+ }
+
+ PhysicalProperties selectedProperties = properties;
+ GroupExpression chosenGE = chooseGroupExpression(group, properties,
requiredMvs, reachableCache);
+ if (chosenGE == null) {
+ // The hinted materialization may be costed only with another
property than the required
+ // one, for example ANY or its own storage distribution, because
the cheapest alternative of
+ // the group owns the required property. Select it on an available
property and enforce the
+ // required one afterwards.
+ Pair<GroupExpression, PhysicalProperties> alternative =
+ findAlternativeWithProperty(group, requiredMvs,
reachableCache);
+ if (alternative == null) {
+ return null;
+ }
+ chosenGE = alternative.first;
+ selectedProperties = alternative.second;
+ }
+
+ if (group.getEnforcers().containsKey(chosenGE)) {
+ return choosePlanWithEnforcer(group, chosenGE, properties,
requiredMvs, reachableCache,
+ cascadesContext);
+ }
+
+ // The materializations which the chosen alternative produces by
itself are not required from the
+ // children anymore, the others still are. The alternatives of a group
are not interchangeable
+ // here: the cheapest one may be the base relation, which produces
nothing.
+ Set<List<String>> childRequiredMvs = new HashSet<>(requiredMvs);
+ childRequiredMvs.removeAll(getScanMvIdentifiers(chosenGE.getPlan(),
requiredMvs));
+
+ // Handle enforcer marking (same as chooseBestPlan)
+ if (chosenGE.getPlan() instanceof PhysicalDistribute
+ && group.getEnforcerSpecs().containsKey(
+ ((PhysicalDistribute<?>)
chosenGE.getPlan()).getDistributionSpec())) {
+ group.addChosenEnforcerId(chosenGE.getId().asInt());
+ group.addChosenEnforcerProperties(selectedProperties);
+ } else {
+ group.setChosenProperties(selectedProperties);
Review Comment:
[P1] Roll back memo choice state when forced selection cannot complete
`chooseBestPlanWithRequiredMaterializations` records the chosen
GroupExpression before recursively proving every child. If a reachable MV
expression has no costed plan for a required child property, the recursion
returns `null`; the caller then invokes the ordinary chooser, whose
`Group.setChosenGroupExpressionId` rejects the already-set marker and raises an
`AnalysisException` instead of falling back. Build the forced plan before
committing these markers, or restore the memo state before the fallback so
USE_MV remains best-effort.
--
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]