>From Preetham Poluparthi <[email protected]>: Preetham Poluparthi has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21335?usp=email )
Change subject: WIP : Optimize grouping sets query ...................................................................... WIP : Optimize grouping sets query Change-Id: I06ab32218c44f7e733092bb7b9326217fd8b945a --- A asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/GroupingSetsHasse.java M asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppGroupingSetsVisitor.java 2 files changed, 380 insertions(+), 55 deletions(-) git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/35/21335/1 diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/GroupingSetsHasse.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/GroupingSetsHasse.java new file mode 100644 index 0000000..3399a5b --- /dev/null +++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/GroupingSetsHasse.java @@ -0,0 +1,314 @@ +/* + * 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.asterix.lang.sqlpp.rewrites.visitor; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import java.util.Set; + +import org.apache.asterix.common.exceptions.CompilationException; +import org.apache.asterix.lang.common.base.Expression; +import org.apache.asterix.lang.common.clause.GroupbyClause; +import org.apache.asterix.lang.common.clause.LetClause; +import org.apache.asterix.lang.common.expression.CallExpr; +import org.apache.asterix.lang.common.expression.GbyVariableExpressionPair; +import org.apache.asterix.lang.common.expression.LiteralExpr; +import org.apache.asterix.lang.common.expression.VariableExpr; +import org.apache.asterix.lang.common.literal.NullLiteral; +import org.apache.asterix.lang.common.rewrites.LangRewritingContext; +import org.apache.asterix.lang.common.struct.Identifier; +import org.apache.asterix.lang.sqlpp.clause.FromClause; +import org.apache.asterix.lang.sqlpp.clause.FromTerm; +import org.apache.asterix.lang.sqlpp.clause.Projection; +import org.apache.asterix.lang.sqlpp.clause.SelectBlock; +import org.apache.asterix.lang.sqlpp.clause.SelectClause; +import org.apache.asterix.lang.sqlpp.clause.SelectRegular; +import org.apache.asterix.lang.sqlpp.clause.SelectSetOperation; +import org.apache.asterix.lang.sqlpp.expression.SelectExpression; +import org.apache.asterix.lang.sqlpp.struct.SetOperationInput; +import org.apache.asterix.lang.sqlpp.util.SqlppRewriteUtil; +import org.apache.asterix.lang.sqlpp.util.SqlppVariableUtil; +import org.apache.hyracks.algebricks.common.utils.Pair; + +/** + * Hasse diagram over grouping sets ordered by subset inclusion. + * + * <p>Each {@link Node} represents one grouping set. An edge from parent P to child C means + * C's variable set is a strict subset of P's and no other node in the diagram lies strictly + * between them (P covers C). A node can have multiple parents (diamond shapes are possible). + * Nodes not covered by any other node are roots ({@link Node#isRoot()} == true). + */ +public final class GroupingSetsHasse { + + public static final class Node { + private final List<GbyVariableExpressionPair> groupingSet; + private final Set<VariableExpr> vars; + private final List<Node> parents = new ArrayList<>(); + private final List<Node> children = new ArrayList<>(); + // Set by generateLetClauses(); children read this to build their FROM clause. + VariableExpr letVar; + + private Node(List<GbyVariableExpressionPair> groupingSet) { + this.groupingSet = groupingSet; + this.vars = new LinkedHashSet<>(); + for (GbyVariableExpressionPair pair : groupingSet) { + if (pair.getVar() != null) { + vars.add(pair.getVar()); + } + } + } + + private boolean isStrictSubsetOf(Node other) { + return this.vars.size() < other.vars.size() && other.vars.containsAll(this.vars); + } + + public List<GbyVariableExpressionPair> getGroupingSet() { + return groupingSet; + } + + public Set<VariableExpr> getVars() { + return vars; + } + + /** Direct parents in the Hasse diagram (covering supersets). Empty for root nodes. */ + public List<Node> getParents() { + return parents; + } + + public boolean isRoot() { + return parents.isEmpty(); + } + + /** Direct children in the Hasse diagram (covered subsets). */ + public List<Node> getChildren() { + return children; + } + + /** The LET variable bound for this node; set after {@link GroupingSetsHasse#generateLetClauses}. */ + public VariableExpr getLetVar() { + return letVar; + } + } + + private final List<Node> nodes; + + GroupingSetsHasse(List<List<GbyVariableExpressionPair>> groupingSets) { + List<Node> allNodes = new ArrayList<>(groupingSets.size()); + for (List<GbyVariableExpressionPair> gs : groupingSets) { + allNodes.add(new Node(gs)); + } + buildEdges(allNodes); + nodes = Collections.unmodifiableList(allNodes); + } + + /** + * Builds the covering relation: for each pair (A, B) where B ⊂ A strictly, + * A is a parent of B only if no other node C satisfies B ⊂ C ⊂ A. + */ + private static void buildEdges(List<Node> allNodes) { + for (Node b : allNodes) { + for (Node a : allNodes) { + if (!b.isStrictSubsetOf(a)) { + continue; + } + boolean covers = true; + for (Node c : allNodes) { + if (c != a && c != b && b.isStrictSubsetOf(c) && c.isStrictSubsetOf(a)) { + covers = false; + break; + } + } + if (covers) { + b.parents.add(a); + a.children.add(b); + } + } + } + } + + /** All nodes in input order. */ + public List<Node> getNodes() { + return nodes; + } + + /** All root nodes (not covered by any other grouping set in the input). */ + public List<Node> getRoots() { + List<Node> roots = new ArrayList<>(); + for (Node node : nodes) { + if (node.isRoot()) { + roots.add(node); + } + } + return roots; + } + + /** + * Returns all nodes in topological order using Kahn's algorithm: for every node in the + * returned list, all of its parents appear strictly before it. + */ + public List<Node> topologicalSort() { + Map<Node, Integer> inDegree = new HashMap<>(); + for (Node node : nodes) { + inDegree.put(node, node.parents.size()); + } + + Queue<Node> queue = new ArrayDeque<>(); + for (Node node : nodes) { + if (node.isRoot()) { + queue.add(node); + } + } + + List<Node> result = new ArrayList<>(nodes.size()); + while (!queue.isEmpty()) { + Node current = queue.poll(); + result.add(current); + for (Node child : current.children) { + if (inDegree.merge(child, -1, Integer::sum) == 0) { + queue.add(child); + } + } + } + return result; + } + + /** + * Generates one LET clause per node in topological order. + * + * <p>Each LET clause binds a fresh variable to a sub-SELECT: + * <ul> + * <li>Root nodes: FROM is a deep copy of {@code originalSelectBlock}'s FROM clause.</li> + * <li>Non-root nodes: FROM is the first (closest) parent's LET variable, bound to itself + * ({@code FROM $parent AS $parent}).</li> + * <li>SELECT keeps variables in the node's grouping set and replaces all others with NULL. + * For non-root nodes, aggregate function arguments are replaced with the parent's + * aggregate output variable (e.g. {@code SUM($sales)} becomes {@code SUM($total_sales)}).</li> + * <li>GROUP BY groups on this node's grouping set pairs.</li> + * </ul> + * + * <p>After this call, {@link Node#getLetVar()} returns the bound variable for every node. + */ + public List<LetClause> generateLetClauses(SelectBlock originalSelectBlock, LangRewritingContext context) + throws CompilationException { + List<Node> sorted = topologicalSort(); + List<LetClause> letClauses = new ArrayList<>(sorted.size()); + + for (Node node : sorted) { + VariableExpr letVar = new VariableExpr(context.newVariable()); + node.letVar = letVar; + + FromClause fromClause = buildFromClause(node, originalSelectBlock); + SelectClause selectClause = + buildSelectClause(originalSelectBlock.getSelectClause(), node.vars, node.isRoot()); + GroupbyClause gbyClause = buildGroupByClause(node.groupingSet, fromClause, context); + + SelectBlock subBlock = new SelectBlock(selectClause, fromClause, null, gbyClause, null); + SelectSetOperation setOp = new SelectSetOperation(new SetOperationInput(subBlock, null), null); + SelectExpression subQuery = new SelectExpression(null, setOp, null, null, true); + + letClauses.add(new LetClause(letVar, subQuery)); + } + + return letClauses; + } + + private static FromClause buildFromClause(Node node, SelectBlock originalSelectBlock) throws CompilationException { + if (node.isRoot()) { + return (FromClause) SqlppRewriteUtil.deepCopy(originalSelectBlock.getFromClause()); + } + // Non-root: FROM $parentLetVar AS $parentLetVar + // The parent's LET var acts as both the collection source and the per-element binding alias. + VariableExpr parentLetVar = node.parents.get(0).letVar; + return new FromClause(Collections.singletonList(new FromTerm(parentLetVar, parentLetVar, null, null))); + } + + /** + * Builds the SELECT clause for a Hasse node: + * <ul> + * <li>Variable projections in {@code nodeVars} are kept as-is.</li> + * <li>Variable projections NOT in {@code nodeVars} are replaced with {@code NULL} + * (preserving the projection name so the output schema stays uniform).</li> + * <li>Non-variable projections (aggregates / function calls): + * kept unchanged for root nodes; for non-root nodes the call's argument is replaced + * with the output variable derived from the projection's alias name, so the child + * re-aggregates the parent's already-aggregated value.</li> + * </ul> + */ + private static SelectClause buildSelectClause(SelectClause original, Set<VariableExpr> nodeVars, boolean isRoot) { + if (!original.selectRegular()) { + return original; + } + List<Projection> result = new ArrayList<>(); + for (Projection p : original.getSelectRegular().getProjections()) { + if (p.getKind() != Projection.Kind.NAMED_EXPR) { + result.add(p); + continue; + } + Expression expr = p.getExpression(); + if (expr.getKind() == Expression.Kind.VARIABLE_EXPRESSION) { + if (nodeVars.contains(expr)) { + result.add(p); // grouping column in this set — keep + } else { + // grouping column excluded from this set — emit NULL with same alias + LiteralExpr nullExpr = new LiteralExpr(NullLiteral.INSTANCE); + nullExpr.setSourceLocation(p.getSourceLocation()); + result.add(new Projection(Projection.Kind.NAMED_EXPR, nullExpr, p.getName())); + } + } else if (!isRoot && expr instanceof CallExpr) { + // Non-root: re-aggregate using the parent's output variable for this aggregate. + // E.g. SUM($sales) AS total_sales → SUM($total_sales) AS total_sales + VariableExpr parentOutputVar = + new VariableExpr(SqlppVariableUtil.toInternalVariableIdentifier(p.getName())); + parentOutputVar.setSourceLocation(p.getSourceLocation()); + CallExpr originalCall = (CallExpr) expr; + CallExpr newCall = + new CallExpr(originalCall.getFunctionSignature(), Collections.singletonList(parentOutputVar)); + newCall.setSourceLocation(p.getSourceLocation()); + result.add(new Projection(Projection.Kind.NAMED_EXPR, newCall, p.getName())); + } else { + result.add(p); // root aggregate or other expression — keep as-is + } + } + return new SelectClause(null, new SelectRegular(result), original.distinct()); + } + + private static GroupbyClause buildGroupByClause(List<GbyVariableExpressionPair> groupingSet, FromClause fromClause, + LangRewritingContext context) throws CompilationException { + List<List<GbyVariableExpressionPair>> gbyPairList = Collections.singletonList(new ArrayList<>(groupingSet)); + boolean groupAll = groupingSet.isEmpty(); + + // SqlppGroupByAggregationSugarVisitor (runs after us) requires every GroupbyClause to have + // a non-empty groupFieldList (the GROUP AS part). Build it from the FROM clause binding + // variables, mirroring what SqlppGroupByVisitor does for original GROUP BY clauses. + VariableExpr groupVar = new VariableExpr(context.newVariable()); + List<Pair<Expression, Identifier>> groupFieldList = new ArrayList<>(); + for (VariableExpr v : SqlppVariableUtil.getBindingVariables(fromClause)) { + String fieldName = SqlppVariableUtil.variableNameToDisplayedFieldName(v.getVar().getValue()); + groupFieldList.add(new Pair<>(v, new Identifier(fieldName))); + } + return new GroupbyClause(gbyPairList, Collections.emptyList(), null, groupVar, groupFieldList, false, groupAll); + } +} diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppGroupingSetsVisitor.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppGroupingSetsVisitor.java index 1259b64..2f0a83a 100644 --- a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppGroupingSetsVisitor.java +++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/SqlppGroupingSetsVisitor.java @@ -45,6 +45,8 @@ import org.apache.asterix.lang.common.literal.NullLiteral; import org.apache.asterix.lang.common.literal.StringLiteral; import org.apache.asterix.lang.common.rewrites.LangRewritingContext; +import org.apache.asterix.lang.sqlpp.clause.FromClause; +import org.apache.asterix.lang.sqlpp.clause.FromTerm; import org.apache.asterix.lang.sqlpp.clause.Projection; import org.apache.asterix.lang.sqlpp.clause.SelectBlock; import org.apache.asterix.lang.sqlpp.clause.SelectClause; @@ -316,74 +318,83 @@ SelectClause selectClause = selectBlock.getSelectClause(); boolean distinct = selectClause.distinct(); - boolean selectElement = selectClause.selectElement(); - boolean selectElementConvertToRegular = selectElement && !extraProjections.isEmpty(); - - // If we're converting SELECT VALUE to regular SELECT then we need to generate a field name - // that'll hold SELECT VALUE expression after the conversion. - // SELECT VALUE expr -> SELECT expr AS main_projection_name - String selectElementMainProjectionName = selectElementConvertToRegular - ? SqlppVariableUtil.variableNameToDisplayedFieldName(context.newVariable().getValue()) : null; tmpAllGroupingSetsVars.clear(); getAllGroupingSetsVars(groupingSets, tmpAllGroupingSetsVars); - List<SetOperationRight> newSetOpRightInputs = new ArrayList<>(nGroupingSets - 1); + // Build Hasse diagram over the grouping sets and generate one LET clause per node. + // Each LET clause's SELECT keeps the node's grouping vars (others become NULL) and + // re-aggregates function calls from the parent node's output. + GroupingSetsHasse groupingSetsHasse = new GroupingSetsHasse(groupingSets); + List<LetClause> letClauses = groupingSetsHasse.generateLetClauses(selectBlock, context); - // process 2nd and following grouping sets + // Build a pass-through SELECT clause shared by every UNION ALL arm. + // Grouping-column projections are kept as variables already in scope; + // aggregate projections become Variable[$outputName] to forward the LET result. + SelectClause passthroughSelect = buildUnionArmSelectClause(selectClause); - for (int i = 1; i < nGroupingSets; i++) { - List<GbyVariableExpressionPair> groupingSet = groupingSets.get(i); + // Build UNION ALL: one arm per node in topological order, each reading from its LET var. + List<GroupingSetsHasse.Node> sortedNodes = groupingSetsHasse.topologicalSort(); - tmpCurrentGroupingSetVars.clear(); - getGroupingSetVars(groupingSet, tmpCurrentGroupingSetVars); - - tmpGroupingSets.clear(); - tmpGroupingSets.add(groupingSet); - gby.setGbyPairList(tmpGroupingSets); // will be cloned by deepCopy() below - - tmpDecorPairList.clear(); - computeDecorVars(tmpCurrentGroupingSetVars, tmpAllGroupingSetsVars, tmpDecorPairList); - gby.setDecorPairList(tmpDecorPairList); // will be cloned by deepCopy() below - - SelectBlock newSelectBlock = (SelectBlock) SqlppRewriteUtil.deepCopy(selectBlock); - rewriteGroupingOperations(newSelectBlock, tmpCurrentGroupingSetVars, tmpAllGroupingSetsVars); - rewriteSelectClause(newSelectBlock, extraProjections, selectElementMainProjectionName); - - SetOperationRight newSetOpRight = - new SetOperationRight(SetOpType.UNION, false, new SetOperationInput(newSelectBlock, null)); - newSetOpRightInputs.add(newSetOpRight); + SelectBlock firstArm = buildUnionArm(sortedNodes.get(0), passthroughSelect); + List<SetOperationRight> rightInputs = new ArrayList<>(sortedNodes.size() - 1); + for (int i = 1; i < sortedNodes.size(); i++) { + SelectBlock arm = buildUnionArm(sortedNodes.get(i), passthroughSelect); + rightInputs.add(new SetOperationRight(SetOpType.UNION, false, new SetOperationInput(arm, null))); } - // process 1st grouping set + SelectSetOperation unionAllSetOp = new SelectSetOperation(new SetOperationInput(firstArm, null), rightInputs); + unionAllSetOp.setSourceLocation(selectBlock.getSourceLocation()); - List<GbyVariableExpressionPair> groupingSet = groupingSets.get(0); - gby.setGbyPairList(Collections.singletonList(groupingSet)); + // Attach LET clauses to the UNION ALL expression, then wrap in an outer + // SELECT VALUE $v FROM (...) AS $v so callers receive a SelectBlock. + SelectExpression innerSelectExpr = new SelectExpression(letClauses, unionAllSetOp, null, null, true); + innerSelectExpr.setSourceLocation(selectBlock.getSourceLocation()); - tmpCurrentGroupingSetVars.clear(); - getGroupingSetVars(groupingSet, tmpCurrentGroupingSetVars); + SelectBlock outerBlock = SetOperationVisitor.createSelectBlock(innerSelectExpr, distinct, null, null, context); + outerBlock.setSourceLocation(selectBlock.getSourceLocation()); + return outerBlock; + } - List<GbyVariableExpressionPair> newDecorPairList = new ArrayList<>(); - computeDecorVars(tmpCurrentGroupingSetVars, tmpAllGroupingSetsVars, newDecorPairList); - gby.setDecorPairList(newDecorPairList); + /** + * Builds one UNION ALL arm: {@code SELECT <passthroughSelect> FROM $letVar AS $letVar}. + * A fresh deep copy of {@code passthroughSelect} is made for each arm so that later + * in-place AST rewrites (e.g. variable-to-field-access substitution) do not mutate the + * shared template and corrupt sibling arms. + */ + private static SelectBlock buildUnionArm(GroupingSetsHasse.Node node, SelectClause passthroughSelect) + throws CompilationException { + VariableExpr letVar = node.getLetVar(); + FromClause fromClause = new FromClause(Collections.singletonList(new FromTerm(letVar, letVar, null, null))); + SelectClause selectClauseCopy = (SelectClause) SqlppRewriteUtil.deepCopy(passthroughSelect); + return new SelectBlock(selectClauseCopy, fromClause, null, null, null); + } - rewriteGroupingOperations(selectBlock, tmpCurrentGroupingSetVars, tmpAllGroupingSetsVars); - rewriteSelectClause(selectBlock, extraProjections, selectElementMainProjectionName); - - SetOperationInput newSetOpInput = new SetOperationInput(selectBlock, null); - - SelectSetOperation newSetOp = new SelectSetOperation(newSetOpInput, newSetOpRightInputs); - newSetOp.setSourceLocation(selectBlock.getSourceLocation()); - - SelectExpression newSelectExpr = new SelectExpression(null, newSetOp, null, null, true); - newSelectExpr.setSourceLocation(selectBlock.getSourceLocation()); - - return selectElement - ? SetOperationVisitor.createSelectBlock(newSelectExpr, distinct, - selectElementConvertToRegular ? SqlppRewriteUtil::getFieldByName : null, - selectElementConvertToRegular ? selectElementMainProjectionName : null, context) - : SetOperationVisitor.createSelectBlock(newSelectExpr, distinct, - SqlppGroupingSetsVisitor::removeFieldsByName, extraProjections.values(), context); + /** + * Builds the SELECT clause shared by every UNION ALL arm. + * Grouping-column projections ({@link Expression.Kind#VARIABLE_EXPRESSION}) are kept verbatim. + * Aggregate / function-call projections become {@code Variable[$outputName] AS name} so each + * arm forwards the already-computed value from its LET clause. + */ + private SelectClause buildUnionArmSelectClause(SelectClause original) { + if (!original.selectRegular()) { + return original; + } + List<Projection> projections = new ArrayList<>(); + for (Projection p : original.getSelectRegular().getProjections()) { + if (p.getKind() != Projection.Kind.NAMED_EXPR) { + projections.add(p); + continue; + } + if (p.getExpression().getKind() == Expression.Kind.VARIABLE_EXPRESSION) { + projections.add(p); + } else { + VariableExpr outputVar = new VariableExpr(SqlppVariableUtil.toInternalVariableIdentifier(p.getName())); + outputVar.setSourceLocation(p.getSourceLocation()); + projections.add(new Projection(Projection.Kind.NAMED_EXPR, outputVar, p.getName())); + } + } + return new SelectClause(null, new SelectRegular(projections), original.distinct()); } private static void rewriteSelectClause(SelectBlock selectBlock, Map<VariableExpr, String> extraProjections, -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21335?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: newchange Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: I06ab32218c44f7e733092bb7b9326217fd8b945a Gerrit-Change-Number: 21335 Gerrit-PatchSet: 1 Gerrit-Owner: Preetham Poluparthi <[email protected]>
