From 1c9a5991aa49724c34a20fcea6fd1252ce03b8d9 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Tue, 19 Sep 2006 23:15:46 +0000 Subject: More tests and fixes. --- .../com/amazon/carbonado/qe/CompositeScore.java | 30 ++- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 9 + .../amazon/carbonado/qe/IndexedQueryExecutor.java | 4 + .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 59 ++++- .../carbonado/qe/TestIndexedQueryAnalyzer.java | 9 + .../carbonado/qe/TestUnionQueryAnalyzer.java | 247 +++++++++++++++++++-- 6 files changed, 327 insertions(+), 31 deletions(-) diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index c8e9490..6d0fad5 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -166,24 +166,38 @@ public class CompositeScore { return result; } - result = FilteringScore.rangeComparator() - .compare(first.getFilteringScore(), second.getFilteringScore()); + FilteringScore firstScore = first.getFilteringScore(); + FilteringScore secondScore = second.getFilteringScore(); + + result = FilteringScore.rangeComparator().compare(firstScore, secondScore); if (result != 0) { return result; } - result = OrderingScore.fullComparator() - .compare(first.getOrderingScore(), second.getOrderingScore()); + 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 + // an index just to get desired ordering can be very expensive + // due to random access I/O. A sort operation is often faster. - if (result != 0) { - return result; + result = OrderingScore.fullComparator() + .compare(first.getOrderingScore(), second.getOrderingScore()); + + if (result != 0) { + return result; + } } - result = FilteringScore.fullComparator() - .compare(first.getFilteringScore(), second.getFilteringScore()); + result = FilteringScore.fullComparator().compare(firstScore, secondScore); return result; } + + private boolean considerOrdering(FilteringScore score) { + return score.isIndexClustered() + || score.getIdentityCount() > 0 + || score.hasRangeMatch(); + } } } diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 76f0b52..dfa76ac 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -370,6 +370,15 @@ public class IndexedQueryAnalyzer { return mForeignProperty; } + /** + * Returns true if local or foreign index is clustered. Scans of + * clustered indexes are generally faster. + */ + public boolean isIndexClustered() { + return (mLocalIndex != null && mLocalIndex.isClustered()) + || (mForeignIndex != null && mForeignIndex.isClustered()); + } + /** * Returns true if the given result uses the same index as this, and in * the same way. The only allowed differences are in the remainder diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java index d87740b..cc342c6 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -177,6 +177,10 @@ public class IndexedQueryExecutor extends AbstractQueryExecu filter = filter == null ? p : filter.and(p); } + if (filter == null) { + return Filter.getOpenFilter(getStorableType()); + } + return filter; } diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index 5933f6c..c64e4d4 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -19,6 +19,7 @@ package com.amazon.carbonado.qe; import java.util.ArrayList; +import java.util.Collection; import java.util.Collections; import java.util.LinkedHashMap; import java.util.HashSet; @@ -184,15 +185,28 @@ public class UnionQueryAnalyzer implements QueryExecutorFact // Keep looping until total ordering achieved. while (true) { - // For each ordering score, find the next free property. If - // property is in the super key increment a tally associated with - // property direction. Choose the property with the best tally and - // augment the orderings with it and create new sub-results. - // Remove the property from the super key and the key set. If any - // key is now fully covered, a total ordering has been achieved. + // For each ordering score, iterate over the entire unused ordering + // properties and select the next free property. If property is in + // the super key increment a tally associated with property + // direction. Choose the property with the best tally and augment + // the orderings with it and create new sub-results. Remove the + // property from the super key and the key set. If any key is now + // fully covered, a total ordering has been achieved. for (IndexedQueryAnalyzer.Result result : subResults) { OrderingScore score = result.getCompositeScore().getOrderingScore(); + + OrderingList unused = score.getUnusedOrdering(); + if (unused.size() > 0) { + for (OrderedProperty prop : unused) { + ChainedProperty chainedProp = prop.getChainedProperty(); + Tally tally = superKey.get(chainedProp); + if (tally != null) { + tally.increment(prop.getDirection()); + } + } + } + OrderingList free = score.getFreeOrdering(); if (free.size() > 0) { OrderedProperty prop = free.get(0); @@ -237,7 +251,9 @@ public class UnionQueryAnalyzer implements QueryExecutorFact /** * Returns a list of all primary and alternate keys, stripped of ordering. */ - private List>> getKeys() { + private List>> getKeys() + throws SupportException, RepositoryException + { StorableInfo info = StorableIntrospector.examine(mIndexAnalyzer.getStorableType()); List>> keys = new ArrayList>>(); @@ -247,6 +263,26 @@ public class UnionQueryAnalyzer implements QueryExecutorFact keys.add(stripOrdering(altKey.getProperties())); } + // Also fold in all unique indexes, just in case they weren't reported + // as actual keys. + Collection> indexes = + mRepoAccess.storageAccessFor(getStorableType()).getAllIndexes(); + + for (StorableIndex index : indexes) { + if (!index.isUnique()) { + continue; + } + + int propCount = index.getPropertyCount(); + Set> props = new HashSet>(propCount); + + for (int i=0; i implements QueryExecutorFact full = result; break; } + if (!result.getCompositeScore().getFilteringScore().hasAnyMatches()) { + if (full == null) { + // This index is used only for its ordering, and it will be + // tentatively selected as the "full scan". If a result is + // found doesn't use an index for anything, then it becomes + // the "full scan" index. + full = result; + } + } } if (full == null) { diff --git a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java index 740f26c..ef1711f 100644 --- a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java +++ b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java @@ -45,6 +45,7 @@ import com.amazon.carbonado.stored.Address; import com.amazon.carbonado.stored.Order; import com.amazon.carbonado.stored.Shipment; import com.amazon.carbonado.stored.Shipper; +import com.amazon.carbonado.stored.StorableTestBasic; import static com.amazon.carbonado.qe.TestIndexedQueryExecutor.Mock; @@ -294,6 +295,14 @@ public class TestIndexedQueryAnalyzer extends TestCase { indexes = new StorableIndex[] { makeIndex(mType, "shipperID") }; + } else if (StorableTestBasic.class.isAssignableFrom(mType)) { + indexes = new StorableIndex[] { + makeIndex(mType, "id").unique(true).clustered(true), + makeIndex(mType, "stringProp", "doubleProp").unique(true), + makeIndex(mType, "-stringProp", "-intProp", "~id").unique(true), + makeIndex(mType, "+intProp", "stringProp", "~id").unique(true), + makeIndex(mType, "-doubleProp", "+longProp", "~id").unique(true), + }; } else { indexes = new StorableIndex[0]; } diff --git a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java index 0278eab..3d99c84 100644 --- a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java +++ b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java @@ -39,6 +39,7 @@ import com.amazon.carbonado.stored.Address; import com.amazon.carbonado.stored.Order; import com.amazon.carbonado.stored.Shipment; import com.amazon.carbonado.stored.Shipper; +import com.amazon.carbonado.stored.StorableTestBasic; import static com.amazon.carbonado.qe.TestIndexedQueryExecutor.Mock; @@ -112,6 +113,7 @@ public class TestUnionQueryAnalyzer extends TestCase { "shipmentID = ? | orderID = ?"); filter = filter.bind(); UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(Shipment.class, "+shipmentID"), result.getTotalOrdering()); List.Result> subResults = result.getSubResults(); assertEquals(2, subResults.size()); @@ -143,6 +145,7 @@ public class TestUnionQueryAnalyzer extends TestCase { "shipmentID = ? | orderID > ?"); filter = filter.bind(); UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(Shipment.class, "+shipmentID"), result.getTotalOrdering()); List.Result> subResults = result.getSubResults(); assertEquals(2, subResults.size()); @@ -157,19 +160,14 @@ public class TestUnionQueryAnalyzer extends TestCase { assertEquals(null, res_0.getForeignProperty()); assertEquals(0, res_0.getRemainderOrdering().size()); - // Note: index that has proper ordering is preferred because "orderId > ?" - // filter does not specify a complete range. It is not expected to actually - // filter much, so we choose to avoid a large sort instead. assertTrue(res_1.handlesAnything()); - assertFalse(res_1.getCompositeScore().getFilteringScore().hasRangeStart()); + assertTrue(res_1.getCompositeScore().getFilteringScore().hasRangeStart()); assertFalse(res_1.getCompositeScore().getFilteringScore().hasRangeEnd()); - assertEquals(makeIndex(Shipment.class, "shipmentID"), res_1.getLocalIndex()); + assertEquals(makeIndex(Shipment.class, "orderID"), res_1.getLocalIndex()); assertEquals(null, res_1.getForeignIndex()); assertEquals(null, res_1.getForeignProperty()); - assertEquals(0, res_0.getRemainderOrdering().size()); - // Remainder filter exists because the "orderID" index was not chosen. - assertEquals(Filter.filterFor(Shipment.class, "orderID > ?").bind(), - res_1.getRemainderFilter()); + assertEquals(1, res_1.getRemainderOrdering().size()); + assertEquals("+shipmentID", res_1.getRemainderOrdering().get(0).toString()); } public void testSimpleUnion3() throws Exception { @@ -179,6 +177,7 @@ public class TestUnionQueryAnalyzer extends TestCase { "shipmentID = ? | orderID > ? & orderID <= ?"); filter = filter.bind(); UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(Shipment.class, "+shipmentID"), result.getTotalOrdering()); List.Result> subResults = result.getSubResults(); assertEquals(2, subResults.size()); @@ -222,6 +221,8 @@ public class TestUnionQueryAnalyzer extends TestCase { OrderingList orderings = makeOrdering(Shipment.class, "~shipmentID", "~orderID"); UnionQueryAnalyzer.Result result = uqa.analyze(filter, orderings); + assertEquals(OrderingList.get(Shipment.class, "+shipmentID", "+orderID"), + result.getTotalOrdering()); List.Result> subResults = result.getSubResults(); assertEquals(2, subResults.size()); @@ -341,20 +342,234 @@ public class TestUnionQueryAnalyzer extends TestCase { IndexedQueryAnalyzer.Result res_1 = subResults.get(1); assertTrue(res_0.handlesAnything()); - assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(makeIndex(Shipment.class, "orderID"), res_0.getLocalIndex()); assertEquals(null, res_0.getForeignIndex()); assertEquals(null, res_0.getForeignProperty()); - assertEquals(0, res_0.getRemainderOrdering().size()); - assertEquals(Filter.filterFor(Shipment.class, "shipmentNotes = ?").bind(), + assertEquals(1, res_0.getRemainderOrdering().size()); + assertEquals("+shipmentID", res_0.getRemainderOrdering().get(0).toString()); + assertEquals(Filter.filterFor(Shipment.class, "order.orderTotal > ?").bind(), res_0.getRemainderFilter()); assertTrue(res_1.handlesAnything()); - assertEquals(makeIndex(Shipment.class, "orderID"), res_1.getLocalIndex()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_1.getLocalIndex()); assertEquals(null, res_1.getForeignIndex()); assertEquals(null, res_1.getForeignProperty()); - assertEquals(1, res_1.getRemainderOrdering().size()); - assertEquals("+shipmentID", res_1.getRemainderOrdering().get(0).toString()); - assertEquals(Filter.filterFor(Shipment.class, "order.orderTotal > ?").bind(), + assertEquals(0, res_1.getRemainderOrdering().size()); + assertEquals(Filter.filterFor(Shipment.class, "shipmentNotes = ?").bind(), res_1.getRemainderFilter()); + + } + + public void testComplexUnionPlan() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(StorableTestBasic.class, + TestIndexedQueryAnalyzer.RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (StorableTestBasic.class, "doubleProp = ? | (stringProp = ? & intProp = ?) | id > ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(StorableTestBasic.class, "+id"), result.getTotalOrdering()); + + QueryExecutor exec = result.createExecutor(); + + assertEquals(filter, exec.getFilter()); + assertEquals(OrderingList.get(StorableTestBasic.class, "+id"), exec.getOrdering()); + + List.Result> subResults = result.getSubResults(); + + assertEquals(3, subResults.size()); + + StringBuffer buf = new StringBuffer(); + exec.printPlan(buf, 0, null); + String plan = buf.toString(); + + String expexted = + "union\n" + + " sort: [+id]\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[-doubleProp, +longProp, ~id], unique=true}\n" + + " ...identity filter: doubleProp = ?\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[-stringProp, -intProp, ~id], unique=true}\n" + + " ...identity filter: stringProp = ? & intProp = ?\n" + + " clustered index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+id], unique=true}\n" + + " ...range filter: id > ?\n"; + + // Test test will fail if the format of the plan changes. + assertEquals(expexted, plan); + } + + public void testComplexUnionPlan2() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(StorableTestBasic.class, + TestIndexedQueryAnalyzer.RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (StorableTestBasic.class, "doubleProp = ? | stringProp = ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(StorableTestBasic.class, "+doubleProp", "+stringProp"), + result.getTotalOrdering()); + + QueryExecutor exec = result.createExecutor(); + + assertEquals(filter, exec.getFilter()); + assertEquals(OrderingList.get(StorableTestBasic.class, "+doubleProp", "+stringProp"), + exec.getOrdering()); + + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + + StringBuffer buf = new StringBuffer(); + exec.printPlan(buf, 0, null); + String plan = buf.toString(); + + String expexted = + "union\n" + + " sort: [+stringProp]\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[-doubleProp, +longProp, ~id], unique=true}\n" + + " ...identity filter: doubleProp = ?\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?\n"; + + // Test test will fail if the format of the plan changes. + assertEquals(expexted, plan); + } + + public void testComplexUnionPlan3() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(StorableTestBasic.class, + TestIndexedQueryAnalyzer.RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (StorableTestBasic.class, "stringProp = ? | stringProp = ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + + boolean a = result.getTotalOrdering() == + OrderingList.get(StorableTestBasic.class, "+doubleProp", "+stringProp"); + boolean b = result.getTotalOrdering() == + OrderingList.get(StorableTestBasic.class, "+stringProp", "+doubleProp"); + + assertTrue(a || b); + + QueryExecutor exec = result.createExecutor(); + + assertEquals(filter, exec.getFilter()); + + a = exec.getOrdering() == + OrderingList.get(StorableTestBasic.class, "+doubleProp", "+stringProp"); + b = exec.getOrdering() == + OrderingList.get(StorableTestBasic.class, "+stringProp", "+doubleProp"); + + assertTrue(a || b); + + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + + StringBuffer buf = new StringBuffer(); + exec.printPlan(buf, 0, null); + String plan = buf.toString(); + + String expexted = + "union\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?[2]\n"; + + // Test test will fail if the format of the plan changes. + assertEquals(expexted, plan); + } + + public void testComplexUnionPlan4() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(StorableTestBasic.class, + TestIndexedQueryAnalyzer.RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (StorableTestBasic.class, "doubleProp = ? | stringProp = ? | id > ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(StorableTestBasic.class, "+doubleProp", "+id"), + result.getTotalOrdering()); + + QueryExecutor exec = result.createExecutor(); + + assertEquals(filter, exec.getFilter()); + assertEquals(OrderingList.get(StorableTestBasic.class, "+doubleProp", "+id"), + exec.getOrdering()); + + List.Result> subResults = result.getSubResults(); + + assertEquals(3, subResults.size()); + + StringBuffer buf = new StringBuffer(); + exec.printPlan(buf, 0, null); + String plan = buf.toString(); + + String expexted = + "union\n" + + " sort: [+id]\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[-doubleProp, +longProp, ~id], unique=true}\n" + + " ...identity filter: doubleProp = ?\n" + + " sort: [+doubleProp], [+id]\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?\n" + + " sort: [+doubleProp, +id]\n" + + " clustered index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+id], unique=true}\n" + + " ...range filter: id > ?\n"; + + // Test test will fail if the format of the plan changes. + assertEquals(expexted, plan); + } + + public void testComplexUnionPlan5() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(StorableTestBasic.class, + TestIndexedQueryAnalyzer.RepoAccess.INSTANCE); + Filter filter = Filter.filterFor + (StorableTestBasic.class, "stringProp = ? | stringProp = ? | id > ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + assertEquals(OrderingList.get(StorableTestBasic.class, "+stringProp", "+doubleProp"), + result.getTotalOrdering()); + + QueryExecutor exec = result.createExecutor(); + + assertEquals(filter, exec.getFilter()); + assertEquals(OrderingList.get(StorableTestBasic.class, "+stringProp", "+doubleProp"), + exec.getOrdering()); + + List.Result> subResults = result.getSubResults(); + + assertEquals(3, subResults.size()); + + StringBuffer buf = new StringBuffer(); + exec.printPlan(buf, 0, null); + String plan = buf.toString(); + + String expexted = + "union\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?\n" + + " index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+stringProp, +doubleProp], unique=true}\n" + + " ...identity filter: stringProp = ?[2]\n" + + " sort: [+stringProp, +doubleProp]\n" + + " clustered index scan: com.amazon.carbonado.stored.StorableTestBasic\n" + + " ...index: {properties=[+id], unique=true}\n" + + " ...range filter: id > ?\n"; + + // Test test will fail if the format of the plan changes. + assertEquals(expexted, plan); } } -- cgit v1.2.3