From 8f791a3e9e36fac4345ebb75ba1d9fe51b4b1b55 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Thu, 7 Sep 2006 01:12:04 +0000 Subject: Initial tests and fixes for union query analysis. --- .../com/amazon/carbonado/filter/AndFilter.java | 7 + .../amazon/carbonado/filter/BinaryOpFilter.java | 3 + .../com/amazon/carbonado/filter/ClosedFilter.java | 4 + .../java/com/amazon/carbonado/filter/Filter.java | 9 + .../com/amazon/carbonado/filter/OpenFilter.java | 4 + .../java/com/amazon/carbonado/filter/OrFilter.java | 7 + .../amazon/carbonado/filter/PropertyFilter.java | 8 +- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 10 + .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 10 +- .../carbonado/qe/TestIndexedQueryAnalyzer.java | 17 ++ .../carbonado/qe/TestUnionQueryAnalyzer.java | 277 +++++++++++++++++++++ 11 files changed, 350 insertions(+), 6 deletions(-) create mode 100644 src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java (limited to 'src') diff --git a/src/main/java/com/amazon/carbonado/filter/AndFilter.java b/src/main/java/com/amazon/carbonado/filter/AndFilter.java index 92c3937..a5aa61e 100644 --- a/src/main/java/com/amazon/carbonado/filter/AndFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/AndFilter.java @@ -53,6 +53,13 @@ public class AndFilter extends BinaryOpFilter { return visitor.visit(this, param); } + public Filter unbind() { + if (!isBound()) { + return this; + } + return mLeft.unbind().and(mRight.unbind()); + } + Filter buildDisjunctiveNormalForm() { Filter left = mLeft.reduce().dnf(); Filter right = mRight.reduce().dnf(); diff --git a/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java b/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java index c95f493..462acf4 100644 --- a/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java @@ -49,6 +49,9 @@ public abstract class BinaryOpFilter extends Filter { } mLeft = left; mRight = right; + if (left.isBound() && right.isBound()) { + markBound(); + } } public Filter getLeftFilter() { diff --git a/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java index 4584109..7895a3d 100644 --- a/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java @@ -66,6 +66,10 @@ public class ClosedFilter extends Filter { return true; } + public Filter unbind() { + return this; + } + void markBound() { } diff --git a/src/main/java/com/amazon/carbonado/filter/Filter.java b/src/main/java/com/amazon/carbonado/filter/Filter.java index 9d55a99..338b768 100644 --- a/src/main/java/com/amazon/carbonado/filter/Filter.java +++ b/src/main/java/com/amazon/carbonado/filter/Filter.java @@ -415,6 +415,15 @@ public abstract class Filter implements Appender { */ public abstract Filter bind(); + /** + * Undoes the effect of a bind operation. The returned filter might still + * report itself as bound if it doesn't make a distinction between these + * states. + * + * @return canonical Filter instance with unbound property filters + */ + public abstract Filter unbind(); + /** * Returns true if all property filters are known to be properly * bound. This is a side effect of calling {@link #bind}, {@link diff --git a/src/main/java/com/amazon/carbonado/filter/OpenFilter.java b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java index 407aed0..6f6e211 100644 --- a/src/main/java/com/amazon/carbonado/filter/OpenFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java @@ -62,6 +62,10 @@ public class OpenFilter extends Filter { return this; } + public Filter unbind() { + return this; + } + public boolean isBound() { return true; } diff --git a/src/main/java/com/amazon/carbonado/filter/OrFilter.java b/src/main/java/com/amazon/carbonado/filter/OrFilter.java index 027ea21..1e7bf72 100644 --- a/src/main/java/com/amazon/carbonado/filter/OrFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/OrFilter.java @@ -53,6 +53,13 @@ public class OrFilter extends BinaryOpFilter { return visitor.visit(this, param); } + public Filter unbind() { + if (!isBound()) { + return this; + } + return mLeft.unbind().or(mRight.unbind()); + } + Filter buildDisjunctiveNormalForm() { return mLeft.dnf().or(mRight.dnf()).reduce(); } diff --git a/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java b/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java index 8fe03d6..824d1d1 100644 --- a/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java +++ b/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java @@ -160,6 +160,10 @@ public class PropertyFilter extends Filter { return mBindID == 0 ? getCanonical(this, 1) : this; } + public Filter unbind() { + return mBindID == 0 ? this : getCanonical(this, 0); + } + public boolean isBound() { return mBindID != 0; } @@ -428,11 +432,9 @@ public class PropertyFilter extends Filter { app.append(String.valueOf(mConstant)); } else { app.append('?'); - /* Uncomment for testing - if (mBindID != 0) { + if (mBindID > 1) { app.append('[').append(String.valueOf(mBindID)).append(']'); } - */ } } diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 76fb5f5..d0bd63f 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -431,6 +431,16 @@ public class IndexedQueryAnalyzer { return new Result(this, filter, getRemainderOrderings()); } + public String toString() { + return "IndexedQueryAnalyzer.Result {score=" + + getCompositeScore() + ", localIndex=" + + getLocalIndex() + ", foreignIndex=" + + getForeignIndex() + ", foreignProperty=" + + getForeignProperty() + ", remainderFilter=" + + getRemainderFilter() + ", remainderOrderings=" + + getRemainderOrderings() + '}'; + } + private boolean equals(Object a, Object b) { return a == null ? (b == null) : (a.equals(b)); } diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index 9ed94fd..5648d21 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -77,9 +77,13 @@ public class UnionQueryAnalyzer { throw new IllegalArgumentException("Filter must be bound"); } + if (orderings == null) { + orderings = Collections.emptyList(); + } + List.Result> subResults = splitIntoSubResults(filter, orderings); - if (subResults.size() < 1) { + if (subResults.size() <= 1) { // Total ordering not required. return new Result(subResults); } @@ -112,7 +116,7 @@ public class UnionQueryAnalyzer { // since one simple change might alter the query plan. subResults = splitIntoSubResults(filter, orderings); - if (subResults.size() < 1) { + if (subResults.size() <= 1) { // Total ordering no longer required. return new Result(subResults); } @@ -183,7 +187,7 @@ public class UnionQueryAnalyzer { orderings.add(OrderedProperty.get(bestProperty, best.getBestDirection())); subResults = splitIntoSubResults(filter, orderings); - if (subResults.size() < 1) { + if (subResults.size() <= 1) { // Total ordering no longer required. break; } diff --git a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java index 166d6e6..dcc07ee 100644 --- a/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java +++ b/src/test/java/com/amazon/carbonado/qe/TestIndexedQueryAnalyzer.java @@ -21,6 +21,7 @@ package com.amazon.carbonado.qe; import java.util.Arrays; import java.util.Collection; import java.util.Collections; +import java.util.List; import junit.framework.TestCase; import junit.framework.TestSuite; @@ -32,6 +33,7 @@ import com.amazon.carbonado.info.StorableIndex; import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.FilterValues; +import com.amazon.carbonado.filter.PropertyFilter; import com.amazon.carbonado.repo.toy.ToyRepository; @@ -114,6 +116,21 @@ public class TestIndexedQueryAnalyzer extends TestCase { assertEquals(makeIndex(Shipment.class, "orderID"), result.getLocalIndex()); assertEquals(null, result.getForeignIndex()); assertEquals(null, result.getForeignProperty()); + + filter = Filter.filterFor(Shipment.class, "orderID > ?"); + filter = filter.bind(); + result = iqa.analyze(filter, null); + + assertTrue(result.handlesAnything()); + assertTrue(result.getCompositeScore().getFilteringScore().hasRangeStart()); + assertFalse(result.getCompositeScore().getFilteringScore().hasRangeEnd()); + List> rangeFilters = + result.getCompositeScore().getFilteringScore().getRangeStartFilters(); + assertEquals(1, rangeFilters.size()); + assertEquals(filter, rangeFilters.get(0)); + assertEquals(makeIndex(Shipment.class, "orderID"), result.getLocalIndex()); + assertEquals(null, result.getForeignIndex()); + assertEquals(null, result.getForeignProperty()); } public void testSimpleJoin() throws Exception { diff --git a/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java new file mode 100644 index 0000000..cb5477f --- /dev/null +++ b/src/test/java/com/amazon/carbonado/qe/TestUnionQueryAnalyzer.java @@ -0,0 +1,277 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.List; + +import junit.framework.TestCase; +import junit.framework.TestSuite; + +import com.amazon.carbonado.Repository; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; +import com.amazon.carbonado.filter.PropertyFilter; + +import com.amazon.carbonado.repo.toy.ToyRepository; + +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 static com.amazon.carbonado.qe.TestIndexedQueryExecutor.Mock; + +/** + * + * + * @author Brian S O'Neill + */ +public class TestUnionQueryAnalyzer extends TestCase { + public static void main(String[] args) { + junit.textui.TestRunner.run(suite()); + } + + public static TestSuite suite() { + return new TestSuite(TestUnionQueryAnalyzer.class); + } + + static StorableIndex makeIndex(Class type, String... props) { + return TestOrderingScore.makeIndex(type, props); + } + + static List> makeOrderings(Class type, + String... props) + { + return TestOrderingScore.makeOrderings(type, props); + } + + public TestUnionQueryAnalyzer(String name) { + super(name); + } + + public void testSingleSubResult() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, "shipmentID = ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + List.Result> subResults = result.getSubResults(); + + assertEquals(1, subResults.size()); + } + + public void testSingleSubResultUnspecifiedDirection() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, "shipmentID > ?"); + filter = filter.bind(); + List> orderings = + makeOrderings(Shipment.class, "~shipmentID", "~orderID"); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, orderings); + List.Result> subResults = result.getSubResults(); + + assertEquals(1, subResults.size()); + List> handled = + subResults.get(0).getCompositeScore().getOrderingScore().getHandledOrderings(); + assertEquals(1, handled.size()); + assertEquals("+shipmentID", handled.get(0).toString()); + } + + public void testSimpleUnion() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, + "shipmentID = ? | orderID = ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + IndexedQueryAnalyzer.Result res_0 = subResults.get(0); + IndexedQueryAnalyzer.Result res_1 = subResults.get(1); + + assertTrue(res_0.handlesAnything()); + assertEquals(Filter.filterFor(Shipment.class, "shipmentID = ?").bind(), + res_0.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(null, res_0.getForeignIndex()); + assertEquals(null, res_0.getForeignProperty()); + assertEquals(0, res_0.getRemainderOrderings().size()); + + assertTrue(res_1.handlesAnything()); + assertEquals(Filter.filterFor(Shipment.class, "orderID = ?").bind(), + res_1.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "orderID"), res_1.getLocalIndex()); + assertEquals(null, res_1.getForeignIndex()); + assertEquals(null, res_1.getForeignProperty()); + assertEquals(1, res_1.getRemainderOrderings().size()); + assertEquals("+shipmentID", res_1.getRemainderOrderings().get(0).toString()); + } + + public void testSimpleUnion2() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, + "shipmentID = ? | orderID > ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + IndexedQueryAnalyzer.Result res_0 = subResults.get(0); + IndexedQueryAnalyzer.Result res_1 = subResults.get(1); + + assertTrue(res_0.handlesAnything()); + assertEquals(Filter.filterFor(Shipment.class, "shipmentID = ?").bind(), + res_0.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(null, res_0.getForeignIndex()); + assertEquals(null, res_0.getForeignProperty()); + assertEquals(0, res_0.getRemainderOrderings().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()); + assertFalse(res_1.getCompositeScore().getFilteringScore().hasRangeEnd()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_1.getLocalIndex()); + assertEquals(null, res_1.getForeignIndex()); + assertEquals(null, res_1.getForeignProperty()); + assertEquals(0, res_0.getRemainderOrderings().size()); + // Remainder filter exists because the "orderID" index was not chosen. + assertEquals(Filter.filterFor(Shipment.class, "orderID > ?").bind(), + res_1.getRemainderFilter()); + } + + public void testSimpleUnion3() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, + "shipmentID = ? | orderID > ? & orderID <= ?"); + filter = filter.bind(); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, null); + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + IndexedQueryAnalyzer.Result res_0 = subResults.get(0); + IndexedQueryAnalyzer.Result res_1 = subResults.get(1); + + assertTrue(res_0.handlesAnything()); + assertEquals(Filter.filterFor(Shipment.class, "shipmentID = ?").bind(), + res_0.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(null, res_0.getForeignIndex()); + assertEquals(null, res_0.getForeignProperty()); + assertEquals(0, res_0.getRemainderOrderings().size()); + + // Note: index that has proper filtering is preferred because + // "orderId > ? & orderID <= ?" filter specifies a complete range. + // We'll have to do a sort, but it isn't expected to be over that many records. + assertTrue(res_1.handlesAnything()); + assertTrue(res_1.getCompositeScore().getFilteringScore().hasRangeStart()); + assertTrue(res_1.getCompositeScore().getFilteringScore().hasRangeEnd()); + List> rangeFilters = + res_1.getCompositeScore().getFilteringScore().getRangeStartFilters(); + assertEquals(1, rangeFilters.size()); + assertEquals(Filter.filterFor(Shipment.class, "orderID > ?").bind(), rangeFilters.get(0)); + rangeFilters = res_1.getCompositeScore().getFilteringScore().getRangeEndFilters(); + assertEquals(1, rangeFilters.size()); + assertEquals(Filter.filterFor(Shipment.class, "orderID <= ?").bind(), rangeFilters.get(0)); + assertEquals(makeIndex(Shipment.class, "orderID"), res_1.getLocalIndex()); + assertEquals(null, res_1.getForeignIndex()); + assertEquals(null, res_1.getForeignProperty()); + // Sort operation required because the "shipmentID" index was not chosen. + assertEquals("+shipmentID", res_1.getRemainderOrderings().get(0).toString()); + } + + public void testSimpleUnionUnspecifiedDirection() throws Exception { + UnionQueryAnalyzer uqa = + new UnionQueryAnalyzer(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor(Shipment.class, + "shipmentID > ? | orderID = ?"); + filter = filter.bind(); + List> orderings = + makeOrderings(Shipment.class, "~shipmentID", "~orderID"); + UnionQueryAnalyzer.Result result = uqa.analyze(filter, orderings); + List.Result> subResults = result.getSubResults(); + + assertEquals(2, subResults.size()); + IndexedQueryAnalyzer.Result res_0 = subResults.get(0); + IndexedQueryAnalyzer.Result res_1 = subResults.get(1); + + List> handled = + res_0.getCompositeScore().getOrderingScore().getHandledOrderings(); + assertEquals(1, handled.size()); + assertEquals("+shipmentID", handled.get(0).toString()); + + handled = res_1.getCompositeScore().getOrderingScore().getHandledOrderings(); + assertEquals(0, handled.size()); + + assertTrue(res_0.handlesAnything()); + assertTrue(res_0.getCompositeScore().getFilteringScore().hasRangeStart()); + assertFalse(res_0.getCompositeScore().getFilteringScore().hasRangeEnd()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(null, res_0.getForeignIndex()); + assertEquals(null, res_0.getForeignProperty()); + assertEquals(1, res_0.getRemainderOrderings().size()); + assertEquals("+orderID", res_0.getRemainderOrderings().get(0).toString()); + + assertTrue(res_1.handlesAnything()); + assertEquals(Filter.filterFor(Shipment.class, "orderID = ?").bind(), + res_1.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "orderID"), res_1.getLocalIndex()); + assertEquals(null, res_1.getForeignIndex()); + assertEquals(null, res_1.getForeignProperty()); + assertEquals(1, res_1.getRemainderOrderings().size()); + assertEquals("+shipmentID", res_1.getRemainderOrderings().get(0).toString()); + } + + public void testSimpleMerge() 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(Shipment.class, TestIndexedQueryAnalyzer.IxProvider.INSTANCE); + Filter filter = Filter.filterFor + (Shipment.class, + "shipmentID = ? & (shipmentID = ? | orderID = ?)"); + 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(Shipment.class, "shipmentID = ?").bind(), + res_0.getCompositeScore().getFilteringScore().getIdentityFilter()); + assertEquals(makeIndex(Shipment.class, "shipmentID"), res_0.getLocalIndex()); + assertEquals(null, res_0.getForeignIndex()); + assertEquals(null, res_0.getForeignProperty()); + assertEquals(0, res_0.getRemainderOrderings().size()); + assertEquals(Filter.filterFor(Shipment.class, "shipmentID = ? | orderID = ?"), + res_0.getRemainderFilter().unbind()); + } +} -- cgit v1.2.3