From 5c74c692c4394d4686e04bacff56c5794f458e6b Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Fri, 8 Sep 2006 22:47:00 +0000 Subject: Use OrderingList class everywhere. --- .../com/amazon/carbonado/qe/CompositeScore.java | 18 +-- .../java/com/amazon/carbonado/qe/EmptyQuery.java | 22 ++-- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 48 +++---- .../amazon/carbonado/qe/JoinedQueryExecutor.java | 4 - .../java/com/amazon/carbonado/qe/OrderingList.java | 104 ++++++++++----- .../com/amazon/carbonado/qe/OrderingScore.java | 142 ++++++++++----------- .../amazon/carbonado/qe/SortedQueryExecutor.java | 9 -- .../com/amazon/carbonado/qe/StandardQuery.java | 32 ++--- .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 61 ++++----- 9 files changed, 218 insertions(+), 222 deletions(-) (limited to 'src/main') diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index 2a85a32..c8e9490 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -45,13 +45,13 @@ public class CompositeScore { * * @param index index to evaluate * @param filter optional filter which cannot contain any logical 'or' operations. - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering * @throws IllegalArgumentException if index is null or filter is not supported */ public static CompositeScore evaluate (StorableIndex index, Filter filter, - List> orderings) + OrderingList ordering) { if (index == null) { throw new IllegalArgumentException("Index required"); @@ -61,7 +61,7 @@ public class CompositeScore { index.isUnique(), index.isClustered(), filter, - orderings); + ordering); } /** @@ -72,7 +72,7 @@ public class CompositeScore { * @param unique true if index is unique * @param clustered true if index is clustered * @param filter optional filter which cannot contain any logical 'or' operations. - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering * @throws IllegalArgumentException if index is null or filter is not supported */ public static CompositeScore evaluate @@ -80,13 +80,13 @@ public class CompositeScore { boolean unique, boolean clustered, Filter filter, - List> orderings) + OrderingList ordering) { FilteringScore filteringScore = FilteringScore .evaluate(indexProperties, unique, clustered, filter); OrderingScore orderingScore = OrderingScore - .evaluate(indexProperties, unique, clustered, filter, orderings); + .evaluate(indexProperties, unique, clustered, filter, ordering); return new CompositeScore(filteringScore, orderingScore); } @@ -133,7 +133,7 @@ public class CompositeScore { */ public boolean canMergeRemainder(CompositeScore other) { return getFilteringScore().canMergeRemainderFilter(other.getFilteringScore()) - && getOrderingScore().canMergeRemainderOrderings(other.getOrderingScore()); + && getOrderingScore().canMergeRemainderOrdering(other.getOrderingScore()); } /** @@ -149,8 +149,8 @@ public class CompositeScore { * Merges the remainder orderings of this score with the one given. Call * canMergeRemainder first to verify if the merge makes any sense. */ - public List> mergeRemainderOrderings(CompositeScore other) { - return getOrderingScore().mergeRemainderOrderings(other.getOrderingScore()); + public OrderingList mergeRemainderOrdering(CompositeScore other) { + return getOrderingScore().mergeRemainderOrdering(other.getOrderingScore()); } public String toString() { diff --git a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java index 16a8f26..5da585a 100644 --- a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java +++ b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java @@ -44,21 +44,21 @@ public final class EmptyQuery extends AbstractQuery { private final Storage mRootStorage; // Properties that this query is ordered by. - private final OrderingList mOrderings; + private final OrderingList mOrdering; /** * @param rootStorage required root storage object, used by 'or' and 'not' methods - * @param orderings optional order-by properties + * @param ordering optional order-by properties */ - public EmptyQuery(Storage rootStorage, OrderingList orderings) { + public EmptyQuery(Storage rootStorage, OrderingList ordering) { if (rootStorage == null) { throw new IllegalArgumentException(); } mRootStorage = rootStorage; - if (orderings == null) { - orderings = OrderingList.emptyList(); + if (ordering == null) { + ordering = OrderingList.emptyList(); } - mOrderings = orderings; + mOrdering = ordering; } /** @@ -194,8 +194,8 @@ public final class EmptyQuery extends AbstractQuery { */ public Query not() throws FetchException { Query query = mRootStorage.query(); - if (mOrderings.size() > 0) { - query = query.orderBy(mOrderings.asStringArray()); + if (mOrdering.size() > 0) { + query = query.orderBy(mOrdering.asStringArray()); } return query; } @@ -255,13 +255,13 @@ public final class EmptyQuery extends AbstractQuery { app.append(", filter="); getFilter().appendTo(app); - if (mOrderings != null && mOrderings.size() > 0) { + if (mOrdering != null && mOrdering.size() > 0) { app.append(", orderBy=["); - for (int i=0; i 0) { app.append(", "); } - app.append(mOrderings.get(i).toString()); + app.append(mOrdering.get(i).toString()); } app.append(']'); } diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index d0bd63f..594fcc1 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -76,10 +76,10 @@ public class IndexedQueryAnalyzer { /** * @param filter optional filter which which must be {@link Filter#isBound * bound} and cannot contain any logical 'or' operations. - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering * @throws IllegalArgumentException if filter is not supported */ - public Result analyze(Filter filter, List> orderings) { + public Result analyze(Filter filter, OrderingList ordering) { if (!filter.isBound()) { // Strictly speaking, this is not required, but it detects the // mistake of not properly calling initialFilterValues. @@ -96,7 +96,7 @@ public class IndexedQueryAnalyzer { if (localIndexes != null) { for (StorableIndex index : localIndexes) { CompositeScore candidateScore = - CompositeScore.evaluate(index, filter, orderings); + CompositeScore.evaluate(index, filter, ordering); if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { bestScore = candidateScore; @@ -128,7 +128,7 @@ public class IndexedQueryAnalyzer { index.isUnique(), index.isClustered(), filter, - orderings); + ordering); if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { bestScore = candidateScore; @@ -249,7 +249,7 @@ public class IndexedQueryAnalyzer { private final ChainedProperty mForeignProperty; private final Filter mRemainderFilter; - private final List> mRemainderOrderings; + private final OrderingList mRemainderOrdering; Result(Filter filter, CompositeScore score, @@ -263,13 +263,13 @@ public class IndexedQueryAnalyzer { mForeignIndex = foreignIndex; mForeignProperty = foreignProperty; mRemainderFilter = score.getFilteringScore().getRemainderFilter(); - mRemainderOrderings = score.getOrderingScore().getRemainderOrderings(); + mRemainderOrdering = score.getOrderingScore().getRemainderOrdering(); } // Called by mergeRemainder. private Result(Result result, Filter remainderFilter, - List> remainderOrderings) + OrderingList remainderOrdering) { mFilter = result.mFilter == null ? remainderFilter : (remainderFilter == null ? result.mFilter : result.mFilter.or(remainderFilter)); @@ -279,7 +279,7 @@ public class IndexedQueryAnalyzer { mForeignIndex = result.mForeignIndex; mForeignProperty = result.mForeignProperty; mRemainderFilter = remainderFilter; - mRemainderOrderings = remainderOrderings; + mRemainderOrdering = remainderOrdering; } /** @@ -302,24 +302,8 @@ public class IndexedQueryAnalyzer { /** * Returns combined handled and remainder orderings for this result. */ - public List> getOrderings() { - List> handled = mScore.getOrderingScore().getHandledOrderings(); - List> remainder = getRemainderOrderings(); - - if (handled.size() == 0) { - return remainder; - } - if (remainder.size() == 0) { - return handled; - } - - List> combined = - new ArrayList>(handled.size() + remainder.size()); - - combined.addAll(handled); - combined.addAll(remainder); - - return combined; + public OrderingList getOrdering() { + return mScore.getOrderingScore().getHandledOrdering().concat(getRemainderOrdering()); } /** @@ -342,8 +326,8 @@ public class IndexedQueryAnalyzer { /** * Remainder orderings which override that in composite score. */ - public List> getRemainderOrderings() { - return mRemainderOrderings; + public OrderingList getRemainderOrdering() { + return mRemainderOrdering; } /** @@ -406,7 +390,7 @@ public class IndexedQueryAnalyzer { return new Result (this, getCompositeScore().mergeRemainderFilter(other.getCompositeScore()), - getCompositeScore().mergeRemainderOrderings(other.getCompositeScore())); + getCompositeScore().mergeRemainderOrdering(other.getCompositeScore())); } /** @@ -428,7 +412,7 @@ public class IndexedQueryAnalyzer { * Returns a new result with the remainder filter replaced. */ public Result setRemainderFilter(Filter filter) { - return new Result(this, filter, getRemainderOrderings()); + return new Result(this, filter, getRemainderOrdering()); } public String toString() { @@ -437,8 +421,8 @@ public class IndexedQueryAnalyzer { + getLocalIndex() + ", foreignIndex=" + getForeignIndex() + ", foreignProperty=" + getForeignProperty() + ", remainderFilter=" - + getRemainderFilter() + ", remainderOrderings=" - + getRemainderOrderings() + '}'; + + getRemainderFilter() + ", remainderOrdering=" + + getRemainderOrdering() + '}'; } private boolean equals(Object a, Object b) { diff --git a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java index 9557b31..ebcb60a 100644 --- a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java @@ -20,10 +20,6 @@ package com.amazon.carbonado.qe; import java.io.IOException; -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; - import com.amazon.carbonado.Cursor; import com.amazon.carbonado.FetchException; import com.amazon.carbonado.Repository; diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingList.java b/src/main/java/com/amazon/carbonado/qe/OrderingList.java index 0cb1fc4..b32f430 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingList.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingList.java @@ -59,10 +59,11 @@ public class OrderingList extends AbstractList OrderingList get(Class type, String property) { - if (property == null) { - return EMPTY_LIST; + OrderingList list = emptyList(); + if (property != null) { + list = list.concat(type, property); } - return getListNode(type).nextNode(type, property); + return list; } /** @@ -71,37 +72,29 @@ public class OrderingList extends AbstractList OrderingList get(Class type, String... orderings) { - if (orderings == null || orderings.length == 0) { - return EMPTY_LIST; - } - - OrderingList node = getListNode(type); - for (String property : orderings) { - node = node.nextNode(type, property); + OrderingList list = emptyList(); + if (orderings != null && orderings.length > 0) { + for (String property : orderings) { + list = list.concat(type, property); + } } - - return node; + return list; } /** * Returns a canonical instance composed of the given orderings. */ public static OrderingList get(OrderedProperty... orderings) { - if (orderings == null || orderings.length == 0) { - return EMPTY_LIST; - } - - Class type = orderings[0].getChainedProperty().getPrimeProperty().getEnclosingType(); - - OrderingList node = getListNode(type); - for (OrderedProperty property : orderings) { - node = node.nextNode(property); + OrderingList list = emptyList(); + if (orderings != null && orderings.length > 0) { + for (OrderedProperty property : orderings) { + list = list.concat(property); + } } - - return node; + return list; } - private static OrderingList getListNode(Class type) { + private static OrderingList getListHead(Class type) { OrderingList node; synchronized (cCache) { node = (OrderingList) cCache.get(type); @@ -145,6 +138,31 @@ public class OrderingList extends AbstractList concat(Class type, String property) { + OrderingList newList = this; + if (newList == EMPTY_LIST) { + // Cannot concat from singleton EMPTY_LIST. + newList = getListHead(type); + } + return newList.nextNode(type, property); + } + + /** + * Returns a list which concatenates this one with the given property. + */ + public OrderingList concat(OrderedProperty property) { + OrderingList newList = this; + if (newList == EMPTY_LIST) { + // Cannot concat from singleton EMPTY_LIST. + newList = getListHead + (property.getChainedProperty().getPrimeProperty().getEnclosingType()); + } + return newList.nextNode(property); + } + /** * Returns a list which concatenates this one with the other one. */ @@ -152,22 +170,48 @@ public class OrderingList extends AbstractList node = this; - + OrderingList newList = this; if (other.size() > 0) { for (OrderedProperty property : other) { - node = node.nextNode(property); + newList = newList.concat(property); } } + return newList; + } - return node; + /** + * Returns this list with all orderings in reverse. + */ + public OrderingList reverseDirections() { + if (size() == 0) { + return this; + } + OrderingList reversedList = emptyList(); + for (int i=0; i replace(int index, OrderedProperty property) { + int size = size(); + if (index < 0 || index >= size) { + throw new IndexOutOfBoundsException(); + } + OrderingList newList = emptyList(); + for (int i=0; i[] asArray() { + OrderedProperty[] asArray() { if (mOrderings == null) { OrderedProperty[] orderings = new OrderedProperty[mSize]; OrderingList node = this; diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java index 82d44a7..97ac4e8 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java @@ -18,9 +18,7 @@ package com.amazon.carbonado.qe; -import java.util.ArrayList; import java.util.Comparator; -import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Map; @@ -68,13 +66,13 @@ public class OrderingScore { * * @param index index to evaluate * @param filter optional filter which cannot contain any logical 'or' operations. - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering * @throws IllegalArgumentException if index is null or filter is not supported */ public static OrderingScore evaluate (StorableIndex index, Filter filter, - List> orderings) + OrderingList ordering) { if (index == null) { throw new IllegalArgumentException("Index required"); @@ -84,7 +82,7 @@ public class OrderingScore { index.isUnique(), index.isClustered(), filter, - orderings); + ordering); } /** @@ -95,7 +93,7 @@ public class OrderingScore { * @param unique true if index is unique * @param clustered true if index is clustered * @param filter optional filter which cannot contain any logical 'or' operations. - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering * @throws IllegalArgumentException if index is null or filter is not supported */ public static OrderingScore evaluate @@ -103,7 +101,7 @@ public class OrderingScore { boolean unique, boolean clustered, Filter filter, - List> orderings) + OrderingList ordering) { if (indexProperties == null) { throw new IllegalArgumentException("Index properties required"); @@ -112,8 +110,8 @@ public class OrderingScore { // Get filter list early to detect errors. List> filterList = PropertyFilterList.get(filter); - if (orderings == null) { - orderings = Collections.emptyList(); + if (ordering == null) { + ordering = OrderingList.emptyList(); } // Ordering properties which match identity filters don't affect order @@ -127,15 +125,18 @@ public class OrderingScore { } } - // Build up list of unused properties that were filtered out. - List> unusedProperties = new ArrayList>(); + OrderingList handledOrdering = OrderingList.emptyList(); + OrderingList remainderOrdering = OrderingList.emptyList(); + OrderingList freeOrdering = OrderingList.emptyList(); + OrderingList unusedOrdering = OrderingList.emptyList(); + // Build up list of unused properties that were filtered out. for (int i=0; i indexProp = indexProperties[i]; ChainedProperty indexChained = indexProp.getChainedProperty(); if (identityPropSet.contains(indexChained)) { - unusedProperties.add(indexProp.direction(UNSPECIFIED)); + unusedOrdering = unusedOrdering.concat(indexProp.direction(UNSPECIFIED)); } } @@ -153,16 +154,13 @@ public class OrderingScore { return new OrderingScore(clustered, indexProperties.length, - null, // no handled properties - null, // no remainder properties - false, // no need to reverse order - null, // no free properties - unusedProperties); + handledOrdering, // no handled properties + remainderOrdering, // no remainder properties + false, // no need to reverse order + freeOrdering, // no free properties + unusedOrdering); } - List> handledProperties = new ArrayList>(); - List> remainderProperties = new ArrayList>(); - Boolean shouldReverseOrder = null; Set> seen = new HashSet>(); @@ -170,8 +168,8 @@ public class OrderingScore { boolean gap = false; int indexPos = 0; calcScore: - for (int i=0; i property = orderings.get(i); + for (int i=0; i property = ordering.get(i); ChainedProperty chained = property.getChainedProperty(); if (seen.contains(chained)) { @@ -211,16 +209,14 @@ public class OrderingScore { // originally unspecified. They might need to be // reversed now. if (shouldReverseOrder) { - for (int hpi = 0; hpi < handledProperties.size(); hpi++) { - handledProperties.set(hpi, handledProperties.get(hpi).reverse()); - } + handledOrdering = handledOrdering.reverseDirections(); } } else if (indexDir != property.getDirection()) { // Direction mismatch, so cannot be handled. break indexPosMatch; } - handledProperties.add(property); + handledOrdering = handledOrdering.concat(property); indexPos++; continue calcScore; @@ -239,13 +235,11 @@ public class OrderingScore { } // Property not handled and not an identity filter. - remainderProperties.add(property); + remainderOrdering = remainderOrdering.concat(property); 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(); @@ -263,7 +257,7 @@ public class OrderingScore { freeProp = freeProp.direction(freePropDir.reverse()); } } - freeProperties.add(freeProp); + freeOrdering = freeOrdering.concat(freeProp); } indexPos++; @@ -275,11 +269,11 @@ public class OrderingScore { return new OrderingScore(clustered, indexProperties.length, - handledProperties, - remainderProperties, + handledOrdering, + remainderOrdering, shouldReverseOrder, - freeProperties, - unusedProperties); + freeOrdering, + unusedOrdering); } /** @@ -295,8 +289,8 @@ public class OrderingScore { private final boolean mIndexClustered; private final int mIndexPropertyCount; - private final List> mHandledOrderings; - private final List> mRemainderOrderings; + private final OrderingList mHandledOrdering; + private final OrderingList mRemainderOrdering; private final boolean mShouldReverseOrder; @@ -304,24 +298,24 @@ public class OrderingScore { // 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 final OrderingList mFreeOrdering; + private final OrderingList mUnusedOrdering; private OrderingScore(boolean indexClustered, int indexPropertyCount, - List> handledOrderings, - List> remainderOrderings, + OrderingList handledOrdering, + OrderingList remainderOrdering, boolean shouldReverseOrder, - List> freeOrderings, - List> unusedOrderings) + OrderingList freeOrdering, + OrderingList unusedOrdering) { mIndexClustered = indexClustered; mIndexPropertyCount = indexPropertyCount; - mHandledOrderings = FilteringScore.prepareList(handledOrderings); - mRemainderOrderings = FilteringScore.prepareList(remainderOrderings); + mHandledOrdering = handledOrdering; + mRemainderOrdering = remainderOrdering; mShouldReverseOrder = shouldReverseOrder; - mFreeOrderings = FilteringScore.prepareList(freeOrderings); - mUnusedOrderings = FilteringScore.prepareList(unusedOrderings); + mFreeOrdering = freeOrdering; + mUnusedOrdering = unusedOrdering; } /** @@ -344,7 +338,7 @@ public class OrderingScore { * supports. The number of orderings is reduced to eliminate redundancies. */ public int getHandledCount() { - return mHandledOrderings.size(); + return mHandledOrdering.size(); } /** @@ -355,8 +349,8 @@ public class OrderingScore { * * @return handled orderings, never null */ - public List> getHandledOrderings() { - return mHandledOrderings; + public OrderingList getHandledOrdering() { + return mHandledOrdering; } /** @@ -366,7 +360,7 @@ public class OrderingScore { * evaluated index must perform a sort. */ public int getRemainderCount() { - return mRemainderOrderings.size(); + return mRemainderOrdering.size(); } /** @@ -375,8 +369,8 @@ public class OrderingScore { * * @return remainder orderings, never null */ - public List> getRemainderOrderings() { - return mRemainderOrderings; + public OrderingList getRemainderOrdering() { + return mRemainderOrdering; } /** @@ -395,8 +389,8 @@ public class OrderingScore { * * @return free orderings, never null */ - public List> getFreeOrderings() { - return mFreeOrderings; + public OrderingList getFreeOrdering() { + return mFreeOrdering; } /** @@ -406,8 +400,8 @@ public class OrderingScore { * * @return unused orderings, never null */ - public List> getUnusedOrderings() { - return mUnusedOrderings; + public OrderingList getUnusedOrdering() { + return mUnusedOrdering; } /** @@ -415,7 +409,7 @@ public class OrderingScore { * one. The only allowed differences are in the count of remainder * orderings. */ - public boolean canMergeRemainderOrderings(OrderingScore other) { + public boolean canMergeRemainderOrdering(OrderingScore other) { if (this == other || (getHandledCount() == 0 && other.getHandledCount() == 0)) { return true; } @@ -423,15 +417,15 @@ public class OrderingScore { if (isIndexClustered() == other.isIndexClustered() && getIndexPropertyCount() == other.getIndexPropertyCount() && shouldReverseOrder() == other.shouldReverseOrder() - && getHandledOrderings().equals(other.getHandledOrderings())) + && getHandledOrdering().equals(other.getHandledOrdering())) { // The remainder orderings cannot conflict. - List> thisRemainderOrderings = getRemainderOrderings(); - List> otherRemainderOrderings = other.getRemainderOrderings(); + OrderingList thisRemainderOrdering = getRemainderOrdering(); + OrderingList otherRemainderOrdering = other.getRemainderOrdering(); - int size = Math.min(thisRemainderOrderings.size(), otherRemainderOrderings.size()); + int size = Math.min(thisRemainderOrdering.size(), otherRemainderOrdering.size()); for (int i=0; i { /** * Merges the remainder orderings of this score with the one given. Call - * canMergeRemainderOrderings first to verify if the merge makes any sense. + * canMergeRemainderOrdering first to verify if the merge makes any sense. */ - public List> mergeRemainderOrderings(OrderingScore other) { - List> thisRemainderOrderings = getRemainderOrderings(); + public OrderingList mergeRemainderOrdering(OrderingScore other) { + OrderingList thisRemainderOrdering = getRemainderOrdering(); if (this == other) { - return thisRemainderOrderings; + return thisRemainderOrdering; } - List> otherRemainderOrderings = other.getRemainderOrderings(); + OrderingList otherRemainderOrdering = other.getRemainderOrdering(); // Choose the longer list. - if (thisRemainderOrderings.size() == 0) { - return otherRemainderOrderings; + if (thisRemainderOrdering.size() == 0) { + return otherRemainderOrdering; } else { - if (otherRemainderOrderings.size() == 0) { - return thisRemainderOrderings; - } else if (thisRemainderOrderings.size() >= otherRemainderOrderings.size()) { - return thisRemainderOrderings; + if (otherRemainderOrdering.size() == 0) { + return thisRemainderOrdering; + } else if (thisRemainderOrdering.size() >= otherRemainderOrdering.size()) { + return thisRemainderOrdering; } else { - return otherRemainderOrderings; + return otherRemainderOrdering; } } } diff --git a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java index b5fdcb9..05474ed 100644 --- a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java @@ -20,10 +20,7 @@ package com.amazon.carbonado.qe; import java.io.IOException; -import java.util.ArrayList; -import java.util.Collections; import java.util.Comparator; -import java.util.List; import com.amazon.carbonado.Cursor; import com.amazon.carbonado.FetchException; @@ -107,12 +104,6 @@ public abstract class SortedQueryExecutor extends AbstractQu } public OrderingList getOrdering() { - if (mHandledOrdering.size() == 0) { - return mRemainderOrdering; - } - if (mRemainderOrdering.size() == 0) { - return mHandledOrdering; - } return mHandledOrdering.concat(mRemainderOrdering); } diff --git a/src/main/java/com/amazon/carbonado/qe/StandardQuery.java b/src/main/java/com/amazon/carbonado/qe/StandardQuery.java index 8c423e6..a347b66 100644 --- a/src/main/java/com/amazon/carbonado/qe/StandardQuery.java +++ b/src/main/java/com/amazon/carbonado/qe/StandardQuery.java @@ -54,7 +54,7 @@ public abstract class StandardQuery extends AbstractQuery // Values for this query, which may be null. private final FilterValues mValues; // Properties that this query is ordered by. - private final OrderingList mOrderings; + private final OrderingList mOrdering; private volatile QueryExecutor mExecutor; @@ -67,14 +67,14 @@ public abstract class StandardQuery extends AbstractQuery /** * @param values optional values object, defaults to open filter if null - * @param orderings optional order-by properties + * @param ordering optional order-by properties */ - protected StandardQuery(FilterValues values, OrderingList orderings) { + protected StandardQuery(FilterValues values, OrderingList ordering) { mValues = values; - if (orderings == null) { - orderings = OrderingList.emptyList(); + if (ordering == null) { + ordering = OrderingList.emptyList(); } - mOrderings = orderings; + mOrdering = ordering; } public Class getStorableType() { @@ -149,7 +149,7 @@ public abstract class StandardQuery extends AbstractQuery newQuery = getStorage().query(values.getFilter().and(filter)); newQuery = newQuery.withValues(values.getValues()); } - return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray()); + return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray()); } public Query or(Filter filter) throws FetchException { @@ -159,17 +159,17 @@ public abstract class StandardQuery extends AbstractQuery } Query newQuery = getStorage().query(values.getFilter().or(filter)); newQuery = newQuery.withValues(values.getValues()); - return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray()); + return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray()); } public Query not() throws FetchException { FilterValues values = mValues; if (values == null) { - return new EmptyQuery(getStorage(), mOrderings); + return new EmptyQuery(getStorage(), mOrdering); } Query newQuery = getStorage().query(values.getFilter().not()); newQuery = newQuery.withValues(values.getSuppliedValues()); - return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray()); + return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray()); } public Query orderBy(String property) throws FetchException { @@ -186,7 +186,7 @@ public abstract class StandardQuery extends AbstractQuery public Cursor fetchAfter(S start) throws FetchException { OrderingList orderings; - if (start == null || (orderings = mOrderings).size() == 0) { + if (start == null || (orderings = mOrdering).size() == 0) { return fetch(); } @@ -328,13 +328,13 @@ public abstract class StandardQuery extends AbstractQuery app.append('"'); } - if (mOrderings != null && mOrderings.size() > 0) { + if (mOrdering != null && mOrdering.size() > 0) { app.append(", orderBy=["); - for (int i=0; i 0) { app.append(", "); } - app.append(mOrderings.get(i).toString()); + app.append(mOrdering.get(i).toString()); } app.append(']'); } @@ -384,13 +384,13 @@ public abstract class StandardQuery extends AbstractQuery OrderingList orderings); private StandardQuery newInstance(FilterValues values) { - return newInstance(values, mOrderings); + return newInstance(values, mOrdering); } private QueryExecutor executor() { QueryExecutor executor = mExecutor; if (executor == null) { - mExecutor = executor = getExecutor(mValues, mOrderings); + mExecutor = executor = getExecutor(mValues, mOrdering); } return executor; } diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index 5648d21..039aea4 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -68,53 +68,46 @@ public class UnionQueryAnalyzer { /** * @param filter optional filter which must be {@link Filter#isBound bound} - * @param orderings optional properties which define desired ordering + * @param ordering optional properties which define desired ordering */ - public Result analyze(Filter filter, List> orderings) { + public Result analyze(Filter filter, OrderingList ordering) { if (!filter.isBound()) { // Strictly speaking, this is not required, but it detects the // mistake of not properly calling initialFilterValues. throw new IllegalArgumentException("Filter must be bound"); } - if (orderings == null) { - orderings = Collections.emptyList(); + if (ordering == null) { + ordering = OrderingList.emptyList(); } - List.Result> subResults = splitIntoSubResults(filter, orderings); + List.Result> subResults = splitIntoSubResults(filter, ordering); if (subResults.size() <= 1) { // Total ordering not required. return new Result(subResults); } - boolean canMutateOrderings = false; - // If any orderings have an unspecified direction, switch to ASCENDING // or DESCENDING, depending on which is more popular. Then build new // sub-results. - for (int pos = 0; pos < orderings.size(); pos++) { - OrderedProperty ordering = orderings.get(pos); - if (ordering.getDirection() != Direction.UNSPECIFIED) { + for (int pos = 0; pos < ordering.size(); pos++) { + OrderedProperty op = ordering.get(pos); + if (op.getDirection() != Direction.UNSPECIFIED) { continue; } // Find out which direction is most popular for this property. - Tally tally = new Tally(ordering.getChainedProperty()); + Tally tally = new Tally(op.getChainedProperty()); for (IndexedQueryAnalyzer.Result result : subResults) { - tally.increment(findHandledDirection(result, ordering)); - } - - if (!canMutateOrderings) { - orderings = new ArrayList>(orderings); - canMutateOrderings = true; + tally.increment(findHandledDirection(result, op)); } - orderings.set(pos, ordering.direction(tally.getBestDirection())); + ordering = ordering.replace(pos, op.direction(tally.getBestDirection())); // Re-calc with specified direction. Only do one property at a time // since one simple change might alter the query plan. - subResults = splitIntoSubResults(filter, orderings); + subResults = splitIntoSubResults(filter, ordering); if (subResults.size() <= 1) { // Total ordering no longer required. @@ -128,8 +121,8 @@ public class UnionQueryAnalyzer { List>> keys = getKeys(); // Check if current ordering is total. - for (OrderedProperty ordering : orderings) { - ChainedProperty property = ordering.getChainedProperty(); + for (OrderedProperty op : ordering) { + ChainedProperty property = op.getChainedProperty(); if (pruneKeys(keys, property)) { // Found a key which is fully covered, indicating total ordering. return new Result(subResults); @@ -152,12 +145,6 @@ public class UnionQueryAnalyzer { } } - // Prepare to augment orderings to ensure a total ordering. - if (!canMutateOrderings) { - orderings = new ArrayList>(orderings); - canMutateOrderings = true; - } - // Keep looping until total ordering achieved. while (true) { // For each ordering score, find the next free property. If @@ -169,7 +156,7 @@ public class UnionQueryAnalyzer { for (IndexedQueryAnalyzer.Result result : subResults) { OrderingScore score = result.getCompositeScore().getOrderingScore(); - List> free = score.getFreeOrderings(); + OrderingList free = score.getFreeOrdering(); if (free.size() > 0) { OrderedProperty prop = free.get(0); ChainedProperty chainedProp = prop.getChainedProperty(); @@ -184,8 +171,8 @@ public class UnionQueryAnalyzer { ChainedProperty bestProperty = best.getProperty(); // Now augment the orderings and create new sub-results. - orderings.add(OrderedProperty.get(bestProperty, best.getBestDirection())); - subResults = splitIntoSubResults(filter, orderings); + ordering = ordering.concat(OrderedProperty.get(bestProperty, best.getBestDirection())); + subResults = splitIntoSubResults(filter, ordering); if (subResults.size() <= 1) { // Total ordering no longer required. @@ -267,7 +254,7 @@ public class UnionQueryAnalyzer { { ChainedProperty chained = unspecified.getChainedProperty(); OrderingScore score = result.getCompositeScore().getOrderingScore(); - List> handled = score.getHandledOrderings(); + OrderingList handled = score.getHandledOrdering(); for (OrderedProperty property : handled) { if (chained.equals(property)) { return property.getDirection(); @@ -277,12 +264,12 @@ public class UnionQueryAnalyzer { } private List.Result> - splitIntoSubResults(Filter filter, List> orderings) + splitIntoSubResults(Filter filter, OrderingList ordering) { // Required for split to work. Filter dnfFilter = filter.disjunctiveNormalForm(); - Splitter splitter = new Splitter(orderings); + Splitter splitter = new Splitter(ordering); dnfFilter.accept(splitter, null); List.Result> subResults = splitter.mSubResults; @@ -451,12 +438,12 @@ public class UnionQueryAnalyzer { * only contain 'and' operations. */ private class Splitter extends Visitor { - private final List> mOrderings; + private final OrderingList mOrdering; final List.Result> mSubResults; - Splitter(List> orderings) { - mOrderings = orderings; + Splitter(OrderingList ordering) { + mOrdering = ordering; mSubResults = new ArrayList.Result>(); } @@ -493,7 +480,7 @@ public class UnionQueryAnalyzer { private void subAnalyze(Filter subFilter) { IndexedQueryAnalyzer.Result subResult = - mIndexAnalyzer.analyze(subFilter, mOrderings); + mIndexAnalyzer.analyze(subFilter, mOrdering); // Rather than blindly add to mSubResults, try to merge with // another result. This in turn reduces the number of cursors -- cgit v1.2.3