Merged in covering index optimization.

5 files changed, 143 insertions, 42 deletions

diff --git a/src/test/java/com/amazon/carbonado/qe/TestFilteringScore.java b/src/test/java/com/amazon/carbonado/qe/TestFilteringScore.java
index 8c6dc78..25222a7 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestFilteringScore.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestFilteringScore.java
@@ -79,8 +79,8 @@ public class TestFilteringScore extends TestCase {
         assertFalse(score.hasAnyMatches());

         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

     }

 

     public void testSimpleIndexMisses() throws Exception {

@@ -105,8 +105,8 @@ public class TestFilteringScore extends TestCase {
         assertEquals(1, score.getRemainderFilters().size());

         assertEquals(filter, score.getRemainderFilters().get(0));

         assertEquals(filter, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

 

         // Try again with matching property, but with an operator that cannot be used by index.

         filter = Filter.filterFor(StorableTestBasic.class, "intProp != ?");

@@ -128,8 +128,8 @@ public class TestFilteringScore extends TestCase {
         assertEquals(1, score.getRemainderFilters().size());

         assertEquals(filter, score.getRemainderFilters().get(0));

         assertEquals(filter, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

     }

 

     public void testSimpleIndexMatches() throws Exception {

@@ -154,9 +154,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

         assertEquals(null, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(null, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(null, score.getCoveringRemainderFilter());

 

         // Try again with open ranges.

         for (int i=0; i<4; i++) {

@@ -179,9 +179,9 @@ public class TestFilteringScore extends TestCase {
             assertEquals(0, score.getRemainderCount());

             assertEquals(0, score.getRemainderFilters().size());

             assertEquals(null, score.getRemainderFilter());

-            assertEquals(0, score.getExtraMatchCount());

-            assertEquals(0, score.getExtraMatchFilters().size());

-            assertEquals(null, score.getExtraMatchRemainderFilter());

+            assertEquals(0, score.getCoveringCount());

+            assertEquals(0, score.getCoveringFilters().size());

+            assertEquals(null, score.getCoveringRemainderFilter());

 

             if (i < 2) {

                 assertTrue(score.hasRangeStart());

@@ -210,9 +210,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

         assertEquals(null, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(null, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(null, score.getCoveringRemainderFilter());

 

         assertTrue(score.hasRangeStart());

         assertEquals(2, score.getRangeStartFilters().size());

@@ -235,9 +235,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

         assertEquals(null, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(null, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(null, score.getCoveringRemainderFilter());

 

         assertFalse(score.hasRangeStart());

         assertEquals(0, score.getRangeStartFilters().size());

@@ -260,9 +260,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

         assertEquals(null, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(null, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(null, score.getCoveringRemainderFilter());

 

         assertTrue(score.hasRangeStart());

         assertEquals(1, score.getRangeStartFilters().size());

@@ -350,9 +350,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(0, score.getRemainderCount());

         assertEquals(0, score.getRemainderFilters().size());

         assertEquals(null, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(null, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(null, score.getCoveringRemainderFilter());

 

         // Filter by a property with a gap. (filter must include "id" to use index)

         filter = Filter.filterFor(StorableTestBasic.class, "intProp = ?");

@@ -364,9 +364,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(1, score.getRemainderCount());

         assertEquals(1, score.getRemainderFilters().size());

         assertEquals(filter, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(filter, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(filter, score.getCoveringRemainderFilter());

 

         // Filter by a property with a gap and a range operator. (index still cannot be used)

         filter = Filter.filterFor(StorableTestBasic.class, "intProp = ? & stringProp < ?");

@@ -378,9 +378,9 @@ public class TestFilteringScore extends TestCase {
         assertEquals(2, score.getRemainderCount());

         assertEquals(2, score.getRemainderFilters().size());

         assertEquals(filter, score.getRemainderFilter());

-        assertEquals(0, score.getExtraMatchCount());

-        assertEquals(0, score.getExtraMatchFilters().size());

-        assertEquals(filter, score.getExtraMatchRemainderFilter());

+        assertEquals(0, score.getCoveringCount());

+        assertEquals(0, score.getCoveringFilters().size());

+        assertEquals(filter, score.getCoveringRemainderFilter());

 

         // Filter with range match before identity match. Identity cannot be used.

         filter = Filter.filterFor(StorableTestBasic.class, "intProp = ? & id < ?");

@@ -400,10 +400,10 @@ public class TestFilteringScore extends TestCase {
         assertEquals(Filter.filterFor(StorableTestBasic.class, "intProp = ?"),

                      score.getRemainderFilter());

 

-        assertEquals(1, score.getExtraMatchCount());

-        assertEquals(1, score.getExtraMatchFilters().size());

+        assertEquals(1, score.getCoveringCount());

+        assertEquals(1, score.getCoveringFilters().size());

         assertEquals(Filter.filterFor(StorableTestBasic.class, "intProp = ?"),

-                     score.getExtraMatchFilter());

+                     score.getCoveringFilter());

 

         // Filter with fully specified identity match, but a few remaining.

         filter = Filter.filterFor

@@ -432,13 +432,13 @@ public class TestFilteringScore extends TestCase {
                      score.getRemainderFilters().get(1));

 

         // Other use of stringProp is an extra match.

-        assertEquals(1, score.getExtraMatchCount());

-        assertEquals(1, score.getExtraMatchFilters().size());

+        assertEquals(1, score.getCoveringCount());

+        assertEquals(1, score.getCoveringFilters().size());

         assertEquals(Filter.filterFor(StorableTestBasic.class, "stringProp > ?"),

-                     score.getExtraMatchFilters().get(0));

+                     score.getCoveringFilters().get(0));

 

         assertEquals(Filter.filterFor(StorableTestBasic.class, "doubleProp = ?"),

-                     score.getExtraMatchRemainderFilter());

+                     score.getCoveringRemainderFilter());

 

         // Filter with identity and range matches.

         filter = Filter.filterFor

@@ -462,12 +462,12 @@ public class TestFilteringScore extends TestCase {
         assertEquals(Filter.filterFor(StorableTestBasic.class, "stringProp < ?"),

                      score.getRemainderFilters().get(2));

 

-        assertEquals(2, score.getExtraMatchCount());

-        assertEquals(2, score.getExtraMatchFilters().size());

+        assertEquals(2, score.getCoveringCount());

+        assertEquals(2, score.getCoveringFilters().size());

         assertEquals(Filter.filterFor(StorableTestBasic.class, "stringProp = ?"),

-                     score.getExtraMatchFilters().get(0));

+                     score.getCoveringFilters().get(0));

         assertEquals(Filter.filterFor(StorableTestBasic.class, "stringProp < ?"),

-                     score.getExtraMatchFilters().get(1));

+                     score.getCoveringFilters().get(1));

 

         assertTrue(score.hasRangeMatch());

         assertTrue(score.hasRangeStart());

diff --git a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java
index 6b1919a..9316b34 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java
@@ -48,6 +48,7 @@ import com.amazon.carbonado.repo.toy.ToyRepository;
 

 import com.amazon.carbonado.stored.Address;

 import com.amazon.carbonado.stored.Order;

+import com.amazon.carbonado.stored.OverIndexedUserAddress;

 import com.amazon.carbonado.stored.Shipment;

 import com.amazon.carbonado.stored.Shipper;

 import com.amazon.carbonado.stored.StorableTestBasic;

@@ -337,6 +338,33 @@ public class TestIndexedQueryAnalyzer extends TestCase {
                      joinExec2.getFilter().unbind().disjunctiveNormalForm());

     }

 

+    public void testCoveringIndex() throws Exception {

+        IndexedQueryAnalyzer<OverIndexedUserAddress> iqa =

+            new IndexedQueryAnalyzer<OverIndexedUserAddress>

+            (OverIndexedUserAddress.class, RepoAccess.INSTANCE);

+        Filter<OverIndexedUserAddress> filter = Filter.filterFor

+            (OverIndexedUserAddress.class, "country > ? & city != ? & state = ? & postalCode = ?");

+        FilterValues<OverIndexedUserAddress> values = filter.initialFilterValues();

+        filter = values.getFilter();

+        IndexedQueryAnalyzer<OverIndexedUserAddress>.Result result = iqa.analyze(filter, null);

+

+        QueryExecutor<OverIndexedUserAddress> qe = result.createExecutor();

+

+        StringBuffer buf = new StringBuffer();

+        qe.printPlan(buf, 0, values);

+        String plan = buf.toString();

+

+        String expected =

+            "filter: postalCode = ?\n" +

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

+            "  ...index: {properties=[+state, +city, +country, +line2, +line1], unique=false}\n" + 

+            "  ...identity filter: state = ?\n" +

+            "  ...covering filter: country > ? & city != ?";

+

+        //System.out.println(plan);

+        assertEquals(expected, plan);

+    }

+

     static class RepoAccess implements RepositoryAccess {

         static final RepoAccess INSTANCE = new RepoAccess();

 

@@ -418,6 +446,13 @@ public class TestIndexedQueryAnalyzer extends TestCase {
                     makeIndex(mType, "+intProp", "stringProp", "~id").unique(true),

                     makeIndex(mType, "-doubleProp", "+longProp", "~id").unique(true),

                 };

+            } else if (OverIndexedUserAddress.class.isAssignableFrom(mType)) {

+                indexes = new StorableIndex[] {

+                    makeIndex(mType, "addressID"),

+                    makeIndex(mType, "country", "state", "city", "line1", "line2", "postalCode"),

+                    makeIndex(mType, "state", "city", "country", "line2", "line1"),

+                    makeIndex(mType, "city", "state", "country", "line1", "line2"),

+                };

             } else {

                 indexes = new StorableIndex[0];

             }

@@ -445,6 +480,15 @@ public class TestIndexedQueryAnalyzer extends TestCase {
             throw new UnsupportedOperationException();

         }

 

+        public Query<?> indexEntryQuery(StorableIndex<S> index) {

+            return new EmptyQuery();

+        }

+

+        public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery)

+        {

+            throw new UnsupportedOperationException();

+        }

+

         public Cursor<S> fetchSubset(StorableIndex<S> index,

                                      Object[] identityValues,

                                      BoundaryType rangeStartBoundary,

diff --git a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryExecutor.java b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryExecutor.java
index a68fbac..71e2f6f 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryExecutor.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryExecutor.java
@@ -27,6 +27,8 @@ import junit.framework.TestCase;
 import junit.framework.TestSuite;

 

 import com.amazon.carbonado.Cursor;

+import com.amazon.carbonado.FetchException;

+import com.amazon.carbonado.Query;

 import com.amazon.carbonado.Storable;

 

 import com.amazon.carbonado.cursor.IteratorCursor;

@@ -726,10 +728,19 @@ public class TestIndexedQueryExecutor extends TestCase {
         boolean mReverseRange;

         boolean mReverseOrder;

 

-        public Mock(StorableIndex<S> index, CompositeScore<S> score) {

+        public Mock(StorableIndex<S> index, CompositeScore<S> score) throws FetchException {

             super(null, index, score);

         }

 

+        public Query<?> indexEntryQuery(StorableIndex<S> index) {

+            return null;

+        }

+

+        public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery)

+        {

+            throw new UnsupportedOperationException();

+        }

+

         public Cursor<S> fetchSubset(StorableIndex<S> index,

                                      Object[] identityValues,

                                      BoundaryType rangeStartBoundary,

diff --git a/src/test/java/com/amazon/carbonado/qe/TestJoinedQueryExecutor.java b/src/test/java/com/amazon/carbonado/qe/TestJoinedQueryExecutor.java
index e1abca9..324af75 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestJoinedQueryExecutor.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestJoinedQueryExecutor.java
@@ -263,6 +263,15 @@ public class TestJoinedQueryExecutor extends TestQueryExecutor {
             throw new UnsupportedOperationException();

         }

 

+        public Query<?> indexEntryQuery(StorableIndex<S> index) {

+            return null;

+        }

+

+        public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery)

+        {

+            throw new UnsupportedOperationException();

+        }

+

         public Cursor<S> fetchSubset(StorableIndex<S> index,

                                      Object[] identityValues,

                                      BoundaryType rangeStartBoundary,

diff --git a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
index 21d0b0c..69a0aa4 100644
--- a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
+++ b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java
@@ -37,6 +37,7 @@ import com.amazon.carbonado.repo.toy.ToyRepository;
 

 import com.amazon.carbonado.stored.Address;

 import com.amazon.carbonado.stored.Order;

+import com.amazon.carbonado.stored.OverIndexedUserAddress;

 import com.amazon.carbonado.stored.Shipment;

 import com.amazon.carbonado.stored.Shipper;

 import com.amazon.carbonado.stored.StorableTestBasic;

@@ -285,6 +286,42 @@ public class TestUnionQueryAnalyzer extends TestCase {
                      res_0.getRemainderFilter().unbind());

     }

 

+    public void testSimpleCoveringMerge() throws Exception {

+        // Because query has an 'or' operation, the analyzer will initially

+        // split this into a union. After futher analysis, it should decide

+        // that this offers no benefit and will merge them back.

+        UnionQueryAnalyzer uqa =

+            new UnionQueryAnalyzer(OverIndexedUserAddress.class,

+                                   TestIndexedQueryAnalyzer.RepoAccess.INSTANCE);

+        Filter<OverIndexedUserAddress> filter = Filter.filterFor

+            (OverIndexedUserAddress.class,

+             "city = ? & (city = ? | line1 = ?)");

+        filter = filter.bind();

+        UnionQueryAnalyzer.Result result = uqa.analyze(filter, null);

+        List<IndexedQueryAnalyzer<OverIndexedUserAddress>.Result> subResults =

+            result.getSubResults();

+

+        assertEquals(1, subResults.size());

+        IndexedQueryAnalyzer<OverIndexedUserAddress>.Result res_0 = subResults.get(0);

+

+        assertTrue(res_0.handlesAnything());

+        assertEquals(Filter.filterFor(OverIndexedUserAddress.class, "city = ?").bind(),

+                     res_0.getCompositeScore().getFilteringScore().getIdentityFilter());

+        assertEquals(makeIndex(OverIndexedUserAddress.class,

+                               "city", "state", "country", "line1", "line2"),

+                     res_0.getLocalIndex());

+        assertEquals(null, res_0.getForeignIndex());

+        assertEquals(null, res_0.getForeignProperty());

+        assertEquals(0, res_0.getRemainderOrdering().size());

+        assertEquals(Filter.filterFor(OverIndexedUserAddress.class, "city = ? | line1 = ?"),

+                     res_0.getRemainderFilter().unbind());

+

+        Filter<OverIndexedUserAddress> covering =

+            res_0.getCompositeScore().getFilteringScore().getCoveringFilter();

+        assertEquals(Filter.filterFor(OverIndexedUserAddress.class, "city = ? | line1 = ?"),

+                     covering.unbind());

+    }

+

     public void testFullScan() throws Exception {

         // Because no indexes were selected, there's no union to perform.

         UnionQueryAnalyzer uqa =