[GitHub] [incubator-doris] kangkaisen commented on a change in pull request #3278: Optimzie where cluase when have duplicate ors

[GitBox <gi...@apache.org>]

kangkaisen commented on a change in pull request #3278: Optimzie where cluase when have duplicate ors
URL: https://github.com/apache/incubator-doris/pull/3278#discussion_r405362817
 
 

 ##########
 File path: fe/src/main/java/org/apache/doris/analysis/SelectStmt.java
 ##########
 @@ -504,6 +509,132 @@ private void whereClauseRewrite() {
         }
     }
 
+    /**
+     * this function only process (a and b and c) or (d and e and f) like clause,
+     * this function will extract this to [[a, b, c], [d, e, f]]
+     */
+    private List<List<Expr>> extractDuplicateOrs(CompoundPredicate expr) {
+        List<List<Expr>> orExprs = new ArrayList<>();
+        for (Expr child : expr.getChildren()) {
+            if (child instanceof CompoundPredicate) {
+                CompoundPredicate childCp = (CompoundPredicate) child;
+                if (childCp.getOp() == CompoundPredicate.Operator.OR) {
+                    orExprs.addAll(extractDuplicateOrs(childCp));
+                    continue;
+                } else if (childCp.getOp() == CompoundPredicate.Operator.AND) {
+                    orExprs.add(flatAndExpr(child));
+                    continue;
+                }
+            }
+            orExprs.add(Arrays.asList(child));
+        }
+        return orExprs;
+    }
+
+    /**
+     * This function attempts to apply the inverse OR distributive law:
+     * ((A AND B) OR (A AND C))  =>  (A AND (B OR C))
+     * That is, locate OR clauses in which every subclause contains an
+     * identical term, and pull out the duplicated terms.
+     */
+    private Expr deduplicateOrs(Expr expr) {
+        if (expr instanceof CompoundPredicate && ((CompoundPredicate) expr).getOp() == CompoundPredicate.Operator.OR) {
+            Expr rewritedExpr = processDuplicateOrs(extractDuplicateOrs((CompoundPredicate) expr));
+            if (rewritedExpr != null) {
+                return rewritedExpr;
+            }
+        } else {
+            for (int i = 0; i < expr.getChildren().size(); i++) {
+                Expr rewritedExpr = deduplicateOrs(expr.getChild(i));
+                if (rewritedExpr != null) {
+                    expr.setChild(i, rewritedExpr);
+                }
+            }
+        }
+        return expr;
+    }
+
+    /**
+     * try to flat and , a and b and c => [a, b, c]
+     */
+    private List<Expr> flatAndExpr(Expr expr) {
+        List<Expr> andExprs = new ArrayList<>();
+        if (expr instanceof CompoundPredicate && ((CompoundPredicate) expr).getOp() == CompoundPredicate.Operator.AND) {
+            andExprs.addAll(flatAndExpr(expr.getChild(0)));
+            andExprs.addAll(flatAndExpr(expr.getChild(1)));
+        } else {
+            andExprs.add(expr);
+        }
+        return andExprs;
+    }
+
+    /**
+     * the input is a list of list, the inner list is and connected exprs, the outer list is or connected
+     * for example clause (a and b and c) or (a and e and f) after extractDuplicateOrs will be [[a, b, c], [a, e, f]]
+     * this is the input of this function, first step is deduplicate [[a, b, c], [a, e, f]] => [[a], [b, c], [e, f]]
+     * then rebuild the expr to a and ((b and c) or (e and f))
+     */
+    private Expr processDuplicateOrs(List<List<Expr>> exprs) {
 
 Review comment:
   Could we move this improve to `ExprRewriteRule` ?

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org