You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by al...@apache.org on 2023/04/24 20:31:17 UTC
[asterixdb] branch master updated: [ASTERIXDB-3167][COMP] Opt. intersecting indexes leading to a poor plan
This is an automated email from the ASF dual-hosted git repository.
alsuliman 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 834e2cc668 [ASTERIXDB-3167][COMP] Opt. intersecting indexes leading to a poor plan
834e2cc668 is described below
commit 834e2cc668ca4aaa160edf4423c17029d0106a55
Author: murali4104 <mu...@couchbase.com>
AuthorDate: Mon Apr 17 15:37:31 2023 -0700
[ASTERIXDB-3167][COMP] Opt. intersecting indexes leading to a poor plan
Change-Id: I856b923d21e6c4e9bc7e65dd9043bdf17bfe502b
Reviewed-on: https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/17491
Integration-Tests: Jenkins <je...@fulliautomatix.ics.uci.edu>
Tested-by: Jenkins <je...@fulliautomatix.ics.uci.edu>
Reviewed-by: Ali Alsuliman <al...@gmail.com>
---
.../am/AbstractIntroduceAccessMethodRule.java | 88 +++++++++++++++-------
.../rules/am/IntroduceSelectAccessMethodRule.java | 72 ++++++++++++++++++
2 files changed, 132 insertions(+), 28 deletions(-)
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
index 52f02797ad..9996e1fa0b 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
@@ -27,6 +27,7 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
+import org.apache.asterix.common.config.DatasetConfig;
import org.apache.asterix.common.config.DatasetConfig.DatasetType;
import org.apache.asterix.common.config.DatasetConfig.IndexType;
import org.apache.asterix.common.exceptions.CompilationException;
@@ -293,6 +294,63 @@ public abstract class AbstractIntroduceAccessMethodRule implements IAlgebraicRew
return false;
}
+ protected List<List<String>> findKeyFieldNames(Index index) throws CompilationException {
+ List<List<String>> keyFieldNames = new ArrayList<>();
+ DatasetConfig.IndexType indexType = index.getIndexType();
+ switch (Index.IndexCategory.of(indexType)) {
+ case ARRAY:
+ Index.ArrayIndexDetails arrayIndexDetails = (Index.ArrayIndexDetails) index.getIndexDetails();
+ for (Index.ArrayIndexElement e : arrayIndexDetails.getElementList()) {
+ for (int i = 0; i < e.getProjectList().size(); i++) {
+ List<String> project = e.getProjectList().get(i);
+ keyFieldNames.add(ArrayIndexUtil.getFlattenedKeyFieldNames(e.getUnnestList(), project));
+ }
+ }
+ break;
+ case VALUE:
+ Index.ValueIndexDetails valueIndexDetails = (Index.ValueIndexDetails) index.getIndexDetails();
+ keyFieldNames = valueIndexDetails.getKeyFieldNames();
+ break;
+ case TEXT:
+ Index.TextIndexDetails textIndexDetails = (Index.TextIndexDetails) index.getIndexDetails();
+ keyFieldNames = textIndexDetails.getKeyFieldNames();
+ break;
+ default:
+ throw new CompilationException(ErrorCode.COMPILATION_UNKNOWN_INDEX_TYPE, String.valueOf(indexType));
+ }
+
+ return keyFieldNames;
+ }
+
+ protected List<IAType> findKeyTypes(Index index) throws CompilationException {
+ List<IAType> keyFieldTypes = new ArrayList<>();
+ DatasetConfig.IndexType indexType = index.getIndexType();
+ switch (Index.IndexCategory.of(indexType)) {
+ case ARRAY:
+ Index.ArrayIndexDetails arrayIndexDetails = (Index.ArrayIndexDetails) index.getIndexDetails();
+ for (Index.ArrayIndexElement e : arrayIndexDetails.getElementList()) {
+ for (int i = 0; i < e.getProjectList().size(); i++) {
+ List<String> project = e.getProjectList().get(i);
+ keyFieldTypes.add(e.getTypeList().get(i));
+ }
+ }
+ break;
+ case VALUE:
+ Index.ValueIndexDetails valueIndexDetails = (Index.ValueIndexDetails) index.getIndexDetails();
+ keyFieldTypes = valueIndexDetails.getKeyFieldTypes();
+ break;
+ case TEXT:
+ Index.TextIndexDetails textIndexDetails = (Index.TextIndexDetails) index.getIndexDetails();
+ keyFieldTypes = textIndexDetails.getKeyFieldTypes();
+ break;
+ default:
+ throw new CompilationException(ErrorCode.COMPILATION_UNKNOWN_INDEX_TYPE, String.valueOf(indexType));
+ }
+
+ return keyFieldTypes;
+
+ }
+
/**
* Removes irrelevant access methods candidates, based on whether the
* expressions in the query match those in the index. For example, some
@@ -318,34 +376,8 @@ public abstract class AbstractIntroduceAccessMethodRule implements IAlgebraicRew
indexExprAndVarIt.remove();
continue;
}
- List<List<String>> keyFieldNames;
- List<IAType> keyFieldTypes;
- switch (Index.IndexCategory.of(indexType)) {
- case ARRAY:
- Index.ArrayIndexDetails arrayIndexDetails = (Index.ArrayIndexDetails) index.getIndexDetails();
- keyFieldNames = new ArrayList<>();
- keyFieldTypes = new ArrayList<>();
- for (Index.ArrayIndexElement e : arrayIndexDetails.getElementList()) {
- for (int i = 0; i < e.getProjectList().size(); i++) {
- List<String> project = e.getProjectList().get(i);
- keyFieldNames.add(ArrayIndexUtil.getFlattenedKeyFieldNames(e.getUnnestList(), project));
- keyFieldTypes.add(e.getTypeList().get(i));
- }
- }
- break;
- case VALUE:
- Index.ValueIndexDetails valueIndexDetails = (Index.ValueIndexDetails) index.getIndexDetails();
- keyFieldNames = valueIndexDetails.getKeyFieldNames();
- keyFieldTypes = valueIndexDetails.getKeyFieldTypes();
- break;
- case TEXT:
- Index.TextIndexDetails textIndexDetails = (Index.TextIndexDetails) index.getIndexDetails();
- keyFieldNames = textIndexDetails.getKeyFieldNames();
- keyFieldTypes = textIndexDetails.getKeyFieldTypes();
- break;
- default:
- throw new CompilationException(ErrorCode.COMPILATION_UNKNOWN_INDEX_TYPE, String.valueOf(indexType));
- }
+ List<List<String>> keyFieldNames = findKeyFieldNames(index);
+ List<IAType> keyFieldTypes = findKeyTypes(index);
boolean allUsed = true;
int lastFieldMatched = -1;
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
index 43e482b7c2..24a7fb25b4 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
@@ -26,6 +26,7 @@ import java.util.Optional;
import java.util.TreeMap;
import org.apache.asterix.algebra.operators.CommitOperator;
+import org.apache.asterix.common.config.DatasetConfig;
import org.apache.asterix.common.exceptions.CompilationException;
import org.apache.asterix.common.exceptions.ErrorCode;
import org.apache.asterix.metadata.declared.MetadataProvider;
@@ -372,6 +373,76 @@ public class IntroduceSelectAccessMethodRule extends AbstractIntroduceAccessMeth
return lop;
}
+ // list1 is <= list2 in terms of size; so check if everything in list1 is also in list2 in the same order
+ protected boolean prefix(List<List<String>> list1, List<List<String>> list2) {
+ int i, j;
+
+ for (i = 0; i < list1.size(); i++) {
+ List<String> l1 = list1.get(i);
+ List<String> l2 = list2.get(i);
+ if (l1.size() != l2.size()) {
+ return false;
+ }
+ for (j = 0; j < l1.size(); j++) {
+ String s1 = l1.get(j);
+ String s2 = l2.get(j);
+ if (!(s1.equals(s2))) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ protected void removeSmallerPrefixIndexes(List<Pair<IAccessMethod, Index>> indexes) throws CompilationException {
+ int len = indexes.size();
+ int i, j;
+ Index indexI, indexJ;
+ boolean include[];
+ include = new boolean[len];
+ for (i = 0; i < len; i++) {
+ include[i] = true; // Initially every index is included.
+ }
+
+ List<List<String>> fieldNamesI, fieldNamesJ;
+
+ for (i = 0; i < len - 1; i++) {
+ if (include[i]) {
+ IAccessMethod ami = indexes.get(i).first;
+ indexI = indexes.get(i).second;
+ DatasetConfig.IndexType typeI = indexI.getIndexType();
+ fieldNamesI = findKeyFieldNames(indexI);
+
+ for (j = i + 1; j < len; j++) {
+ if (include[j]) {
+ IAccessMethod amj = indexes.get(j).first;
+ if (ami == amj) { // should be the same accessMethods
+ indexJ = indexes.get(j).second;
+ DatasetConfig.IndexType typeJ = indexJ.getIndexType();
+ if (typeI == typeJ) {
+ fieldNamesJ = findKeyFieldNames(indexJ);
+ if (fieldNamesI.size() <= fieldNamesJ.size()) {
+ if (prefix(fieldNamesI, fieldNamesJ)) {
+ include[i] = false;
+ }
+ } else if (prefix(fieldNamesJ, fieldNamesI)) {
+ include[j] = false;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // remove the shorter indexes if any
+ for (i = len - 1; i >= 0; i--) { // removing from the end; seems safer that way
+ if (!include[i]) { // if this index can be removed it, do so;
+ indexes.remove(i);
+ }
+ }
+ }
+
/**
* Recursively traverse the given plan and check whether a SELECT operator exists.
* If one is found, maintain the path from the root to SELECT operator and
@@ -486,6 +557,7 @@ public class IntroduceSelectAccessMethodRule extends AbstractIntroduceAccessMeth
// Choose all indexes that will be applied.
chooseAllIndexes(analyzedAMs, chosenIndexes);
+ removeSmallerPrefixIndexes(chosenIndexes);
if (chosenIndexes == null || chosenIndexes.isEmpty()) {
// We can't apply any index for this SELECT operator