Add rule to check user preferences as index selection tie-breaker.

4 files changed, 124 insertions, 21 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>

diff --git a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
index 7c92772..21d0b0c 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
@@ -385,7 +385,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
         exec.printPlan(buf, 0, null);

         String plan = buf.toString();

 

-        String expexted =

+        String expected =

             "union\n" +

             "  sort: [+id]\n" +

             "    index scan: com.amazon.carbonado.stored.StorableTestBasic\n" +

@@ -399,7 +399,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
             "  ...range filter: id > ?\n";

 

         // Test test will fail if the format of the plan changes.

-        assertEquals(expexted, plan);

+        assertEquals(expected, plan);

     }

 

     public void testComplexUnionPlan2() throws Exception {

@@ -427,7 +427,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
         exec.printPlan(buf, 0, null);

         String plan = buf.toString();

 

-        String expexted =

+        String expected =

             "union\n" +

             "  sort: [+stringProp]\n" +

             "    index scan: com.amazon.carbonado.stored.StorableTestBasic\n" +

@@ -438,7 +438,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
             "  ...identity filter: stringProp = ?\n";

 

         // Test test will fail if the format of the plan changes.

-        assertEquals(expexted, plan);

+        assertEquals(expected, plan);

     }

 

     public void testComplexUnionPlan3() throws Exception {

@@ -464,7 +464,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
         exec.printPlan(buf, 0, null);

         String plan = buf.toString();

 

-        String expexted =

+        String expected =

             "union\n" +

             "  index scan: com.amazon.carbonado.stored.StorableTestBasic\n" +

             "  ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" +

@@ -474,7 +474,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
             "  ...identity filter: stringProp = ?[2]\n";

 

         // Test test will fail if the format of the plan changes.

-        assertEquals(expexted, plan);

+        assertEquals(expected, plan);

     }

 

     public void testComplexUnionPlan4() throws Exception {

@@ -502,7 +502,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
         exec.printPlan(buf, 0, null);

         String plan = buf.toString();

 

-        String expexted =

+        String expected =

             "union\n" +

             "  sort: [+id]\n" +

             "    index scan: com.amazon.carbonado.stored.StorableTestBasic\n" +

@@ -518,7 +518,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
             "    ...range filter: id > ?\n";

 

         // Test test will fail if the format of the plan changes.

-        assertEquals(expexted, plan);

+        assertEquals(expected, plan);

     }

 

     public void testComplexUnionPlan5() throws Exception {

@@ -546,7 +546,7 @@ public class TestUnionQueryAnalyzer extends TestCase {
         exec.printPlan(buf, 0, null);

         String plan = buf.toString();

 

-        String expexted =

+        String expected =

             "union\n" +

             "  index scan: com.amazon.carbonado.stored.StorableTestBasic\n" +

             "  ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" +

@@ -560,6 +560,6 @@ public class TestUnionQueryAnalyzer extends TestCase {
             "    ...range filter: id > ?\n";

 

         // Test test will fail if the format of the plan changes.

-        assertEquals(expexted, plan);

+        assertEquals(expected, plan);

     }

 }