atlas-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From shweth...@apache.org
Subject incubator-atlas git commit: ATLAS-1042 Performance improvement changes for propertykey+typeName based queries (sumasai via shwethags)
Date Fri, 22 Jul 2016 07:11:57 GMT
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 <sshivalingamurthy@hortonworks.com>
Authored: Fri Jul 22 12:41:45 2016 +0530
Committer: Shwetha GS <sshivalingamurthy@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;
+        }
+    }
+
+
+}


Mime
View raw message