This is an automated email from the ASF dual-hosted git repository.
vsarathy1 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/asterixdb.git
The following commit(s) were added to refs/heads/master by this push:
new 6d17c6205f [ASTERIXDB-3470][COMP] Correctly detect triangles in Join
Graph
6d17c6205f is described below
commit 6d17c6205fb09a4a18d4de1e833657cd74a136e0
Author: murali4104 <[email protected]>
AuthorDate: Fri Aug 16 11:40:28 2024 -0700
[ASTERIXDB-3470][COMP] Correctly detect triangles in Join Graph
Change-Id: I1537b09e5d21333d0d810cc058988fcadb5192f8
Reviewed-on: https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/18683
Integration-Tests: Jenkins <[email protected]>
Tested-by: Jenkins <[email protected]>
Reviewed-by: Vijay Sarathy <[email protected]>
---
.../asterix/optimizer/rules/cbo/JoinCondition.java | 1 +
.../asterix/optimizer/rules/cbo/JoinNode.java | 56 +++++++++++++++-------
.../warnings-limit/warnings-limit.03.regexadm | 18 +------
.../warnings-limit/warnings-limit.04.regexadm | 18 +------
.../warnings-limit/warnings-limit.05.regexadm | 18 +------
.../warnings-limit/warnings-limit.07.regexadm | 18 +------
.../warnings-limit/warnings-limit.08.regexadm | 18 +------
7 files changed, 51 insertions(+), 96 deletions(-)
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinCondition.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinCondition.java
index d56d38ad50..b5c290fda6 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinCondition.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinCondition.java
@@ -29,6 +29,7 @@ public class JoinCondition {
protected boolean outerJoin;
private boolean derived = false;
protected boolean partOfComposite = false;
+ protected boolean deleted = false;
protected int numberOfVars = 0; // how many variables
protected int componentNumber = 0; // for identifying if join graph is
connected
protected int datasetBits;
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
index d6ea457f85..b988ad9b7a 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
@@ -446,7 +446,10 @@ public class JoinNode {
if (this.applicableJoinConditions.size() >= 3) {
redundantSel = removeRedundantPred(this.applicableJoinConditions);
}
-
+ // mark all conditions back to non deleted state
+ for (JoinCondition jc : joinConditions) {
+ jc.deleted = false;
+ }
// By dividing by redundantSel, we are undoing the earlier
multiplication of all the selectivities.
return joinCard / redundantSel;
}
@@ -456,7 +459,7 @@ public class JoinNode {
if (jc1.comparisonType == JoinCondition.comparisonOp.OP_EQ
&& jc2.comparisonType == JoinCondition.comparisonOp.OP_EQ
&& jc3.comparisonType == JoinCondition.comparisonOp.OP_EQ) {
- sel = findRedundantSel(jc1.selectivity, jc2.selectivity,
jc3.selectivity);
+ sel = findRedundantSel(jc1, jc2, jc3);
} else {
// at least one of the predicates in not an equality predicate
//this can get messy here, as 1, or 2 or all 3 can be non equality
@@ -472,6 +475,35 @@ public class JoinNode {
return sel;
}
+ private static double findRedundantSel(JoinCondition jc1, JoinCondition
jc2, JoinCondition jc3) {
+ // find middle selectivity
+ if (jc2.selectivity <= jc1.selectivity && jc1.selectivity <=
jc3.selectivity) {
+ jc1.deleted = true;
+ return jc1.selectivity;
+ }
+ if (jc3.selectivity <= jc1.selectivity && jc1.selectivity <=
jc2.selectivity) {
+ jc1.deleted = true;
+ return jc1.selectivity;
+ }
+ if (jc1.selectivity <= jc2.selectivity && jc2.selectivity <=
jc3.selectivity) {
+ jc2.deleted = true;
+ return jc2.selectivity;
+ }
+ if (jc3.selectivity <= jc2.selectivity && jc2.selectivity <=
jc1.selectivity) {
+ jc2.deleted = true;
+ return jc2.selectivity;
+ }
+ if (jc1.selectivity <= jc3.selectivity && jc3.selectivity <=
jc2.selectivity) {
+ jc3.deleted = true;
+ return jc3.selectivity;
+ }
+ if (jc2.selectivity <= jc3.selectivity && jc3.selectivity <=
jc1.selectivity) {
+ jc3.deleted = true;
+ return jc3.selectivity;
+ }
+ return 1.0; // keep compiler happy
+ }
+
// if a redundant edge is found, we need to eliminate one of the edges.
// If two triangles share an edge, removing the common edge will suffice
// Each edge has two vertices. So we can only handle predicate with
exactly two tables such as R.a = S.a
@@ -485,21 +517,21 @@ public class JoinNode {
int[] verticesCopy = new int[6];
for (int i = 0; i <= applicablePredicatesInCurrentJn.size() - 3; i++) {
jc1 = joinConditions.get(applicablePredicatesInCurrentJn.get(i));
- if (jc1.partOfComposite) {
+ if (jc1.partOfComposite || jc1.deleted) {
continue; // must ignore these or the same triangles will be
found more than once.
}
vertices[0] = jc1.leftSideBits;
vertices[1] = jc1.rightSideBits;
for (int j = i + 1; j <= applicablePredicatesInCurrentJn.size() -
2; j++) {
jc2 =
joinConditions.get(applicablePredicatesInCurrentJn.get(j));
- if (jc2.partOfComposite) {
+ if (jc2.partOfComposite || jc2.deleted) {
continue;
}
vertices[2] = jc2.leftSideBits;
vertices[3] = jc2.rightSideBits;
for (int k = j + 1; k <=
applicablePredicatesInCurrentJn.size() - 1; k++) {
jc3 =
joinConditions.get(applicablePredicatesInCurrentJn.get(k));
- if (jc3.partOfComposite) {
+ if (jc3.partOfComposite || jc3.deleted) {
continue;
}
vertices[4] = jc3.leftSideBits;
@@ -510,7 +542,9 @@ public class JoinNode {
if (verticesCopy[0] == verticesCopy[1] && verticesCopy[2]
== verticesCopy[3]
&& verticesCopy[4] == verticesCopy[5]) {
// redundant edge found
- redundantSel *= adjustSelectivities(jc1, jc2, jc3);
+ if (!(jc1.deleted || jc2.deleted || jc3.deleted)) {
+ redundantSel *= adjustSelectivities(jc1, jc2, jc3);
+ }
}
}
}
@@ -518,16 +552,6 @@ public class JoinNode {
return redundantSel;
}
- private static double findRedundantSel(double sel1, double sel2, double
sel3) {
- double[] sels = new double[3];
- sels[0] = sel1;
- sels[1] = sel2;
- sels[2] = sel3;
-
- Arrays.sort(sels); // we are sorting to make this deterministic
- return sels[1]; // the middle one is closest to one of the extremes
- }
-
protected int addSingleDatasetPlans() {
List<PlanNode> allPlans = joinEnum.allPlans;
ICost opCost;
diff --git
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.03.regexadm
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.03.regexadm
index 0717e21b1b..69842dfe83 100644
---
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.03.regexadm
+++
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.03.regexadm
@@ -3,21 +3,7 @@
\s*\Q"signature": {\E
\s*\Q"*": "*"\E
\s*\Q},\E
-\s*\Q"results": [ { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q]\E
+\s*\Q"results": [
{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null}
]\E
\s*\Q,\E
\s*\Q"plans":{},\E
\s*\Q"warnings": [{\E\s*
@@ -40,4 +26,4 @@
\s*\Q"bufferCachePageReadCount": \E[0-9]+\Q,\E
\s*\Q"warningCount": 12\E
\s*\Q}\E
-\s*\Q}\E\s*
\ No newline at end of file
+\s*\Q}\E\s*
diff --git
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.04.regexadm
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.04.regexadm
index 7c0d2e7727..245357d076 100644
---
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.04.regexadm
+++
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.04.regexadm
@@ -3,21 +3,7 @@
\s*\Q"signature": {\E
\s*\Q"*": "*"\E
\s*\Q},\E
-\s*\Q"results": [ { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q]\E
+\s*\Q"results": [
{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null}
]\E
\s*\Q,\E
\s*\Q"plans":{},\E
\s*\Q"status": "success",\E
@@ -33,4 +19,4 @@
\s*\Q"bufferCachePageReadCount": \E[0-9]+\Q,\E
\s*\Q"warningCount": 10\E
\s*\Q}\E
-\s*\Q}\E\s*
\ No newline at end of file
+\s*\Q}\E\s*
diff --git
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.05.regexadm
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.05.regexadm
index 49d65fff11..28a9b78212 100644
---
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.05.regexadm
+++
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.05.regexadm
@@ -3,21 +3,7 @@
\s*\Q"signature": {\E
\s*\Q"*": "*"\E
\s*\Q},\E
-\s*\Q"results": [ { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q]\E
+\s*\Q"results": [
{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null}
]\E
\s*\Q,\E
\s*\Q"plans":{},\E
\s*\Q"status": "success",\E
@@ -33,4 +19,4 @@
\s*\Q"bufferCachePageReadCount": \E[0-9]+\Q,\E
\s*\Q"warningCount": 11\E
\s*\Q}\E
-\s*\Q}\E\s*
\ No newline at end of file
+\s*\Q}\E\s*
diff --git
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.07.regexadm
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.07.regexadm
index 49d65fff11..28a9b78212 100644
---
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.07.regexadm
+++
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.07.regexadm
@@ -3,21 +3,7 @@
\s*\Q"signature": {\E
\s*\Q"*": "*"\E
\s*\Q},\E
-\s*\Q"results": [ { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q]\E
+\s*\Q"results": [
{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null}
]\E
\s*\Q,\E
\s*\Q"plans":{},\E
\s*\Q"status": "success",\E
@@ -33,4 +19,4 @@
\s*\Q"bufferCachePageReadCount": \E[0-9]+\Q,\E
\s*\Q"warningCount": 11\E
\s*\Q}\E
-\s*\Q}\E\s*
\ No newline at end of file
+\s*\Q}\E\s*
diff --git
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.08.regexadm
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.08.regexadm
index 0717e21b1b..69842dfe83 100644
---
a/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.08.regexadm
+++
b/asterixdb/asterix-app/src/test/resources/runtimets/results_cbo/warnings/warnings-limit/warnings-limit.08.regexadm
@@ -3,21 +3,7 @@
\s*\Q"signature": {\E
\s*\Q"*": "*"\E
\s*\Q},\E
-\s*\Q"results": [ { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": false }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q, { "F1": { "a": 1 }, "F2": null }\E
-\s*\Q]\E
+\s*\Q"results": [
{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":false},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null},{"F1":{"a":1},"F2":null}
]\E
\s*\Q,\E
\s*\Q"plans":{},\E
\s*\Q"warnings": [{\E\s*
@@ -40,4 +26,4 @@
\s*\Q"bufferCachePageReadCount": \E[0-9]+\Q,\E
\s*\Q"warningCount": 12\E
\s*\Q}\E
-\s*\Q}\E\s*
\ No newline at end of file
+\s*\Q}\E\s*
