From b53f2a2c22a5cda5801cc48e230d31b12c3adfc8 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Wed, 30 Aug 2006 02:13:43 +0000 Subject: Add new query engine --- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 480 +++++++++++++++++++++ 1 file changed, 480 insertions(+) create mode 100644 src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java (limited to 'src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java') diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java new file mode 100644 index 0000000..dfe13cc --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -0,0 +1,480 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * 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.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.RelOp; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; +import com.amazon.carbonado.info.StorableProperty; + +/** + * Analyzes a simple query specification and determines which index is best + * suited for its execution. Query filters passed to this analyzer cannot + * contain any 'or' operations. + * + *

IndexedQueryAnalyzer is sharable and thread-safe. An instance for a + * particular Storable type can be cached, avoiding repeated construction + * cost. In addition, the analyzer caches learned foreign indexes. + * + * @author Brian S O'Neill + * @see UnionQueryAnalyzer + */ +public class IndexedQueryAnalyzer { + private final Class mType; + private final IndexProvider mIndexProvider; + + // Growable cache which maps join properties to lists of usable foreign indexes. + private Map, ForeignIndexes> mForeignIndexCache; + + /** + * @param type type of storable being queried + * @param indexProvider + * @throws IllegalArgumentException if type or indexProvider is null + */ + public IndexedQueryAnalyzer(Class type, IndexProvider indexProvider) { + if (type == null || indexProvider == null) { + throw new IllegalArgumentException(); + } + mType = type; + mIndexProvider = indexProvider; + } + + public Class getStorableType() { + return mType; + } + + /** + * @param filter optional filter which which must be {@link Filter#isBound + * bound} and cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if filter is not supported + */ + public Result analyze(Filter filter, OrderedProperty... orderings) { + if (!filter.isBound()) { + // Strictly speaking, this is not required, but it detects the + // mistake of not properly calling initialFilterValues. + throw new IllegalArgumentException("Filter must be bound"); + } + + final Comparator> comparator = CompositeScore.fullComparator(); + + // First find best local index. + CompositeScore bestScore = null; + StorableIndex bestLocalIndex = null; + + Collection> localIndexes = mIndexProvider.indexesFor(mType); + if (localIndexes != null) { + for (StorableIndex index : localIndexes) { + CompositeScore candidateScore = + CompositeScore.evaluate(index, filter, orderings); + + if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { + bestScore = candidateScore; + bestLocalIndex = index; + } + } + } + + // Now try to find better foreign index. + StorableIndex bestForeignIndex = null; + ChainedProperty bestForeignProperty = null; + + for (PropertyFilter propFilter : PropertyFilterList.get(filter)) { + ChainedProperty chainedProp = propFilter.getChainedProperty(); + + if (chainedProp.getChainCount() == 0) { + // Cannot possibly be a join, so move on. + continue; + } + + ForeignIndexes foreignIndexes = getForeignIndexes(chainedProp); + if (foreignIndexes == null) { + continue; + } + + for (StorableIndex index : foreignIndexes.mIndexes) { + CompositeScore candidateScore = CompositeScore.evaluate + (foreignIndexes.getVirtualIndex(index), + index.isUnique(), + index.isClustered(), + filter, + orderings); + + if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { + bestScore = candidateScore; + bestLocalIndex = null; + bestForeignIndex = index; + bestForeignProperty = foreignIndexes.mProperty; + } + } + } + + return new Result(filter, + bestScore, + bestLocalIndex, + bestForeignIndex, + bestForeignProperty); + } + + /** + * @return null if no foreign indexes for property + */ + private synchronized ForeignIndexes getForeignIndexes(ChainedProperty chainedProp) { + // Remove the last property as it is expected to be a simple storable + // property instead of a joined Storable. + chainedProp = chainedProp.trim(); + + ForeignIndexes foreignIndexes = null; + if (mForeignIndexCache != null) { + foreignIndexes = mForeignIndexCache.get(chainedProp); + if (foreignIndexes != null || mForeignIndexCache.containsKey(chainedProp)) { + return foreignIndexes; + } + } + + // Check if property chain is properly joined and indexed along the way. + evaluate: { + if (!isProperJoin(chainedProp.getPrimeProperty())) { + break evaluate; + } + + int count = chainedProp.getChainCount(); + for (int i=0; i> indexes = mIndexProvider.indexesFor(foreignType); + + foreignIndexes = new ForeignIndexes(chainedProp, indexes); + } + + if (mForeignIndexCache == null) { + mForeignIndexCache = Collections.synchronizedMap + (new HashMap, ForeignIndexes>()); + } + + mForeignIndexCache.put(chainedProp, foreignIndexes); + + return foreignIndexes; + } + + /** + * Checks if the property is a join and its internal properties are fully + * indexed. + */ + private boolean isProperJoin(StorableProperty property) { + if (!property.isJoin() || property.isQuery()) { + return false; + } + + // Make up a filter over the join's internal properties and then search + // for an index that filters with no remainder. + Filter filter = Filter.getOpenFilter((Class) property.getType()); + int count = property.getJoinElementCount(); + for (int i=0; i boolean simpleAnalyze(Filter filter) { + Collection> indexes = mIndexProvider.indexesFor(filter.getStorableType()); + + if (indexes != null) { + for (StorableIndex index : indexes) { + FilteringScore score = FilteringScore.evaluate(index, filter); + if (score.getRemainderCount() == 0) { + return true; + } + } + } + + return false; + } + + public class Result { + private final Filter mFilter; + + private final CompositeScore mScore; + private final StorableIndex mLocalIndex; + private final StorableIndex mForeignIndex; + private final ChainedProperty mForeignProperty; + + private final Filter mRemainderFilter; + private final List> mRemainderOrderings; + + Result(Filter filter, + CompositeScore score, + StorableIndex localIndex, + StorableIndex foreignIndex, + ChainedProperty foreignProperty) + { + mFilter = filter; + mScore = score; + mLocalIndex = localIndex; + mForeignIndex = foreignIndex; + mForeignProperty = foreignProperty; + mRemainderFilter = score.getFilteringScore().getRemainderFilter(); + mRemainderOrderings = score.getOrderingScore().getRemainderOrderings(); + } + + // Called by mergeRemainder. + private Result(Result result, + Filter remainderFilter, + List> remainderOrderings) + { + mFilter = result.mFilter == null ? remainderFilter + : (remainderFilter == null ? result.mFilter : result.mFilter.or(remainderFilter)); + + mScore = result.mScore; + mLocalIndex = result.mLocalIndex; + mForeignIndex = result.mForeignIndex; + mForeignProperty = result.mForeignProperty; + mRemainderFilter = remainderFilter; + mRemainderOrderings = remainderOrderings; + } + + /** + * Returns true if the selected index does anything at all to filter + * results or to order them. If not, a filtered and sorted full scan + * makes more sense. + */ + public boolean handlesAnything() { + return mScore.getFilteringScore().hasAnyMatches() == true + || mScore.getOrderingScore().getHandledCount() > 0; + } + + /** + * Returns combined handled and remainder filter for this result. + */ + public Filter getFilter() { + return mFilter; + } + + /** + * Returns combined handled and remainder orderings for this result. + */ + public List> getOrderings() { + List> handled = mScore.getOrderingScore().getHandledOrderings(); + List> remainder = getRemainderOrderings(); + + if (handled.size() == 0) { + return remainder; + } + if (remainder.size() == 0) { + return handled; + } + + List> combined = + new ArrayList>(handled.size() + remainder.size()); + + combined.addAll(handled); + combined.addAll(remainder); + + return combined; + } + + /** + * Returns the score on how well the selected index performs the + * desired filtering and ordering. When building a query executor, do + * not use the remainder filter and orderings available in the + * composite score. Instead, get them directly from this result object. + */ + public CompositeScore getCompositeScore() { + return mScore; + } + + /** + * Remainder filter which overrides that in composite score. + */ + public Filter getRemainderFilter() { + return mRemainderFilter; + } + + /** + * Remainder orderings which override that in composite score. + */ + public List> getRemainderOrderings() { + return mRemainderOrderings; + } + + /** + * Returns the local index that was selected, or null if a foreign + * index was selected. + */ + public StorableIndex getLocalIndex() { + return mLocalIndex; + } + + /** + * Returns the foreign index that was selected, or null if a local + * index was selected. If a foreign index has been selected, then a + * {@link JoinedQueryExecutor} is needed. + */ + public StorableIndex getForeignIndex() { + return mForeignIndex; + } + + /** + * Returns the simple or chained property that maps to the selected + * foreign index. Returns null if foreign index was not selected. This + * property corresponds to the "bToAProperty" of {@link + * JoinedQueryExecutor}. + */ + public ChainedProperty getForeignProperty() { + return mForeignProperty; + } + + /** + * Returns true if the given result uses the same index as this, and in + * the same way. The only allowed differences are in the remainder + * filter and orderings. + */ + public boolean canMergeRemainder(Result other) { + if (this == other || (!handlesAnything() && !other.handlesAnything())) { + return true; + } + + if (equals(getLocalIndex(), other.getLocalIndex()) + && equals(getForeignIndex(), other.getForeignIndex()) + && equals(getForeignProperty(), other.getForeignProperty())) + { + return getCompositeScore().canMergeRemainder(other.getCompositeScore()); + } + + return false; + } + + /** + * Merges the remainder filter and orderings of this result with the + * one given, returning a new result. Call canMergeRemainder first to + * verify if the merge makes any sense. + */ + public Result mergeRemainder(Result other) { + if (this == other) { + return this; + } + + return new Result + (this, + getCompositeScore().mergeRemainderFilter(other.getCompositeScore()), + getCompositeScore().mergeRemainderOrderings(other.getCompositeScore())); + } + + /** + * Merges the remainder filter of this result with the given filter, + * returning a new result. If handlesAnything return true, then it + * doesn't make sense to call this method. + */ + public Result mergeRemainder(Filter filter) { + Filter remainderFilter = getRemainderFilter(); + if (remainderFilter == null) { + remainderFilter = filter; + } else if (filter != null) { + remainderFilter = remainderFilter.or(filter); + } + + return new Result(this, remainderFilter, getRemainderOrderings()); + } + + private boolean equals(Object a, Object b) { + return a == null ? (b == null) : (a.equals(b)); + } + } + + private static class ForeignIndexes { + final ChainedProperty mProperty; + + final List> mIndexes; + + // Cache of virtual indexes. + private final Map, OrderedProperty[]> mVirtualIndexMap; + + /** + * @param property type of property must be a joined Storable + */ + ForeignIndexes(ChainedProperty property, Collection> indexes) { + mProperty = property; + if (indexes == null || indexes.size() == 0) { + mIndexes = Collections.emptyList(); + } else { + mIndexes = new ArrayList>(indexes); + } + mVirtualIndexMap = new HashMap, OrderedProperty[]>(); + } + + /** + * Prepends local chained property with names of index elements, + * producing a virtual index on local storable. This allows + * CompositeScore to evaluate it. + */ + synchronized OrderedProperty[] getVirtualIndex(StorableIndex index) { + OrderedProperty[] virtualProps = mVirtualIndexMap.get(index); + if (virtualProps != null) { + return virtualProps; + } + + OrderedProperty[] realProps = index.getOrderedProperties(); + virtualProps = new OrderedProperty[realProps.length]; + + for (int i=realProps.length; --i>=0; ) { + OrderedProperty realProp = realProps[i]; + ChainedProperty virtualChained = + mProperty.append(realProp.getChainedProperty()); + virtualProps[i] = OrderedProperty.get(virtualChained, realProp.getDirection()); + } + + mVirtualIndexMap.put(index, virtualProps); + + return virtualProps; + } + } +} -- cgit v1.2.3