From ee94d7b776703a45ac314026b51b8d0d8aa1cbbf Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sun, 20 May 2007 00:24:06 +0000 Subject: Merged in covering index optimization. --- .../com/amazon/carbonado/qe/CompositeScore.java | 22 +++ .../java/com/amazon/carbonado/qe/EmptyQuery.java | 8 + .../com/amazon/carbonado/qe/FilteringScore.java | 216 ++++++++++++++------- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 94 ++++----- .../amazon/carbonado/qe/IndexedQueryExecutor.java | 152 ++++++++++++++- .../com/amazon/carbonado/qe/OrderingScore.java | 38 +++- .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 2 +- .../carbonado/repo/indexed/IndexedStorage.java | 47 ++--- .../carbonado/repo/indexed/ManagedIndex.java | 127 ++---------- .../carbonado/repo/sleepycat/BDBStorage.java | 9 + 10 files changed, 436 insertions(+), 279 deletions(-) (limited to 'src') diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index e031fe2..8194dbb 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -162,6 +162,28 @@ public class CompositeScore { return getOrderingScore().mergeRemainderOrdering(other.getOrderingScore()); } + /** + * Returns a new CompositeScore with the filtering remainder replaced and + * covering matches recalculated. Other matches are not recalculated. + * + * @since 1.2 + */ + public CompositeScore withRemainderFilter(Filter filter) { + return new CompositeScore(mFilteringScore.withRemainderFilter(filter), + mOrderingScore); + } + + /** + * Returns a new CompositeScore with the ordering remainder + * replaced. Handled count is not recalculated. + * + * @since 1.2 + */ + public CompositeScore withRemainderOrdering(OrderingList ordering) { + return new CompositeScore(mFilteringScore, + mOrderingScore.withRemainderOrdering(ordering)); + } + public String toString() { return "CompositeScore {" + getFilteringScore() + ", " + getOrderingScore() + '}'; } diff --git a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java index d9969c5..31d9dd3 100644 --- a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java +++ b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java @@ -73,6 +73,14 @@ public final class EmptyQuery extends AbstractQuery { this(factory, OrderingList.get(factory.getStorableType(), orderings)); } + /** + * Used only by test suite. Query throws NullPointerException when invoked. + */ + EmptyQuery() { + mFactory = null; + mOrdering = OrderingList.emptyList(); + } + public Class getStorableType() { return mFactory.getStorableType(); } diff --git a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java index 2661f69..7722873 100644 --- a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java +++ b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java @@ -27,9 +27,12 @@ import java.util.List; import com.amazon.carbonado.Storable; +import com.amazon.carbonado.filter.AndFilter; import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.OrFilter; import com.amazon.carbonado.filter.PropertyFilter; import com.amazon.carbonado.filter.RelOp; +import com.amazon.carbonado.filter.Visitor; import com.amazon.carbonado.info.ChainedProperty; import com.amazon.carbonado.info.Direction; @@ -206,38 +209,15 @@ public class FilteringScore { indexProperties[indexPropPos].getDirection() == Direction.DESCENDING; } - List> extraMatchFilters = null; - - boolean checkForExtraMatches = !filterList.isEmpty() - && (identityFilters.size() > 0 - || rangeStartFilters.size() > 0 - || rangeEndFilters.size() > 0); - - if (checkForExtraMatches) { - // Any remainder property which is provided by the index is an extra match. - for (PropertyFilter subFilter : filterList) { - ChainedProperty filterProp = subFilter.getChainedProperty(); - for (OrderedProperty indexProp : indexProperties) { - if (indexProp.getChainedProperty().equals(filterProp)) { - if (extraMatchFilters == null) { - extraMatchFilters = new ArrayList>(); - } - extraMatchFilters.add(subFilter); - } - } - } - } - - return new FilteringScore(clustered, + return new FilteringScore(indexProperties, + clustered, unique, - indexProperties.length, identityFilters, rangeStartFilters, rangeEndFilters, arrangementScore, preferenceScore, filterList, - extraMatchFilters, shouldReverseRange); } @@ -285,9 +265,37 @@ public class FilteringScore { return 0; } + /** + * Splits the filter from its conjunctive normal form. And'ng the filters + * together produces the original filter. + */ + static List> split(Filter filter) { + if (filter == null) { + return null; + } + + filter = filter.conjunctiveNormalForm(); + + final List> list = new ArrayList>(); + + filter.accept(new Visitor() { + public Object visit(OrFilter filter, Object param) { + list.add(filter); + return null; + } + + public Object visit(PropertyFilter filter, Object param) { + list.add(filter); + return null; + } + }, null); + + return list; + } + + private final OrderedProperty[] mIndexProperties; private final boolean mIndexClustered; private final boolean mIndexUnique; - private final int mIndexPropertyCount; private final List> mIdentityFilters; @@ -297,39 +305,57 @@ public class FilteringScore { private final int mArrangementScore; private final BigInteger mPreferenceScore; - private final List> mRemainderFilters; - private final List> mExtraMatchFilters; + private final List> mRemainderFilters; + private final List> mCoveringFilters; private final boolean mShouldReverseRange; private transient Filter mIdentityFilter; private transient Filter mRemainderFilter; - private transient Filter mExtraMatchFilter; - private transient Filter mExtraMatchRemainderFilter; + private transient Filter mCoveringFilter; + private transient Filter mCoveringRemainderFilter; - private FilteringScore(boolean indexClustered, + private FilteringScore(OrderedProperty[] indexProperties, + boolean indexClustered, boolean indexUnique, - int indexPropertyCount, List> identityFilters, List> rangeStartFilters, List> rangeEndFilters, int arrangementScore, BigInteger preferenceScore, - List> remainderFilters, - List> extraMatchFilters, + List> remainderFilters, boolean shouldReverseRange) { + mIndexProperties = indexProperties; mIndexClustered = indexClustered; mIndexUnique = indexUnique; - mIndexPropertyCount = indexPropertyCount; mIdentityFilters = prepareList(identityFilters); mRangeStartFilters = prepareList(rangeStartFilters); mRangeEndFilters = prepareList(rangeEndFilters); mArrangementScore = arrangementScore; mPreferenceScore = preferenceScore; mRemainderFilters = prepareList(remainderFilters); - mExtraMatchFilters = prepareList(extraMatchFilters); mShouldReverseRange = shouldReverseRange; + + mCoveringFilters = findCoveringMatches(); + } + + private FilteringScore(FilteringScore score, Filter remainderFilter) { + mIndexProperties = score.mIndexProperties; + mIndexClustered = score.mIndexClustered; + mIndexUnique = score.mIndexUnique; + mIdentityFilters = score.mIdentityFilters; + mRangeStartFilters = score.mRangeStartFilters; + mRangeEndFilters = score.mRangeEndFilters; + mArrangementScore = score.mArrangementScore; + mPreferenceScore = score.mPreferenceScore; + mRemainderFilters = prepareList(split(remainderFilter)); + mShouldReverseRange = score.mShouldReverseRange; + + mCoveringFilters = findCoveringMatches(); + + mIdentityFilter = score.mIdentityFilter; + mRemainderFilter = remainderFilter; } /** @@ -351,7 +377,7 @@ public class FilteringScore { * Returns the amount of properties in the evaluated index. */ public int getIndexPropertyCount() { - return mIndexPropertyCount; + return mIndexProperties.length; } /** @@ -531,7 +557,7 @@ public class FilteringScore { /** * Returns the filters not supported by the evaluated index. */ - public List> getRemainderFilters() { + public List> getRemainderFilters() { return mRemainderFilters; } @@ -547,54 +573,54 @@ public class FilteringScore { } /** - * Returns number of extra property filters which are supported by the + * Returns number of covering property filters which are supported by the * evaluated index. This count is no more than the remainder count. If - * hasAnyMatches returns false, then the extra match count is zero. + * hasAnyMatches returns false, then the covering count is zero. * * @since 1.2 */ - public int getExtraMatchCount() { - return mExtraMatchFilters.size(); + public int getCoveringCount() { + return mCoveringFilters.size(); } /** - * Returns the extra filters which are supported by the evaluated index, + * Returns the covering filters which are supported by the evaluated index, * which is a subset of the remainder filters. * * @since 1.2 */ - public List> getExtraMatchFilters() { - return mExtraMatchFilters; + public List> getCoveringFilters() { + return mCoveringFilters; } /** - * Returns the composite extra match filter supported by the evaluated - * index, or null if no extra match. + * Returns the composite covering filter supported by the evaluated index, + * or null if the covering count is zero. * * @since 1.2 */ - public Filter getExtraMatchFilter() { - if (mExtraMatchFilter == null) { - mExtraMatchFilter = buildCompositeFilter(getExtraMatchFilters()); + public Filter getCoveringFilter() { + if (mCoveringFilter == null) { + mCoveringFilter = buildCompositeFilter(getCoveringFilters()); } - return mExtraMatchFilter; + return mCoveringFilter; } /** - * Returns the composite remainder filter without including the extra match + * Returns the composite remainder filter without including the covering * filter. Returns null if no remainder. * * @since 1.2 */ - public Filter getExtraMatchRemainderFilter() { - if (mExtraMatchRemainderFilter == null) { - List> remainderFilters = mRemainderFilters; - List> extraMatchFilters = mExtraMatchFilters; - if (extraMatchFilters.size() < remainderFilters.size()) { + public Filter getCoveringRemainderFilter() { + if (mCoveringRemainderFilter == null) { + List> remainderFilters = mRemainderFilters; + List> coveringFilters = mCoveringFilters; + if (coveringFilters.size() < remainderFilters.size()) { Filter composite = null; for (int i=0; i subFilter = remainderFilters.get(i); - if (!extraMatchFilters.contains(subFilter)) { + if (!coveringFilters.contains(subFilter)) { if (composite == null) { composite = subFilter; } else { @@ -602,10 +628,10 @@ public class FilteringScore { } } } - mExtraMatchRemainderFilter = composite; + mCoveringRemainderFilter = composite; } } - return mExtraMatchRemainderFilter; + return mCoveringRemainderFilter; } /** @@ -674,12 +700,22 @@ public class FilteringScore { } } + /** + * Returns a new FilteringScore with the remainder replaced and covering + * matches recalculated. Other matches are not recalculated. + * + * @since 1.2 + */ + public FilteringScore withRemainderFilter(Filter filter) { + return new FilteringScore(this, filter); + } + public String toString() { return "FilteringScore {identityCount=" + getIdentityCount() + ", hasRangeStart=" + hasRangeStart() + ", hasRangeEnd=" + hasRangeEnd() + ", remainderCount=" + getRemainderCount() + - ", extraMatchCount=" + getExtraMatchCount() + + ", coveringCount=" + getCoveringCount() + '}'; } @@ -703,7 +739,7 @@ public class FilteringScore { return reduced == null ? filters : reduced; } - private Filter buildCompositeFilter(List> filterList) { + private Filter buildCompositeFilter(List> filterList) { if (filterList.size() == 0) { return null; } @@ -714,6 +750,56 @@ public class FilteringScore { return composite; } + /** + * Finds covering matches from the remainder. + */ + private List> findCoveringMatches() { + List> coveringFilters = null; + + boolean check = !mRemainderFilters.isEmpty() + && (mIdentityFilters.size() > 0 + || mRangeStartFilters.size() > 0 + || mRangeEndFilters.size() > 0); + + if (check) { + // Any remainder property which is provided by the index is a covering match. + for (Filter subFilter : mRemainderFilters) { + if (isProvidedByIndex(subFilter)) { + if (coveringFilters == null) { + coveringFilters = new ArrayList>(); + } + coveringFilters.add(subFilter); + } + } + } + + return prepareList(coveringFilters); + } + + private boolean isProvidedByIndex(Filter filter) { + return filter.accept(new Visitor() { + public Boolean visit(OrFilter filter, Object param) { + return filter.getLeftFilter().accept(this, param) + && filter.getRightFilter().accept(this, param); + } + + public Boolean visit(AndFilter filter, Object param) { + return filter.getLeftFilter().accept(this, param) + && filter.getRightFilter().accept(this, param); + } + + public Boolean visit(PropertyFilter filter, Object param) { + ChainedProperty filterProp = filter.getChainedProperty(); + for (OrderedProperty indexProp : mIndexProperties) { + if (indexProp.getChainedProperty().equals(filterProp)) { + return true; + } + } + return false; + } + }, null); + } + private static class Range implements Comparator> { static final Comparator> INSTANCE = new Range(); @@ -811,11 +897,11 @@ public class FilteringScore { return 1; } - // Favor index which contains more extra matches. - if (first.getExtraMatchCount() > second.getExtraMatchCount()) { + // Favor index which contains more covering matches. + if (first.getCoveringCount() > second.getCoveringCount()) { return -1; } - if (first.getExtraMatchCount() < second.getExtraMatchCount()) { + if (first.getCoveringCount() < second.getCoveringCount()) { return 1; } diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 366c2d7..60cf3da 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -283,35 +283,17 @@ public class IndexedQueryAnalyzer { private final StorableIndex mForeignIndex; private final ChainedProperty mForeignProperty; - private final Filter mRemainderFilter; - private final OrderingList mRemainderOrdering; - Result(Filter filter, CompositeScore score, StorableIndex localIndex, StorableIndex foreignIndex, ChainedProperty foreignProperty) - { - this(filter, score, localIndex, foreignIndex, foreignProperty, - score.getFilteringScore().getRemainderFilter(), - score.getOrderingScore().getRemainderOrdering()); - } - - private Result(Filter filter, - CompositeScore score, - StorableIndex localIndex, - StorableIndex foreignIndex, - ChainedProperty foreignProperty, - Filter remainderFilter, - OrderingList remainderOrdering) { mFilter = filter; mScore = score; mLocalIndex = localIndex; mForeignIndex = foreignIndex; mForeignProperty = foreignProperty; - mRemainderFilter = remainderFilter; - mRemainderOrdering = remainderOrdering; } /** @@ -340,9 +322,7 @@ public class IndexedQueryAnalyzer { /** * 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. + * desired filtering and ordering. */ public CompositeScore getCompositeScore() { return mScore; @@ -352,14 +332,14 @@ public class IndexedQueryAnalyzer { * Remainder filter which overrides that in composite score. */ public Filter getRemainderFilter() { - return mRemainderFilter; + return mScore.getFilteringScore().getRemainderFilter(); } /** * Remainder orderings which override that in composite score. */ public OrderingList getRemainderOrdering() { - return mRemainderOrdering; + return mScore.getOrderingScore().getRemainderOrdering(); } /** @@ -442,9 +422,11 @@ public class IndexedQueryAnalyzer { Filter filter = andFilters(handledFilter, remainderFilter); - return new Result - (filter, mScore, mLocalIndex, mForeignIndex, mForeignProperty, - remainderFilter, remainderOrdering); + CompositeScore score = mScore + .withRemainderFilter(remainderFilter) + .withRemainderOrdering(remainderOrdering); + + return new Result(filter, score, mLocalIndex, mForeignIndex, mForeignProperty); } /** @@ -453,7 +435,7 @@ public class IndexedQueryAnalyzer { * doesn't usually make sense to call this method. */ public Result mergeRemainderFilter(Filter filter) { - return setRemainderFilter(orFilters(getRemainderFilter(), filter)); + return withRemainderFilter(orFilters(getRemainderFilter(), filter)); } private Filter andFilters(Filter a, Filter b) { @@ -479,19 +461,17 @@ public class IndexedQueryAnalyzer { /** * Returns a new result with the remainder filter replaced. */ - public Result setRemainderFilter(Filter remainderFilter) { - return new Result - (mFilter, mScore, mLocalIndex, mForeignIndex, mForeignProperty, - remainderFilter, mRemainderOrdering); + public Result withRemainderFilter(Filter remainderFilter) { + CompositeScore score = mScore.withRemainderFilter(remainderFilter); + return new Result(mFilter, score, mLocalIndex, mForeignIndex, mForeignProperty); } /** * Returns a new result with the remainder ordering replaced. */ - public Result setRemainderOrdering(OrderingList remainderOrdering) { - return new Result - (mFilter, mScore, mLocalIndex, mForeignIndex, mForeignProperty, - mRemainderFilter, remainderOrdering); + public Result withRemainderOrdering(OrderingList remainderOrdering) { + CompositeScore score = mScore.withRemainderOrdering(remainderOrdering); + return new Result(mFilter, score, mLocalIndex, mForeignIndex, mForeignProperty); } /** @@ -510,14 +490,30 @@ public class IndexedQueryAnalyzer { } } - QueryExecutor executor = baseLocalExecutor(localAccess); + Filter remainderFilter = getRemainderFilter(); - if (executor == null) { + QueryExecutor executor; + if (!handlesAnything()) { + executor = new FullScanQueryExecutor(localAccess); + } else if (localIndex == null) { + // Use foreign executor. return JoinedQueryExecutor.build (mRepoAccess, getForeignProperty(), getFilter(), getOrdering()); + } else { + CompositeScore score = getCompositeScore(); + FilteringScore fScore = score.getFilteringScore(); + if (fScore.isKeyMatch()) { + executor = new KeyQueryExecutor(localAccess, localIndex, fScore); + } else { + IndexedQueryExecutor ixExecutor = + new IndexedQueryExecutor(localAccess, localIndex, score); + executor = ixExecutor; + if (ixExecutor.getCoveringFilter() != null) { + remainderFilter = fScore.getCoveringRemainderFilter(); + } + } } - Filter remainderFilter = getRemainderFilter(); if (remainderFilter != null) { executor = new FilteredQueryExecutor(executor, remainderFilter); } @@ -534,28 +530,6 @@ public class IndexedQueryAnalyzer { return executor; } - /** - * Returns local executor or null if foreign executor should be used. - */ - private QueryExecutor baseLocalExecutor(StorageAccess localAccess) { - if (!handlesAnything()) { - return new FullScanQueryExecutor(localAccess); - } - - StorableIndex localIndex = getLocalIndex(); - - if (localIndex != null) { - CompositeScore score = getCompositeScore(); - FilteringScore fScore = score.getFilteringScore(); - if (fScore.isKeyMatch()) { - return new KeyQueryExecutor(localAccess, localIndex, fScore); - } - return new IndexedQueryExecutor(localAccess, localIndex, score); - } - - return null; - } - public String toString() { return "IndexedQueryAnalyzer.Result {score=" + getCompositeScore() + ", localIndex=" diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java index 45ce4aa..d306e25 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -24,12 +24,15 @@ import java.util.List; import com.amazon.carbonado.Cursor; import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Query; import com.amazon.carbonado.Storable; import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.FilterValues; import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.RelOp; +import com.amazon.carbonado.info.Direction; import com.amazon.carbonado.info.StorableIndex; /** @@ -59,6 +62,11 @@ public class IndexedQueryExecutor extends AbstractQueryExecu private final boolean mReverseOrder; private final boolean mReverseRange; + private final Filter mCoveringFilter; + + // Total of nine start and end boundary type permutations. + private final Query[] mIndexEntryQueryCache; + /** * @param index index to use, which may be a primary key index * @param score score determines how best to utilize the index @@ -67,6 +75,7 @@ public class IndexedQueryExecutor extends AbstractQueryExecu public IndexedQueryExecutor(Support support, StorableIndex index, CompositeScore score) + throws FetchException { if (support == null && this instanceof Support) { support = (Support) this; @@ -92,6 +101,15 @@ public class IndexedQueryExecutor extends AbstractQueryExecu mReverseOrder = oScore.shouldReverseOrder(); mReverseRange = fScore.shouldReverseRange(); + + Query indexEntryQuery = support.indexEntryQuery(index); + if (indexEntryQuery == null) { + mCoveringFilter = null; + mIndexEntryQueryCache = null; + } else { + mCoveringFilter = fScore.getCoveringFilter(); + mIndexEntryQueryCache = new Query[9]; // Nine start and end boundary permutations + } } @Override @@ -158,11 +176,33 @@ public class IndexedQueryExecutor extends AbstractQueryExecu } } - return mSupport.fetchSubset(mIndex, identityValues, - rangeStartBoundary, rangeStartValue, - rangeEndBoundary, rangeEndValue, - mReverseRange, - mReverseOrder); + Query indexEntryQuery = getIndexEntryQuery(rangeStartBoundary, rangeEndBoundary); + if (indexEntryQuery == null) { + return mSupport.fetchSubset(mIndex, identityValues, + rangeStartBoundary, rangeStartValue, + rangeEndBoundary, rangeEndValue, + mReverseRange, + mReverseOrder); + } else { + indexEntryQuery = indexEntryQuery.withValues(identityValues); + if (rangeStartBoundary != BoundaryType.OPEN) { + indexEntryQuery = indexEntryQuery.with(rangeStartValue); + } + if (rangeEndBoundary != BoundaryType.OPEN) { + indexEntryQuery = indexEntryQuery.with(rangeEndValue); + } + if (mCoveringFilter != null && values != null) { + indexEntryQuery = indexEntryQuery.withValues(values.getValuesFor(mCoveringFilter)); + } + return mSupport.fetchFromIndexEntryQuery(mIndex, indexEntryQuery); + } + } + + /** + * @return null if executor doesn't support or use a covering index + */ + public Filter getCoveringFilter() { + return mCoveringFilter; } public Filter getFilter() { @@ -181,6 +221,10 @@ public class IndexedQueryExecutor extends AbstractQueryExecu filter = filter == null ? p : filter.and(p); } + if (mCoveringFilter != null) { + filter = filter == null ? mCoveringFilter : filter.and(mCoveringFilter); + } + if (filter == null) { return Filter.getOpenFilter(getStorableType()); } @@ -262,19 +306,117 @@ public class IndexedQueryExecutor extends AbstractQueryExecu } newline(app); } + if (mCoveringFilter != null) { + indent(app, indentLevel); + app.append("...covering filter: "); + mCoveringFilter.appendTo(app, values); + + } return true; } + /** + * @return null if query not supported + */ + private Query getIndexEntryQuery(BoundaryType rangeStartBoundary, + BoundaryType rangeEndBoundary) + throws FetchException + { + Query[] indexEntryQueryCache = mIndexEntryQueryCache; + if (indexEntryQueryCache == null) { + return null; + } + + int key = 0; + if (rangeEndBoundary != BoundaryType.OPEN) { + key += (rangeEndBoundary == BoundaryType.INCLUSIVE) ? 1 : 2; + } + if (rangeStartBoundary != BoundaryType.OPEN) { + key += (rangeStartBoundary == BoundaryType.INCLUSIVE) ? (1 * 3) : (2 * 3); + } + + Query indexEntryQuery = indexEntryQueryCache[key]; + + if (indexEntryQuery == null) { + indexEntryQuery = mSupport.indexEntryQuery(mIndex); + Filter filter = indexEntryQuery.getFilter(); + + int i; + for (i=0; i { + /** + * Returns an open query if the given index supports query access. If + * not supported, return null. An index entry query might be used to + * perform filtering and sorting of index entries prior to being + * resolved into referenced Storables. + * + *

If an index entry query is returned, the fetchSubset method is + * never called by IndexedQueryExecutor. + * + * @return index entry query or null if not supported + */ + Query indexEntryQuery(StorableIndex index) throws FetchException; + + /** + * Fetch Storables referenced by the given index entry query. This + * method is only called if index supports query access. + * + * @param index index to open + * @param indexEntryQuery query with no blank parameters, derived from + * the query returned by indexEntryQuery + */ + Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) + throws FetchException; + /** * Perform an index scan of a subset of Storables referenced by an * index. The identity values are aligned with the index properties at * property 0. An optional range start or range end aligns with the index * property following the last of the identity values. * + *

This method is only called if no index entry query was provided + * for the given index. * * @param index index to open, which may be a primary key index * @param identityValues optional list of exactly matching values to apply to index diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java index 15a277f..abf7ac8 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java @@ -151,8 +151,8 @@ public class OrderingScore { } } - return new OrderingScore(clustered, - indexProperties.length, + return new OrderingScore(indexProperties, + clustered, handledOrdering, // no handled properties remainderOrdering, // no remainder properties false, // no need to reverse order @@ -266,8 +266,8 @@ public class OrderingScore { shouldReverseOrder = false; } - return new OrderingScore(clustered, - indexProperties.length, + return new OrderingScore(indexProperties, + clustered, handledOrdering, remainderOrdering, shouldReverseOrder, @@ -285,8 +285,8 @@ public class OrderingScore { return Full.INSTANCE; } + private final OrderedProperty[] mIndexProperties; private final boolean mIndexClustered; - private final int mIndexPropertyCount; private final OrderingList mHandledOrdering; private final OrderingList mRemainderOrdering; @@ -300,16 +300,16 @@ public class OrderingScore { private final OrderingList mFreeOrdering; private final OrderingList mUnusedOrdering; - private OrderingScore(boolean indexClustered, - int indexPropertyCount, + private OrderingScore(OrderedProperty[] indexProperties, + boolean indexClustered, OrderingList handledOrdering, OrderingList remainderOrdering, boolean shouldReverseOrder, OrderingList freeOrdering, OrderingList unusedOrdering) { + mIndexProperties = indexProperties; mIndexClustered = indexClustered; - mIndexPropertyCount = indexPropertyCount; mHandledOrdering = handledOrdering; mRemainderOrdering = remainderOrdering; mShouldReverseOrder = shouldReverseOrder; @@ -317,6 +317,16 @@ public class OrderingScore { mUnusedOrdering = unusedOrdering; } + private OrderingScore(OrderingScore score, OrderingList remainderOrdering) { + mIndexProperties = score.mIndexProperties; + mIndexClustered = score.mIndexClustered; + mHandledOrdering = score.mHandledOrdering; + mRemainderOrdering = remainderOrdering; + mShouldReverseOrder = score.mShouldReverseOrder; + mFreeOrdering = score.mFreeOrdering; + mUnusedOrdering = score.mUnusedOrdering; + } + /** * Returns true if evaluated index is clustered. Scans of clustered indexes * are generally faster. @@ -329,7 +339,7 @@ public class OrderingScore { * Returns the amount of properties in the evaluated index. */ public int getIndexPropertyCount() { - return mIndexPropertyCount; + return mIndexProperties.length; } /** @@ -463,6 +473,16 @@ public class OrderingScore { } } + /** + * Returns a new OrderingScore with the remainder replaced. Handled count + * is not recalculated. + * + * @since 1.2 + */ + public OrderingScore withRemainderOrdering(OrderingList ordering) { + return new OrderingScore(this, ordering); + } + public String toString() { return "OrderingScore {handledCount=" + getHandledCount() + ", remainderCount=" + getRemainderCount() + diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index ea60490..fda5f29 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -422,7 +422,7 @@ public class UnionQueryAnalyzer implements QueryExecutorFact if (mergedResults.size() == 0) { // Nothing was exempt. Rather than return a result with a dnf // filter, return full scan with a simpler reduced filter. - full.setRemainderFilter(filter.reduce()); + full.withRemainderFilter(filter.reduce()); } mergedResults.add(full); diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java index 078069a..87e8eb9 100644 --- a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java +++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java @@ -431,10 +431,22 @@ class IndexedStorage implements Storage, StorageAccess Object[] identityValues) throws FetchException { - return fetchSubset(index, identityValues, - BoundaryType.OPEN, null, - BoundaryType.OPEN, null, - false, false); + ManagedIndex indexInfo = (ManagedIndex) mAllIndexInfoMap.get(index); + return indexInfo.fetchOne(this, identityValues); + } + + public Query indexEntryQuery(StorableIndex index) + throws FetchException + { + ManagedIndex indexInfo = (ManagedIndex) mAllIndexInfoMap.get(index); + return indexInfo.getIndexEntryStorage().query(); + } + + public Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) + throws FetchException + { + ManagedIndex indexInfo = (ManagedIndex) mAllIndexInfoMap.get(index); + return indexInfo.fetchFromIndexEntryQuery(this, indexEntryQuery); } public Cursor fetchSubset(StorableIndex index, @@ -447,31 +459,8 @@ class IndexedStorage implements Storage, StorageAccess boolean reverseOrder) throws FetchException { - // Note: this code ignores the reverseRange parameter to avoid double - // reversal. Only the lowest storage layer should examine this - // parameter. - - ManagedIndex indexInfo = (ManagedIndex) mAllIndexInfoMap.get(index); - - Query query = indexInfo.getIndexEntryQueryFor - (identityValues == null ? 0 : identityValues.length, - rangeStartBoundary, rangeEndBoundary, reverseOrder); - - if (identityValues != null) { - query = query.withValues(identityValues); - } - - if (rangeStartBoundary != BoundaryType.OPEN) { - query = query.with(rangeStartValue); - } - if (rangeEndBoundary != BoundaryType.OPEN) { - query = query.with(rangeEndValue); - } - - Cursor indexEntryCursor = query.fetch(); - - return new IndexedCursor - (indexEntryCursor, IndexedStorage.this, indexInfo.getIndexEntryClassBuilder()); + // This method should never be called since a query was returned by indexEntryQuery. + throw new UnsupportedOperationException(); } private void registerIndex(ManagedIndex managedIndex) diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java index b1e76cc..73469db 100644 --- a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java +++ b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java @@ -38,6 +38,9 @@ import com.amazon.carbonado.SupportException; import com.amazon.carbonado.Transaction; import com.amazon.carbonado.UniqueConstraintException; +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.RelOp; + import com.amazon.carbonado.info.Direction; import com.amazon.carbonado.info.StorableIndex; @@ -65,7 +68,7 @@ class ManagedIndex implements IndexEntryAccessor { private final IndexEntryGenerator mGenerator; private final Storage mIndexEntryStorage; - private final Query[] mQueryCache; + private Query mSingleMatchQuery; ManagedIndex(StorableIndex index, IndexEntryGenerator generator, @@ -75,23 +78,6 @@ class ManagedIndex implements IndexEntryAccessor { mIndex = index; mGenerator = generator; mIndexEntryStorage = indexEntryStorage; - - // Cache keys are encoded as follows: - // bits 1..0: range end boundary - // 0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used - // bits 3..2: range start boundary - // 0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used - // bit 4: 0=forward order, 1=reverse - // bits n..5: exact property match count - - // The size of the cache is dependent on the number of possible - // exactly matching properties, which is the property count of the - // index. If the index contained a huge number of properties, say - // 31, the cache size would be 1024. - - int cacheSize = Integer.highestOneBit(index.getPropertyCount()) << (1 + 5); - - mQueryCache = new Query[cacheSize]; } public String getName() { @@ -153,106 +139,27 @@ class ManagedIndex implements IndexEntryAccessor { return mGenerator.getComparator(); } - public IndexEntryGenerator getIndexEntryClassBuilder() { - return mGenerator; - } - - public Query getIndexEntryQueryFor(int exactMatchCount, - BoundaryType rangeStartBoundary, - BoundaryType rangeEndBoundary, - boolean reverse) + Cursor fetchOne(IndexedStorage storage, Object[] identityValues) throws FetchException { - int key = exactMatchCount << 5; - if (rangeEndBoundary != BoundaryType.OPEN) { - if (rangeEndBoundary == BoundaryType.INCLUSIVE) { - key |= 0x01; - } else { - key |= 0x02; - } - } - if (rangeStartBoundary != BoundaryType.OPEN) { - if (rangeStartBoundary == BoundaryType.INCLUSIVE) { - key |= 0x04; - } else { - key |= 0x08; - } - } + Query query = mSingleMatchQuery; - if (reverse) { - key |= 0x10; - } - - Query query = mQueryCache[key]; if (query == null) { StorableIndex index = mIndex; - - StringBuilder filter = new StringBuilder(); - - int i; - for (i=0; i 0) { - filter.append(" & "); - } - filter.append(index.getProperty(i).getName()); - filter.append(" = ?"); - } - - boolean addOrderBy = false; - - if (rangeStartBoundary != BoundaryType.OPEN) { - addOrderBy = true; - if (filter.length() > 0) { - filter.append(" & "); - } - filter.append(index.getProperty(i).getName()); - if (rangeStartBoundary == BoundaryType.INCLUSIVE) { - filter.append(" >= ?"); - } else { - filter.append(" > ?"); - } - } - - if (rangeEndBoundary != BoundaryType.OPEN) { - addOrderBy = true; - if (filter.length() > 0) { - filter.append(" & "); - } - filter.append(index.getProperty(i).getName()); - if (rangeEndBoundary == BoundaryType.INCLUSIVE) { - filter.append(" <= ?"); - } else { - filter.append(" < ?"); - } - } - - if (filter.length() == 0) { - query = mIndexEntryStorage.query(); - } else { - query = mIndexEntryStorage.query(filter.toString()); + Filter filter = Filter.getOpenFilter(mIndexEntryStorage.getStorableType()); + for (int i=0; i fetchFromIndexEntryQuery(IndexedStorage storage, Query indexEntryQuery) + throws FetchException + { + return new IndexedCursor(indexEntryQuery.fetch(), storage, mGenerator); } public String toString() { diff --git a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java index c33acba..c2d1844 100644 --- a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java +++ b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java @@ -298,6 +298,15 @@ abstract class BDBStorage implements Storage, Storag return new SingletonCursor(instantiate(key, value)); } + public Query indexEntryQuery(StorableIndex index) { + return null; + } + + public Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) { + // This method should never be called since null was returned by indexEntryQuery. + throw new UnsupportedOperationException(); + } + public Cursor fetchSubset(StorableIndex index, Object[] identityValues, BoundaryType rangeStartBoundary, -- cgit v1.2.3