From d4969b5a1e375145e5ca399be7fe9cb6b59f39e5 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sun, 20 May 2007 00:24:06 +0000 Subject: Merged in covering index optimization. --- .../amazon/carbonado/qe/TestFilteringScore.java | 82 +++++++++++----------- .../carbonado/qe/TestIndexedQueryAnalyzer.java | 44 ++++++++++++ .../carbonado/qe/TestIndexedQueryExecutor.java | 13 +++- .../carbonado/qe/TestJoinedQueryExecutor.java | 9 +++ .../carbonado/qe/TestUnionQueryAnalyzer.java | 37 ++++++++++ 5 files changed, 143 insertions(+), 42 deletions(-) (limited to 'src/test/java/com/amazon/carbonado/qe') 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 iqa = + new IndexedQueryAnalyzer + (OverIndexedUserAddress.class, RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (OverIndexedUserAddress.class, "country > ? & city != ? & state = ? & postalCode = ?"); + FilterValues values = filter.initialFilterValues(); + filter = values.getFilter(); + IndexedQueryAnalyzer.Result result = iqa.analyze(filter, null); + + QueryExecutor 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 index) { + return new EmptyQuery(); + } + + public Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) + { + throw new UnsupportedOperationException(); + } + public Cursor fetchSubset(StorableIndex 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 index, CompositeScore score) { + public Mock(StorableIndex index, CompositeScore score) throws FetchException { super(null, index, score); } + public Query indexEntryQuery(StorableIndex index) { + return null; + } + + public Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) + { + throw new UnsupportedOperationException(); + } + public Cursor fetchSubset(StorableIndex 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 index) { + return null; + } + + public Cursor fetchFromIndexEntryQuery(StorableIndex index, Query indexEntryQuery) + { + throw new UnsupportedOperationException(); + } + public Cursor fetchSubset(StorableIndex 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 filter = Filter.filterFor + (OverIndexedUserAddress.class, + "city = ? & (city = ? | line1 = ?)"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + List.Result> subResults = + result.getSubResults(); + + assertEquals(1, subResults.size()); + IndexedQueryAnalyzer.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 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 = -- cgit v1.2.3