You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@atlas.apache.org by sh...@apache.org on 2016/07/22 07:11:57 UTC
incubator-atlas git commit: ATLAS-1042 Performance improvement
changes for propertykey+typeName based queries (sumasai via shwethags)
Repository: incubator-atlas
Updated Branches:
refs/heads/master b73e62ba3 -> a10444d39
ATLAS-1042 Performance improvement changes for propertykey+typeName based queries (sumasai via shwethags)
Project: http://git-wip-us.apache.org/repos/asf/incubator-atlas/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-atlas/commit/a10444d3
Tree: http://git-wip-us.apache.org/repos/asf/incubator-atlas/tree/a10444d3
Diff: http://git-wip-us.apache.org/repos/asf/incubator-atlas/diff/a10444d3
Branch: refs/heads/master
Commit: a10444d3939c93a6ab8b21c0f03a97e295190bc4
Parents: b73e62b
Author: Shwetha GS <ss...@hortonworks.com>
Authored: Fri Jul 22 12:41:45 2016 +0530
Committer: Shwetha GS <ss...@hortonworks.com>
Committed: Fri Jul 22 12:41:45 2016 +0530
----------------------------------------------------------------------
release-log.txt | 1 +
.../graph/GraphBackedSearchIndexer.java | 34 +-
.../atlas/services/DefaultMetadataService.java | 2 +
.../graph/GraphBackedSearchIndexerTest.java | 9 +-
.../graph/GraphRepoMapperScaleTest.java | 3 +
.../query/graph/GraphCentricQueryBuilder.java | 459 +++++++++++++++++++
6 files changed, 498 insertions(+), 10 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/release-log.txt
----------------------------------------------------------------------
diff --git a/release-log.txt b/release-log.txt
index a2d01ba..9a26e88 100644
--- a/release-log.txt
+++ b/release-log.txt
@@ -6,6 +6,7 @@ INCOMPATIBLE CHANGES:
ALL CHANGES:
+ATLAS-1042 Performance improvement changes for propertykey+typeName based queries (sumasai via shwethags)
ATLAS-1036 Multiple instances of AtlasPluginClassloader getting initialized (sumasai, mneethiraj)
ATLAS-1033 fix for issues flagged by Coverity scan (mneethiraj via sumasai)
ATLAS-1036 Compilation error on java 1.8 - GraphBackedDiscoveryService (shwethags via sumasai)
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/repository/src/main/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexer.java
----------------------------------------------------------------------
diff --git a/repository/src/main/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexer.java b/repository/src/main/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexer.java
index e960c2f..c77004d 100755
--- a/repository/src/main/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexer.java
+++ b/repository/src/main/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexer.java
@@ -106,6 +106,11 @@ public class GraphBackedSearchIndexer implements SearchIndexer, ActiveStateChang
// create a composite index for entity state
createIndexes(management, Constants.TIMESTAMP_PROPERTY_KEY, Long.class, false, Cardinality.SINGLE, true);
+ // create a mixed index for entity state. Set systemProperty flag deliberately to false
+ // so that it doesnt create a composite index which has issues with
+ // titan 0.5.4 - Refer https://groups.google.com/forum/#!searchin/aureliusgraphs/hemanth/aureliusgraphs/bx7T843mzXU/fjAsclx7GAAJ
+ createIndexes(management, Constants.STATE_PROPERTY_KEY, String.class, false, Cardinality.SINGLE, false);
+
// create a composite index for entity state
createIndexes(management, Constants.MODIFICATION_TIMESTAMP_PROPERTY_KEY, Long.class, false,
Cardinality.SINGLE, true);
@@ -170,7 +175,7 @@ public class GraphBackedSearchIndexer implements SearchIndexer, ActiveStateChang
LOG.info("Creating indexes for type name={}, definition={}", dataType.getName(), dataType.getClass());
try {
addIndexForType(management, dataType);
- LOG.debug("Index creation for type {} complete", dataType.getName());
+ LOG.info("Index creation for type {} complete", dataType.getName());
} catch (Throwable throwable) {
LOG.error("Error creating index for type {}", dataType, throwable);
//Rollback indexes if any failure
@@ -325,7 +330,7 @@ public class GraphBackedSearchIndexer implements SearchIndexer, ActiveStateChang
} else if (isUnique) {
// send uniqueness as false because there can be many vertexes with the same property value
// but state can be active / deleted.
- createCompositeIndex(management, propertyName, propertyClass, propertyKey, false);
+ createCompositeIndexWithTypeName(management, propertyName, propertyClass, propertyKey);
}
}
return propertyKey;
@@ -333,7 +338,7 @@ public class GraphBackedSearchIndexer implements SearchIndexer, ActiveStateChang
private void createCompositeIndex(TitanManagement management, String propertyName, Class propertyClass,
PropertyKey propertyKey, boolean enforceUniqueness) {
- LOG.debug("Creating composite index for property {} of type {} ", propertyName,
+ LOG.info("Creating composite index for property {} of type {} ", propertyName,
propertyClass.getName());
TitanManagement.IndexBuilder indexBuilder =
management.buildIndex(propertyName, Vertex.class).addKey(propertyKey);
@@ -341,17 +346,34 @@ public class GraphBackedSearchIndexer implements SearchIndexer, ActiveStateChang
indexBuilder.unique();
}
indexBuilder.buildCompositeIndex();
- LOG.debug("Created composite index for property {} of type {} ", propertyName, propertyClass.getName());
+ LOG.info("Created composite index for property {} of type {} ", propertyName, propertyClass.getName());
+ }
+
+ private void createCompositeIndexWithTypeName(TitanManagement management, String propertyName, Class propertyClass,
+ PropertyKey propertyKey) {
+ LOG.info("Creating composite index for property {} of type {} and {}", propertyName,
+ propertyClass.getName(), Constants.ENTITY_TYPE_PROPERTY_KEY);
+ PropertyKey typePropertyKey = management.getPropertyKey(Constants.ENTITY_TYPE_PROPERTY_KEY);
+ if (typePropertyKey == null) {
+ typePropertyKey = management.makePropertyKey(Constants.ENTITY_TYPE_PROPERTY_KEY).
+ dataType(String.class).cardinality(Cardinality.SINGLE)
+ .make();
+ }
+ TitanManagement.IndexBuilder indexBuilder =
+ management.buildIndex(propertyName + Constants.ENTITY_TYPE_PROPERTY_KEY, Vertex.class).
+ addKey(propertyKey).addKey(typePropertyKey);
+ indexBuilder.buildCompositeIndex();
+ LOG.info("Created composite index for property {} of type {} and {}", propertyName, propertyClass.getName(), Constants.ENTITY_TYPE_PROPERTY_KEY);
}
private void enhanceMixedIndex(TitanManagement management, String propertyName, Class propertyClass,
Cardinality cardinality, PropertyKey propertyKey) {
if (checkIfMixedIndexApplicable(propertyClass, cardinality)) {
//Use backing index
- LOG.debug("Creating backing index for property {} of type {} ", propertyName, propertyClass.getName());
+ LOG.info("Creating backing index for property {} of type {} ", propertyName, propertyClass.getName());
TitanGraphIndex vertexIndex = management.getGraphIndex(Constants.VERTEX_INDEX);
management.addIndexKey(vertexIndex, propertyKey);
- LOG.debug("Created backing index for property {} of type {} ", propertyName, propertyClass.getName());
+ LOG.info("Created backing index for property {} of type {} ", propertyName, propertyClass.getName());
}
}
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/repository/src/main/java/org/apache/atlas/services/DefaultMetadataService.java
----------------------------------------------------------------------
diff --git a/repository/src/main/java/org/apache/atlas/services/DefaultMetadataService.java b/repository/src/main/java/org/apache/atlas/services/DefaultMetadataService.java
index 484a877..b870c62 100755
--- a/repository/src/main/java/org/apache/atlas/services/DefaultMetadataService.java
+++ b/repository/src/main/java/org/apache/atlas/services/DefaultMetadataService.java
@@ -23,6 +23,8 @@ import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.inject.Provider;
+import com.thinkaurelius.titan.core.schema.TitanManagement;
+import com.tinkerpop.blueprints.Vertex;
import org.apache.atlas.ApplicationProperties;
import org.apache.atlas.AtlasClient;
import org.apache.atlas.AtlasConstants;
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/repository/src/test/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexerTest.java
----------------------------------------------------------------------
diff --git a/repository/src/test/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexerTest.java b/repository/src/test/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexerTest.java
index 3d9d45a..1fa0619 100644
--- a/repository/src/test/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexerTest.java
+++ b/repository/src/test/java/org/apache/atlas/repository/graph/GraphBackedSearchIndexerTest.java
@@ -69,6 +69,8 @@ public class GraphBackedSearchIndexerTest {
assertNotNull(edgeIndex);
assertTrue(edgeIndex.isMixedIndex());
assertTrue(Edge.class.isAssignableFrom(edgeIndex.getIndexedElement()));
+
+ verifyVertexIndexContains(managementSystem, Constants.STATE_PROPERTY_KEY);
}
@Test
@@ -126,15 +128,14 @@ public class GraphBackedSearchIndexerTest {
HierarchicalTypeDefinition<ClassType> databaseTypeDefinition =
createClassTypeDef("Database", "Database type description", null,
TypesUtil.createUniqueRequiredAttrDef("name", DataTypes.STRING_TYPE),
- TypesUtil.createUniqueRequiredAttrDef("managedType", managedType));
+ TypesUtil.createRequiredAttrDef("managedType", managedType));
ClassType databaseType = typeSystem.defineClassType(databaseTypeDefinition);
graphBackedSearchIndexer.onAdd(Arrays.asList(databaseType));
- verifySystemCompositeIndex(managementSystem, "Database.name", false);
- verifyVertexIndexContains(managementSystem, "Database.name");
+ verifySystemCompositeIndex(managementSystem, "Database.name" + Constants.ENTITY_TYPE_PROPERTY_KEY, false);
+ verifyVertexIndexContains(managementSystem, "Database.name" + Constants.ENTITY_TYPE_PROPERTY_KEY);
- verifySystemCompositeIndex(managementSystem, "Database.managedType", false);
verifyVertexIndexContains(managementSystem, "Database.managedType");
}
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/repository/src/test/java/org/apache/atlas/repository/graph/GraphRepoMapperScaleTest.java
----------------------------------------------------------------------
diff --git a/repository/src/test/java/org/apache/atlas/repository/graph/GraphRepoMapperScaleTest.java b/repository/src/test/java/org/apache/atlas/repository/graph/GraphRepoMapperScaleTest.java
index 2f02ae2..0a870d8 100755
--- a/repository/src/test/java/org/apache/atlas/repository/graph/GraphRepoMapperScaleTest.java
+++ b/repository/src/test/java/org/apache/atlas/repository/graph/GraphRepoMapperScaleTest.java
@@ -33,6 +33,7 @@ import org.apache.atlas.repository.Constants;
import org.apache.atlas.typesystem.ITypedReferenceableInstance;
import org.apache.atlas.typesystem.Referenceable;
import org.apache.atlas.typesystem.Struct;
+import org.apache.atlas.typesystem.persistence.Id;
import org.apache.atlas.typesystem.types.ClassType;
import org.apache.atlas.typesystem.types.IDataType;
import org.apache.atlas.typesystem.types.Multiplicity;
@@ -134,6 +135,8 @@ public class GraphRepoMapperScaleTest {
for (int index = 500; index < 600; index++) {
searchWithIndex("hive_table.name", "bar-" + index);
}
+
+ searchWithIndex(Constants.STATE_PROPERTY_KEY, Id.EntityState.ACTIVE.name());
}
private void searchWithOutIndex(String key, String value) {
http://git-wip-us.apache.org/repos/asf/incubator-atlas/blob/a10444d3/titan/src/main/java/com/thinkaurelius/titan/graphdb/query/graph/GraphCentricQueryBuilder.java
----------------------------------------------------------------------
diff --git a/titan/src/main/java/com/thinkaurelius/titan/graphdb/query/graph/GraphCentricQueryBuilder.java b/titan/src/main/java/com/thinkaurelius/titan/graphdb/query/graph/GraphCentricQueryBuilder.java
new file mode 100644
index 0000000..17453a4
--- /dev/null
+++ b/titan/src/main/java/com/thinkaurelius/titan/graphdb/query/graph/GraphCentricQueryBuilder.java
@@ -0,0 +1,459 @@
+/*
+ * Copyright 2012-2013 Aurelius LLC
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.thinkaurelius.titan.graphdb.query.graph;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.collect.*;
+import com.thinkaurelius.titan.core.*;
+import com.thinkaurelius.titan.core.attribute.Cmp;
+import com.thinkaurelius.titan.core.Cardinality;
+import com.thinkaurelius.titan.core.schema.SchemaStatus;
+import com.thinkaurelius.titan.core.schema.TitanSchemaType;
+import com.thinkaurelius.titan.graphdb.database.IndexSerializer;
+import com.thinkaurelius.titan.graphdb.internal.ElementCategory;
+import com.thinkaurelius.titan.graphdb.internal.InternalRelationType;
+import com.thinkaurelius.titan.graphdb.internal.OrderList;
+import com.thinkaurelius.titan.graphdb.query.*;
+import com.thinkaurelius.titan.graphdb.query.condition.*;
+import com.thinkaurelius.titan.graphdb.transaction.StandardTitanTx;
+import com.thinkaurelius.titan.graphdb.types.*;
+import com.thinkaurelius.titan.graphdb.types.system.ImplicitKey;
+import com.thinkaurelius.titan.util.datastructures.Interval;
+import com.thinkaurelius.titan.util.datastructures.PointInterval;
+import com.tinkerpop.blueprints.Edge;
+import com.tinkerpop.blueprints.Vertex;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import javax.annotation.Nullable;
+import java.util.*;
+
+/**
+ *
+ * Builds a {@link TitanGraphQuery}, optimizes the query and compiles the result into a {@link GraphCentricQuery} which
+ * is then executed through a {@link QueryProcessor}.
+ * This class from titan-0.5.4 has no major changes except adding a few logs for debugging index usage
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public class GraphCentricQueryBuilder implements TitanGraphQuery<GraphCentricQueryBuilder> {
+
+ private static final Logger log = LoggerFactory.getLogger(GraphCentricQueryBuilder.class);
+
+ /**
+ * Transaction in which this query is executed.
+ */
+ private final StandardTitanTx tx;
+ /**
+ * Serializer used to serialize the query conditions into backend queries.
+ */
+ private final IndexSerializer serializer;
+ /**
+ * The constraints added to this query. None by default.
+ */
+ private List<PredicateCondition<String, TitanElement>> constraints;
+ /**
+ * The order in which the elements should be returned. None by default.
+ */
+ private OrderList orders = new OrderList();
+ /**
+ * The limit of this query. No limit by default.
+ */
+ private int limit = Query.NO_LIMIT;
+
+ public GraphCentricQueryBuilder(StandardTitanTx tx, IndexSerializer serializer) {
+ log.debug("Loaded shaded version of class GraphCentricQueryBuilder");
+ Preconditions.checkNotNull(tx);
+ Preconditions.checkNotNull(serializer);
+ this.tx = tx;
+ this.serializer = serializer;
+ this.constraints = new ArrayList<PredicateCondition<String, TitanElement>>(5);
+ }
+
+ /* ---------------------------------------------------------------
+ * Query Construction
+ * ---------------------------------------------------------------
+ */
+
+ private GraphCentricQueryBuilder has(String key, TitanPredicate predicate, Object condition) {
+ Preconditions.checkNotNull(key);
+ Preconditions.checkNotNull(predicate);
+ Preconditions.checkArgument(predicate.isValidCondition(condition), "Invalid condition: %s", condition);
+ constraints.add(new PredicateCondition<String, TitanElement>(key, predicate, condition));
+ return this;
+ }
+
+ @Override
+ public GraphCentricQueryBuilder has(String key, com.tinkerpop.blueprints.Predicate predicate, Object condition) {
+ Preconditions.checkNotNull(key);
+ TitanPredicate titanPredicate = TitanPredicate.Converter.convert(predicate);
+ return has(key, titanPredicate, condition);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder has(PropertyKey key, TitanPredicate predicate, Object condition) {
+ Preconditions.checkNotNull(key);
+ Preconditions.checkNotNull(predicate);
+ return has(key.getName(), predicate, condition);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder has(String key) {
+ return has(key, Cmp.NOT_EQUAL, (Object) null);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder hasNot(String key) {
+ return has(key, Cmp.EQUAL, (Object) null);
+ }
+
+ @Override
+ @Deprecated
+ public <T extends Comparable<T>> GraphCentricQueryBuilder has(String s, T t, Compare compare) {
+ return has(s, compare, t);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder has(String key, Object value) {
+ return has(key, Cmp.EQUAL, value);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder hasNot(String key, Object value) {
+ return has(key, Cmp.NOT_EQUAL, value);
+ }
+
+ @Override
+ public <T extends Comparable<?>> GraphCentricQueryBuilder interval(String s, T t1, T t2) {
+ has(s, Cmp.GREATER_THAN_EQUAL, t1);
+ return has(s, Cmp.LESS_THAN, t2);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder limit(final int limit) {
+ Preconditions.checkArgument(limit >= 0, "Non-negative limit expected: %s", limit);
+ this.limit = limit;
+ return this;
+ }
+
+ @Override
+ public GraphCentricQueryBuilder orderBy(String key, Order order) {
+ Preconditions.checkArgument(tx.containsPropertyKey(key),"Provided key does not exist: %s",key);
+ return orderBy(tx.getPropertyKey(key), order);
+ }
+
+ @Override
+ public GraphCentricQueryBuilder orderBy(PropertyKey key, Order order) {
+ Preconditions.checkArgument(key!=null && order!=null,"Need to specify and key and an order");
+ Preconditions.checkArgument(Comparable.class.isAssignableFrom(key.getDataType()),
+ "Can only order on keys with comparable data type. [%s] has datatype [%s]", key.getName(), key.getDataType());
+ Preconditions.checkArgument(key.getCardinality()== Cardinality.SINGLE, "Ordering is undefined on multi-valued key [%s]", key.getName());
+ Preconditions.checkArgument(!orders.containsKey(key));
+ orders.add(key, order);
+ return this;
+ }
+
+ /* ---------------------------------------------------------------
+ * Query Execution
+ * ---------------------------------------------------------------
+ */
+
+ @Override
+ public Iterable<Vertex> vertices() {
+ GraphCentricQuery query = constructQuery(ElementCategory.VERTEX);
+ return Iterables.filter(new QueryProcessor<GraphCentricQuery, TitanElement, JointIndexQuery>(query, tx.elementProcessor), Vertex.class);
+ }
+
+ @Override
+ public Iterable<Edge> edges() {
+ GraphCentricQuery query = constructQuery(ElementCategory.EDGE);
+ return Iterables.filter(new QueryProcessor<GraphCentricQuery, TitanElement, JointIndexQuery>(query, tx.elementProcessor), Edge.class);
+ }
+
+ @Override
+ public Iterable<TitanProperty> properties() {
+ GraphCentricQuery query = constructQuery(ElementCategory.PROPERTY);
+ return Iterables.filter(new QueryProcessor<GraphCentricQuery, TitanElement, JointIndexQuery>(query, tx.elementProcessor), TitanProperty.class);
+ }
+
+ private QueryDescription describe(ElementCategory category) {
+ return new StandardQueryDescription(1,constructQuery(category));
+ }
+
+ public QueryDescription describeForVertices() {
+ return describe(ElementCategory.VERTEX);
+ }
+
+ public QueryDescription describeForEdges() {
+ return describe(ElementCategory.EDGE);
+ }
+
+ public QueryDescription describeForProperties() {
+ return describe(ElementCategory.PROPERTY);
+ }
+
+ /* ---------------------------------------------------------------
+ * Query Construction
+ * ---------------------------------------------------------------
+ */
+
+ private static final int DEFAULT_NO_LIMIT = 1000;
+ private static final int MAX_BASE_LIMIT = 20000;
+ private static final int HARD_MAX_LIMIT = 100000;
+
+ private static final double EQUAL_CONDITION_SCORE = 4;
+ private static final double OTHER_CONDITION_SCORE = 1;
+ private static final double ORDER_MATCH = 2;
+ private static final double ALREADY_MATCHED_ADJUSTOR = 0.1;
+ private static final double CARDINALITY_SINGE_SCORE = 1000;
+ private static final double CARDINALITY_OTHER_SCORE = 1000;
+
+ public GraphCentricQuery constructQuery(final ElementCategory resultType) {
+ Preconditions.checkNotNull(resultType);
+ if (limit == 0) return GraphCentricQuery.emptyQuery(resultType);
+
+ //Prepare constraints
+ And<TitanElement> conditions = QueryUtil.constraints2QNF(tx, constraints);
+ if (conditions == null) return GraphCentricQuery.emptyQuery(resultType);
+
+ //Prepare orders
+ orders.makeImmutable();
+ if (orders.isEmpty()) orders = OrderList.NO_ORDER;
+
+ //Compile all indexes that cover at least one of the query conditions
+ final Set<IndexType> indexCandidates = new HashSet<IndexType>();
+ ConditionUtil.traversal(conditions,new Predicate<Condition<TitanElement>>() {
+ @Override
+ public boolean apply(@Nullable Condition<TitanElement> condition) {
+ if (condition instanceof PredicateCondition) {
+ RelationType type = ((PredicateCondition<RelationType,TitanElement>)condition).getKey();
+ Preconditions.checkArgument(type!=null && type.isPropertyKey());
+ Iterables.addAll(indexCandidates,Iterables.filter(((InternalRelationType) type).getKeyIndexes(), new Predicate<IndexType>() {
+ @Override
+ public boolean apply(@Nullable IndexType indexType) {
+ return indexType.getElement()==resultType;
+ }
+ }));
+ }
+ return true;
+ }
+ });
+
+ /*
+ Determine the best join index query to answer this query:
+ Iterate over all potential indexes (as compiled above) and compute a score based on how many clauses
+ this index covers. The index with the highest score (as long as it covers at least one additional clause)
+ is picked and added to the joint query for as long as such exist.
+ */
+ JointIndexQuery jointQuery = new JointIndexQuery();
+ boolean isSorted = orders.isEmpty();
+ Set<Condition> coveredClauses = Sets.newHashSet();
+ while (true) {
+ IndexType bestCandidate = null;
+ double candidateScore = 0.0;
+ Set<Condition> candidateSubcover = null;
+ boolean candidateSupportsSort = false;
+ Object candidateSubcondition = null;
+
+ for (IndexType index : indexCandidates) {
+ Set<Condition> subcover = Sets.newHashSet();
+ Object subcondition;
+ boolean supportsSort = orders.isEmpty();
+ //Check that this index actually applies in case of a schema constraint
+ if (index.hasSchemaTypeConstraint()) {
+ TitanSchemaType type = index.getSchemaTypeConstraint();
+ Map.Entry<Condition,Collection<Object>> equalCon = getEqualityConditionValues(conditions,ImplicitKey.LABEL);
+ if (equalCon==null) continue;
+ Collection<Object> labels = equalCon.getValue();
+ assert labels.size()>=1;
+ if (labels.size()>1) {
+ log.warn("The query optimizer currently does not support multiple label constraints in query: {}",this);
+ continue;
+ }
+ if (!type.getName().equals((String)Iterables.getOnlyElement(labels))) continue;
+ subcover.add(equalCon.getKey());
+ }
+
+ if (index.isCompositeIndex()) {
+ subcondition = indexCover((CompositeIndexType) index,conditions,subcover);
+ } else {
+ subcondition = indexCover((MixedIndexType) index,conditions,serializer,subcover);
+ if (coveredClauses.isEmpty() && !supportsSort
+ && indexCoversOrder((MixedIndexType)index,orders)) supportsSort=true;
+ }
+ if (subcondition==null) continue;
+ assert !subcover.isEmpty();
+ double score = 0.0;
+ boolean coversAdditionalClause = false;
+ for (Condition c : subcover) {
+ double s = (c instanceof PredicateCondition && ((PredicateCondition)c).getPredicate()==Cmp.EQUAL)?
+ EQUAL_CONDITION_SCORE:OTHER_CONDITION_SCORE;
+ if (coveredClauses.contains(c)) s=s*ALREADY_MATCHED_ADJUSTOR;
+ else coversAdditionalClause = true;
+ score+=s;
+ if (index.isCompositeIndex())
+ score+=((CompositeIndexType)index).getCardinality()==Cardinality.SINGLE?
+ CARDINALITY_SINGE_SCORE:CARDINALITY_OTHER_SCORE;
+ }
+ if (supportsSort) score+=ORDER_MATCH;
+ if (coversAdditionalClause && score>candidateScore) {
+ candidateScore=score;
+ bestCandidate=index;
+ candidateSubcover = subcover;
+ candidateSubcondition = subcondition;
+ candidateSupportsSort = supportsSort;
+ }
+ }
+ if (bestCandidate!=null) {
+ if (coveredClauses.isEmpty()) isSorted=candidateSupportsSort;
+ coveredClauses.addAll(candidateSubcover);
+
+ log.info("Index chosen for query {} {} " , bestCandidate.isCompositeIndex() ? "COMPOSITE" : "MIXED", coveredClauses);
+ if (bestCandidate.isCompositeIndex()) {
+ jointQuery.add((CompositeIndexType)bestCandidate,
+ serializer.getQuery((CompositeIndexType)bestCandidate,(List<Object[]>)candidateSubcondition));
+ } else {
+ jointQuery.add((MixedIndexType)bestCandidate,
+ serializer.getQuery((MixedIndexType)bestCandidate,(Condition)candidateSubcondition,orders));
+ }
+ } else {
+ break;
+ }
+ /* TODO: smarter optimization:
+ - use in-memory histograms to estimate selectivity of PredicateConditions and filter out low-selectivity ones
+ if they would result in an individual index call (better to filter afterwards in memory)
+ - move OR's up and extend GraphCentricQuery to allow multiple JointIndexQuery for proper or'ing of queries
+ */
+ }
+
+ BackendQueryHolder<JointIndexQuery> query;
+ if (!coveredClauses.isEmpty()) {
+ int indexLimit = limit == Query.NO_LIMIT ? HARD_MAX_LIMIT : limit;
+ if (tx.getGraph().getConfiguration().adjustQueryLimit()) {
+ indexLimit = limit == Query.NO_LIMIT ? DEFAULT_NO_LIMIT : Math.min(MAX_BASE_LIMIT, limit);
+ }
+ indexLimit = Math.min(HARD_MAX_LIMIT, QueryUtil.adjustLimitForTxModifications(tx, coveredClauses.size(), indexLimit));
+ jointQuery.setLimit(indexLimit);
+ query = new BackendQueryHolder<JointIndexQuery>(jointQuery, coveredClauses.size()==conditions.numChildren(), isSorted, null);
+ } else {
+ query = new BackendQueryHolder<JointIndexQuery>(new JointIndexQuery(), false, isSorted, null);
+ }
+
+ return new GraphCentricQuery(resultType, conditions, orders, query, limit);
+ }
+
+ public static final boolean indexCoversOrder(MixedIndexType index, OrderList orders) {
+ for (int i = 0; i < orders.size(); i++) {
+ if (!index.indexesKey(orders.getKey(i))) return false;
+ }
+ return true;
+ }
+
+ public static List<Object[]> indexCover(final CompositeIndexType index, Condition<TitanElement> condition, Set<Condition> covered) {
+ assert QueryUtil.isQueryNormalForm(condition);
+ assert condition instanceof And;
+ if (index.getStatus()!= SchemaStatus.ENABLED) return null;
+ IndexField[] fields = index.getFieldKeys();
+ Object[] indexValues = new Object[fields.length];
+ Set<Condition> coveredClauses = new HashSet<Condition>(fields.length);
+ List<Object[]> indexCovers = new ArrayList<Object[]>(4);
+
+ constructIndexCover(indexValues,0,fields,condition,indexCovers,coveredClauses);
+ if (!indexCovers.isEmpty()) {
+ covered.addAll(coveredClauses);
+ return indexCovers;
+ } else return null;
+ }
+
+ private static void constructIndexCover(Object[] indexValues, int position, IndexField[] fields,
+ Condition<TitanElement> condition,
+ List<Object[]> indexCovers, Set<Condition> coveredClauses) {
+ if (position>=fields.length) {
+ indexCovers.add(indexValues);
+ } else {
+ IndexField field = fields[position];
+ Map.Entry<Condition,Collection<Object>> equalCon = getEqualityConditionValues(condition,field.getFieldKey());
+ if (equalCon!=null) {
+ coveredClauses.add(equalCon.getKey());
+ assert equalCon.getValue().size()>0;
+ for (Object value : equalCon.getValue()) {
+ Object[] newValues = Arrays.copyOf(indexValues,fields.length);
+ newValues[position]=value;
+ constructIndexCover(newValues,position+1,fields,condition,indexCovers,coveredClauses);
+ }
+ } else return;
+ }
+
+ }
+
+ private static final Map.Entry<Condition,Collection<Object>> getEqualityConditionValues(Condition<TitanElement> condition, RelationType type) {
+ for (Condition c : condition.getChildren()) {
+ if (c instanceof Or) {
+ Map.Entry<RelationType,Collection> orEqual = QueryUtil.extractOrCondition((Or)c);
+ if (orEqual!=null && orEqual.getKey().equals(type) && !orEqual.getValue().isEmpty()) {
+ return new AbstractMap.SimpleImmutableEntry(c,orEqual.getValue());
+ }
+ } else if (c instanceof PredicateCondition) {
+ PredicateCondition<RelationType, TitanRelation> atom = (PredicateCondition)c;
+ if (atom.getKey().equals(type) && atom.getPredicate()==Cmp.EQUAL && atom.getValue()!=null) {
+ return new AbstractMap.SimpleImmutableEntry(c,ImmutableList.of(atom.getValue()));
+ }
+ }
+
+ }
+ return null;
+ }
+
+ public static final Condition<TitanElement> indexCover(final MixedIndexType index, Condition<TitanElement> condition,
+ final IndexSerializer indexInfo, final Set<Condition> covered) {
+ assert QueryUtil.isQueryNormalForm(condition);
+ assert condition instanceof And;
+ And<TitanElement> subcondition = new And<TitanElement>(condition.numChildren());
+ for (Condition<TitanElement> subclause : condition.getChildren()) {
+ if (coversAll(index,subclause,indexInfo)) {
+ subcondition.add(subclause);
+ covered.add(subclause);
+ }
+ }
+ return subcondition.isEmpty()?null:subcondition;
+ }
+
+ private static final boolean coversAll(final MixedIndexType index, Condition<TitanElement> condition, IndexSerializer indexInfo) {
+ if (condition.getType()==Condition.Type.LITERAL) {
+ if (!(condition instanceof PredicateCondition)) return false;
+ PredicateCondition<RelationType, TitanElement> atom = (PredicateCondition) condition;
+ if (atom.getValue()==null) return false;
+
+ Preconditions.checkArgument(atom.getKey().isPropertyKey());
+ PropertyKey key = (PropertyKey) atom.getKey();
+ ParameterIndexField[] fields = index.getFieldKeys();
+ ParameterIndexField match = null;
+ for (int i = 0; i < fields.length; i++) {
+ if (fields[i].getStatus()!= SchemaStatus.ENABLED) continue;
+ if (fields[i].getFieldKey().equals(key)) match = fields[i];
+ }
+ if (match==null) return false;
+ return indexInfo.supports(index,match,atom.getPredicate());
+ } else {
+ for (Condition<TitanElement> child : condition.getChildren()) {
+ if (!coversAll(index,child,indexInfo)) return false;
+ }
+ return true;
+ }
+ }
+
+
+}