You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2026/06/25 12:00:26 UTC

[S] Change in asterixdb[master]: wip compilation optimizations

From Janhavi Tripurwar <ja...@apache.org>:

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 <ja...@apache.org>