asterixdb-notifications mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Taewoo Kim (Code Review)" <do-not-re...@asterixdb.incubator.apache.org>
Subject Change in asterixdb[master]: ASTERIXDB-1157: Implemented Limit Pushdown into Order (Exter...
Date Sat, 06 Feb 2016 01:52:23 GMT
Taewoo Kim has uploaded a new change for review.

  https://asterix-gerrit.ics.uci.edu/617

Change subject: ASTERIXDB-1157: Implemented Limit Pushdown into Order (ExternalSort)
......................................................................

ASTERIXDB-1157: Implemented Limit Pushdown into Order (ExternalSort)

Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
---
M asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
A asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java
M asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
3 files changed, 143 insertions(+), 0 deletions(-)


  git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/17/617/1

diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
index 4187059..62cada1 100644
--- a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
@@ -56,6 +56,7 @@
 import org.apache.asterix.optimizer.rules.PushAggregateIntoGroupbyRule;
 import org.apache.asterix.optimizer.rules.PushFieldAccessRule;
 import org.apache.asterix.optimizer.rules.PushGroupByThroughProduct;
+import org.apache.asterix.optimizer.rules.PushLimitIntoOrderByRule;
 import org.apache.asterix.optimizer.rules.PushProperJoinThroughProduct;
 import org.apache.asterix.optimizer.rules.PushSimilarityFunctionsBelowJoin;
 import org.apache.asterix.optimizer.rules.RemoveRedundantListifyRule;
@@ -310,6 +311,7 @@
         List<IAlgebraicRewriteRule> physicalRewritesTopLevel = new LinkedList<IAlgebraicRewriteRule>();
         physicalRewritesTopLevel.add(new PushNestedOrderByUnderPreSortedGroupByRule());
         physicalRewritesTopLevel.add(new CopyLimitDownRule());
+        physicalRewritesTopLevel.add(new PushLimitIntoOrderByRule());
         physicalRewritesTopLevel.add(new IntroduceProjectsRule());
         physicalRewritesTopLevel.add(new SetAlgebricksPhysicalOperatorsRule());
         physicalRewritesTopLevel.add(new IntroduceRapidFrameFlushProjectAssignRule());
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java
b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java
new file mode 100644
index 0000000..565952d
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java
@@ -0,0 +1,135 @@
+/*
+ * 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.optimizer.rules;
+
+import org.apache.asterix.optimizer.rules.am.AccessMethodUtils;
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import org.apache.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.LimitOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.physical.StableSortPOperator;
+import org.apache.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import org.apache.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+import org.apache.hyracks.algebricks.core.rewriter.base.PhysicalOptimizationConfig;
+
+/**
+ * If an ORDER operator is followed by LIMIT, then we can push LIMIT into ORDER operator.
+ * Finally, ORDER operator use TopKSorterOperatorDescriptor that can efficiently
+ * sort tuples and fetch top K results.
+ * =================
+ * matching pattern:
+ * limit <- order
+ * =
+ * producing pattern:
+ * limit <- new order (topK applied)
+ */
+public class PushLimitIntoOrderByRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext
context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext
context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        // The current operator should be LIMIT operator.
+        if (op.getOperatorTag() != LogicalOperatorTag.LIMIT) {
+            return false;
+        }
+
+        Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+
+        if (context.checkAndAddToAlreadyCompared(op, op2)) {
+            return false;
+        }
+
+        // Should be ORDER operator
+        if (op2.getOperatorTag() != LogicalOperatorTag.ORDER) {
+            return false;
+        } else {
+            // ORDER operator is followed by LIMIT. Thus we can check whether we can apply
this rule.
+            boolean res = pushLimitIntoOrder(opRef, opRef2, context);
+            if (res) {
+                OperatorPropertiesUtil.typeOpRec(opRef, context);
+            }
+            return res;
+        }
+    }
+
+    /**
+     * Generate new ORDER operator that uses TopKSort module and replaces the old ORDER operator.
+     */
+    private boolean pushLimitIntoOrder(Mutable<ILogicalOperator> opRef, Mutable<ILogicalOperator>
opRef2,
+            IOptimizationContext context) throws AlgebricksException {
+        PhysicalOptimizationConfig physicalOptimizationConfig = context.getPhysicalOptimizationConfig();
+        LimitOperator limitOp = (LimitOperator) opRef.getValue();
+        OrderOperator orderOp = (OrderOperator) opRef2.getValue();
+        long topK = -1;
+
+        // We don't push-down LIMIT into in-memory sort.
+        if (orderOp.getPhysicalOperator().getOperatorTag() != PhysicalOperatorTag.STABLE_SORT)
{
+            return false;
+        }
+
+        // Get the LIMIT constant
+        if (limitOp.getMaxObjects().getValue().getExpressionTag() == LogicalExpressionTag.CONSTANT)
{
+            // Currently, we support LIMIT with a constant value.
+            topK = AccessMethodUtils.getInt64Constant(limitOp.getMaxObjects());
+            // If topK is huge, there is no reason to use topK sort module
+            // since the original external sort's performance might be better.
+            if (topK > Integer.MAX_VALUE) {
+                return false;
+            }
+        } else {
+            return false;
+        }
+
+        // Get the offset constant if there is one. If one presents, then topK = topK + offset.
+        // This is because we can't apply offset to the external sort.
+        // Final topK will be applied through LIMIT.
+        if (limitOp.getOffset().getValue() != null
+                && limitOp.getOffset().getValue().getExpressionTag() == LogicalExpressionTag.CONSTANT)
{
+            topK = topK + ((int) AccessMethodUtils.getInt64Constant(limitOp.getOffset()));
+        }
+
+        // Create the new ORDER operator, set the topK value, and replace the current one.
+        OrderOperator newOrderOp = new OrderOperator(orderOp.getOrderExpressions(), (int)
topK);
+        newOrderOp.setPhysicalOperator(
+                new StableSortPOperator(physicalOptimizationConfig.getMaxFramesExternalSort(),
newOrderOp.getTopK()));
+        newOrderOp.getInputs().addAll(orderOp.getInputs());
+        newOrderOp.setExecutionMode(orderOp.getExecutionMode());
+        newOrderOp.recomputeSchema();
+        newOrderOp.computeDeliveredPhysicalProperties(context);
+        opRef2.setValue(newOrderOp);
+        context.computeAndSetTypeEnvironmentForOperator(newOrderOp);
+        context.addToDontApplySet(this, limitOp);
+
+        return true;
+    }
+
+}
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
index 1ff3df6..9165506 100644
--- a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
@@ -38,6 +38,7 @@
 import org.apache.asterix.metadata.utils.DatasetUtils;
 import org.apache.asterix.om.base.ABoolean;
 import org.apache.asterix.om.base.AInt32;
+import org.apache.asterix.om.base.AInt64;
 import org.apache.asterix.om.base.AString;
 import org.apache.asterix.om.base.IAObject;
 import org.apache.asterix.om.constants.AsterixConstantValue;
@@ -118,6 +119,11 @@
         return ((AInt32) obj).getIntegerValue();
     }
 
+    public static long getInt64Constant(Mutable<ILogicalExpression> expr) {
+        IAObject obj = ((AsterixConstantValue) ((ConstantExpression) expr.getValue()).getValue()).getObject();
+        return ((AInt64) obj).getLongValue();
+    }
+
     public static boolean getBooleanConstant(Mutable<ILogicalExpression> expr) {
         IAObject obj = ((AsterixConstantValue) ((ConstantExpression) expr.getValue()).getValue()).getObject();
         return ((ABoolean) obj).getBoolean();

-- 
To view, visit https://asterix-gerrit.ics.uci.edu/617
To unsubscribe, visit https://asterix-gerrit.ics.uci.edu/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 1
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wangsaeu@gmail.com>

Mime
View raw message