From b523f10dcac0a265edfd74ce78d83bf079ead8da Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Mon, 4 Sep 2006 06:01:57 +0000 Subject: More progress on union analysis. --- .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 12 ++- .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 108 ++++++++++++++++++--- 2 files changed, 105 insertions(+), 15 deletions(-) (limited to 'src/main/java/com/amazon/carbonado') diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 23ec0d1..76fb5f5 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -412,17 +412,23 @@ public class IndexedQueryAnalyzer { /** * Merges the remainder filter of this result with the given filter, * returning a new result. If handlesAnything return true, then it - * doesn't make sense to call this method. + * doesn't usually make sense to call this method. */ - public Result mergeRemainder(Filter filter) { + public Result mergeRemainderFilter(Filter filter) { Filter remainderFilter = getRemainderFilter(); if (remainderFilter == null) { remainderFilter = filter; } else if (filter != null) { remainderFilter = remainderFilter.or(filter); } + return setRemainderFilter(remainderFilter); + } - return new Result(this, remainderFilter, getRemainderOrderings()); + /** + * Returns a new result with the remainder filter replaced. + */ + public Result setRemainderFilter(Filter filter) { + return new Result(this, filter, getRemainderOrderings()); } private boolean equals(Object a, Object b) { diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index b07934c..2fd492e 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -20,7 +20,9 @@ package com.amazon.carbonado.qe; import java.util.ArrayList; import java.util.Collections; +import java.util.HashSet; import java.util.List; +import java.util.Set; import com.amazon.carbonado.Storable; @@ -30,8 +32,12 @@ import com.amazon.carbonado.filter.OrFilter; import com.amazon.carbonado.filter.PropertyFilter; import com.amazon.carbonado.filter.Visitor; +import com.amazon.carbonado.info.ChainedProperty; import com.amazon.carbonado.info.OrderedProperty; import com.amazon.carbonado.info.StorableIndex; +import com.amazon.carbonado.info.StorableInfo; +import com.amazon.carbonado.info.StorableIntrospector; +import com.amazon.carbonado.info.StorableKey; /** * Analyzes a query specification and determines how it can be executed as a @@ -68,30 +74,87 @@ public class UnionQueryAnalyzer { throw new IllegalArgumentException("Filter must be bound"); } - // Required for split to work. - filter = filter.disjunctiveNormalForm(); - List.Result> subResults = splitIntoSubResults(filter, orderings); - if (subResults.size() > 1) { + if (subResults.size() > 1 && !isTotalOrdering(orderings)) { // If more than one, then a total ordering is required. + // The approach is to choose an index, and then augment ordering + // properties arranged in accordance with the index. The index is + // chosen from the sub-result that has the worst filtering + // score. Why? The other sub-results are likely to filter and sort + // fewer records than worst one. Imposing a total ordering may + // require a post-sort on the high scoring sub-results which might + // not see many records. Put another way, the worst scoring + // sub-result is already the bottleneck, so avoid making it work + // any harder. + + // The properties to augment with are the contents of a primary or + // alternate key. Select the key which most closely matches the + // user's desired ordering. Default to primary key if none. + + // 1. Results guaranteed to produce one result already have a total ordering. + // FIXME } return new Result(subResults); } - private List> isTotalOrdering() { - // FIXME - return null; + private boolean isTotalOrdering(List> orderings) { + // First strip out directions, since they are not relevent here. + List> properties = new ArrayList>(orderings.size()); + for (OrderedProperty ordering : orderings) { + properties.add(ordering.getChainedProperty()); + } + + StorableInfo info = StorableIntrospector.examine(mIndexAnalyzer.getStorableType()); + + if (containsKey(properties, info.getPrimaryKey())) { + return true; + } + + for (StorableKey altKey : info.getAlternateKeys()) { + if (containsKey(properties, altKey)) { + return true; + } + } + + return false; + } + + private boolean containsKey(List> properties, StorableKey key) { + Set> orderedKeyProps = key.getProperties(); + + if (properties.size() < orderedKeyProps.size()) { + // Short-circuit. + return false; + } + + // Strip out directions, since they are not relevent here. + Set> keyProps = new HashSet>(orderedKeyProps.size()); + for (OrderedProperty ordering : orderedKeyProps) { + keyProps.add(ordering.getChainedProperty()); + } + + for (ChainedProperty property : properties) { + keyProps.remove(property); + if (keyProps.size() == 0) { + break; + } + } + + return keyProps.size() == 0; } private List.Result> splitIntoSubResults(Filter filter, List> orderings) { + // Required for split to work. + Filter dnfFilter = filter.disjunctiveNormalForm(); + Splitter splitter = new Splitter(orderings); - filter.accept(splitter, null); + dnfFilter.accept(splitter, null); List.Result> subResults = splitter.mSubResults; @@ -99,7 +162,7 @@ public class UnionQueryAnalyzer { // best option for the entire query and all sub-results merge into a // single sub-result. Any sub-results which filter anything and contain // a join property in the filter are exempt from the merge. This is - // because fewer joins are read then if a full scan is performed for + // because fewer joins are read than if a full scan is performed for // the entire query. The resulting union has both a full scan and an // index scan. @@ -126,15 +189,36 @@ public class UnionQueryAnalyzer { } boolean exempt = result.getCompositeScore().getFilteringScore().hasAnyMatches(); - // FIXME: check for joins if (exempt) { - subResults.add(result); + // Must also have a join in the filter to be exempt. + List> subFilters = PropertyFilterList.get(result.getFilter()); + + joinCheck: { + for (PropertyFilter subFilter : subFilters) { + if (subFilter.getChainedProperty().getChainCount() > 0) { + // A chain implies a join was followed, so result is exempt. + break joinCheck; + } + } + // No joins found, result is not exempt from merging into full scan. + exempt = false; + } + } + + if (exempt) { + mergedResults.add(result); } else { - full = full.mergeRemainder(result.getFilter()); + full = full.mergeRemainderFilter(result.getFilter()); } } + if (mergedResults.size() == 0) { + // Nothing was exempt. Rather than return a result with a dnf + // filter, return full scan with a simpler reduced filter. + full.setRemainderFilter(filter.reduce()); + } + mergedResults.add(full); return mergedResults; -- cgit v1.2.3