From 84a22c3b1003a29344859b8af286e37bbe4c7b21 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Tue, 5 Sep 2006 01:31:18 +0000 Subject: Added support to get free and unused orderings. --- .../com/amazon/carbonado/qe/OrderingScore.java | 95 ++++++++++++++++++++-- .../com/amazon/carbonado/qe/TestOrderingScore.java | 84 +++++++++++++++++++ 2 files changed, 170 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java index ce85cb6..0730b4f 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java @@ -112,8 +112,8 @@ public class OrderingScore { // Get filter list early to detect errors. List> filterList = PropertyFilterList.get(filter); - if (orderings == null || orderings.size() == 0) { - return new OrderingScore(clustered, indexProperties.length, null, null, false); + if (orderings == null) { + orderings = Collections.emptyList(); } // Ordering properties which match identity filters don't affect order @@ -127,13 +127,25 @@ public class OrderingScore { } } + // Build up list of unused properties that were filtered out. + List> unusedProperties = new ArrayList>(); + + for (int i=0; i indexProp = indexProperties[i]; + ChainedProperty indexChained = indexProp.getChainedProperty(); + + if (identityPropSet.contains(indexChained)) { + unusedProperties.add(indexProp.direction(UNSPECIFIED)); + } + } + // If index is unique and every property is matched by an identity // filter, then there won't be any handled or remainder properties. uniquelyCheck: if (unique) { for (int i=0; i indexProp = indexProperties[i].getChainedProperty(); - if (!identityPropSet.contains(indexProp)) { + ChainedProperty indexChained = indexProperties[i].getChainedProperty(); + if (!identityPropSet.contains(indexChained)) { // Missed a property, so ordering is still relevent. break uniquelyCheck; } @@ -143,7 +155,9 @@ public class OrderingScore { indexProperties.length, null, // no handled properties null, // no remainder properties - false); // no need to reverse order + false, // no need to reverse order + null, // no free properties + unusedProperties); } List> handledProperties = new ArrayList>(); @@ -153,6 +167,7 @@ public class OrderingScore { Set> seen = new HashSet>(); + boolean gap = false; int indexPos = 0; calcScore: for (int i=0; i { } indexPosMatch: - while (indexPos < indexProperties.length) { + while (!gap && indexPos < indexProperties.length) { OrderedProperty indexProp = indexProperties[indexPos]; ChainedProperty indexChained = indexProp.getChainedProperty(); @@ -225,7 +240,33 @@ public class OrderingScore { // Property not handled and not an identity filter. remainderProperties.add(property); - indexPos = Integer.MAX_VALUE; + gap = true; + } + + // Walk through all remaining index properties and list them as free. + List> freeProperties = new ArrayList>(); + + while (indexPos < indexProperties.length) { + OrderedProperty freeProp = indexProperties[indexPos]; + ChainedProperty freeChained = freeProp.getChainedProperty(); + + // Don't list as free if already listed as unused. + if (!identityPropSet.contains(freeChained)) { + if (shouldReverseOrder == null) { + freeProp = freeProp.direction(UNSPECIFIED); + } else { + Direction freePropDir = freePropDir = freeProp.getDirection(); + if (freePropDir == UNSPECIFIED) { + freePropDir = ASCENDING; + } + if (shouldReverseOrder) { + freeProp = freeProp.direction(freePropDir.reverse()); + } + } + freeProperties.add(freeProp); + } + + indexPos++; } if (shouldReverseOrder == null) { @@ -236,7 +277,9 @@ public class OrderingScore { indexProperties.length, handledProperties, remainderProperties, - shouldReverseOrder); + shouldReverseOrder, + freeProperties, + unusedProperties); } /** @@ -257,17 +300,28 @@ public class OrderingScore { private final boolean mShouldReverseOrder; + // Free and unused orderings are not relevant for index selection, but they + // are useful for determining a total ordering that does not adversely + // affect a query plan. Combining handled, free, and unused ordering lists + // produces all the properties of the evaluated index. + private final List> mFreeOrderings; + private final List> mUnusedOrderings; + private OrderingScore(boolean indexClustered, int indexPropertyCount, List> handledOrderings, List> remainderOrderings, - boolean shouldReverseOrder) + boolean shouldReverseOrder, + List> freeOrderings, + List> unusedOrderings) { mIndexClustered = indexClustered; mIndexPropertyCount = indexPropertyCount; mHandledOrderings = FilteringScore.prepareList(handledOrderings); mRemainderOrderings = FilteringScore.prepareList(remainderOrderings); mShouldReverseOrder = shouldReverseOrder; + mFreeOrderings = FilteringScore.prepareList(freeOrderings); + mUnusedOrderings = FilteringScore.prepareList(unusedOrderings); } /** @@ -333,6 +387,29 @@ public class OrderingScore { return mShouldReverseOrder; } + /** + * Returns potential ordering properties that the evaluated index can + * handle, if arranged to immediately follow the handled orderings. The + * direction of any free orderings may be UNSPECIFIED, which indicates that + * specific order is not relevent. + * + * @return free orderings, never null + */ + public List> getFreeOrderings() { + return mFreeOrderings; + } + + /** + * Returns unused ordering properties of the evaluated index because they + * were filtered out. The direction of each unused ordering is UNSPECIFIED + * because specific order is not relevent. + * + * @return unused orderings, never null + */ + public List> getUnusedOrderings() { + return mUnusedOrderings; + } + /** * Returns true if the given score uses an index exactly the same as this * one. The only allowed differences are in the count of remainder diff --git a/src/test/java/com/amazon/carbonado/qe/TestOrderingScore.java b/src/test/java/com/amazon/carbonado/qe/TestOrderingScore.java index 83b2364..02f7808 100644 --- a/src/test/java/com/amazon/carbonado/qe/TestOrderingScore.java +++ b/src/test/java/com/amazon/carbonado/qe/TestOrderingScore.java @@ -596,4 +596,88 @@ public class TestOrderingScore extends TestCase { assertEquals("-intProp", score.getHandledOrderings().get(1).toString()); assertEquals("~longProp", score.getRemainderOrderings().get(0).toString()); } + + public void testFreeOrderings() throws Exception { + final StorableIndex ix; + List> ops; + OrderingScore score; + Filter filter = null; + + ix = makeIndex(StorableTestBasic.class, "id", "intProp", "doubleProp"); + ops = makeOrderings(StorableTestBasic.class, "~id"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(1, score.getHandledCount()); + assertEquals(0, score.getRemainderCount()); + assertEquals(false, score.shouldReverseOrder()); + assertEquals(2, score.getFreeOrderings().size()); + assertEquals("~intProp", score.getFreeOrderings().get(0).toString()); + assertEquals("~doubleProp", score.getFreeOrderings().get(1).toString()); + assertEquals(0, score.getUnusedOrderings().size()); + + ops = makeOrderings(StorableTestBasic.class, "~id", "-intProp"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(2, score.getHandledCount()); + assertEquals(0, score.getRemainderCount()); + assertEquals(true, score.shouldReverseOrder()); + assertEquals(1, score.getFreeOrderings().size()); + assertEquals("-doubleProp", score.getFreeOrderings().get(0).toString()); + assertEquals(0, score.getUnusedOrderings().size()); + + ops = makeOrderings(StorableTestBasic.class, "~id", "-intProp", "+doubleProp"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(2, score.getHandledCount()); + assertEquals(1, score.getRemainderCount()); + assertEquals("+doubleProp", score.getRemainderOrderings().get(0).toString()); + assertEquals(true, score.shouldReverseOrder()); + assertEquals(1, score.getFreeOrderings().size()); + assertEquals("-doubleProp", score.getFreeOrderings().get(0).toString()); + assertEquals(0, score.getUnusedOrderings().size()); + } + + public void testFreeAndUnusedOrderings() throws Exception { + final StorableIndex ix; + List> ops; + OrderingScore score; + Filter filter; + + ix = makeIndex(StorableTestBasic.class, "stringProp", "id", "intProp", "doubleProp"); + ops = makeOrderings(StorableTestBasic.class, "~id"); + filter = Filter.filterFor(StorableTestBasic.class, "stringProp = ?"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(1, score.getHandledCount()); + assertEquals(0, score.getRemainderCount()); + assertEquals(false, score.shouldReverseOrder()); + assertEquals(2, score.getFreeOrderings().size()); + assertEquals("~intProp", score.getFreeOrderings().get(0).toString()); + assertEquals("~doubleProp", score.getFreeOrderings().get(1).toString()); + assertEquals(1, score.getUnusedOrderings().size()); + assertEquals("~stringProp", score.getUnusedOrderings().get(0).toString()); + + ops = makeOrderings(StorableTestBasic.class, "~id", "-intProp"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(2, score.getHandledCount()); + assertEquals(0, score.getRemainderCount()); + assertEquals(true, score.shouldReverseOrder()); + assertEquals(1, score.getFreeOrderings().size()); + assertEquals("-doubleProp", score.getFreeOrderings().get(0).toString()); + assertEquals(1, score.getUnusedOrderings().size()); + assertEquals("~stringProp", score.getUnusedOrderings().get(0).toString()); + + ops = makeOrderings(StorableTestBasic.class, "~id", "-intProp", "+doubleProp"); + + score = OrderingScore.evaluate(ix, filter, ops); + assertEquals(2, score.getHandledCount()); + assertEquals(1, score.getRemainderCount()); + assertEquals("+doubleProp", score.getRemainderOrderings().get(0).toString()); + assertEquals(true, score.shouldReverseOrder()); + assertEquals(1, score.getFreeOrderings().size()); + assertEquals("-doubleProp", score.getFreeOrderings().get(0).toString()); + assertEquals(1, score.getUnusedOrderings().size()); + assertEquals("~stringProp", score.getUnusedOrderings().get(0).toString()); + } } -- cgit v1.2.3