You are viewing a plain text version of this content. The canonical link for it is here.

Posted to notifications@asterixdb.apache.org by "Taewoo Kim (Code Review)" <do...@asterixdb.incubator.apache.org> on 2016/02/06 02:52:23 UTC

Change in asterixdb[master]: ASTERIXDB-1157: Implemented Limit Pushdown into Order (Exter...

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 <wa...@gmail.com>

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Taewoo Kim (Code Review)" <do...@asterixdb.incubator.apache.org>.

Taewoo Kim has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 5:

@Yingyi: it happens regardless of my rule. When I add "ConstantFoldingRule" after "CopyLimitDownRule", it happens. But, it's not happening after "CopyLimitDownRule". It's happening after "RemoveUnusedAssignRule".

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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 5
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: No

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Yingyi Bu (Code Review)" <do...@asterixdb.incubator.apache.org>.

Yingyi Bu has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 5:

@Taewoo, I think in general, record functions shouldn't be constant-folded.  Maybe that causes the failures.
What you can test is to just disable your new rule but keep the added application of ConstantFoldRule to see if the failures were caused by your rule or by the folding of those record functions.

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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 5
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: No

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Jenkins (Code Review)" <do...@asterixdb.incubator.apache.org>.

Jenkins has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 3: Verified-1

Build Unstable 

https://asterix-jenkins.ics.uci.edu/job/asterix-gerrit-topic/669/ : UNSTABLE

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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 3
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: No

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Yingyi Bu (Code Review)" <do...@asterixdb.incubator.apache.org>.

Yingyi Bu has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 7: Code-Review+1

(2 comments)

Just two minor comments.

https://asterix-gerrit.ics.uci.edu/#/c/617/7/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/ConstantFoldingRule.java
File asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/ConstantFoldingRule.java:

Line 87:     private final ImmutableSet<FunctionIdentifier> funcIDSetThatShouldNotBeApplied = ImmutableSet.of(
static? and rename the variable according to static variable convention?


Line 195:             if (expr.getFunctionIdentifier().equals(AsterixBuiltinFunctions.OPEN_RECORD_CONSTRUCTOR)) {
can you move this also into funcIDSetThatShouldNotBeApplied?


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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 7
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: Yes

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Yingyi Bu (Code Review)" <do...@asterixdb.incubator.apache.org>.

Yingyi Bu has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 4:

(1 comment)

https://asterix-gerrit.ics.uci.edu/#/c/617/4/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java
File asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/PushLimitIntoOrderByRule.java:

Line 115:             // a copied non-topmost LIMIT can contain NUMERIC-ADD to add the given limit value + offset value
> Throughout the compilation, this LIMIT remains as "NUMERIC_ADD", it doesn't
It is probably because ConstantFoldingRule is applied before CopyLimitDownRule.

What you can do is to apply ConstantFoldingRule again after you do CopyLimitDownRule, by setting the RuleCollections properly.


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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 4
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: Yes

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Yingyi Bu (Code Review)" <do...@asterixdb.incubator.apache.org>.

Yingyi Bu has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 8: Code-Review+2

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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 8
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: No

Change in asterixdb[master]: ASTERIXDB-1157: Pushdown Limit

Posted by "Jenkins (Code Review)" <do...@asterixdb.incubator.apache.org>.

Jenkins has posted comments on this change.

Change subject: ASTERIXDB-1157: Pushdown Limit
......................................................................


Patch Set 5:

Build Started https://asterix-jenkins.ics.uci.edu/job/asterix-gerrit-topic/672/

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

Gerrit-MessageType: comment
Gerrit-Change-Id: I19aa4ce402b1834d9f68320acb72d7635a41a837
Gerrit-PatchSet: 5
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Reviewer: Jianfeng Jia <ji...@gmail.com>
Gerrit-Reviewer: Taewoo Kim <wa...@gmail.com>
Gerrit-Reviewer: Yingyi Bu <bu...@gmail.com>
Gerrit-Reviewer: Young-Seok Kim <ki...@gmail.com>
Gerrit-HasComments: No