From 5ffb4e8e94b67ba749414b393980483e8373d326 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Mon, 9 Oct 2006 15:05:35 +0000 Subject: Add rule to check user preferences as index selection tie-breaker. --- .../com/amazon/carbonado/qe/CompositeScore.java | 41 ++++++++++++++++ .../com/amazon/carbonado/qe/FilteringScore.java | 30 +++++++++++- .../amazon/carbonado/qe/PropertyFilterList.java | 54 ++++++++++++++++++---- 3 files changed, 114 insertions(+), 11 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 eba6106..7190776 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -190,10 +190,51 @@ public class CompositeScore { result = FilteringScore.rangeComparator().compare(firstScore, secondScore); + OrderingScore firstOrderingScore = first.getOrderingScore(); + OrderingScore secondOrderingScore = second.getOrderingScore(); + if (result != 0) { + if (!firstScore.hasAnyMatches() || !secondScore.hasAnyMatches()) { + // Return result if either index filters nothing. + return result; + } + + // negative: first is better, zero: same, positive: second is better + int handledScore = + secondOrderingScore.getHandledCount() - firstOrderingScore.getHandledCount(); + + if (handledScore == 0) { + // Neither index handles ordering any better, so don't + // bother examining that. + return result; + } + + if (Integer.signum(result) == Integer.signum(handledScore)) { + // Index is better at both filtering and ordering. A double win. + return result; + } + + // This is a tough call. Both indexes perform some filtering, + // but one index is clearly better at it. The other index is + // clearly better for ordering, however. Without knowing how + // many results can be filtered out, it isn't possible to + // decide which index is better. Let the user decide in this + // case, by examing the preference order of filter properties. + + int preferenceResult = + secondScore.getPreferenceScore().compareTo(firstScore.getPreferenceScore()); + if (preferenceResult != 0) { + return preferenceResult; + } + + // Preference scores are the same? That seems unlikely, but + // choose the better filtering index. return result; } + // If this point is reached, the filtering score has not been + // terribly helpful in deciding an index. Check the ordering score. + 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 diff --git a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java index c9178a1..d872ec6 100644 --- a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java +++ b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java @@ -18,6 +18,8 @@ package com.amazon.carbonado.qe; +import java.math.BigInteger; + import java.util.ArrayList; import java.util.Comparator; import java.util.Collections; @@ -106,15 +108,16 @@ public class FilteringScore { // List is ordered such that '=' operations are first and '!=' // operations are last. - List> filterList = PropertyFilterList.get(filter); + PropertyFilterList originalFilterList = PropertyFilterList.get(filter); // Copy so it so that matching elements can be removed. - filterList = new ArrayList>(filterList); + List> filterList = new ArrayList>(originalFilterList); // First find the identity matches. List> identityFilters = new ArrayList>(); int arrangementScore = 0; + BigInteger preferenceScore = BigInteger.ZERO; int indexPropPos; int lastFilterPos = 0; @@ -131,6 +134,9 @@ public class FilteringScore { } if (subFilter.getChainedProperty().equals(indexProp)) { identityFilters.add(subFilter); + int shift = originalFilterList.size() + - originalFilterList.getOriginalPosition(subFilter) - 1; + preferenceScore = preferenceScore.or(BigInteger.ONE.shiftLeft(shift)); if (pos >= lastFilterPos) { arrangementScore++; } @@ -186,6 +192,10 @@ public class FilteringScore { filterList.remove(pos); + int shift = originalFilterList.size() + - originalFilterList.getOriginalPosition(subFilter) - 1; + preferenceScore = preferenceScore.or(BigInteger.ONE.shiftLeft(shift)); + // Loop correction after removing element. pos--; } @@ -204,6 +214,7 @@ public class FilteringScore { rangeStartFilters, rangeEndFilters, arrangementScore, + preferenceScore, filterList, shouldReverseRange); } @@ -262,6 +273,7 @@ public class FilteringScore { private final List> mRangeEndFilters; private final int mArrangementScore; + private final BigInteger mPreferenceScore; private final List> mRemainderFilters; @@ -277,6 +289,7 @@ public class FilteringScore { List> rangeStartFilters, List> rangeEndFilters, int arrangementScore, + BigInteger preferenceScore, List> remainderFilters, boolean shouldReverseRange) { @@ -287,6 +300,7 @@ public class FilteringScore { mRangeStartFilters = prepareList(rangeStartFilters); mRangeEndFilters = prepareList(rangeEndFilters); mArrangementScore = arrangementScore; + mPreferenceScore = preferenceScore; mRemainderFilters = prepareList(remainderFilters); mShouldReverseRange = shouldReverseRange; } @@ -441,6 +455,17 @@ public class FilteringScore { return mArrangementScore; } + /** + * Returns a value which indicates user index preference, based on the + * original ordering of elements in the filter. A higher value can + * indicate that the index is a slightly better match. + * + * @return preference value which can be compared to another one + */ + public Comparable getPreferenceScore() { + return mPreferenceScore; + } + /** * Returns number of property filters not supported by the evaluated index. */ @@ -496,6 +521,7 @@ public class FilteringScore { && isIndexUnique() == other.isIndexUnique() && getIndexPropertyCount() == other.getIndexPropertyCount() && getArrangementScore() == other.getArrangementScore() + && getPreferenceScore().equals(other.getPreferenceScore()) && shouldReverseRange() == other.shouldReverseRange() // List comparisons assume identical ordering, but this is // not strictly required. Since the different scores likely diff --git a/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java b/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java index f17a2df..497a620 100644 --- a/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java +++ b/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java @@ -18,9 +18,11 @@ package com.amazon.carbonado.qe; +import java.util.AbstractList; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; +import java.util.HashMap; import java.util.List; import java.util.Map; @@ -41,8 +43,8 @@ import com.amazon.carbonado.filter.Visitor; * * @author Brian S O'Neill */ -class PropertyFilterList { - private static Map, List> cCache; +class PropertyFilterList extends AbstractList> { + private static Map, PropertyFilterList> cCache; static { cCache = new SoftValuedHashMap(); @@ -53,21 +55,26 @@ class PropertyFilterList { * @return unmodifiable list of PropertyFilters, which is empty if input filter was null * @throws IllegalArgumentException if filter has any operators other than 'and'. */ - static List> get(Filter filter) { - List> list; + static PropertyFilterList get(Filter filter) { + PropertyFilterList plist; synchronized (cCache) { - list = (List>) cCache.get(filter); + plist = (PropertyFilterList) cCache.get(filter); } - if (list != null) { - return list; + if (plist != null) { + return plist; } + List> list; + Map, Integer> posMap; + if (filter == null) { list = Collections.emptyList(); + posMap = Collections.emptyMap(); } else if (filter instanceof PropertyFilter) { list = Collections.singletonList((PropertyFilter) filter); + posMap = Collections.singletonMap((PropertyFilter) filter, 0); } else { list = new ArrayList>(); final List> flist = list; @@ -83,17 +90,46 @@ class PropertyFilterList { } }, null); + posMap = new HashMap, Integer>(); + for (int i=0; i()); ((ArrayList) list).trimToSize(); list = Collections.unmodifiableList(list); } + plist = new PropertyFilterList(list, posMap); + synchronized (cCache) { - cCache.put(filter, list); + cCache.put(filter, plist); } - return list; + return plist; + } + + private final List> mList; + private final Map, Integer> mPosMap; + + private PropertyFilterList(List> list, + Map, Integer> posMap) + { + mList = list; + mPosMap = posMap; + } + + public Integer getOriginalPosition(PropertyFilter filter) { + return mPosMap.get(filter); + } + + public int size() { + return mList.size(); + } + + public PropertyFilter get(int index) { + return mList.get(index); } private static class PFComparator -- cgit v1.2.3