>From Janhavi Tripurwar <[email protected]>:
Janhavi Tripurwar has uploaded this change for review. (
https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21368?usp=email )
Change subject: wip compilation optimizations
......................................................................
wip compilation optimizations
Change-Id: Ie9cbb77084510244bd119cbd2f1023c816ae351e
---
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
2 files changed, 20 insertions(+), 5 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb
refs/changes/68/21368/1
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
index 3d4986d..c5abc56 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
@@ -19,9 +19,11 @@
package org.apache.asterix.optimizer.rules.am;
import java.util.ArrayList;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
+import java.util.Set;
import java.util.TreeMap;
import org.apache.asterix.metadata.entities.Dataset;
@@ -31,6 +33,7 @@
import org.apache.hyracks.algebricks.common.utils.Pair;
import org.apache.hyracks.algebricks.common.utils.Quadruple;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import
org.apache.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
import
org.apache.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
/**
@@ -41,6 +44,11 @@
private List<IOptimizableFuncExpr> matchedFuncExprs = new
ArrayList<IOptimizableFuncExpr>();
+ // Mirrors the func-exprs in matchedFuncExprs for O(1) duplicate detection
(see addMatchedFuncExpr).
+ // Without this, de-duplicating a new candidate required a linear scan
with a deep equals() over all
+ // already-matched exprs, which is O(n^2) for conditions with many
conjuncts/disjuncts (e.g. a large IN list).
+ private final Set<AbstractFunctionCallExpression> matchedFuncExprSet = new
HashSet<>();
+
// Contains candidate indexes and a list of (integer,integer) tuples that
index into matchedFuncExprs and
// matched variable inside this expr. We are mapping from candidate
indexes to a list of function expressions
// that match one of the index's expressions.
@@ -112,6 +120,13 @@
public void addMatchedFuncExpr(IOptimizableFuncExpr optFuncExpr) {
matchedFuncExprs.add(optFuncExpr);
+ matchedFuncExprSet.add(optFuncExpr.getFuncExpr());
+ }
+
+ // O(1) structural-duplicate check, equivalent to scanning
getMatchedFuncExprs() and comparing
+ // getFuncExpr().equals(funcExpr), but without the O(n) deep-equals scan
per insertion.
+ public boolean containsMatchedFuncExpr(AbstractFunctionCallExpression
funcExpr) {
+ return matchedFuncExprSet.contains(funcExpr);
}
public Iterator<Map.Entry<Index, List<Pair<Integer, Integer>>>>
getIteratorForIndexExprsAndVars() {
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
index 8c854da..fd71b5f 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
@@ -353,12 +353,12 @@
private static void
addNewOptFuncExprToAnalysisCtx(AbstractFunctionCallExpression funcExpr,
OptimizableFuncExpr newOptFuncExpr, AccessMethodAnalysisContext
analysisCtx) {
- for (IOptimizableFuncExpr optFuncExpr :
analysisCtx.getMatchedFuncExprs()) {
- //avoid additional optFuncExpressions in case of a join
- if (optFuncExpr.getFuncExpr().equals(funcExpr)) {
- return;
- }
+ //avoid additional optFuncExpressions in case of a join (O(1)
structural-duplicate check;
+ //previously a linear scan with deep equals(), i.e. O(n^2) for
many-conjunct/disjunct conditions)
+ if (analysisCtx.containsMatchedFuncExpr(funcExpr)) {
+ return;
}
+
analysisCtx.addMatchedFuncExpr(newOptFuncExpr);
}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21368?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: Ie9cbb77084510244bd119cbd2f1023c816ae351e
Gerrit-Change-Number: 21368
Gerrit-PatchSet: 1
Gerrit-Owner: Janhavi Tripurwar <[email protected]>
