diff options
Diffstat (limited to 'src/main/java/com/amazon/carbonado/qe')
3 files changed, 114 insertions, 11 deletions
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<S extends Storable> { 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<S extends Storable> { // List is ordered such that '=' operations are first and '!='
// operations are last.
- List<PropertyFilter<S>> filterList = PropertyFilterList.get(filter);
+ PropertyFilterList<S> originalFilterList = PropertyFilterList.get(filter);
// Copy so it so that matching elements can be removed.
- filterList = new ArrayList<PropertyFilter<S>>(filterList);
+ List<PropertyFilter<S>> filterList = new ArrayList<PropertyFilter<S>>(originalFilterList);
// First find the identity matches.
List<PropertyFilter<S>> identityFilters = new ArrayList<PropertyFilter<S>>();
int arrangementScore = 0;
+ BigInteger preferenceScore = BigInteger.ZERO;
int indexPropPos;
int lastFilterPos = 0;
@@ -131,6 +134,9 @@ public class FilteringScore<S extends Storable> { }
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<S extends Storable> { 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<S extends Storable> { rangeStartFilters,
rangeEndFilters,
arrangementScore,
+ preferenceScore,
filterList,
shouldReverseRange);
}
@@ -262,6 +273,7 @@ public class FilteringScore<S extends Storable> { private final List<PropertyFilter<S>> mRangeEndFilters;
private final int mArrangementScore;
+ private final BigInteger mPreferenceScore;
private final List<PropertyFilter<S>> mRemainderFilters;
@@ -277,6 +289,7 @@ public class FilteringScore<S extends Storable> { List<PropertyFilter<S>> rangeStartFilters,
List<PropertyFilter<S>> rangeEndFilters,
int arrangementScore,
+ BigInteger preferenceScore,
List<PropertyFilter<S>> remainderFilters,
boolean shouldReverseRange)
{
@@ -287,6 +300,7 @@ public class FilteringScore<S extends Storable> { mRangeStartFilters = prepareList(rangeStartFilters);
mRangeEndFilters = prepareList(rangeEndFilters);
mArrangementScore = arrangementScore;
+ mPreferenceScore = preferenceScore;
mRemainderFilters = prepareList(remainderFilters);
mShouldReverseRange = shouldReverseRange;
}
@@ -442,6 +456,17 @@ public class FilteringScore<S extends Storable> { }
/**
+ * 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.
*/
public int getRemainderCount() {
@@ -496,6 +521,7 @@ public class FilteringScore<S extends Storable> { && 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<Filter<?>, List> cCache;
+class PropertyFilterList<S extends Storable> extends AbstractList<PropertyFilter<S>> {
+ private static Map<Filter<?>, 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 <S extends Storable> List<PropertyFilter<S>> get(Filter<S> filter) {
- List<PropertyFilter<S>> list;
+ static <S extends Storable> PropertyFilterList<S> get(Filter<S> filter) {
+ PropertyFilterList<S> plist;
synchronized (cCache) {
- list = (List<PropertyFilter<S>>) cCache.get(filter);
+ plist = (PropertyFilterList<S>) cCache.get(filter);
}
- if (list != null) {
- return list;
+ if (plist != null) {
+ return plist;
}
+ List<PropertyFilter<S>> list;
+ Map<PropertyFilter<S>, Integer> posMap;
+
if (filter == null) {
list = Collections.emptyList();
+ posMap = Collections.emptyMap();
} else if (filter instanceof PropertyFilter) {
list = Collections.singletonList((PropertyFilter<S>) filter);
+ posMap = Collections.singletonMap((PropertyFilter<S>) filter, 0);
} else {
list = new ArrayList<PropertyFilter<S>>();
final List<PropertyFilter<S>> flist = list;
@@ -83,17 +90,46 @@ class PropertyFilterList { }
}, null);
+ posMap = new HashMap<PropertyFilter<S>, Integer>();
+ for (int i=0; i<list.size(); i++) {
+ posMap.put(list.get(i), i);
+ }
+
Collections.sort(list, new PFComparator<S>());
((ArrayList) list).trimToSize();
list = Collections.unmodifiableList(list);
}
+ plist = new PropertyFilterList<S>(list, posMap);
+
synchronized (cCache) {
- cCache.put(filter, list);
+ cCache.put(filter, plist);
}
- return list;
+ return plist;
+ }
+
+ private final List<PropertyFilter<S>> mList;
+ private final Map<PropertyFilter<S>, Integer> mPosMap;
+
+ private PropertyFilterList(List<PropertyFilter<S>> list,
+ Map<PropertyFilter<S>, Integer> posMap)
+ {
+ mList = list;
+ mPosMap = posMap;
+ }
+
+ public Integer getOriginalPosition(PropertyFilter<S> filter) {
+ return mPosMap.get(filter);
+ }
+
+ public int size() {
+ return mList.size();
+ }
+
+ public PropertyFilter<S> get(int index) {
+ return mList.get(index);
}
private static class PFComparator<S extends Storable>
|