diff options
11 files changed, 437 insertions, 279 deletions
diff --git a/RELEASE-NOTES.txt b/RELEASE-NOTES.txt index 4deef67..08cf3d8 100644 --- a/RELEASE-NOTES.txt +++ b/RELEASE-NOTES.txt @@ -22,6 +22,7 @@ Carbonado change history - FilteredCursor ensures that filter being used is bound.
- BDBRepository detects if changes are made to primary key and throws exception.
- Added support for derived properies.
+- Enhanced query engine to optimize for covering indexes.
1.1-BETA11 to 1.1 (release)
-------------------------------
diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index e031fe2..8194dbb 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -162,6 +162,28 @@ public class CompositeScore<S extends Storable> { return getOrderingScore().mergeRemainderOrdering(other.getOrderingScore());
}
+ /**
+ * Returns a new CompositeScore with the filtering remainder replaced and
+ * covering matches recalculated. Other matches are not recalculated.
+ *
+ * @since 1.2
+ */
+ public CompositeScore<S> withRemainderFilter(Filter<S> filter) {
+ return new CompositeScore<S>(mFilteringScore.withRemainderFilter(filter),
+ mOrderingScore);
+ }
+
+ /**
+ * Returns a new CompositeScore with the ordering remainder
+ * replaced. Handled count is not recalculated.
+ *
+ * @since 1.2
+ */
+ public CompositeScore<S> withRemainderOrdering(OrderingList<S> ordering) {
+ return new CompositeScore<S>(mFilteringScore,
+ mOrderingScore.withRemainderOrdering(ordering));
+ }
+
public String toString() {
return "CompositeScore {" + getFilteringScore() + ", " + getOrderingScore() + '}';
}
diff --git a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java index d9969c5..31d9dd3 100644 --- a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java +++ b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java @@ -73,6 +73,14 @@ public final class EmptyQuery<S extends Storable> extends AbstractQuery<S> { this(factory, OrderingList.get(factory.getStorableType(), orderings));
}
+ /**
+ * Used only by test suite. Query throws NullPointerException when invoked.
+ */
+ EmptyQuery() {
+ mFactory = null;
+ mOrdering = OrderingList.emptyList();
+ }
+
public Class<S> getStorableType() {
return mFactory.getStorableType();
}
diff --git a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java index 2661f69..7722873 100644 --- a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java +++ b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java @@ -27,9 +27,12 @@ import java.util.List; import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.filter.AndFilter;
import com.amazon.carbonado.filter.Filter;
+import com.amazon.carbonado.filter.OrFilter;
import com.amazon.carbonado.filter.PropertyFilter;
import com.amazon.carbonado.filter.RelOp;
+import com.amazon.carbonado.filter.Visitor;
import com.amazon.carbonado.info.ChainedProperty;
import com.amazon.carbonado.info.Direction;
@@ -206,38 +209,15 @@ public class FilteringScore<S extends Storable> { indexProperties[indexPropPos].getDirection() == Direction.DESCENDING;
}
- List<PropertyFilter<S>> extraMatchFilters = null;
-
- boolean checkForExtraMatches = !filterList.isEmpty()
- && (identityFilters.size() > 0
- || rangeStartFilters.size() > 0
- || rangeEndFilters.size() > 0);
-
- if (checkForExtraMatches) {
- // Any remainder property which is provided by the index is an extra match.
- for (PropertyFilter<S> subFilter : filterList) {
- ChainedProperty<S> filterProp = subFilter.getChainedProperty();
- for (OrderedProperty<S> indexProp : indexProperties) {
- if (indexProp.getChainedProperty().equals(filterProp)) {
- if (extraMatchFilters == null) {
- extraMatchFilters = new ArrayList<PropertyFilter<S>>();
- }
- extraMatchFilters.add(subFilter);
- }
- }
- }
- }
-
- return new FilteringScore<S>(clustered,
+ return new FilteringScore<S>(indexProperties,
+ clustered,
unique,
- indexProperties.length,
identityFilters,
rangeStartFilters,
rangeEndFilters,
arrangementScore,
preferenceScore,
filterList,
- extraMatchFilters,
shouldReverseRange);
}
@@ -285,9 +265,37 @@ public class FilteringScore<S extends Storable> { return 0;
}
+ /**
+ * Splits the filter from its conjunctive normal form. And'ng the filters
+ * together produces the original filter.
+ */
+ static <S extends Storable> List<Filter<S>> split(Filter<S> filter) {
+ if (filter == null) {
+ return null;
+ }
+
+ filter = filter.conjunctiveNormalForm();
+
+ final List<Filter<S>> list = new ArrayList<Filter<S>>();
+
+ filter.accept(new Visitor<S, Object, Object>() {
+ public Object visit(OrFilter<S> filter, Object param) {
+ list.add(filter);
+ return null;
+ }
+
+ public Object visit(PropertyFilter<S> filter, Object param) {
+ list.add(filter);
+ return null;
+ }
+ }, null);
+
+ return list;
+ }
+
+ private final OrderedProperty<S>[] mIndexProperties;
private final boolean mIndexClustered;
private final boolean mIndexUnique;
- private final int mIndexPropertyCount;
private final List<PropertyFilter<S>> mIdentityFilters;
@@ -297,39 +305,57 @@ public class FilteringScore<S extends Storable> { private final int mArrangementScore;
private final BigInteger mPreferenceScore;
- private final List<PropertyFilter<S>> mRemainderFilters;
- private final List<PropertyFilter<S>> mExtraMatchFilters;
+ private final List<? extends Filter<S>> mRemainderFilters;
+ private final List<? extends Filter<S>> mCoveringFilters;
private final boolean mShouldReverseRange;
private transient Filter<S> mIdentityFilter;
private transient Filter<S> mRemainderFilter;
- private transient Filter<S> mExtraMatchFilter;
- private transient Filter<S> mExtraMatchRemainderFilter;
+ private transient Filter<S> mCoveringFilter;
+ private transient Filter<S> mCoveringRemainderFilter;
- private FilteringScore(boolean indexClustered,
+ private FilteringScore(OrderedProperty<S>[] indexProperties,
+ boolean indexClustered,
boolean indexUnique,
- int indexPropertyCount,
List<PropertyFilter<S>> identityFilters,
List<PropertyFilter<S>> rangeStartFilters,
List<PropertyFilter<S>> rangeEndFilters,
int arrangementScore,
BigInteger preferenceScore,
- List<PropertyFilter<S>> remainderFilters,
- List<PropertyFilter<S>> extraMatchFilters,
+ List<? extends PropertyFilter<S>> remainderFilters,
boolean shouldReverseRange)
{
+ mIndexProperties = indexProperties;
mIndexClustered = indexClustered;
mIndexUnique = indexUnique;
- mIndexPropertyCount = indexPropertyCount;
mIdentityFilters = prepareList(identityFilters);
mRangeStartFilters = prepareList(rangeStartFilters);
mRangeEndFilters = prepareList(rangeEndFilters);
mArrangementScore = arrangementScore;
mPreferenceScore = preferenceScore;
mRemainderFilters = prepareList(remainderFilters);
- mExtraMatchFilters = prepareList(extraMatchFilters);
mShouldReverseRange = shouldReverseRange;
+
+ mCoveringFilters = findCoveringMatches();
+ }
+
+ private FilteringScore(FilteringScore<S> score, Filter<S> remainderFilter) {
+ mIndexProperties = score.mIndexProperties;
+ mIndexClustered = score.mIndexClustered;
+ mIndexUnique = score.mIndexUnique;
+ mIdentityFilters = score.mIdentityFilters;
+ mRangeStartFilters = score.mRangeStartFilters;
+ mRangeEndFilters = score.mRangeEndFilters;
+ mArrangementScore = score.mArrangementScore;
+ mPreferenceScore = score.mPreferenceScore;
+ mRemainderFilters = prepareList(split(remainderFilter));
+ mShouldReverseRange = score.mShouldReverseRange;
+
+ mCoveringFilters = findCoveringMatches();
+
+ mIdentityFilter = score.mIdentityFilter;
+ mRemainderFilter = remainderFilter;
}
/**
@@ -351,7 +377,7 @@ public class FilteringScore<S extends Storable> { * Returns the amount of properties in the evaluated index.
*/
public int getIndexPropertyCount() {
- return mIndexPropertyCount;
+ return mIndexProperties.length;
}
/**
@@ -531,7 +557,7 @@ public class FilteringScore<S extends Storable> { /**
* Returns the filters not supported by the evaluated index.
*/
- public List<PropertyFilter<S>> getRemainderFilters() {
+ public List<? extends Filter<S>> getRemainderFilters() {
return mRemainderFilters;
}
@@ -547,54 +573,54 @@ public class FilteringScore<S extends Storable> { }
/**
- * Returns number of extra property filters which are supported by the
+ * Returns number of covering property filters which are supported by the
* evaluated index. This count is no more than the remainder count. If
- * hasAnyMatches returns false, then the extra match count is zero.
+ * hasAnyMatches returns false, then the covering count is zero.
*
* @since 1.2
*/
- public int getExtraMatchCount() {
- return mExtraMatchFilters.size();
+ public int getCoveringCount() {
+ return mCoveringFilters.size();
}
/**
- * Returns the extra filters which are supported by the evaluated index,
+ * Returns the covering filters which are supported by the evaluated index,
* which is a subset of the remainder filters.
*
* @since 1.2
*/
- public List<PropertyFilter<S>> getExtraMatchFilters() {
- return mExtraMatchFilters;
+ public List<? extends Filter<S>> getCoveringFilters() {
+ return mCoveringFilters;
}
/**
- * Returns the composite extra match filter supported by the evaluated
- * index, or null if no extra match.
+ * Returns the composite covering filter supported by the evaluated index,
+ * or null if the covering count is zero.
*
* @since 1.2
*/
- public Filter<S> getExtraMatchFilter() {
- if (mExtraMatchFilter == null) {
- mExtraMatchFilter = buildCompositeFilter(getExtraMatchFilters());
+ public Filter<S> getCoveringFilter() {
+ if (mCoveringFilter == null) {
+ mCoveringFilter = buildCompositeFilter(getCoveringFilters());
}
- return mExtraMatchFilter;
+ return mCoveringFilter;
}
/**
- * Returns the composite remainder filter without including the extra match
+ * Returns the composite remainder filter without including the covering
* filter. Returns null if no remainder.
*
* @since 1.2
*/
- public Filter<S> getExtraMatchRemainderFilter() {
- if (mExtraMatchRemainderFilter == null) {
- List<PropertyFilter<S>> remainderFilters = mRemainderFilters;
- List<PropertyFilter<S>> extraMatchFilters = mExtraMatchFilters;
- if (extraMatchFilters.size() < remainderFilters.size()) {
+ public Filter<S> getCoveringRemainderFilter() {
+ if (mCoveringRemainderFilter == null) {
+ List<? extends Filter<S>> remainderFilters = mRemainderFilters;
+ List<? extends Filter<S>> coveringFilters = mCoveringFilters;
+ if (coveringFilters.size() < remainderFilters.size()) {
Filter<S> composite = null;
for (int i=0; i<remainderFilters.size(); i++) {
Filter<S> subFilter = remainderFilters.get(i);
- if (!extraMatchFilters.contains(subFilter)) {
+ if (!coveringFilters.contains(subFilter)) {
if (composite == null) {
composite = subFilter;
} else {
@@ -602,10 +628,10 @@ public class FilteringScore<S extends Storable> { }
}
}
- mExtraMatchRemainderFilter = composite;
+ mCoveringRemainderFilter = composite;
}
}
- return mExtraMatchRemainderFilter;
+ return mCoveringRemainderFilter;
}
/**
@@ -674,12 +700,22 @@ public class FilteringScore<S extends Storable> { }
}
+ /**
+ * Returns a new FilteringScore with the remainder replaced and covering
+ * matches recalculated. Other matches are not recalculated.
+ *
+ * @since 1.2
+ */
+ public FilteringScore<S> withRemainderFilter(Filter<S> filter) {
+ return new FilteringScore<S>(this, filter);
+ }
+
public String toString() {
return "FilteringScore {identityCount=" + getIdentityCount() +
", hasRangeStart=" + hasRangeStart() +
", hasRangeEnd=" + hasRangeEnd() +
", remainderCount=" + getRemainderCount() +
- ", extraMatchCount=" + getExtraMatchCount() +
+ ", coveringCount=" + getCoveringCount() +
'}';
}
@@ -703,7 +739,7 @@ public class FilteringScore<S extends Storable> { return reduced == null ? filters : reduced;
}
- private Filter<S> buildCompositeFilter(List<PropertyFilter<S>> filterList) {
+ private Filter<S> buildCompositeFilter(List<? extends Filter<S>> filterList) {
if (filterList.size() == 0) {
return null;
}
@@ -714,6 +750,56 @@ public class FilteringScore<S extends Storable> { return composite;
}
+ /**
+ * Finds covering matches from the remainder.
+ */
+ private List<Filter<S>> findCoveringMatches() {
+ List<Filter<S>> coveringFilters = null;
+
+ boolean check = !mRemainderFilters.isEmpty()
+ && (mIdentityFilters.size() > 0
+ || mRangeStartFilters.size() > 0
+ || mRangeEndFilters.size() > 0);
+
+ if (check) {
+ // Any remainder property which is provided by the index is a covering match.
+ for (Filter<S> subFilter : mRemainderFilters) {
+ if (isProvidedByIndex(subFilter)) {
+ if (coveringFilters == null) {
+ coveringFilters = new ArrayList<Filter<S>>();
+ }
+ coveringFilters.add(subFilter);
+ }
+ }
+ }
+
+ return prepareList(coveringFilters);
+ }
+
+ private boolean isProvidedByIndex(Filter<S> filter) {
+ return filter.accept(new Visitor<S, Boolean, Object>() {
+ public Boolean visit(OrFilter<S> filter, Object param) {
+ return filter.getLeftFilter().accept(this, param)
+ && filter.getRightFilter().accept(this, param);
+ }
+
+ public Boolean visit(AndFilter<S> filter, Object param) {
+ return filter.getLeftFilter().accept(this, param)
+ && filter.getRightFilter().accept(this, param);
+ }
+
+ public Boolean visit(PropertyFilter<S> filter, Object param) {
+ ChainedProperty<S> filterProp = filter.getChainedProperty();
+ for (OrderedProperty<S> indexProp : mIndexProperties) {
+ if (indexProp.getChainedProperty().equals(filterProp)) {
+ return true;
+ }
+ }
+ return false;
+ }
+ }, null);
+ }
+
private static class Range implements Comparator<FilteringScore<?>> {
static final Comparator<FilteringScore<?>> INSTANCE = new Range();
@@ -811,11 +897,11 @@ public class FilteringScore<S extends Storable> { return 1;
}
- // Favor index which contains more extra matches.
- if (first.getExtraMatchCount() > second.getExtraMatchCount()) {
+ // Favor index which contains more covering matches.
+ if (first.getCoveringCount() > second.getCoveringCount()) {
return -1;
}
- if (first.getExtraMatchCount() < second.getExtraMatchCount()) {
+ if (first.getCoveringCount() < second.getCoveringCount()) {
return 1;
}
diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index 366c2d7..60cf3da 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -283,35 +283,17 @@ public class IndexedQueryAnalyzer<S extends Storable> { private final StorableIndex<?> mForeignIndex;
private final ChainedProperty<S> mForeignProperty;
- private final Filter<S> mRemainderFilter;
- private final OrderingList<S> mRemainderOrdering;
-
Result(Filter<S> filter,
CompositeScore<S> score,
StorableIndex<S> localIndex,
StorableIndex<?> foreignIndex,
ChainedProperty<S> foreignProperty)
{
- this(filter, score, localIndex, foreignIndex, foreignProperty,
- score.getFilteringScore().getRemainderFilter(),
- score.getOrderingScore().getRemainderOrdering());
- }
-
- private Result(Filter<S> filter,
- CompositeScore<S> score,
- StorableIndex<S> localIndex,
- StorableIndex<?> foreignIndex,
- ChainedProperty<S> foreignProperty,
- Filter<S> remainderFilter,
- OrderingList<S> remainderOrdering)
- {
mFilter = filter;
mScore = score;
mLocalIndex = localIndex;
mForeignIndex = foreignIndex;
mForeignProperty = foreignProperty;
- mRemainderFilter = remainderFilter;
- mRemainderOrdering = remainderOrdering;
}
/**
@@ -340,9 +322,7 @@ public class IndexedQueryAnalyzer<S extends Storable> { /**
* Returns the score on how well the selected index performs the
- * desired filtering and ordering. When building a query executor, do
- * not use the remainder filter and orderings available in the
- * composite score. Instead, get them directly from this result object.
+ * desired filtering and ordering.
*/
public CompositeScore<S> getCompositeScore() {
return mScore;
@@ -352,14 +332,14 @@ public class IndexedQueryAnalyzer<S extends Storable> { * Remainder filter which overrides that in composite score.
*/
public Filter<S> getRemainderFilter() {
- return mRemainderFilter;
+ return mScore.getFilteringScore().getRemainderFilter();
}
/**
* Remainder orderings which override that in composite score.
*/
public OrderingList<S> getRemainderOrdering() {
- return mRemainderOrdering;
+ return mScore.getOrderingScore().getRemainderOrdering();
}
/**
@@ -442,9 +422,11 @@ public class IndexedQueryAnalyzer<S extends Storable> { Filter<S> filter = andFilters(handledFilter, remainderFilter);
- return new Result
- (filter, mScore, mLocalIndex, mForeignIndex, mForeignProperty,
- remainderFilter, remainderOrdering);
+ CompositeScore<S> score = mScore
+ .withRemainderFilter(remainderFilter)
+ .withRemainderOrdering(remainderOrdering);
+
+ return new Result(filter, score, mLocalIndex, mForeignIndex, mForeignProperty);
}
/**
@@ -453,7 +435,7 @@ public class IndexedQueryAnalyzer<S extends Storable> { * doesn't usually make sense to call this method.
*/
public Result mergeRemainderFilter(Filter<S> filter) {
- return setRemainderFilter(orFilters(getRemainderFilter(), filter));
+ return withRemainderFilter(orFilters(getRemainderFilter(), filter));
}
private Filter<S> andFilters(Filter<S> a, Filter<S> b) {
@@ -479,19 +461,17 @@ public class IndexedQueryAnalyzer<S extends Storable> { /**
* Returns a new result with the remainder filter replaced.
*/
- public Result setRemainderFilter(Filter<S> remainderFilter) {
- return new Result
- (mFilter, mScore, mLocalIndex, mForeignIndex, mForeignProperty,
- remainderFilter, mRemainderOrdering);
+ public Result withRemainderFilter(Filter<S> remainderFilter) {
+ CompositeScore<S> score = mScore.withRemainderFilter(remainderFilter);
+ return new Result(mFilter, score, mLocalIndex, mForeignIndex, mForeignProperty);
}
/**
* Returns a new result with the remainder ordering replaced.
*/
- public Result setRemainderOrdering(OrderingList<S> remainderOrdering) {
- return new Result
- (mFilter, mScore, mLocalIndex, mForeignIndex, mForeignProperty,
- mRemainderFilter, remainderOrdering);
+ public Result withRemainderOrdering(OrderingList<S> remainderOrdering) {
+ CompositeScore<S> score = mScore.withRemainderOrdering(remainderOrdering);
+ return new Result(mFilter, score, mLocalIndex, mForeignIndex, mForeignProperty);
}
/**
@@ -510,14 +490,30 @@ public class IndexedQueryAnalyzer<S extends Storable> { }
}
- QueryExecutor<S> executor = baseLocalExecutor(localAccess);
+ Filter<S> remainderFilter = getRemainderFilter();
- if (executor == null) {
+ QueryExecutor<S> executor;
+ if (!handlesAnything()) {
+ executor = new FullScanQueryExecutor<S>(localAccess);
+ } else if (localIndex == null) {
+ // Use foreign executor.
return JoinedQueryExecutor.build
(mRepoAccess, getForeignProperty(), getFilter(), getOrdering());
+ } else {
+ CompositeScore<S> score = getCompositeScore();
+ FilteringScore<S> fScore = score.getFilteringScore();
+ if (fScore.isKeyMatch()) {
+ executor = new KeyQueryExecutor<S>(localAccess, localIndex, fScore);
+ } else {
+ IndexedQueryExecutor ixExecutor =
+ new IndexedQueryExecutor<S>(localAccess, localIndex, score);
+ executor = ixExecutor;
+ if (ixExecutor.getCoveringFilter() != null) {
+ remainderFilter = fScore.getCoveringRemainderFilter();
+ }
+ }
}
- Filter<S> remainderFilter = getRemainderFilter();
if (remainderFilter != null) {
executor = new FilteredQueryExecutor<S>(executor, remainderFilter);
}
@@ -534,28 +530,6 @@ public class IndexedQueryAnalyzer<S extends Storable> { return executor;
}
- /**
- * Returns local executor or null if foreign executor should be used.
- */
- private QueryExecutor<S> baseLocalExecutor(StorageAccess<S> localAccess) {
- if (!handlesAnything()) {
- return new FullScanQueryExecutor<S>(localAccess);
- }
-
- StorableIndex<S> localIndex = getLocalIndex();
-
- if (localIndex != null) {
- CompositeScore<S> score = getCompositeScore();
- FilteringScore<S> fScore = score.getFilteringScore();
- if (fScore.isKeyMatch()) {
- return new KeyQueryExecutor<S>(localAccess, localIndex, fScore);
- }
- return new IndexedQueryExecutor<S>(localAccess, localIndex, score);
- }
-
- return null;
- }
-
public String toString() {
return "IndexedQueryAnalyzer.Result {score="
+ getCompositeScore() + ", localIndex="
diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java index 45ce4aa..d306e25 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -24,12 +24,15 @@ import java.util.List; import com.amazon.carbonado.Cursor;
import com.amazon.carbonado.FetchException;
+import com.amazon.carbonado.Query;
import com.amazon.carbonado.Storable;
import com.amazon.carbonado.filter.Filter;
import com.amazon.carbonado.filter.FilterValues;
import com.amazon.carbonado.filter.PropertyFilter;
+import com.amazon.carbonado.filter.RelOp;
+import com.amazon.carbonado.info.Direction;
import com.amazon.carbonado.info.StorableIndex;
/**
@@ -59,6 +62,11 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu private final boolean mReverseOrder;
private final boolean mReverseRange;
+ private final Filter<S> mCoveringFilter;
+
+ // Total of nine start and end boundary type permutations.
+ private final Query<?>[] mIndexEntryQueryCache;
+
/**
* @param index index to use, which may be a primary key index
* @param score score determines how best to utilize the index
@@ -67,6 +75,7 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu public IndexedQueryExecutor(Support<S> support,
StorableIndex<S> index,
CompositeScore<S> score)
+ throws FetchException
{
if (support == null && this instanceof Support) {
support = (Support<S>) this;
@@ -92,6 +101,15 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu mReverseOrder = oScore.shouldReverseOrder();
mReverseRange = fScore.shouldReverseRange();
+
+ Query<?> indexEntryQuery = support.indexEntryQuery(index);
+ if (indexEntryQuery == null) {
+ mCoveringFilter = null;
+ mIndexEntryQueryCache = null;
+ } else {
+ mCoveringFilter = fScore.getCoveringFilter();
+ mIndexEntryQueryCache = new Query[9]; // Nine start and end boundary permutations
+ }
}
@Override
@@ -158,11 +176,33 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu }
}
- return mSupport.fetchSubset(mIndex, identityValues,
- rangeStartBoundary, rangeStartValue,
- rangeEndBoundary, rangeEndValue,
- mReverseRange,
- mReverseOrder);
+ Query<?> indexEntryQuery = getIndexEntryQuery(rangeStartBoundary, rangeEndBoundary);
+ if (indexEntryQuery == null) {
+ return mSupport.fetchSubset(mIndex, identityValues,
+ rangeStartBoundary, rangeStartValue,
+ rangeEndBoundary, rangeEndValue,
+ mReverseRange,
+ mReverseOrder);
+ } else {
+ indexEntryQuery = indexEntryQuery.withValues(identityValues);
+ if (rangeStartBoundary != BoundaryType.OPEN) {
+ indexEntryQuery = indexEntryQuery.with(rangeStartValue);
+ }
+ if (rangeEndBoundary != BoundaryType.OPEN) {
+ indexEntryQuery = indexEntryQuery.with(rangeEndValue);
+ }
+ if (mCoveringFilter != null && values != null) {
+ indexEntryQuery = indexEntryQuery.withValues(values.getValuesFor(mCoveringFilter));
+ }
+ return mSupport.fetchFromIndexEntryQuery(mIndex, indexEntryQuery);
+ }
+ }
+
+ /**
+ * @return null if executor doesn't support or use a covering index
+ */
+ public Filter<S> getCoveringFilter() {
+ return mCoveringFilter;
}
public Filter<S> getFilter() {
@@ -181,6 +221,10 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu filter = filter == null ? p : filter.and(p);
}
+ if (mCoveringFilter != null) {
+ filter = filter == null ? mCoveringFilter : filter.and(mCoveringFilter);
+ }
+
if (filter == null) {
return Filter.getOpenFilter(getStorableType());
}
@@ -262,19 +306,117 @@ public class IndexedQueryExecutor<S extends Storable> extends AbstractQueryExecu }
newline(app);
}
+ if (mCoveringFilter != null) {
+ indent(app, indentLevel);
+ app.append("...covering filter: ");
+ mCoveringFilter.appendTo(app, values);
+
+ }
return true;
}
/**
+ * @return null if query not supported
+ */
+ private Query<?> getIndexEntryQuery(BoundaryType rangeStartBoundary,
+ BoundaryType rangeEndBoundary)
+ throws FetchException
+ {
+ Query<?>[] indexEntryQueryCache = mIndexEntryQueryCache;
+ if (indexEntryQueryCache == null) {
+ return null;
+ }
+
+ int key = 0;
+ if (rangeEndBoundary != BoundaryType.OPEN) {
+ key += (rangeEndBoundary == BoundaryType.INCLUSIVE) ? 1 : 2;
+ }
+ if (rangeStartBoundary != BoundaryType.OPEN) {
+ key += (rangeStartBoundary == BoundaryType.INCLUSIVE) ? (1 * 3) : (2 * 3);
+ }
+
+ Query<?> indexEntryQuery = indexEntryQueryCache[key];
+
+ if (indexEntryQuery == null) {
+ indexEntryQuery = mSupport.indexEntryQuery(mIndex);
+ Filter filter = indexEntryQuery.getFilter();
+
+ int i;
+ for (i=0; i<mIdentityCount; i++) {
+ filter = filter.and(mIndex.getProperty(i).getName(), RelOp.EQ);
+ }
+
+ if (rangeStartBoundary != BoundaryType.OPEN) {
+ RelOp op = (rangeStartBoundary == BoundaryType.INCLUSIVE) ? RelOp.GE : RelOp.GT;
+ filter = filter.and(mIndex.getProperty(i).getName(), op);
+ }
+
+ if (rangeEndBoundary != BoundaryType.OPEN) {
+ RelOp op = (rangeEndBoundary == BoundaryType.INCLUSIVE) ? RelOp.LE : RelOp.LT;
+ filter = filter.and(mIndex.getProperty(i).getName(), op);
+ }
+
+ if (mCoveringFilter != null) {
+ filter = filter.and(mCoveringFilter.unbind().toString());
+ }
+
+ indexEntryQuery = indexEntryQuery.and(filter);
+
+ // Enforce index ordering where applicable.
+ if (mIdentityCount < mIndex.getPropertyCount()) {
+ String[] orderProperties = new String[mIdentityCount + 1];
+ for (i=0; i<orderProperties.length; i++) {
+ Direction dir = mIndex.getPropertyDirection(i);
+ if (mReverseOrder) {
+ dir = dir.reverse();
+ }
+ orderProperties[i] = dir.toCharacter() + mIndex.getProperty(i).getName();
+ }
+ indexEntryQuery = indexEntryQuery.orderBy(orderProperties);
+ }
+
+ mIndexEntryQueryCache[key] = indexEntryQuery;
+ }
+
+ return indexEntryQuery;
+ }
+
+ /**
* Provides support for {@link IndexedQueryExecutor}.
*/
public static interface Support<S extends Storable> {
/**
+ * Returns an open query if the given index supports query access. If
+ * not supported, return null. An index entry query might be used to
+ * perform filtering and sorting of index entries prior to being
+ * resolved into referenced Storables.
+ *
+ * <p>If an index entry query is returned, the fetchSubset method is
+ * never called by IndexedQueryExecutor.
+ *
+ * @return index entry query or null if not supported
+ */
+ Query<?> indexEntryQuery(StorableIndex<S> index) throws FetchException;
+
+ /**
+ * Fetch Storables referenced by the given index entry query. This
+ * method is only called if index supports query access.
+ *
+ * @param index index to open
+ * @param indexEntryQuery query with no blank parameters, derived from
+ * the query returned by indexEntryQuery
+ */
+ Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery)
+ throws FetchException;
+
+ /**
* Perform an index scan of a subset of Storables referenced by an
* index. The identity values are aligned with the index properties at
* property 0. An optional range start or range end aligns with the index
* property following the last of the identity values.
*
+ * <p>This method is only called if no index entry query was provided
+ * for the given index.
*
* @param index index to open, which may be a primary key index
* @param identityValues optional list of exactly matching values to apply to index
diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java index 15a277f..abf7ac8 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java @@ -151,8 +151,8 @@ public class OrderingScore<S extends Storable> { }
}
- return new OrderingScore<S>(clustered,
- indexProperties.length,
+ return new OrderingScore<S>(indexProperties,
+ clustered,
handledOrdering, // no handled properties
remainderOrdering, // no remainder properties
false, // no need to reverse order
@@ -266,8 +266,8 @@ public class OrderingScore<S extends Storable> { shouldReverseOrder = false;
}
- return new OrderingScore<S>(clustered,
- indexProperties.length,
+ return new OrderingScore<S>(indexProperties,
+ clustered,
handledOrdering,
remainderOrdering,
shouldReverseOrder,
@@ -285,8 +285,8 @@ public class OrderingScore<S extends Storable> { return Full.INSTANCE;
}
+ private final OrderedProperty<S>[] mIndexProperties;
private final boolean mIndexClustered;
- private final int mIndexPropertyCount;
private final OrderingList<S> mHandledOrdering;
private final OrderingList<S> mRemainderOrdering;
@@ -300,16 +300,16 @@ public class OrderingScore<S extends Storable> { private final OrderingList<S> mFreeOrdering;
private final OrderingList<S> mUnusedOrdering;
- private OrderingScore(boolean indexClustered,
- int indexPropertyCount,
+ private OrderingScore(OrderedProperty<S>[] indexProperties,
+ boolean indexClustered,
OrderingList<S> handledOrdering,
OrderingList<S> remainderOrdering,
boolean shouldReverseOrder,
OrderingList<S> freeOrdering,
OrderingList<S> unusedOrdering)
{
+ mIndexProperties = indexProperties;
mIndexClustered = indexClustered;
- mIndexPropertyCount = indexPropertyCount;
mHandledOrdering = handledOrdering;
mRemainderOrdering = remainderOrdering;
mShouldReverseOrder = shouldReverseOrder;
@@ -317,6 +317,16 @@ public class OrderingScore<S extends Storable> { mUnusedOrdering = unusedOrdering;
}
+ private OrderingScore(OrderingScore<S> score, OrderingList<S> remainderOrdering) {
+ mIndexProperties = score.mIndexProperties;
+ mIndexClustered = score.mIndexClustered;
+ mHandledOrdering = score.mHandledOrdering;
+ mRemainderOrdering = remainderOrdering;
+ mShouldReverseOrder = score.mShouldReverseOrder;
+ mFreeOrdering = score.mFreeOrdering;
+ mUnusedOrdering = score.mUnusedOrdering;
+ }
+
/**
* Returns true if evaluated index is clustered. Scans of clustered indexes
* are generally faster.
@@ -329,7 +339,7 @@ public class OrderingScore<S extends Storable> { * Returns the amount of properties in the evaluated index.
*/
public int getIndexPropertyCount() {
- return mIndexPropertyCount;
+ return mIndexProperties.length;
}
/**
@@ -463,6 +473,16 @@ public class OrderingScore<S extends Storable> { }
}
+ /**
+ * Returns a new OrderingScore with the remainder replaced. Handled count
+ * is not recalculated.
+ *
+ * @since 1.2
+ */
+ public OrderingScore<S> withRemainderOrdering(OrderingList<S> ordering) {
+ return new OrderingScore<S>(this, ordering);
+ }
+
public String toString() {
return "OrderingScore {handledCount=" + getHandledCount() +
", remainderCount=" + getRemainderCount() +
diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java index ea60490..fda5f29 100644 --- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -422,7 +422,7 @@ public class UnionQueryAnalyzer<S extends Storable> implements QueryExecutorFact 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());
+ full.withRemainderFilter(filter.reduce());
}
mergedResults.add(full);
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java index 078069a..87e8eb9 100644 --- a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java +++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java @@ -431,10 +431,22 @@ class IndexedStorage<S extends Storable> implements Storage<S>, StorageAccess<S> Object[] identityValues)
throws FetchException
{
- return fetchSubset(index, identityValues,
- BoundaryType.OPEN, null,
- BoundaryType.OPEN, null,
- false, false);
+ ManagedIndex<S> indexInfo = (ManagedIndex<S>) mAllIndexInfoMap.get(index);
+ return indexInfo.fetchOne(this, identityValues);
+ }
+
+ public Query<?> indexEntryQuery(StorableIndex<S> index)
+ throws FetchException
+ {
+ ManagedIndex<S> indexInfo = (ManagedIndex<S>) mAllIndexInfoMap.get(index);
+ return indexInfo.getIndexEntryStorage().query();
+ }
+
+ public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery)
+ throws FetchException
+ {
+ ManagedIndex<S> indexInfo = (ManagedIndex<S>) mAllIndexInfoMap.get(index);
+ return indexInfo.fetchFromIndexEntryQuery(this, indexEntryQuery);
}
public Cursor<S> fetchSubset(StorableIndex<S> index,
@@ -447,31 +459,8 @@ class IndexedStorage<S extends Storable> implements Storage<S>, StorageAccess<S> boolean reverseOrder)
throws FetchException
{
- // Note: this code ignores the reverseRange parameter to avoid double
- // reversal. Only the lowest storage layer should examine this
- // parameter.
-
- ManagedIndex<S> indexInfo = (ManagedIndex<S>) mAllIndexInfoMap.get(index);
-
- Query<?> query = indexInfo.getIndexEntryQueryFor
- (identityValues == null ? 0 : identityValues.length,
- rangeStartBoundary, rangeEndBoundary, reverseOrder);
-
- if (identityValues != null) {
- query = query.withValues(identityValues);
- }
-
- if (rangeStartBoundary != BoundaryType.OPEN) {
- query = query.with(rangeStartValue);
- }
- if (rangeEndBoundary != BoundaryType.OPEN) {
- query = query.with(rangeEndValue);
- }
-
- Cursor<? extends Storable> indexEntryCursor = query.fetch();
-
- return new IndexedCursor<S>
- (indexEntryCursor, IndexedStorage.this, indexInfo.getIndexEntryClassBuilder());
+ // This method should never be called since a query was returned by indexEntryQuery.
+ throw new UnsupportedOperationException();
}
private void registerIndex(ManagedIndex<S> managedIndex)
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java index b1e76cc..73469db 100644 --- a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java +++ b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java @@ -38,6 +38,9 @@ import com.amazon.carbonado.SupportException; import com.amazon.carbonado.Transaction;
import com.amazon.carbonado.UniqueConstraintException;
+import com.amazon.carbonado.filter.Filter;
+import com.amazon.carbonado.filter.RelOp;
+
import com.amazon.carbonado.info.Direction;
import com.amazon.carbonado.info.StorableIndex;
@@ -65,7 +68,7 @@ class ManagedIndex<S extends Storable> implements IndexEntryAccessor<S> { private final IndexEntryGenerator<S> mGenerator;
private final Storage<?> mIndexEntryStorage;
- private final Query<?>[] mQueryCache;
+ private Query<?> mSingleMatchQuery;
ManagedIndex(StorableIndex<S> index,
IndexEntryGenerator<S> generator,
@@ -75,23 +78,6 @@ class ManagedIndex<S extends Storable> implements IndexEntryAccessor<S> { mIndex = index;
mGenerator = generator;
mIndexEntryStorage = indexEntryStorage;
-
- // Cache keys are encoded as follows:
- // bits 1..0: range end boundary
- // 0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used
- // bits 3..2: range start boundary
- // 0=open boundary, 1=inclusive boundary, 2=exlusive boundary, 3=not used
- // bit 4: 0=forward order, 1=reverse
- // bits n..5: exact property match count
-
- // The size of the cache is dependent on the number of possible
- // exactly matching properties, which is the property count of the
- // index. If the index contained a huge number of properties, say
- // 31, the cache size would be 1024.
-
- int cacheSize = Integer.highestOneBit(index.getPropertyCount()) << (1 + 5);
-
- mQueryCache = new Query[cacheSize];
}
public String getName() {
@@ -153,106 +139,27 @@ class ManagedIndex<S extends Storable> implements IndexEntryAccessor<S> { return mGenerator.getComparator();
}
- public IndexEntryGenerator<S> getIndexEntryClassBuilder() {
- return mGenerator;
- }
-
- public Query<?> getIndexEntryQueryFor(int exactMatchCount,
- BoundaryType rangeStartBoundary,
- BoundaryType rangeEndBoundary,
- boolean reverse)
+ Cursor<S> fetchOne(IndexedStorage storage, Object[] identityValues)
throws FetchException
{
- int key = exactMatchCount << 5;
- if (rangeEndBoundary != BoundaryType.OPEN) {
- if (rangeEndBoundary == BoundaryType.INCLUSIVE) {
- key |= 0x01;
- } else {
- key |= 0x02;
- }
- }
- if (rangeStartBoundary != BoundaryType.OPEN) {
- if (rangeStartBoundary == BoundaryType.INCLUSIVE) {
- key |= 0x04;
- } else {
- key |= 0x08;
- }
- }
+ Query<?> query = mSingleMatchQuery;
- if (reverse) {
- key |= 0x10;
- }
-
- Query<?> query = mQueryCache[key];
if (query == null) {
StorableIndex index = mIndex;
-
- StringBuilder filter = new StringBuilder();
-
- int i;
- for (i=0; i<exactMatchCount; i++) {
- if (i > 0) {
- filter.append(" & ");
- }
- filter.append(index.getProperty(i).getName());
- filter.append(" = ?");
- }
-
- boolean addOrderBy = false;
-
- if (rangeStartBoundary != BoundaryType.OPEN) {
- addOrderBy = true;
- if (filter.length() > 0) {
- filter.append(" & ");
- }
- filter.append(index.getProperty(i).getName());
- if (rangeStartBoundary == BoundaryType.INCLUSIVE) {
- filter.append(" >= ?");
- } else {
- filter.append(" > ?");
- }
- }
-
- if (rangeEndBoundary != BoundaryType.OPEN) {
- addOrderBy = true;
- if (filter.length() > 0) {
- filter.append(" & ");
- }
- filter.append(index.getProperty(i).getName());
- if (rangeEndBoundary == BoundaryType.INCLUSIVE) {
- filter.append(" <= ?");
- } else {
- filter.append(" < ?");
- }
- }
-
- if (filter.length() == 0) {
- query = mIndexEntryStorage.query();
- } else {
- query = mIndexEntryStorage.query(filter.toString());
+ Filter filter = Filter.getOpenFilter(mIndexEntryStorage.getStorableType());
+ for (int i=0; i<index.getPropertyCount(); i++) {
+ filter = filter.and(index.getProperty(i).getName(), RelOp.EQ);
}
-
- if (addOrderBy || reverse) {
- // Enforce ordering of properties for range searches and
- // reverse ordering to work properly. Underlying repository
- // should have ordered index properly, so this shouldn't
- // cause a sort.
- // TODO: should somehow warn if a sort is triggered
- String[] orderProperties = new String[exactMatchCount + 1];
- for (i=0; i<orderProperties.length; i++) {
- Direction dir = index.getPropertyDirection(i);
- if (reverse) {
- dir = dir.reverse();
- }
- orderProperties[i] = dir.toCharacter() + index.getProperty(i).getName();
- }
- query = query.orderBy(orderProperties);
- }
-
- mQueryCache[key] = query;
+ mSingleMatchQuery = query = mIndexEntryStorage.query(filter);
}
- return query;
+ return fetchFromIndexEntryQuery(storage, query.withValues(identityValues));
+ }
+
+ Cursor<S> fetchFromIndexEntryQuery(IndexedStorage storage, Query<?> indexEntryQuery)
+ throws FetchException
+ {
+ return new IndexedCursor<S>(indexEntryQuery.fetch(), storage, mGenerator);
}
public String toString() {
diff --git a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java index c33acba..c2d1844 100644 --- a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java +++ b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java @@ -298,6 +298,15 @@ abstract class BDBStorage<Txn, S extends Storable> implements Storage<S>, Storag return new SingletonCursor<S>(instantiate(key, value));
}
+ public Query<?> indexEntryQuery(StorableIndex<S> index) {
+ return null;
+ }
+
+ public Cursor<S> fetchFromIndexEntryQuery(StorableIndex<S> index, Query<?> indexEntryQuery) {
+ // This method should never be called since null was returned by indexEntryQuery.
+ throw new UnsupportedOperationException();
+ }
+
public Cursor<S> fetchSubset(StorableIndex<S> index,
Object[] identityValues,
BoundaryType rangeStartBoundary,
|