From 1c9a5991aa49724c34a20fcea6fd1252ce03b8d9 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Tue, 19 Sep 2006 23:15:46 +0000 Subject: More tests and fixes. --- .../com/amazon/carbonado/qe/CompositeScore.java | 30 ++++++++--- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 9 ++++ .../amazon/carbonado/qe/IndexedQueryExecutor.java | 4 ++ .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 59 +++++++++++++++++++--- 4 files changed, 87 insertions(+), 15 deletions(-) (limited to 'src/main/java/com') diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index c8e9490..6d0fad5 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -166,24 +166,38 @@ public class CompositeScore { return result; } - result = FilteringScore.rangeComparator() - .compare(first.getFilteringScore(), second.getFilteringScore()); + FilteringScore firstScore = first.getFilteringScore(); + FilteringScore secondScore = second.getFilteringScore(); + + result = FilteringScore.rangeComparator().compare(firstScore, secondScore); if (result != 0) { return result; } - result = OrderingScore.fullComparator() - .compare(first.getOrderingScore(), second.getOrderingScore()); + if (considerOrdering(firstScore) && considerOrdering(secondScore)) { + // Only consider ordering if index is fast (clustered) or if + // index is used for any significant filtering. A full scan of + // an index just to get desired ordering can be very expensive + // due to random access I/O. A sort operation is often faster. - if (result != 0) { - return result; + result = OrderingScore.fullComparator() + .compare(first.getOrderingScore(), second.getOrderingScore()); + + if (result != 0) { + return result; + } } - result = FilteringScore.fullComparator() - .compare(first.getFilteringScore(), second.getFilteringScore()); + result = FilteringScore.fullComparator().compare(firstScore, secondScore); return result; } + + private boolean considerOrdering(FilteringScore score) { + return score.isIndexClustered() + || score.getIdentityCount() > 0 + || score.hasRangeMatch(); + } } } diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 76f0b52..dfa76ac 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -370,6 +370,15 @@ public class IndexedQueryAnalyzer { return mForeignProperty; } + /** + * Returns true if local or foreign index is clustered. Scans of + * clustered indexes are generally faster. + */ + public boolean isIndexClustered() { + return (mLocalIndex != null && mLocalIndex.isClustered()) + || (mForeignIndex != null && mForeignIndex.isClustered()); + } + /** * 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 diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java index d87740b..cc342c6 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -177,6 +177,10 @@ public class IndexedQueryExecutor extends AbstractQueryExecu filter = filter == null ? p : filter.and(p); } + if (filter == null) { + return Filter.getOpenFilter(getStorableType()); + } + return filter; } diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index 5933f6c..c64e4d4 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -19,6 +19,7 @@ package com.amazon.carbonado.qe; import java.util.ArrayList; +import java.util.Collection; import java.util.Collections; import java.util.LinkedHashMap; import java.util.HashSet; @@ -184,15 +185,28 @@ public class UnionQueryAnalyzer implements QueryExecutorFact // Keep looping until total ordering achieved. while (true) { - // For each ordering score, find the next free property. If - // property is in the super key increment a tally associated with - // property direction. Choose the property with the best tally and - // augment the orderings with it and create new sub-results. - // Remove the property from the super key and the key set. If any - // key is now fully covered, a total ordering has been achieved. + // For each ordering score, iterate over the entire unused ordering + // properties and select the next free property. If property is in + // the super key increment a tally associated with property + // direction. Choose the property with the best tally and augment + // the orderings with it and create new sub-results. Remove the + // property from the super key and the key set. If any key is now + // fully covered, a total ordering has been achieved. for (IndexedQueryAnalyzer.Result result : subResults) { OrderingScore score = result.getCompositeScore().getOrderingScore(); + + OrderingList unused = score.getUnusedOrdering(); + if (unused.size() > 0) { + for (OrderedProperty prop : unused) { + ChainedProperty chainedProp = prop.getChainedProperty(); + Tally tally = superKey.get(chainedProp); + if (tally != null) { + tally.increment(prop.getDirection()); + } + } + } + OrderingList free = score.getFreeOrdering(); if (free.size() > 0) { OrderedProperty prop = free.get(0); @@ -237,7 +251,9 @@ public class UnionQueryAnalyzer implements QueryExecutorFact /** * Returns a list of all primary and alternate keys, stripped of ordering. */ - private List>> getKeys() { + private List>> getKeys() + throws SupportException, RepositoryException + { StorableInfo info = StorableIntrospector.examine(mIndexAnalyzer.getStorableType()); List>> keys = new ArrayList>>(); @@ -247,6 +263,26 @@ public class UnionQueryAnalyzer implements QueryExecutorFact keys.add(stripOrdering(altKey.getProperties())); } + // Also fold in all unique indexes, just in case they weren't reported + // as actual keys. + Collection> indexes = + mRepoAccess.storageAccessFor(getStorableType()).getAllIndexes(); + + for (StorableIndex index : indexes) { + if (!index.isUnique()) { + continue; + } + + int propCount = index.getPropertyCount(); + Set> props = new HashSet>(propCount); + + for (int i=0; i implements QueryExecutorFact full = result; break; } + if (!result.getCompositeScore().getFilteringScore().hasAnyMatches()) { + if (full == null) { + // This index is used only for its ordering, and it will be + // tentatively selected as the "full scan". If a result is + // found doesn't use an index for anything, then it becomes + // the "full scan" index. + full = result; + } + } } if (full == null) { -- cgit v1.2.3