diff options
| author | Brian S. O'Neill <bronee@gmail.com> | 2006-09-17 21:40:47 +0000 |
|---|---|---|
| committer | Brian S. O'Neill <bronee@gmail.com> | 2006-09-17 21:40:47 +0000 |
| commit | d5e7a0f66f639d42934074a751aa9af9f76a3ceb (patch) | |
| tree | db90bd0a88ce228c86c82adba44fcd384aafb79f /src/main/java/com/amazon/carbonado/spi | |
| parent | 2b6eaf1ba86117afea79e2416d97b0ed12f30795 (diff) | |
Finished replacing old query engine.
Diffstat (limited to 'src/main/java/com/amazon/carbonado/spi')
4 files changed, 0 insertions, 3262 deletions
diff --git a/src/main/java/com/amazon/carbonado/spi/BaseQuery.java b/src/main/java/com/amazon/carbonado/spi/BaseQuery.java deleted file mode 100644 index e5fc3b0..0000000 --- a/src/main/java/com/amazon/carbonado/spi/BaseQuery.java +++ /dev/null @@ -1,395 +0,0 @@ -/*
- * 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.spi;
-
-import java.io.IOException;
-
-import org.cojen.util.BeanPropertyAccessor;
-
-import com.amazon.carbonado.Cursor;
-import com.amazon.carbonado.FetchException;
-import com.amazon.carbonado.IsolationLevel;
-import com.amazon.carbonado.PersistException;
-import com.amazon.carbonado.PersistMultipleException;
-import com.amazon.carbonado.Repository;
-import com.amazon.carbonado.Storage;
-import com.amazon.carbonado.Storable;
-import com.amazon.carbonado.Transaction;
-import com.amazon.carbonado.Query;
-import com.amazon.carbonado.util.Appender;
-
-import com.amazon.carbonado.filter.ClosedFilter;
-import com.amazon.carbonado.filter.Filter;
-import com.amazon.carbonado.filter.FilterValues;
-import com.amazon.carbonado.filter.OpenFilter;
-import com.amazon.carbonado.filter.RelOp;
-
-import com.amazon.carbonado.info.OrderedProperty;
-
-import com.amazon.carbonado.qe.AbstractQuery;
-import com.amazon.carbonado.qe.EmptyQuery;
-
-/**
- * BaseQuery supports binding filters to values.
- *
- * @author Brian S O'Neill
- * @deprecated Use {@link com.amazon.carbonado.qe.StandardQuery}
- */
-public abstract class BaseQuery<S extends Storable> extends AbstractQuery<S> implements Appender {
- /**
- * Appends spaces to the given appendable. Useful for implementing
- * printNative and printPlan.
- */
- public static void indent(Appendable app, int indentLevel) throws IOException {
- for (int i=0; i<indentLevel; i++) {
- app.append(' ');
- }
- }
-
- protected static final String[] EMPTY_ORDERINGS = {};
-
- protected static String[] extractOrderingNames(OrderedProperty<?>[] orderings) {
- String[] orderingStrings;
- if (orderings == null || orderings.length == 0) {
- return EMPTY_ORDERINGS;
- }
- orderingStrings = new String[orderings.length];
- for (int i=0; i<orderingStrings.length; i++) {
- orderingStrings[i] = orderings[i].toString().intern();
- }
- return orderingStrings;
- }
-
- private final Repository mRepository;
- private final Storage<S> mStorage;
- // Values for this query.
- private final FilterValues<S> mValues;
- // Properties that this query is ordered by.
- private final String[] mOrderings;
-
- // Note: Since constructor has parameters, this class is called Base
- // instead of Abstract.
- /**
- * @param storage required storage object
- * @param values optional values object, defaults to open filter if null
- * @param orderings optional order-by properties
- */
- protected BaseQuery(Repository repo,
- Storage<S> storage,
- FilterValues<S> values,
- OrderedProperty<S>[] orderings)
- {
- if (repo == null || storage == null) {
- throw new IllegalArgumentException();
- }
- mRepository = repo;
- mStorage = storage;
- mValues = values;
- mOrderings = extractOrderingNames(orderings);
- }
-
- /**
- * @param storage required storage object
- * @param values optional values object, defaults to open filter if null
- * @param orderings optional order-by properties, not cloned
- */
- protected BaseQuery(Repository repo,
- Storage<S> storage,
- FilterValues<S> values,
- String[] orderings)
- {
- if (repo == null || storage == null) {
- throw new IllegalArgumentException();
- }
- mRepository = repo;
- mStorage = storage;
- mValues = values;
- mOrderings = orderings == null ? EMPTY_ORDERINGS : orderings;
- }
-
- public Class<S> getStorableType() {
- return mStorage.getStorableType();
- }
-
- public Filter<S> getFilter() {
- FilterValues<S> values = mValues;
- if (values != null) {
- return values.getFilter();
- }
- return Filter.getOpenFilter(mStorage.getStorableType());
- }
-
- public FilterValues<S> getFilterValues() {
- return mValues;
- }
-
- public int getBlankParameterCount() {
- return mValues == null ? 0 : mValues.getBlankParameterCount();
- }
-
- public Query<S> with(int value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(long value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(float value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(double value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(boolean value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(char value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(byte value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(short value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> with(Object value) {
- return newInstance(requireValues().with(value));
- }
-
- public Query<S> withValues(Object... values) {
- if (values == null || values.length == 0) {
- return this;
- }
- return newInstance(requireValues().withValues(values));
- }
-
- public Query<S> and(Filter<S> filter) throws FetchException {
- FilterValues<S> values = getFilterValues();
- Query<S> newQuery;
- if (values == null) {
- newQuery = mStorage.query(filter);
- } else {
- newQuery = mStorage.query(values.getFilter().and(filter));
- newQuery = newQuery.withValues(values.getValues());
- }
- return mOrderings.length == 0 ? newQuery : newQuery.orderBy(mOrderings);
- }
-
- public Query<S> or(Filter<S> filter) throws FetchException {
- FilterValues<S> values = getFilterValues();
- if (values == null) {
- throw new IllegalStateException("Query is already guaranteed to fetch everything");
- }
- Query<S> newQuery = mStorage.query(values.getFilter().or(filter));
- newQuery = newQuery.withValues(values.getValues());
- return mOrderings.length == 0 ? newQuery : newQuery.orderBy(mOrderings);
- }
-
- public Query<S> not() throws FetchException {
- FilterValues<S> values = getFilterValues();
- if (values == null) {
- // FIXME: fix this or remove BaseQuery class.
- throw new UnsupportedOperationException();
- //return new EmptyQuery<S>(mStorage, mOrderings);
- }
- Query<S> newQuery = mStorage.query(values.getFilter().not());
- newQuery = newQuery.withValues(values.getSuppliedValues());
- return mOrderings.length == 0 ? newQuery : newQuery.orderBy(mOrderings);
- }
-
- public Cursor<S> fetchAfter(S start) throws FetchException {
- String[] orderings;
- if (start == null || (orderings = mOrderings).length == 0) {
- return fetch();
- }
-
- Class<S> storableType = mStorage.getStorableType();
- Filter<S> orderFilter = Filter.getClosedFilter(storableType);
- Filter<S> lastSubFilter = Filter.getOpenFilter(storableType);
- BeanPropertyAccessor accessor = BeanPropertyAccessor.forClass(storableType);
-
- Object[] values = new Object[orderings.length];
-
- for (int i=0;;) {
- String propertyName = orderings[i];
- RelOp operator = RelOp.GT;
- char c = propertyName.charAt(0);
- if (c == '-') {
- propertyName = propertyName.substring(1);
- operator = RelOp.LT;
- } else if (c == '+') {
- propertyName = propertyName.substring(1);
- }
-
- values[i] = accessor.getPropertyValue(start, propertyName);
-
- orderFilter = orderFilter.or(lastSubFilter.and(propertyName, operator));
-
- if (++i >= orderings.length) {
- break;
- }
-
- lastSubFilter = lastSubFilter.and(propertyName, RelOp.EQ);
- }
-
- Query<S> newQuery = this.and(orderFilter);
-
- for (int i=0; i<values.length; i++) {
- for (int j=0; j<=i; j++) {
- newQuery = newQuery.with(values[j]);
- }
- }
-
- return newQuery.fetch();
- }
-
- public boolean tryDeleteOne() throws PersistException {
- Transaction txn = mRepository.enterTransaction(IsolationLevel.READ_COMMITTED);
- try {
- Cursor<S> cursor = fetch();
- boolean result;
- try {
- if (cursor.hasNext()) {
- S obj = cursor.next();
- if (cursor.hasNext()) {
- throw new PersistMultipleException(toString());
- }
- result = obj.tryDelete();
- } else {
- return false;
- }
- } finally {
- cursor.close();
- }
- txn.commit();
- return result;
- } catch (FetchException e) {
- throw e.toPersistException();
- } finally {
- txn.exit();
- }
- }
-
- public void deleteAll() throws PersistException {
- Transaction txn = mRepository.enterTransaction(IsolationLevel.READ_COMMITTED);
- try {
- Cursor<S> cursor = fetch();
- try {
- while (cursor.hasNext()) {
- cursor.next().tryDelete();
- }
- } finally {
- cursor.close();
- }
- txn.commit();
- } catch (FetchException e) {
- throw e.toPersistException();
- } finally {
- txn.exit();
- }
- }
-
- /**
- * Returns the query ordering properties, never null. The returned array is
- * not cloned, only for performance reasons. Subclasses should not alter it.
- */
- protected String[] getOrderings() {
- return mOrderings;
- }
-
- protected final Repository getRepository() {
- return mRepository;
- }
-
- protected final Storage<S> getStorage() {
- return mStorage;
- }
-
- @Override
- public int hashCode() {
- return mStorage.hashCode() * 31 + getFilterValues().hashCode();
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj) {
- return true;
- }
- if (obj instanceof BaseQuery) {
- BaseQuery<?> other = (BaseQuery<?>) obj;
- return mStorage.equals(other.mStorage) &&
- getFilterValues().equals(other.getFilterValues());
- }
- return false;
- }
-
- public void appendTo(Appendable app) throws IOException {
- app.append("Query {type=");
- app.append(getStorableType().getName());
- app.append(", filter=");
- Filter<S> filter = getFilter();
- if (filter instanceof OpenFilter || filter instanceof ClosedFilter) {
- filter.appendTo(app);
- } else {
- app.append('"');
- filter.appendTo(app, getFilterValues());
- app.append('"');
- }
-
- if (mOrderings != null && mOrderings.length > 0) {
- app.append(", orderBy=[");
- for (int i=0; i<mOrderings.length; i++) {
- if (i > 0) {
- app.append(", ");
- }
- app.append(mOrderings[i]);
- }
- app.append(']');
- }
-
- app.append('}');
- }
-
- private FilterValues<S> requireValues() {
- FilterValues<S> values = getFilterValues();
- if (values == null) {
- throw new IllegalStateException("Query doesn't have any parameters");
- }
- return values;
- }
-
- /**
- * Return a new instance of BaseQuery implementation, using new filter
- * values. The Filter in the FilterValues is the same as was passed in the
- * constructor.
- *
- * <p>Any orderings in this query must also be applied in the new
- * query. Call getOrderings to get them.
- *
- * @param values never null
- */
- protected abstract BaseQuery<S> newInstance(FilterValues<S> values);
-}
diff --git a/src/main/java/com/amazon/carbonado/spi/BaseQueryCompiler.java b/src/main/java/com/amazon/carbonado/spi/BaseQueryCompiler.java deleted file mode 100644 index 4160b0e..0000000 --- a/src/main/java/com/amazon/carbonado/spi/BaseQueryCompiler.java +++ /dev/null @@ -1,249 +0,0 @@ -/*
- * 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.spi;
-
-import java.util.Map;
-
-import org.cojen.util.KeyFactory;
-import org.cojen.util.SoftValuedHashMap;
-import org.cojen.util.WeakIdentityMap;
-
-import com.amazon.carbonado.FetchException;
-import com.amazon.carbonado.Storable;
-import com.amazon.carbonado.MalformedFilterException;
-import com.amazon.carbonado.Query;
-
-import com.amazon.carbonado.filter.ClosedFilter;
-import com.amazon.carbonado.filter.Filter;
-import com.amazon.carbonado.filter.FilterValues;
-
-import com.amazon.carbonado.info.OrderedProperty;
-import com.amazon.carbonado.info.StorableInfo;
-
-/**
- * BaseQueryCompiler caches compiled queries, and calls an abstract method
- * to compile queries it doesn't have cached.
- *
- * @author Brian S O'Neill
- * @deprecated Use {@link com.amazon.carbonado.qe.StandardQueryFactory}
- */
-public abstract class BaseQueryCompiler<S extends Storable> {
- private final StorableInfo<S> mInfo;
- private final Map<String, Query<S>> mStringToQuery;
- private final Map<Filter<S>, Queries<S>> mFilterToQueries;
-
- /**
- * @throws IllegalArgumentException if type is null
- */
- // Note: Since constructor has parameters, this class is called Base
- // instead of Abstract.
- @SuppressWarnings("unchecked")
- protected BaseQueryCompiler(StorableInfo<S> info) {
- if (info == null) {
- throw new IllegalArgumentException();
- }
- mInfo = info;
- mStringToQuery = new SoftValuedHashMap(7);
- mFilterToQueries = new WeakIdentityMap(7);
- }
-
- /**
- * Looks up compiled query in the cache, and returns it. If not found, then
- * one is created and cached for later retrieval.
- *
- * @return cached compiled query which returns everything from storage
- */
- public synchronized Query<S> getCompiledQuery() throws FetchException {
- return getCompiledQuery(Filter.getOpenFilter(mInfo.getStorableType()));
- }
-
- /**
- * Looks up compiled query in the cache, and returns it. If not found, then
- * the filter expression is parsed, and compileQuery is invoked on the
- * result. The compiled query is cached for later retrieval.
- *
- * @param filter query filter expression to parse
- * @return cached compiled query
- * @throws IllegalArgumentException if query filter expression is null
- * @throws MalformedFilterException if query filter expression is malformed
- */
- public synchronized Query<S> getCompiledQuery(String filter) throws FetchException {
- if (filter == null) {
- throw new IllegalArgumentException("Query filter must not be null");
- }
- Query<S> query = mStringToQuery.get(filter);
- if (query == null) {
- query = getCompiledQuery(Filter.filterFor(mInfo.getStorableType(), filter));
- mStringToQuery.put(filter, query);
- }
- return query;
- }
-
- /**
- * Looks up compiled query in the cache, and returns it. If not found, then
- * compileQuery is invoked on the result. The compiled query is cached for
- * later retrieval.
- *
- * @param filter root filter tree
- * @return cached compiled query
- * @throws IllegalArgumentException if root filter is null
- */
- public synchronized Query<S> getCompiledQuery(Filter<S> filter) throws FetchException {
- if (filter == null) {
- throw new IllegalArgumentException("Filter is null");
- }
- Queries<S> queries = mFilterToQueries.get(filter);
- if (queries == null) {
- Query<S> query;
- FilterValues<S> values = filter.initialFilterValues();
- if (values != null) {
- // FilterValues applies to bound filter. Use that instead.
- Filter<S> altFilter = values.getFilter();
- if (altFilter != filter) {
- return getCompiledQuery(altFilter);
- }
- query = compileQuery(values, null);
- } else {
- query = compileQuery(null, null);
- if (filter instanceof ClosedFilter) {
- query = query.not();
- }
- }
- queries = new Queries<S>(query);
- mFilterToQueries.put(filter, queries);
- }
- return queries.mPlainQuery;
- }
-
- /**
- * Used by implementations to retrieve cached queries that have order-by
- * properties.
- *
- * @param values filter values produced earlier by this compiler, or null,
- * or a derived instance
- * @param propertyNames optional property names to order by, which may be
- * prefixed with '+' or '-'
- * @throws IllegalArgumentException if properties are not supported or if
- * filter did not originate from this compiler
- */
- @SuppressWarnings("unchecked")
- public Query<S> getOrderedQuery(FilterValues<S> values, String... propertyNames)
- throws FetchException, IllegalArgumentException, UnsupportedOperationException
- {
- final Filter<S> filter =
- values == null ? Filter.getOpenFilter(mInfo.getStorableType()) : values.getFilter();
-
- final Queries<S> queries = mFilterToQueries.get(filter);
-
- if (queries == null) {
- throw new IllegalArgumentException("Unknown filter provided");
- }
-
- if (propertyNames == null || propertyNames.length == 0) {
- return queries.mPlainQuery;
- }
-
- final Object key = KeyFactory.createKey(propertyNames);
- Query<S> query = queries.mOrderingsToQuery.get(key);
-
- if (query != null) {
- // Now transfer property values.
- if (values != null) {
- query = query.withValues(values.getSuppliedValues());
- }
-
- return query;
- }
-
- // Try again with property names that have an explicit direction,
- // hoping for a cache hit.
-
- boolean propertyNamesChanged = false;
- final int length = propertyNames.length;
- for (int i=0; i<length; i++) {
- String propertyName = propertyNames[i];
- if (propertyName == null) {
- throw new IllegalArgumentException("Order by property [" + i + "] is null");
- }
- if (!propertyName.startsWith("+") && !propertyName.startsWith("-")) {
- if (!propertyNamesChanged) {
- propertyNames = propertyNames.clone();
- propertyNamesChanged = true;
- }
- propertyNames[i] = "+".concat(propertyName);
- }
- }
-
- if (propertyNamesChanged) {
- return getOrderedQuery(values, propertyNames);
- }
-
- // If this point is reached, propertyNames is guaranteed to have no
- // null elements, and all have an explicit direction.
-
- OrderedProperty<S>[] orderings = new OrderedProperty[length];
-
- for (int i=0; i<length; i++) {
- orderings[i] = OrderedProperty.parse(mInfo, propertyNames[i]);
- }
-
- FilterValues<S> initialValues = filter.initialFilterValues();
-
- query = compileQuery(initialValues, orderings);
- queries.mOrderingsToQuery.put(key, query);
-
- // Now transfer property values.
- if (values != null) {
- query = query.withValues(values.getSuppliedValues());
- }
-
- return query;
- }
-
- /**
- * Returns the StorableInfo object in this object.
- */
- protected StorableInfo<S> getStorableInfo() {
- return mInfo;
- }
-
- /**
- * Compile the query represented by the type checked root node. If any
- * order-by properties are supplied, they have been checked as well.
- *
- * @param values values and filter for query, which may be null if
- * unfiltered
- * @param orderings optional list of properties to order by
- */
- protected abstract Query<S> compileQuery(FilterValues<S> values,
- OrderedProperty<S>[] orderings)
- throws FetchException, UnsupportedOperationException;
-
- private static class Queries<S extends Storable> {
- final Query<S> mPlainQuery;
-
- final Map<Object, Query<S>> mOrderingsToQuery;
-
- @SuppressWarnings("unchecked")
- Queries(Query<S> query) {
- mPlainQuery = query;
- mOrderingsToQuery = new SoftValuedHashMap(7);
- }
- }
-}
diff --git a/src/main/java/com/amazon/carbonado/spi/BaseQueryEngine.java b/src/main/java/com/amazon/carbonado/spi/BaseQueryEngine.java deleted file mode 100644 index f1ede60..0000000 --- a/src/main/java/com/amazon/carbonado/spi/BaseQueryEngine.java +++ /dev/null @@ -1,1413 +0,0 @@ -/*
- * 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.spi;
-
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Comparator;
-import java.util.LinkedHashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.cojen.util.BeanComparator;
-
-import com.amazon.carbonado.Cursor;
-import com.amazon.carbonado.FetchException;
-import com.amazon.carbonado.Query;
-import com.amazon.carbonado.Repository;
-import com.amazon.carbonado.Storable;
-import com.amazon.carbonado.Storage;
-
-import com.amazon.carbonado.filter.AndFilter;
-import com.amazon.carbonado.filter.Filter;
-import com.amazon.carbonado.filter.FilterValues;
-import com.amazon.carbonado.filter.OrFilter;
-import com.amazon.carbonado.filter.PropertyFilter;
-import com.amazon.carbonado.filter.Visitor;
-
-import com.amazon.carbonado.info.Direction;
-import com.amazon.carbonado.info.OrderedProperty;
-import com.amazon.carbonado.info.StorableIndex;
-import com.amazon.carbonado.info.StorableInfo;
-
-import com.amazon.carbonado.cursor.FilteredCursor;
-import com.amazon.carbonado.cursor.MergeSortBuffer;
-import com.amazon.carbonado.cursor.SortBuffer;
-import com.amazon.carbonado.cursor.SortedCursor;
-import com.amazon.carbonado.cursor.UnionCursor;
-
-import com.amazon.carbonado.qe.BoundaryType;
-
-/**
- * Basis for a rule-based query engine. It takes care of index selection,
- * filtering, sorting, and unions.
- *
- * @author Brian S O'Neill
- * @deprecated Use {@link com.amazon.carbonado.qe.QueryEngine}
- */
-public abstract class BaseQueryEngine<S extends Storable> extends BaseQueryCompiler<S> {
- private static PropertyFilter[] NO_FILTERS = new PropertyFilter[0];
-
- /**
- * Compares two objects which are assumed to be Comparable. If one value is
- * null, it is treated as being higher. This consistent with all other
- * property value comparisons in carbonado.
- */
- static int compareWithNullHigh(Object a, Object b) {
- return a == null ? (b == null ? 0 : -1) : (b == null ? 1 : ((Comparable) a).compareTo(b));
- }
-
- private final Repository mRepository;
- private final Storage<S> mStorage;
- private final StorableIndex<S> mPrimaryKeyIndex;
- private final StorableIndexSet<S> mIndexSet;
-
- String mMergeSortTempDir;
-
- /**
- * @param info info for Storable
- * @param repo repository for entering transactions
- * @param storage source for queried objects
- * @param primaryKeyIndex optional parameter representing primary key index
- * @param indexSet optional parameter representing all available indexes.
- * Constructor makes a local copy of the set.
- * @throws IllegalArgumentException if primaryKeyIndex is null and indexSet
- * is empty
- */
- protected BaseQueryEngine(StorableInfo<S> info,
- Repository repo,
- Storage<S> storage,
- StorableIndex<S> primaryKeyIndex,
- StorableIndexSet<S> indexSet) {
- super(info);
- if (primaryKeyIndex == null && (indexSet == null || indexSet.size() == 0)) {
- throw new IllegalArgumentException();
- }
- mRepository = repo;
- mStorage = storage;
- mPrimaryKeyIndex = primaryKeyIndex;
- mIndexSet = (indexSet == null || indexSet.size() == 0) ? null
- : new StorableIndexSet<S>(indexSet);
- }
-
- /**
- * @param tempDir directory to store temp files for merge sorting, or null
- * for default
- */
- protected void setMergeSortTempDirectory(String tempDir) {
- mMergeSortTempDir = tempDir;
- }
-
- @SuppressWarnings("unchecked")
- protected Query<S> compileQuery(final FilterValues<S> values,
- final OrderedProperty<S>[] orderings)
- throws FetchException, UnsupportedOperationException
- {
- if (values == null) {
- // Perform requested full scan.
- return fullScan(values, orderings);
- }
-
- final Filter<S> originalFilter = values.getFilter();
- final Filter<S> dnfFilter = originalFilter.disjunctiveNormalForm();
-
- // Analyze the disjunctive normal form, breaking down the query into
- // separate queries that can be unioned together.
-
- IndexAnalysis<S> analysis = new IndexAnalysis<S>(mPrimaryKeyIndex, mIndexSet, orderings);
- dnfFilter.accept(analysis, null);
-
- if (analysis.noBestIndex()) {
- // Fallback to full scan for everything if no best index found for
- // just one query component.
- return fullScan(values, orderings);
- }
-
- OrderedProperty<S>[] totalOrderings = null;
- ensureTotalOrdering:
- if (analysis.getResults().size() > 1) {
- // Union will be performed, and so a total ordering is required.
-
- // TODO: The logic in this section needs to be totally reworked. It
- // does a terrible job of finding the best total ordering, often
- // performing full sorts when not needed. Essentially, inefficient
- // query plans can get generated.
-
- // If all selected indexes are unique and have the same effective ordering, then
- // nothing special needs to be done to ensure total ordering.
- OrderedProperty<S>[] effectiveOrderings = null;
- totalOrderCheck:
- if (orderings == null || orderings.length == 0) {
- for (IndexSelector.IndexFitness<S> result : analysis.getResults()) {
- StorableIndex<S> index = result.getIndex();
- if (!index.isUnique()) {
- break totalOrderCheck;
- }
- if (effectiveOrderings == null) {
- effectiveOrderings = result.getEffectiveOrderings();
- continue;
- }
- if (!Arrays.equals(effectiveOrderings, result.getEffectiveOrderings())) {
- break totalOrderCheck;
- }
- }
- // All indexes already define a total ordering.
- totalOrderings = effectiveOrderings;
- break ensureTotalOrdering;
- }
-
- // Augment the ordering with elements of a unique index.
-
- // Count how often an index has been used.
- Map<StorableIndex<S>, Integer> counts = new LinkedHashMap<StorableIndex<S>, Integer>();
-
- for (IndexSelector.IndexFitness<S> result : analysis.getResults()) {
- StorableIndex<S> index = result.getIndex();
- counts.put(index, (counts.containsKey(index)) ? (counts.get(index) + 1) : 1);
- }
-
- // Find the unique index that has been selected most often.
- StorableIndex<S> unique = mPrimaryKeyIndex;
- int uniqueCount = 0;
- for (Map.Entry<StorableIndex<S>, Integer> entry : counts.entrySet()) {
- if (entry.getKey().isUnique() && entry.getValue() > uniqueCount) {
- unique = entry.getKey();
- uniqueCount = entry.getValue();
- }
- }
-
- if (unique == null) {
- // Select first found unique index.
- for (StorableIndex<S> index : mIndexSet) {
- if (index.isUnique()) {
- unique = index;
- break;
- }
- }
- if (unique == null) {
- throw new UnsupportedOperationException
- ("Cannot perform union; sort requires at least one unique index");
- }
- }
-
- // To avoid full sorts, choose an index which is already being used
- // for its ordering. It may have a range filter or handled
- // orderings.
- StorableIndex<S> best = null;
- int bestCount = 0;
- for (IndexSelector.IndexFitness<S> result : analysis.getResults()) {
- if ((result.getInclusiveRangeStartFilters().length > 0 ||
- result.getExclusiveRangeStartFilters().length > 0 ||
- result.getInclusiveRangeEndFilters().length > 0 ||
- result.getExclusiveRangeEndFilters().length > 0) &&
- (result.getHandledOrderings() != null ||
- result.getRemainderOrderings() == null)) {
-
- StorableIndex<S> index = result.getIndex();
- int count = counts.get(index);
-
- if (count > bestCount) {
- best = index;
- bestCount = count;
- }
- }
- }
-
- {
- int newLength = (orderings == null ? 0 : orderings.length)
- + (best == null ? 0 : best.getPropertyCount())
- + unique.getPropertyCount();
- totalOrderings = new OrderedProperty[newLength];
-
- int j = 0;
- if (orderings != null) {
- for (int i=0; i<orderings.length; i++) {
- totalOrderings[j++] = orderings[i];
- }
- }
- if (best != null) {
- for (int i=0; i<best.getPropertyCount(); i++) {
- totalOrderings[j++] = OrderedProperty.get
- (best.getProperty(i), best.getPropertyDirection(i));
- }
- }
- for (int i=0; i<unique.getPropertyCount(); i++) {
- totalOrderings[j++] = OrderedProperty.get
- (unique.getProperty(i), unique.getPropertyDirection(i));
- }
- }
-
- // Augmented total orderings may contain redundancies, which are
- // removed by index selector. Running the analysis again may be
- // produce the exact same results as before. No harm done.
-
- analysis = new IndexAnalysis<S>(mPrimaryKeyIndex, mIndexSet, totalOrderings);
- dnfFilter.accept(analysis, null);
-
- if (analysis.noBestIndex()) {
- // Fallback to full scan for everything if no best index found for
- // just one query component.
- return fullScan(values, orderings);
- }
- }
-
- // Attempt to reduce the number of separate cursors need to be opened for union.
- analysis.reduceResults();
-
- List<CursorFactory<S>> subFactories = new ArrayList<CursorFactory<S>>();
-
- for (IndexSelector.IndexFitness<S> result : analysis.getResults()) {
- CursorFactory<S> subFactory;
-
- // Determine if KeyCursorFactory should be used instead.
- boolean isKeyFilter = result.isKeyFilter();
- if (isKeyFilter) {
- subFactory = new KeyCursorFactory<S>
- (this, result.getIndex(), result.getExactFilter());
- } else {
- subFactory = new IndexCursorFactory<S>
- (this, result.getIndex(),
- result.shouldReverseOrder(), result.shouldReverseRange(),
- result.getExactFilter(),
- result.getInclusiveRangeStartFilters(),
- result.getExclusiveRangeStartFilters(),
- result.getInclusiveRangeEndFilters(),
- result.getExclusiveRangeEndFilters());
- }
-
- Filter<S> remainderFilter = result.getRemainderFilter();
- if (remainderFilter != null) {
- subFactory = new FilteredCursorFactory<S>(this, subFactory, remainderFilter);
- }
-
- if (!isKeyFilter) {
- OrderedProperty<S>[] remainderOrderings = result.getRemainderOrderings();
- if (remainderOrderings != null && remainderOrderings.length > 0) {
- subFactory = new SortedCursorFactory<S>
- (this, subFactory, result.getHandledOrderings(), remainderOrderings);
- }
- }
-
- subFactories.add(subFactory);
- }
-
- CursorFactory<S> factory = UnionedCursorFactory
- .createUnion(this, subFactories, totalOrderings);
-
- return CompiledQuery.create(mRepository, mStorage, values, orderings, this, factory);
- }
-
- private Query<S> fullScan(FilterValues<S> values, OrderedProperty<S>[] orderings)
- throws FetchException
- {
- // Try to select index that has best ordering.
- IndexSelector<S> selector = new IndexSelector<S>(null, orderings);
- StorableIndex<S> best = mPrimaryKeyIndex;
-
- if (mIndexSet != null) {
- for (StorableIndex<S> candidate : mIndexSet) {
- int cmpResult = selector.compare(best, candidate);
- if (cmpResult > 0) {
- best = candidate;
- }
- }
- }
-
- IndexSelector.IndexFitness<S> result = selector.examine(best);
-
- CursorFactory<S> factory;
- if (result == null || result.isUseless()) {
- factory = new FullScanCursorFactory<S>(this, mPrimaryKeyIndex);
- if (values != null) {
- factory = new FilteredCursorFactory<S>(this, factory, values.getFilter());
- }
- if (orderings != null && orderings.length > 0) {
- factory = new SortedCursorFactory<S>(this, factory, null, orderings);
- }
- } else {
- factory = new IndexCursorFactory<S>
- (this, result.getIndex(),
- result.shouldReverseOrder(), result.shouldReverseRange(),
- result.getExactFilter(),
- result.getInclusiveRangeStartFilters(),
- result.getExclusiveRangeStartFilters(),
- result.getInclusiveRangeEndFilters(),
- result.getExclusiveRangeEndFilters());
-
- Filter<S> remainderFilter = result.getRemainderFilter();
- if (remainderFilter != null) {
- factory = new FilteredCursorFactory<S>(this, factory, remainderFilter);
- }
-
- OrderedProperty<S>[] remainderOrderings = result.getRemainderOrderings();
- if (remainderOrderings != null && remainderOrderings.length > 0) {
- factory = new SortedCursorFactory<S>
- (this, factory, result.getHandledOrderings(), remainderOrderings);
- }
- }
-
- return CompiledQuery.create(mRepository, mStorage, values, orderings, this, factory);
- }
-
- /**
- * Returns the primary Storage object in this object.
- */
- protected final Storage<S> getStorage() {
- return mStorage;
- }
-
- /**
- * Returns the storage object that the given index applies to. By default,
- * this method returns the primary storage. Override if indexes may be
- * defined in multiple storages.
- */
- protected Storage<S> getStorageFor(StorableIndex<S> index) {
- return mStorage;
- }
-
- /**
- * Return a new Cursor instance constrained by the given parameters. The
- * index values are aligned with the index properties at property index
- * 0. An optional start or end boundary matches up with the index property
- * following the last of the index values.
- *
- * @param index index to open, which may be the primary key index
- * @param exactValues optional list of exactly matching values to apply to index
- * @param rangeStartBoundary start boundary type
- * @param rangeStartValue value to start at if boundary is not open
- * @param rangeEndBoundary end boundary type
- * @param rangeEndValue value to end at if boundary is not open
- * @param reverseRange indicates that range operates on a property that is
- * ordered in reverse (this parameter might also be true simply because
- * reverseOrder is true)
- * @param reverseOrder when true, iteration is reversed
- */
- protected abstract Cursor<S> openCursor(StorableIndex<S> index,
- Object[] exactValues,
- BoundaryType rangeStartBoundary,
- Object rangeStartValue,
- BoundaryType rangeEndBoundary,
- Object rangeEndValue,
- boolean reverseRange,
- boolean reverseOrder)
- throws FetchException;
-
- /**
- * Return a new Cursor instance which is expected to fetch at most one
- * object. The chosen index is unique, and a primary or alternate key is
- * contained within it.
- * <p>
- * Subclasses are encouraged to override this method and provide a more
- * efficient implementation.
- *
- * @param index index to open, which may be the primary key index
- * @param exactValues first values to set for index; length may be smaller
- * than index property count
- */
- protected Cursor<S> openKeyCursor(StorableIndex<S> index,
- Object[] exactValues)
- throws FetchException
- {
- return openCursor(index, exactValues,
- BoundaryType.OPEN, null,
- BoundaryType.OPEN, null,
- false,
- false);
- }
-
- @SuppressWarnings("unchecked")
- Comparator<S> makeComparator(OrderedProperty<S>[] orderings) {
- if (orderings == null) {
- return null;
- }
-
- BeanComparator bc = BeanComparator.forClass(getStorableInfo().getStorableType());
-
- for (OrderedProperty<S> property : orderings) {
- bc = bc.orderBy(property.getChainedProperty().toString());
- bc = bc.caseSensitive();
- if (property.getDirection() == Direction.DESCENDING) {
- bc = bc.reverse();
- }
- }
-
- return bc;
- }
-
- private static class CompiledQuery<S extends Storable> extends BaseQuery<S> {
- private final BaseQueryEngine<S> mEngine;
- private final CursorFactory<S> mFactory;
-
- static <S extends Storable> Query<S> create(Repository repo,
- Storage<S> storage,
- FilterValues<S> values,
- OrderedProperty<S>[] orderings,
- BaseQueryEngine<S> engine,
- CursorFactory<S> factory)
- throws FetchException
- {
- if (factory == null) {
- throw new IllegalArgumentException();
- }
- factory = factory.getActualFactory();
- return new CompiledQuery<S>(repo, storage, values, orderings, engine, factory);
- }
-
- private CompiledQuery(Repository repo,
- Storage<S> storage,
- FilterValues<S> values,
- OrderedProperty<S>[] orderings,
- BaseQueryEngine<S> engine,
- CursorFactory<S> factory)
- throws FetchException
- {
- super(repo, storage, values, orderings);
- mEngine = engine;
- mFactory = factory;
- }
-
- private CompiledQuery(Repository repo,
- Storage<S> storage,
- FilterValues<S> values,
- String[] orderings,
- BaseQueryEngine<S> engine,
- CursorFactory<S> factory)
- {
- super(repo, storage, values, orderings);
- mEngine = engine;
- mFactory = factory;
- }
-
- public Query<S> orderBy(String property)
- throws FetchException, UnsupportedOperationException
- {
- return mEngine.getOrderedQuery(getFilterValues(), property);
- }
-
- public Query<S> orderBy(String... properties)
- throws FetchException, UnsupportedOperationException
- {
- return mEngine.getOrderedQuery(getFilterValues(), properties);
- }
-
- public Cursor<S> fetch() throws FetchException {
- return mFactory.openCursor(getFilterValues());
- }
-
- public long count() throws FetchException {
- return mFactory.count(getFilterValues());
- }
-
- public boolean printNative(Appendable app, int indentLevel) throws IOException {
- return mFactory.printNative(app, indentLevel, getFilterValues());
- }
-
- public boolean printPlan(Appendable app, int indentLevel) throws IOException {
- return mFactory.printPlan(app, indentLevel, getFilterValues());
- }
-
- protected BaseQuery<S> newInstance(FilterValues<S> values) {
- return new CompiledQuery<S>
- (getRepository(), getStorage(), values, getOrderings(), mEngine, mFactory);
- }
- }
-
- private static interface CursorFactory<S extends Storable> {
- Cursor<S> openCursor(FilterValues<S> values) throws FetchException;
-
- long count(FilterValues<S> values) throws FetchException;
-
- /**
- * Append filter rules to the given filter.
- *
- * @param filter initial filter, might be null.
- */
- Filter<S> buildFilter(Filter<S> filter);
-
- /**
- * Applies an ordering to the given query in a new query.
- */
- Query<S> applyOrderBy(Query<S> query) throws FetchException;
-
- /**
- * Returns the storage object that this factory needs to use. Usually,
- * this is the same as the primary. If multiple storages are needed,
- * then null is returned. In either case, if the storage is not the
- * primary, then this factory cannot be used. Use the factory from
- * getActualFactory instead.
- */
- Storage<S> getActualStorage();
-
- /**
- * Returns another instance of this factory that uses the proper
- * storage.
- */
- CursorFactory<S> getActualFactory() throws FetchException;
-
- /**
- * @param values optional
- */
- boolean printNative(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException;
-
- /**
- * @param values optional
- */
- boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException;
- }
-
- private abstract static class AbstractCursorFactory<S extends Storable>
- implements CursorFactory<S>
- {
- protected final BaseQueryEngine<S> mEngine;
-
- AbstractCursorFactory(BaseQueryEngine<S> engine) {
- mEngine = engine;
- }
-
- public long count(FilterValues<S> values) throws FetchException {
- Cursor<S> cursor = openCursor(values);
- try {
- long count = cursor.skipNext(Integer.MAX_VALUE);
- if (count == Integer.MAX_VALUE) {
- int amt;
- while ((amt = cursor.skipNext(Integer.MAX_VALUE)) > 0) {
- count += amt;
- }
- }
- return count;
- } finally {
- cursor.close();
- }
- }
-
- public CursorFactory<S> getActualFactory() throws FetchException {
- Storage<S> storage = getActualStorage();
- if (storage == mEngine.getStorage()) {
- return this;
- }
- return new QueryCursorFactory<S>(this, storage);
- }
-
- public boolean printNative(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- return false;
- }
-
- void indent(Appendable app, int indentLevel) throws IOException {
- for (int i=0; i<indentLevel; i++) {
- app.append(' ');
- }
- }
- }
-
- private static class IndexCursorFactory<S extends Storable>
- extends AbstractCursorFactory<S>
- {
- protected final StorableIndex<S> mIndex;
-
- private final boolean mReverseOrder;
- private final boolean mReverseRange;
- private final Filter<S> mExactFilter;
- private final PropertyFilter<S>[] mInclusiveRangeStartFilters;
- private final PropertyFilter<S>[] mExclusiveRangeStartFilters;
- private final PropertyFilter<S>[] mInclusiveRangeEndFilters;
- private final PropertyFilter<S>[] mExclusiveRangeEndFilters;
-
- IndexCursorFactory(BaseQueryEngine<S> engine,
- StorableIndex<S> index,
- boolean reverseOrder,
- boolean reverseRange,
- Filter<S> exactFilter,
- PropertyFilter<S>[] inclusiveRangeStartFilters,
- PropertyFilter<S>[] exclusiveRangeStartFilters,
- PropertyFilter<S>[] inclusiveRangeEndFilters,
- PropertyFilter<S>[] exclusiveRangeEndFilters)
- {
- super(engine);
- mIndex = index;
- mExactFilter = exactFilter;
- mReverseOrder = reverseOrder;
- mReverseRange = reverseRange;
- mInclusiveRangeStartFilters = inclusiveRangeStartFilters;
- mExclusiveRangeStartFilters = exclusiveRangeStartFilters;
- mInclusiveRangeEndFilters = inclusiveRangeEndFilters;
- mExclusiveRangeEndFilters = exclusiveRangeEndFilters;
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- Object[] exactValues = null;
- Object rangeStartValue = null;
- Object rangeEndValue = null;
- BoundaryType rangeStartBoundary = BoundaryType.OPEN;
- BoundaryType rangeEndBoundary = BoundaryType.OPEN;
-
- if (values != null) {
- if (mExactFilter != null) {
- exactValues = values.getValuesFor(mExactFilter);
- }
-
- // In determining the proper range values and boundary types,
- // the order in which this code runs is important. The exclusive
- // filters must be checked before the inclusive filters.
-
- for (PropertyFilter<S> p : mExclusiveRangeStartFilters) {
- Object value = values.getValue(p);
- if (rangeStartBoundary == BoundaryType.OPEN ||
- compareWithNullHigh(value, rangeStartValue) > 0)
- {
- rangeStartValue = value;
- rangeStartBoundary = BoundaryType.EXCLUSIVE;
- }
- }
-
- for (PropertyFilter<S> p : mInclusiveRangeStartFilters) {
- Object value = values.getValue(p);
- if (rangeStartBoundary == BoundaryType.OPEN ||
- compareWithNullHigh(value, rangeStartValue) > 0)
- {
- rangeStartValue = value;
- rangeStartBoundary = BoundaryType.INCLUSIVE;
- }
- }
-
- for (PropertyFilter<S> p : mExclusiveRangeEndFilters) {
- Object value = values.getValue(p);
- if (rangeEndBoundary == BoundaryType.OPEN ||
- compareWithNullHigh(value, rangeEndValue) < 0)
- {
- rangeEndValue = value;
- rangeEndBoundary = BoundaryType.EXCLUSIVE;
- }
- }
-
- for (PropertyFilter<S> p : mInclusiveRangeEndFilters) {
- Object value = values.getValue(p);
- if (rangeEndBoundary == BoundaryType.OPEN ||
- compareWithNullHigh(value, rangeEndValue) < 0)
- {
- rangeEndValue = value;
- rangeEndBoundary = BoundaryType.INCLUSIVE;
- }
- }
- }
-
- return mEngine.openCursor(mIndex, exactValues,
- rangeStartBoundary, rangeStartValue,
- rangeEndBoundary, rangeEndValue,
- mReverseRange,
- mReverseOrder);
- }
-
- public Filter<S> buildFilter(Filter<S> filter) {
- if (mExactFilter != null) {
- filter = filter == null ? mExactFilter : filter.and(mExactFilter);
- }
- for (PropertyFilter<S> p : mInclusiveRangeStartFilters) {
- filter = filter == null ? p : filter.and(p);
- }
- for (PropertyFilter<S> p : mExclusiveRangeStartFilters) {
- filter = filter == null ? p : filter.and(p);
- }
- for (PropertyFilter<S> p : mInclusiveRangeEndFilters) {
- filter = filter == null ? p : filter.and(p);
- }
- for (PropertyFilter<S> p : mExclusiveRangeEndFilters) {
- filter = filter == null ? p : filter.and(p);
- }
- return filter;
- }
-
- public Query<S> applyOrderBy(Query<S> query) throws FetchException {
- if (mIndex == null) {
- // Index is null if this is a full scan with no ordering specified.
- return query;
- }
-
- int count = mIndex.getPropertyCount();
- String[] orderBy = new String[count];
-
- for (int i=0; i<count; i++) {
- String propName = mIndex.getProperty(i).getName();
- Direction dir = mIndex.getPropertyDirection(i);
- if (mReverseOrder) {
- dir = dir.reverse();
- }
- if (dir == Direction.ASCENDING) {
- propName = "+".concat(propName);
- } else if (dir == Direction.DESCENDING) {
- propName = "-".concat(propName);
- }
- orderBy[i] = propName;
- }
-
- return query.orderBy(orderBy);
- }
-
- public Storage<S> getActualStorage() {
- return mEngine.getStorageFor(mIndex);
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- if (mReverseOrder) {
- app.append("reverse ");
- }
- if (mIndex.isClustered()) {
- app.append("clustered ");
- }
- app.append("index scan: ");
- app.append(mEngine.getStorableInfo().getStorableType().getName());
- app.append('\n');
- indent(app, indentLevel);
- app.append("...index: ");
- mIndex.appendTo(app);
- app.append('\n');
- if (mExactFilter != null) {
- indent(app, indentLevel);
- app.append("...exact filter: ");
- mExactFilter.appendTo(app, values);
- app.append('\n');
- }
- if (mInclusiveRangeStartFilters.length > 0 || mExclusiveRangeStartFilters.length > 0 ||
- mInclusiveRangeEndFilters.length > 0 || mExclusiveRangeEndFilters.length > 0)
- {
- indent(app, indentLevel);
- app.append("...range filter: ");
- int count = 0;
- for (PropertyFilter<S> p : mExclusiveRangeStartFilters) {
- if (count++ > 0) {
- app.append(" & ");
- }
- p.appendTo(app, values);
- }
- for (PropertyFilter<S> p : mInclusiveRangeStartFilters) {
- if (count++ > 0) {
- app.append(" & ");
- }
- p.appendTo(app, values);
- }
- for (PropertyFilter<S> p : mExclusiveRangeEndFilters) {
- if (count++ > 0) {
- app.append(" & ");
- }
- p.appendTo(app, values);
- }
- for (PropertyFilter<S> p : mInclusiveRangeEndFilters) {
- if (count++ > 0) {
- app.append(" & ");
- }
- p.appendTo(app, values);
- }
- app.append('\n');
- }
- return true;
- }
- }
-
- private static class FullScanCursorFactory<S extends Storable> extends IndexCursorFactory<S> {
- FullScanCursorFactory(BaseQueryEngine<S> engine, StorableIndex<S> index) {
- super(engine, index, false, false,
- null, NO_FILTERS, NO_FILTERS, NO_FILTERS, NO_FILTERS);
- }
-
- @Override
- public Filter<S> buildFilter(Filter<S> filter) {
- // Full scan doesn't filter anything.
- return filter;
- }
-
- @Override
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- app.append("full scan: ");
- app.append(mEngine.getStorableInfo().getStorableType().getName());
- app.append('\n');
- return true;
- }
- }
-
- private static class KeyCursorFactory<S extends Storable> extends AbstractCursorFactory<S> {
- private final StorableIndex<S> mIndex;
- private final Filter<S> mExactFilter;
-
- KeyCursorFactory(BaseQueryEngine<S> engine,
- StorableIndex<S> index, Filter<S> exactFilter) {
- super(engine);
- mIndex = index;
- mExactFilter = exactFilter;
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- return mEngine.openKeyCursor(mIndex, values.getValuesFor(mExactFilter));
- }
-
- public Filter<S> buildFilter(Filter<S> filter) {
- if (mExactFilter != null) {
- filter = filter == null ? mExactFilter : filter.and(mExactFilter);
- }
- return filter;
- }
-
- public Query<S> applyOrderBy(Query<S> query) {
- return query;
- }
-
- public Storage<S> getActualStorage() {
- return mEngine.getStorageFor(mIndex);
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- app.append("index key: ");
- app.append(mEngine.getStorableInfo().getStorableType().getName());
- app.append('\n');
- indent(app, indentLevel);
- app.append("...index: ");
- mIndex.appendTo(app);
- app.append('\n');
- indent(app, indentLevel);
- app.append("...exact filter: ");
- mExactFilter.appendTo(app, values);
- app.append('\n');
- return true;
- }
- }
-
- private static class FilteredCursorFactory<S extends Storable>
- extends AbstractCursorFactory<S>
- {
- private final CursorFactory<S> mFactory;
- private final Filter<S> mFilter;
-
- FilteredCursorFactory(BaseQueryEngine<S> engine,
- CursorFactory<S> factory, Filter<S> filter) {
- super(engine);
- mFactory = factory;
- mFilter = filter;
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- return FilteredCursor.applyFilter(mFilter,
- values,
- mFactory.openCursor(values));
- }
-
- public Filter<S> buildFilter(Filter<S> filter) {
- filter = mFactory.buildFilter(filter);
- filter = filter == null ? mFilter : filter.and(mFilter);
- return filter;
- }
-
- public Query<S> applyOrderBy(Query<S> query) throws FetchException {
- return mFactory.applyOrderBy(query);
- }
-
- public Storage<S> getActualStorage() {
- return mFactory.getActualStorage();
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- app.append("filter: ");
- mFilter.appendTo(app, values);
- app.append('\n');
- mFactory.printPlan(app, indentLevel + 2, values);
- return true;
- }
- }
-
- private static class SortedCursorFactory<S extends Storable> extends AbstractCursorFactory<S> {
- private final CursorFactory<S> mFactory;
- private final OrderedProperty<S>[] mHandledOrderings;
- private final OrderedProperty<S>[] mRemainderOrderings;
-
- private final Comparator<S> mHandledComparator;
- private final Comparator<S> mFinisherComparator;
-
- SortedCursorFactory(BaseQueryEngine<S> engine,
- CursorFactory<S> factory,
- OrderedProperty<S>[] handledOrderings,
- OrderedProperty<S>[] remainderOrderings) {
- super(engine);
- mFactory = factory;
- if (handledOrderings != null && handledOrderings.length == 0) {
- handledOrderings = null;
- }
- if (remainderOrderings != null && remainderOrderings.length == 0) {
- remainderOrderings = null;
- }
- if (handledOrderings == null && remainderOrderings == null) {
- throw new IllegalArgumentException();
- }
- mHandledOrderings = handledOrderings;
- mRemainderOrderings = remainderOrderings;
-
- mHandledComparator = engine.makeComparator(handledOrderings);
- mFinisherComparator = engine.makeComparator(remainderOrderings);
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- Cursor<S> cursor = mFactory.openCursor(values);
-
- SortBuffer<S> buffer = new MergeSortBuffer<S>
- (getActualStorage(), mEngine.mMergeSortTempDir);
-
- return new SortedCursor<S>(cursor, buffer, mHandledComparator, mFinisherComparator);
- }
-
- @Override
- public long count(FilterValues<S> values) throws FetchException {
- return mFactory.count(values);
- }
-
-
- public Filter<S> buildFilter(Filter<S> filter) {
- return mFactory.buildFilter(filter);
- }
-
- public Query<S> applyOrderBy(Query<S> query) throws FetchException {
- int handledLength = mHandledOrderings == null ? 0 : mHandledOrderings.length;
- int remainderLength = mRemainderOrderings == null ? 0 : mRemainderOrderings.length;
- String[] orderBy = new String[handledLength + remainderLength];
- int pos = 0;
- for (int i=0; i<handledLength; i++) {
- orderBy[pos++] = mHandledOrderings[i].toString();
- }
- for (int i=0; i<remainderLength; i++) {
- orderBy[pos++] = mRemainderOrderings[i].toString();
- }
- return query.orderBy(orderBy);
- }
-
- public Storage<S> getActualStorage() {
- return mFactory.getActualStorage();
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- if (mHandledOrderings == null) {
- app.append("full sort: ");
- } else {
- app.append("finish sort: ");
- }
- app.append(Arrays.toString(mRemainderOrderings));
- app.append('\n');
- mFactory.printPlan(app, indentLevel + 2, values);
- return true;
- }
- }
-
- private static class UnionedCursorFactory<S extends Storable>
- extends AbstractCursorFactory<S>
- {
- static <S extends Storable> CursorFactory<S> createUnion
- (BaseQueryEngine<S> engine,
- List<CursorFactory<S>> factories,
- OrderedProperty<S>[] totalOrderings)
- {
- Comparator<S> orderComparator = engine.makeComparator(totalOrderings);
- return createUnion(engine, factories, totalOrderings, orderComparator);
- }
-
- @SuppressWarnings("unchecked")
- static <S extends Storable> CursorFactory<S> createUnion
- (BaseQueryEngine<S> engine,
- List<CursorFactory<S>> factories,
- OrderedProperty<S>[] totalOrderings,
- Comparator<S> orderComparator)
- {
- if (factories.size() > 1) {
- CursorFactory<S>[] array = new CursorFactory[factories.size()];
- factories.toArray(array);
- return new UnionedCursorFactory<S>(engine, array, totalOrderings, orderComparator);
- }
- return factories.get(0);
- }
-
- private final CursorFactory<S>[] mFactories;
- private final OrderedProperty<S>[] mTotalOrderings;
- private final Comparator<S> mOrderComparator;
-
- private UnionedCursorFactory(BaseQueryEngine<S> engine,
- CursorFactory<S>[] factories,
- OrderedProperty<S>[] totalOrderings,
- Comparator<S> orderComparator) {
- super(engine);
- mFactories = factories;
- mTotalOrderings = totalOrderings;
- mOrderComparator = orderComparator;
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- Cursor<S> cursor = null;
- for (CursorFactory<S> factory : mFactories) {
- Cursor<S> subCursor = factory.openCursor(values);
- cursor = (cursor == null) ? subCursor
- : new UnionCursor<S>(cursor, subCursor, mOrderComparator);
- }
- return cursor;
- }
-
- public Filter<S> buildFilter(Filter<S> filter) {
- for (CursorFactory<S> factory : mFactories) {
- Filter<S> subFilter = factory.buildFilter(null);
- filter = filter == null ? subFilter : filter.or(subFilter);
- }
- return filter;
- }
-
- public Query<S> applyOrderBy(Query<S> query) throws FetchException {
- if (mTotalOrderings == null || mTotalOrderings.length == 0) {
- return query;
- }
-
- String[] orderBy = new String[mTotalOrderings.length];
- for (int i=mTotalOrderings.length; --i>=0; ) {
- orderBy[i] = mTotalOrderings[i].toString();
- }
-
- return query.orderBy(orderBy);
- }
-
- public Storage<S> getActualStorage() {
- Storage<S> storage = null;
- for (CursorFactory<S> factory : mFactories) {
- Storage<S> subStorage = factory.getActualStorage();
- if (storage == null) {
- storage = subStorage;
- } else if (storage != subStorage) {
- return null;
- }
- }
- return storage;
- }
-
- @Override
- public CursorFactory<S> getActualFactory() throws FetchException {
- Storage<S> requiredStorage = getActualStorage();
- if (requiredStorage == mEngine.getStorage()) {
- // Alternate not really needed.
- return this;
- }
- if (requiredStorage != null) {
- // All components require same external storage, so let
- // external storage do the union.
- return new QueryCursorFactory<S>(this, requiredStorage);
- }
-
- // Group factories by required storage instance, and then create a
- // union of unions.
-
- Comparator<CursorFactory<S>> comparator = new Comparator<CursorFactory<S>>() {
- public int compare(CursorFactory<S> a, CursorFactory<S> b) {
- Storage<S> aStorage = a.getActualStorage();
- Storage<S> bStorage = b.getActualStorage();
- if (aStorage == bStorage) {
- return 0;
- }
- Storage<S> engineStorage = mEngine.getStorage();
- if (aStorage == engineStorage) {
- return -1;
- } else if (bStorage == engineStorage) {
- return 1;
- }
- int aHash = System.identityHashCode(a);
- int bHash = System.identityHashCode(b);
- if (aHash < bHash) {
- return -1;
- } else if (aHash > bHash) {
- return 1;
- }
- return 0;
- }
- };
-
- Arrays.sort(mFactories, comparator);
-
- List<CursorFactory<S>> masterList = new ArrayList<CursorFactory<S>>();
-
- List<CursorFactory<S>> subList = new ArrayList<CursorFactory<S>>();
- Storage<S> group = null;
- for (CursorFactory<S> factory : mFactories) {
- Storage<S> storage = factory.getActualStorage();
- if (group != storage) {
- if (subList.size() > 0) {
- masterList.add(createUnion
- (mEngine, subList, mTotalOrderings, mOrderComparator));
- subList.clear();
- }
- group = storage;
- }
- CursorFactory<S> subFactory = new QueryCursorFactory<S>(factory, storage);
- subList.add(subFactory);
- }
- if (subList.size() > 0) {
- masterList.add(createUnion(mEngine, subList, mTotalOrderings, mOrderComparator));
- subList.clear();
- }
-
- return createUnion(mEngine, masterList, mTotalOrderings, mOrderComparator);
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- indent(app, indentLevel);
- app.append("union");
- app.append('\n');
- for (CursorFactory<S> factory : mFactories) {
- factory.printPlan(app, indentLevel + 2, values);
- }
- return true;
- }
- }
-
- /**
- * CursorFactory implementation that reconstructs and calls an external
- * Query.
- */
- private static class QueryCursorFactory<S extends Storable> implements CursorFactory<S> {
- private final CursorFactory<S> mFactory;
- private final Storage<S> mStorage;
- private final Query<S> mQuery;
-
- /**
- * @param factory factory to derive this factory from
- * @param storage actual storage to query against
- */
- QueryCursorFactory(CursorFactory<S> factory, Storage<S> storage) throws FetchException {
- mFactory = factory;
- mStorage = storage;
-
- Filter<S> filter = factory.buildFilter(null);
-
- Query<S> query;
- if (filter == null) {
- query = storage.query();
- } else {
- query = storage.query(filter);
- }
-
- mQuery = factory.applyOrderBy(query);
- }
-
- public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
- return applyFilterValues(values).fetch();
- }
-
- public long count(FilterValues<S> values) throws FetchException {
- return applyFilterValues(values).count();
- }
-
- public Filter<S> buildFilter(Filter<S> filter) {
- return mFactory.buildFilter(filter);
- }
-
- public Query<S> applyOrderBy(Query<S> query) throws FetchException {
- return mFactory.applyOrderBy(query);
- }
-
- public Storage<S> getActualStorage() {
- return mStorage;
- }
-
- public CursorFactory<S> getActualFactory() {
- return this;
- }
-
- public boolean printNative(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- return applyFilterValues(values).printNative(app, indentLevel);
- }
-
- public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
- throws IOException
- {
- Query<S> query;
- try {
- query = applyFilterValues(values);
- } catch (IllegalStateException e) {
- query = mQuery;
- }
- return query.printPlan(app, indentLevel);
- }
-
- private Query<S> applyFilterValues(FilterValues<S> values) {
- // FIXME: figure out how to transfer values directly to query.
-
- Query<S> query = mQuery;
- Filter<S> filter = query.getFilter();
- // FIXME: this code can get confused if filter has constants.
- if (values != null && filter != null && query.getBlankParameterCount() != 0) {
- query = query.withValues(values.getValuesFor(filter));
- }
- return query;
- }
- }
-
- private static class IndexAnalysis<S extends Storable> extends Visitor<S, Object, Object>
- implements Comparable<IndexAnalysis<?>>
- {
- private final StorableIndex<S> mPrimaryKeyIndex;
- private final StorableIndexSet<S> mIndexSet;
- private final OrderedProperty<S>[] mOrderings;
-
- private List<IndexSelector.IndexFitness<S>> mResults;
-
- IndexAnalysis(StorableIndex<S> primaryKeyIndex,
- StorableIndexSet<S> indexSet,
- OrderedProperty<S>[] orderings)
- {
- mPrimaryKeyIndex = primaryKeyIndex;
- mIndexSet = indexSet;
- mOrderings = orderings;
- mResults = new ArrayList<IndexSelector.IndexFitness<S>>();
- }
-
- public Object visit(OrFilter<S> filter, Object param) {
- Filter<S> left = filter.getLeftFilter();
- if (!(left instanceof OrFilter)) {
- selectIndex(left);
- } else {
- left.accept(this, param);
- }
- Filter<S> right = filter.getRightFilter();
- if (!(right instanceof OrFilter)) {
- selectIndex(right);
- } else {
- right.accept(this, param);
- }
- return null;
- }
-
- // This method should only be called if root filter has no 'or' operators.
- public Object visit(AndFilter<S> filter, Object param) {
- selectIndex(filter);
- return null;
- }
-
- // This method should only be called if root filter has no logical operators.
- public Object visit(PropertyFilter<S> filter, Object param) {
- selectIndex(filter);
- return null;
- }
-
- /**
- * Compares this analysis to another which belongs to a different
- * Storable type. Filters that reference a joined property may be best
- * served by an index defined in the joined type, and this method aids
- * in that selection.
- *
- * @return <0 if these results are better, 0 if equal, or >0 if other is better
- */
- public int compareTo(IndexAnalysis<?> otherAnalysis) {
- if (noBestIndex()) {
- if (otherAnalysis.noBestIndex()) {
- return 0;
- }
- return 1;
- } else if (otherAnalysis.noBestIndex()) {
- return -1;
- } else {
- return IndexSelector.listCompare(mResults, otherAnalysis.mResults);
- }
- }
-
- /**
- * If more than one result returned, then a union must be performed.
- * This is because there exist 'or' operators in the full filter.
- */
- List<IndexSelector.IndexFitness<S>> getResults() {
- return mResults;
- }
-
- /**
- * If more than one result, then a union must be performed. Attempt to
- * reduce the result list by performing unions at the index layer. This
- * reduces the number of cursors that need to be opened for a query,
- * eliminating duplicate work.
- */
- void reduceResults() {
- if (mResults.size() <= 1) {
- return;
- }
-
- List<IndexSelector.IndexFitness<S>> reduced =
- new ArrayList<IndexSelector.IndexFitness<S>>(mResults.size());
-
- gather:
- for (int i=0; i<mResults.size(); i++) {
- IndexSelector.IndexFitness fitness = mResults.get(i);
- for (int j=0; j<reduced.size(); j++) {
- IndexSelector.IndexFitness unioned = fitness.union(reduced.get(j));
- if (unioned != null) {
- reduced.set(j, unioned);
- continue gather;
- }
- }
- // Couldn't union with another use of index, so add it to reduced list.
- reduced.add(fitness);
- }
-
- mResults = reduced;
- }
-
- boolean noBestIndex() {
- // Must be an index for each property filter. No point in unioning
- // an index scan with a full scan. Just do a full scan.
- for (IndexSelector.IndexFitness<S> result : mResults) {
- if (result.isUseless()) {
- return true;
- }
- }
- return false;
- }
-
- private void selectIndex(Filter<S> filter) {
- IndexSelector<S> selector = new IndexSelector<S>(filter, mOrderings);
-
- StorableIndex<S> best = mPrimaryKeyIndex;
- if (mIndexSet != null) {
- for (StorableIndex<S> candidate : mIndexSet) {
- int result = selector.compare(best, candidate);
- if (result > 0) {
- best = candidate;
- }
- }
- }
-
- mResults.add(selector.examine(best));
- }
- }
-}
diff --git a/src/main/java/com/amazon/carbonado/spi/IndexSelector.java b/src/main/java/com/amazon/carbonado/spi/IndexSelector.java deleted file mode 100644 index 4f72fdd..0000000 --- a/src/main/java/com/amazon/carbonado/spi/IndexSelector.java +++ /dev/null @@ -1,1205 +0,0 @@ -/*
- * 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.spi;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Comparator;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.LinkedHashMap;
-import java.util.LinkedHashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import com.amazon.carbonado.Storable;
-
-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;
-import com.amazon.carbonado.info.OrderedProperty;
-import com.amazon.carbonado.info.StorableIndex;
-import com.amazon.carbonado.info.StorableProperty;
-
-/**
- * Tries to find the best index to use for a query. When used to sort a list of
- * indexes, the first in the list (the lowest) is the best index.
- *
- * @author Brian S O'Neill
- * @deprecated Use {@link com.amazon.carbonado.qe.CompositeScore}
- */
-public class IndexSelector<S extends Storable> implements Comparator<StorableIndex<S>> {
- static int intCompare(int a, int b) {
- if (a < b) {
- return -1;
- }
- if (a > b) {
- return 1;
- }
- return 0;
- }
-
- // Also called by BaseQueryEngine.
- @SuppressWarnings("unchecked")
- static <E extends Comparable> int listCompare(List<? extends E> a,
- List<? extends E> b) {
- int size = Math.min(a.size(), b.size());
- for (int i=0; i<size; i++) {
- int result = a.get(i).compareTo(b.get(i));
- if (result != 0) {
- return result;
- }
- }
- if (a.size() < size) {
- return -1;
- }
- if (a.size() > size) {
- return 1;
- }
- return 0;
- }
-
- // Original filter passed into constructor
- private final Filter<S> mFilter;
-
- // Elements of original filter, which are combined by logical 'and's. Filters
- // which are likely to remove more results are ordered first in the array.
- final PropertyFilter<S>[] mFilters;
-
- final OrderedProperty<S>[] mOrderings;
-
- /**
- * @param filter filter which cannot contain any logical 'or' operations.
- * @throws IllegalArgumentException if filter not supported
- */
- public IndexSelector(Filter<S> filter) {
- this(filter, (OrderedProperty<S>[]) null);
- }
-
- /**
- * @param filter optional filter which cannot contain any logical 'or' operations.
- * @param orderings optional orderings
- * @throws IllegalArgumentException if filter not supported
- */
- @SuppressWarnings("unchecked")
- public IndexSelector(Filter<S> filter, OrderedProperty<S>... orderings) {
- mFilter = filter;
-
- // Copy property filters.
- final List<PropertyFilter<S>> filterList = new ArrayList<PropertyFilter<S>>();
-
- if (filter != null) {
- filter.accept(new Visitor<S, Object, Object>() {
- public Object visit(OrFilter<S> filter, Object param) {
- throw new IllegalArgumentException("Logical 'or' not allowed");
- }
-
- public Object visit(PropertyFilter<S> filter, Object param) {
- filterList.add(filter);
- return null;
- }
- }, null);
- }
-
- mFilters = filterList.toArray(new PropertyFilter[filterList.size()]);
- // Ensure all '=' operators are first, and all '!=' operators are last.
- Arrays.sort(mFilters, new PropertyFilterComparator<S>());
-
- if (orderings == null || orderings.length == 0) {
- mOrderings = null;
- } else {
- // Copy ordering properties, but don't duplicate properties.
- int length = orderings.length;
- Map<ChainedProperty<S>, OrderedProperty<S>> orderingMap =
- new LinkedHashMap<ChainedProperty<S>, OrderedProperty<S>>(length);
- for (int i=0; i<length; i++) {
- OrderedProperty<S> ordering = orderings[i];
- if (ordering != null) {
- ChainedProperty<S> prop = ordering.getChainedProperty();
- if (!orderingMap.containsKey(prop)) {
- orderingMap.put(prop, ordering);
- }
- }
- }
-
- // Drop orderings against exact matches in filter since they aren't needed.
- for (PropertyFilter<S> propFilter : filterList) {
- if (propFilter.getOperator() == RelOp.EQ) {
- orderingMap.remove(propFilter.getChainedProperty());
- }
- }
-
- mOrderings = orderingMap.values().toArray(new OrderedProperty[orderingMap.size()]);
- }
- }
-
- /**
- * Returns <0 if the current index is better than the candidate index, 0
- * if they are equally good, or >0 if the candidate index is
- * better.
- * <p>
- * Note: the best index may sort results totally reversed. The cursor that
- * uses this index must iterate in reverse to compensate.
- *
- * @param currentIndex current "best" index
- * @param candidateIndex index to test against
- */
- public int compare(StorableIndex<S> currentIndex, StorableIndex<S> candidateIndex) {
- if (currentIndex == null) {
- if (candidateIndex == null) {
- return 0;
- } else {
- return 1;
- }
- } else if (candidateIndex == null) {
- return -1;
- }
-
- IndexScore<S> currentScore = new IndexScore<S>(this, currentIndex);
- IndexScore<S> candidateScore = new IndexScore<S>(this, candidateIndex);
-
- return currentScore.compareTo(candidateScore);
- }
-
- /**
- * Examines the given index for overall fitness.
- */
- public IndexFitness<S> examine(StorableIndex<S> index) {
- return new IndexFitness<S>(this, index, mFilter, mFilters, mOrderings);
- }
-
- /**
- * Provides information regarding the overall fitness of an index for use
- * in a query, and gives us information about how we can properly apply it. That is,
- * if the index provides 3 out of 7 properties, we'll have to scan the output and apply the
- * remaining four by hand. If an index does not sort the property for which we're doing an
- * inexact match, we'll have to subsort -- and so on.
- */
- public static class IndexFitness<S extends Storable> implements Comparable<IndexFitness<?>> {
- private final StorableIndex<S> mIndex;
- private final IndexScore<S> mIndexScore;
-
- private final Filter<S> mExactFilter;
- private final PropertyFilter<S>[] mInclusiveRangeStartFilters;
- private final PropertyFilter<S>[] mExclusiveRangeStartFilters;
- private final PropertyFilter<S>[] mInclusiveRangeEndFilters;
- private final PropertyFilter<S>[] mExclusiveRangeEndFilters;
- private final Filter<S> mRemainderFilter;
-
- private final OrderedProperty<S>[] mHandledOrderings;
- private final OrderedProperty<S>[] mRemainderOrderings;
-
- private final boolean mShouldReverseOrder;
- private final boolean mShouldReverseRange;
-
- @SuppressWarnings("unchecked")
- IndexFitness(IndexSelector<S> selector, StorableIndex<S> index,
- Filter<S> fullFilter, PropertyFilter<S>[] fullFilters,
- OrderedProperty<S>[] fullOrderings)
- {
- mIndex = index;
- mIndexScore = new IndexScore<S>(selector, index);
-
- FilterScore filterScore = mIndexScore.getFilterScore();
-
- Filter<S> exactFilter;
- List<PropertyFilter<S>> inclusiveRangeStartFilters =
- new ArrayList<PropertyFilter<S>>();
- List<PropertyFilter<S>> exclusiveRangeStartFilters =
- new ArrayList<PropertyFilter<S>>();
- List<PropertyFilter<S>> inclusiveRangeEndFilters = new ArrayList<PropertyFilter<S>>();
- List<PropertyFilter<S>> exclusiveRangeEndFilters = new ArrayList<PropertyFilter<S>>();
- Filter<S> remainderFilter;
-
- Direction rangeDirection = null;
- buildFilters: {
- if (fullFilter == null) {
- exactFilter = null;
- remainderFilter = fullFilter;
- break buildFilters;
- }
-
- int exactMatches = filterScore.exactMatches();
- int indexPos = 0;
-
- LinkedList<PropertyFilter<S>> filterList =
- new LinkedList<PropertyFilter<S>>(Arrays.asList(fullFilters));
-
- if (exactMatches <= 0) {
- exactFilter = null;
- } else {
- exactFilter = null;
- // Build filter whose left-to-right property order matches
- // the order of the index.
- for (int i=0; i<exactMatches; i++) {
- StorableProperty<S> indexProp = index.getProperty(indexPos++);
- Filter<S> next = removeIndexProp(filterList, indexProp, RelOp.EQ);
- if (next != null) {
- exactFilter = (exactFilter == null) ? next : exactFilter.and(next);
- }
- }
- }
-
- if (filterScore.hasInexactMatch()) {
- // All matches must be consecutive, so first inexact match
- // is index property after all exact matches.
- StorableProperty<S> indexProp = index.getProperty(indexPos);
- rangeDirection = index.getPropertyDirection(indexPos);
-
- while (true) {
- PropertyFilter<S> p = removeIndexProp(filterList, indexProp, RelOp.GE);
- if (p == null) {
- break;
- }
- inclusiveRangeStartFilters.add(p);
- }
-
- while (true) {
- PropertyFilter<S> p = removeIndexProp(filterList, indexProp, RelOp.GT);
- if (p == null) {
- break;
- }
- exclusiveRangeStartFilters.add(p);
- }
-
- while (true) {
- PropertyFilter<S> p = removeIndexProp(filterList, indexProp, RelOp.LE);
- if (p == null) {
- break;
- }
- inclusiveRangeEndFilters.add(p);
- }
-
- while (true) {
- PropertyFilter<S> p = removeIndexProp(filterList, indexProp, RelOp.LT);
- if (p == null) {
- break;
- }
- exclusiveRangeEndFilters.add(p);
- }
- }
-
- remainderFilter = null;
- while (filterList.size() > 0) {
- Filter<S> next = filterList.removeFirst();
- remainderFilter = (remainderFilter == null) ? next : remainderFilter.and(next);
- }
- }
-
- mExactFilter = exactFilter;
- mInclusiveRangeStartFilters =
- inclusiveRangeStartFilters.toArray(new PropertyFilter[0]);
- mExclusiveRangeStartFilters =
- exclusiveRangeStartFilters.toArray(new PropertyFilter[0]);
- mInclusiveRangeEndFilters = inclusiveRangeEndFilters.toArray(new PropertyFilter[0]);
- mExclusiveRangeEndFilters = exclusiveRangeEndFilters.toArray(new PropertyFilter[0]);
- mRemainderFilter = remainderFilter;
-
- OrderingScore orderingScore = mIndexScore.getOrderingScore();
-
- OrderedProperty<S>[] handledOrderings;
- OrderedProperty<S>[] remainderOrderings;
- boolean shouldReverseOrder;
-
- buildOrderings: {
- int totalMatches = orderingScore.totalMatches();
- if (fullOrderings == null || fullOrderings.length == 0 || totalMatches == 0) {
- handledOrderings = null;
- remainderOrderings = fullOrderings;
- shouldReverseOrder = false;
- break buildOrderings;
- }
-
- shouldReverseOrder = totalMatches < 0;
- totalMatches = Math.abs(totalMatches);
-
- if (totalMatches >= fullOrderings.length) {
- handledOrderings = fullOrderings;
- remainderOrderings = null;
- break buildOrderings;
- }
-
- final int pos = orderingScore.startPosition();
-
- if (index.isUnique() && (pos + totalMatches) >= index.getPropertyCount()) {
- // Since all properties of unique index have been used, additional
- // remainder ordering is superfluous, and so it is handled.
- handledOrderings = fullOrderings;
- remainderOrderings = null;
- break buildOrderings;
- }
-
- Set<OrderedProperty<S>> handledSet = new LinkedHashSet<OrderedProperty<S>>();
- Set<OrderedProperty<S>> remainderSet =
- new LinkedHashSet<OrderedProperty<S>>(Arrays.asList(fullOrderings));
-
- for (int i=0; i<totalMatches; i++) {
- ChainedProperty<S> chainedProp =
- ChainedProperty.get(index.getProperty(pos + i));
- OrderedProperty<S> op;
- op = OrderedProperty.get(chainedProp, Direction.ASCENDING);
- if (remainderSet.remove(op)) {
- handledSet.add(op);
- }
- op = OrderedProperty.get(chainedProp, Direction.DESCENDING);
- if (remainderSet.remove(op)) {
- handledSet.add(op);
- }
- op = OrderedProperty.get(chainedProp, Direction.UNSPECIFIED);
- if (remainderSet.remove(op)) {
- handledSet.add(op);
- }
- }
-
- if (remainderSet.size() == 0) {
- handledOrderings = fullOrderings;
- remainderOrderings = null;
- break buildOrderings;
- }
-
- if (handledSet.size() == 0) {
- handledOrderings = null;
- remainderOrderings = fullOrderings;
- break buildOrderings;
- }
-
- handledOrderings = handledSet.toArray
- (new OrderedProperty[handledSet.size()]);
- remainderOrderings = remainderSet.toArray
- (new OrderedProperty[remainderSet.size()]);
- }
-
- // If using range match, but index direction is backwards. Flipping
- // "shouldReverseOrder" doesn't fix the problem. Instead, swap the
- // ranges around.
- boolean shouldReverseRange = rangeDirection == Direction.DESCENDING;
-
- mHandledOrderings = handledOrderings;
- mRemainderOrderings = remainderOrderings;
- mShouldReverseOrder = shouldReverseOrder;
- mShouldReverseRange = shouldReverseRange;
- }
-
- private IndexFitness(StorableIndex<S> index, IndexScore<S> indexScore,
- Filter<S> exactFilter,
- PropertyFilter<S>[] inclusiveRangeStartFilters,
- PropertyFilter<S>[] exclusiveRangeStartFilters,
- PropertyFilter<S>[] inclusiveRangeEndFilters,
- PropertyFilter<S>[] exclusiveRangeEndFilters,
- Filter<S> remainderFilter,
- OrderedProperty<S>[] handledOrderings,
- OrderedProperty<S>[] remainderOrderings,
- boolean shouldReverseOrder,
- boolean shouldReverseRange)
- {
- mIndex = index;
- mIndexScore = indexScore;
-
- mExactFilter = exactFilter;
- mInclusiveRangeStartFilters = inclusiveRangeStartFilters;
- mExclusiveRangeStartFilters = exclusiveRangeStartFilters;
- mInclusiveRangeEndFilters = inclusiveRangeEndFilters;
- mExclusiveRangeEndFilters = exclusiveRangeEndFilters;
- mRemainderFilter = remainderFilter;
-
- mHandledOrderings = handledOrderings;
- mRemainderOrderings = remainderOrderings;
-
- mShouldReverseOrder = shouldReverseOrder;
- mShouldReverseRange = shouldReverseRange;
- }
-
- private PropertyFilter<S> removeIndexProp(List<PropertyFilter<S>> filterList,
- StorableProperty<S> indexProp,
- RelOp operator)
- {
- Iterator<PropertyFilter<S>> it = filterList.iterator();
- while (it.hasNext()) {
- PropertyFilter<S> filter = it.next();
-
- if (operator != filter.getOperator()) {
- continue;
- }
-
- ChainedProperty<S> chainedProp = filter.getChainedProperty();
- if (chainedProp.getChainCount() == 0) {
- StorableProperty<S> prime = chainedProp.getPrimeProperty();
- if (indexProp.equals(prime)) {
- it.remove();
- return filter;
- }
- }
- }
- return null;
- }
-
- /**
- * Returns the index that this fitness object applies to.
- */
- public StorableIndex<S> getIndex() {
- return mIndex;
- }
-
- /**
- * Returns true if the index doesn't actually do anything to filter
- * results or to order them.
- */
- public boolean isUseless() {
- return mExactFilter == null
- && mInclusiveRangeStartFilters.length == 0
- && mExclusiveRangeStartFilters.length == 0
- && mInclusiveRangeEndFilters.length == 0
- && mExclusiveRangeEndFilters.length == 0
- && (mHandledOrderings == null || mHandledOrderings.length == 0);
- }
-
- /**
- * Returns true if the index results should be iterated in reverse.
- */
- public boolean shouldReverseOrder() {
- return mShouldReverseOrder;
- }
-
- /**
- * Returns true if start and end ranges should be reversed.
- */
- public boolean shouldReverseRange() {
- return mShouldReverseRange;
- }
-
- /**
- * Returns the filter handled by the applicable index for exact
- * matches. Is null if none.
- */
- public Filter<S> getExactFilter() {
- return mExactFilter;
- }
-
- /**
- * Returns true if index is unique and exact filter matches each index
- * property. Using this index guarantees one fetch result.
- */
- public boolean isKeyFilter() {
- if (mExactFilter == null || !mIndex.isUnique()) {
- return false;
- }
-
- final Set<StorableProperty<S>> properties;
- {
- int propertyCount = mIndex.getPropertyCount();
- properties = new HashSet<StorableProperty<S>>(propertyCount);
- for (int i=0; i<propertyCount; i++) {
- properties.add(mIndex.getProperty(i));
- }
- }
-
- mExactFilter.accept(new Visitor<S, Object, Object>() {
- public Object visit(PropertyFilter<S> filter, Object param) {
- ChainedProperty<S> chained = filter.getChainedProperty();
- if (chained.getChainCount() == 0) {
- properties.remove(chained.getPrimeProperty());
- }
- return null;
- }
- }, null);
-
- return properties.size() == 0;
- }
-
- /**
- * Returns the filters handled by the applicable index for range
- * matches. All property names are the same and operator is GE.
- */
- public PropertyFilter<S>[] getInclusiveRangeStartFilters() {
- return mInclusiveRangeStartFilters;
- }
-
- /**
- * Returns the filters handled by the applicable index for range
- * matches. All property names are the same and operator is GT.
- */
- public PropertyFilter<S>[] getExclusiveRangeStartFilters() {
- return mExclusiveRangeStartFilters;
- }
-
- /**
- * Returns the filters handled by the applicable index for range
- * matches. All property names are the same and operator is LE.
- */
- public PropertyFilter<S>[] getInclusiveRangeEndFilters() {
- return mInclusiveRangeEndFilters;
- }
-
- /**
- * Returns the filters handled by the applicable index for range
- * matches. All property names are the same and operator is LT.
- */
- public PropertyFilter<S>[] getExclusiveRangeEndFilters() {
- return mExclusiveRangeEndFilters;
- }
-
- /**
- * Returns a filter which contains terms not handled by the applicable
- * index. If the selector has no filter or if the index is complete,
- * null is returned. If the index filters nothing required by the
- * selector, the complete filter is returned.
- */
- public Filter<S> getRemainderFilter() {
- return mRemainderFilter;
- }
-
- /**
- * Returns the desired orderings handled by the applicable index,
- * possibly when reversed.
- */
- public OrderedProperty<S>[] getHandledOrderings() {
- return (mHandledOrderings == null) ? null : mHandledOrderings.clone();
- }
-
- /**
- * Returns desired orderings not handled by the applicable index,
- * possibly when reversed. If the selector has no ordering or the index
- * is complete, null is returned. If the index orders nothing required
- * by the selector, the complete reduced ordering is returned.
- */
- public OrderedProperty<S>[] getRemainderOrderings() {
- return (mRemainderOrderings == null) ? null : mRemainderOrderings.clone();
- }
-
- /**
- * Returns the orderings actually provided by the applicable index,
- * possibly when reversed. Natural order is not a total order unless
- * index is unique.
- */
- public OrderedProperty<S>[] getNaturalOrderings() {
- return getActualOrderings(false);
- }
-
- /**
- * Returns the orderings actually provided by the applicable index,
- * excluding exact filter matches, possibly when reversed. Effective
- * order is not a total order unless index is unique.
- */
- public OrderedProperty<S>[] getEffectiveOrderings() {
- return getActualOrderings(true);
- }
-
- @SuppressWarnings("unchecked")
- private OrderedProperty<S>[] getActualOrderings(boolean excludeExactMatches) {
- int exactMatches = 0;
- if (excludeExactMatches) {
- exactMatches = mIndexScore.getFilterScore().exactMatches();
- }
-
- int count = mIndex.getPropertyCount();
- OrderedProperty<S>[] orderings = new OrderedProperty[count - exactMatches];
- for (int i=exactMatches; i<count; i++) {
- StorableProperty<S> property = mIndex.getProperty(i);
- Direction direction = mIndex.getPropertyDirection(i);
- if (mShouldReverseOrder) {
- direction = direction.reverse();
- }
- orderings[i - exactMatches] = OrderedProperty.get(property, direction);
- }
- return orderings;
- }
-
- /**
- * Compares this fitness to another which belongs to a different
- * Storable type. Filters that reference a joined property may be best
- * served by an index defined in the joined type, and this method aids
- * in that selection.
- *
- * @return <0 if this score is better, 0 if equal, or >0 if other is better
- */
- public int compareTo(IndexFitness<?> otherFitness) {
- return mIndexScore.compareTo(otherFitness.mIndexScore);
- }
-
- /**
- * Returns true if given fitness result uses the same index, and in the
- * same way.
- */
- public boolean canUnion(IndexFitness fitness) {
- if (this == fitness) {
- return true;
- }
-
- return mIndex.equals(fitness.mIndex) &&
- (mExactFilter == null ?
- fitness.mExactFilter == null :
- (mExactFilter.equals(fitness.mExactFilter))) &&
- Arrays.equals(mInclusiveRangeStartFilters,
- fitness.mInclusiveRangeStartFilters) &&
- Arrays.equals(mExclusiveRangeStartFilters,
- fitness.mExclusiveRangeStartFilters) &&
- Arrays.equals(mInclusiveRangeEndFilters,
- fitness.mInclusiveRangeEndFilters) &&
- Arrays.equals(mExclusiveRangeEndFilters,
- fitness.mExclusiveRangeEndFilters) &&
- mShouldReverseOrder == fitness.mShouldReverseOrder &&
- mShouldReverseRange == fitness.mShouldReverseRange &&
- (mHandledOrderings == null ?
- fitness.mHandledOrderings == null :
- (Arrays.equals(mHandledOrderings, fitness.mHandledOrderings)));
- }
-
- /**
- * If the given fitness can union with this one, return a new unioned
- * one. If union not possible, null is returned.
- */
- public IndexFitness union(IndexFitness fitness) {
- if (this == fitness) {
- return this;
- }
-
- if (!canUnion(fitness)) {
- return null;
- }
-
- // Union the remainder filter and orderings.
-
- Filter<S> remainderFilter;
- if (mRemainderFilter == null) {
- if (fitness.mRemainderFilter == null) {
- remainderFilter = null;
- } else {
- remainderFilter = fitness.mRemainderFilter;
- }
- } else {
- if (fitness.mRemainderFilter == null) {
- remainderFilter = mRemainderFilter;
- } else if (mRemainderFilter.equals(fitness.mRemainderFilter)) {
- remainderFilter = mRemainderFilter;
- } else {
- remainderFilter = mRemainderFilter.or(fitness.mRemainderFilter);
- }
- }
-
- OrderedProperty<S>[] remainderOrderings;
- if (mRemainderOrderings == null) {
- if (fitness.mRemainderOrderings == null) {
- remainderOrderings = null;
- } else {
- remainderOrderings = fitness.mRemainderOrderings;
- }
- } else {
- if (fitness.mRemainderOrderings == null) {
- remainderOrderings = mRemainderOrderings;
- } else if (mRemainderOrderings.length >= fitness.mRemainderOrderings.length) {
- remainderOrderings = mRemainderOrderings;
- } else {
- remainderOrderings = fitness.mRemainderOrderings;
- }
- }
-
- return new IndexFitness<S>(mIndex, mIndexScore,
- mExactFilter,
- mInclusiveRangeStartFilters,
- mExclusiveRangeStartFilters,
- mInclusiveRangeEndFilters,
- mExclusiveRangeEndFilters,
- remainderFilter,
- mHandledOrderings,
- remainderOrderings,
- mShouldReverseOrder,
- mShouldReverseRange);
- }
-
- public String toString() {
- return "IndexFitness [index=" + mIndex
- + ", filterScore=" + mIndexScore.getFilterScore()
- + ", orderingScore=" + mIndexScore.getOrderingScore()
- + ", exactFilter=" + quoteNonNull(mExactFilter)
- + ", inclusiveRangeStartFilters=" + mInclusiveRangeStartFilters
- + ", exclusiveRangeStartFilters=" + mExclusiveRangeStartFilters
- + ", inclusiveRangeEndFilters=" + mInclusiveRangeEndFilters
- + ", exclusiveRangeEndFilters=" + mExclusiveRangeEndFilters
- + ", remainderFilter=" + quoteNonNull(mRemainderFilter)
- + ", handledOrderings=" + Arrays.toString(mHandledOrderings)
- + ", remainderOrderings=" + Arrays.toString(mRemainderOrderings)
- + ", shouldReverse=" + mShouldReverseOrder
- + ']';
- }
-
- private static String quoteNonNull(Filter value) {
- return value == null ? null : ('"' + String.valueOf(value) + '"');
- }
- }
-
- /**
- * Composite of filter score and ordering score. The filter score measures
- * how well an index performs the desired level of filtering. Likewise, the
- * ordering score measures how well an index performs the desired ordering.
- */
- private static class IndexScore<S extends Storable> implements Comparable<IndexScore<?>> {
- private final IndexSelector<S> mSelector;
- private final StorableIndex<S> mIndex;
-
- private FilterScore<S> mFilterScore;
- private OrderingScore mOrderingScore;
-
- IndexScore(IndexSelector<S> selector, StorableIndex<S> index) {
- mSelector = selector;
- mIndex = index;
- }
-
- @SuppressWarnings("unchecked")
- public int compareTo(IndexScore<?> candidateScore) {
- final FilterScore thisFilterScore = this.getFilterScore();
- final FilterScore candidateFilterScore = candidateScore.getFilterScore();
-
- // Compare total count of exact matching properties.
- {
- int result = thisFilterScore.compareExact(candidateFilterScore);
- if (result != 0) {
- return result;
- }
- }
-
- // Exact matches same, choose clustered index if more than one match.
- if (thisFilterScore.exactMatches() > 1) {
- if (mIndex.isClustered()) {
- if (!candidateScore.mIndex.isClustered()) {
- return -1;
- }
- } else if (candidateScore.mIndex.isClustered()) {
- return 1;
- }
- }
-
- // Compare range match. (index can have at most one range match)
- if (thisFilterScore.hasRangeMatch()) {
- if (candidateFilterScore.hasRangeMatch()) {
- // Both have range match, choose clustered index.
- if (mIndex.isClustered()) {
- if (!candidateScore.mIndex.isClustered()) {
- return -1;
- }
- } else if (candidateScore.mIndex.isClustered()) {
- return 1;
- }
- } else {
- return -1;
- }
- } else if (candidateFilterScore.hasRangeMatch()) {
- return 1;
- }
-
- final OrderingScore thisOrderingScore = this.getOrderingScore();
- final OrderingScore candidateOrderingScore = candidateScore.getOrderingScore();
-
- int finalResult = 0;
-
- // Compare orderings, but only if candidate filters anything. It is
- // generally slower to scan an index just for correct ordering,
- // than it is to sort the results of a full scan. Why? Because an
- // index scan results in a lot of random file accesses, and disk is
- // so slow. There is an exception to this rule if the candidate is
- // a clustered index, in which case there are no random file
- // accesses.
- if (candidateFilterScore.anyMatches() || candidateScore.mIndex.isClustered()) {
- int currentMatches = thisOrderingScore.totalMatches();
- int candidateMatches = candidateOrderingScore.totalMatches();
- if (currentMatches != candidateMatches) {
- if (Math.abs(currentMatches) > Math.abs(candidateMatches)) {
- // Only select current filter if it filters anything.
- if (thisFilterScore.anyMatches()) {
- return -1;
- }
- // Potentially use this result later.
- finalResult = -1;
- } else if (Math.abs(currentMatches) < Math.abs(candidateMatches)) {
- return 1;
- } else {
- // Magnitudes are equal, but sign differs. Choose positive,
- // but not yet.
- finalResult = (currentMatches > 0) ? -1 : 1;
- }
- }
- }
-
- // Compare total count of inexact matching properties.
- {
- int result = thisFilterScore.compareInexact(candidateFilterScore);
- if (result != 0) {
- return result;
- }
- }
-
- // Compare positioning of matching properties (favor index that best
- // matches specified property sequence of filter)
- {
- int result = thisFilterScore.compareExactPositions(candidateFilterScore);
- if (result != 0) {
- return result;
- }
- result = thisFilterScore.compareInexactPosition(candidateFilterScore);
- if (result != 0) {
- return result;
- }
- }
-
- // If both indexes have a non-zero score (that is, either index would
- // actually be useful), choose the one that has the least number of
- // properties in it. The theory being that smaller index keys mean more
- // nodes will fit into the memory cache during an index scan. This
- // extra test doesn't try to estimate the average size of properties,
- // so it may choose wrong.
- {
- if ((thisFilterScore.anyMatches() && candidateFilterScore.anyMatches()) ||
- (thisOrderingScore.anyMatches() && candidateOrderingScore.anyMatches()))
- {
- if (mIndex.getPropertyCount() < candidateScore.mIndex.getPropertyCount()) {
- return -1;
- }
- if (mIndex.getPropertyCount() > candidateScore.mIndex.getPropertyCount()) {
- return 1;
- }
- }
- }
-
- // Final result derived from ordering comparison earlier.
- return finalResult;
- }
-
- /**
- * Total matches on score indicates how many consecutive index
- * properties (from the start) match the filter requirements.
- */
- public FilterScore<S> getFilterScore() {
- if (mFilterScore != null) {
- return mFilterScore;
- }
-
- mFilterScore = new FilterScore<S>();
-
- int indexPropCount = mIndex.getPropertyCount();
- PropertyFilter<S>[] filters = mSelector.mFilters;
- int filterCount = filters.length;
-
- for (int i=0; i<indexPropCount; i++) {
- StorableProperty<S> prop = mIndex.getProperty(i);
- int matchesBefore = mFilterScore.totalMatches();
- for (int pos=0; pos<filterCount; pos++) {
- mFilterScore.tally(prop, filters[pos], pos);
- }
- if (mFilterScore.totalMatches() <= matchesBefore) {
- // Missed an index property and cannot have holes in index.
- break;
- }
- }
-
- return mFilterScore;
- }
-
- public OrderingScore getOrderingScore() {
- if (mOrderingScore != null) {
- return mOrderingScore;
- }
-
- OrderedProperty<S>[] orderings = mSelector.mOrderings;
-
- if (orderings == null || orderings.length == 0) {
- return mOrderingScore = new OrderingScore(0, 0);
- }
-
- int indexPropCount = mIndex.getPropertyCount();
- if (indexPropCount <= 0) {
- return mOrderingScore = new OrderingScore(0, 0);
- }
-
- // Make sure first ordering property follows exact matches.
-
- if (orderings[0].getChainedProperty().getChainCount() > 0) {
- // Indexes don't currently support chained properties.
- return mOrderingScore = new OrderingScore(0, 0);
- }
-
- final StorableProperty<S> first =
- orderings[0].getChainedProperty().getPrimeProperty();
-
- // Start pos after all exact matching filter properties
- int pos = getFilterScore().exactMatches();
-
- if (pos >= indexPropCount || !mIndex.getProperty(pos).equals(first)) {
- return mOrderingScore = new OrderingScore(0, 0);
- }
-
- boolean reverse = false;
- switch (mIndex.getPropertyDirection(pos)) {
- case ASCENDING:
- reverse = (orderings[0].getDirection() == Direction.DESCENDING);
- break;
- case DESCENDING:
- reverse = (orderings[0].getDirection() == Direction.ASCENDING);
- break;
- }
-
- // Match count is the run length of matching properties.
- int matches = 1;
- final int startPos = pos;
-
- calcMatches:
- for (int i=1; i<orderings.length && ++pos<indexPropCount; i++) {
- if (orderings[i].getChainedProperty().getChainCount() > 0) {
- // Indexes don't currently support chained properties.
- break;
- }
-
- if (mIndex.getProperty(pos).equals
- (orderings[i].getChainedProperty().getPrimeProperty())) {
- if (orderings[i].getDirection() != Direction.UNSPECIFIED) {
- Direction expected = mIndex.getPropertyDirection(pos);
- if (reverse) {
- expected = expected.reverse();
- }
- if (orderings[i].getDirection() != expected) {
- break calcMatches;
- }
- }
- matches++;
- }
- }
-
- return mOrderingScore = new OrderingScore(startPos, reverse ? -matches : matches);
- }
- }
-
- /**
- * One of the scores that evaluates an index's fitness for a given filter.
- * <P>A filter mentions properties, either as exact ("=") or inexact (">" "<", et al)
- * <P>An index contains properties, in order.
- * <P>An index property matches a filter if the filter uses that property, and if all of the
- * properties in the index to the left of the property are also in the filter (since holes
- * in the index make the index useless for subsequent properties)
- * <P>Then the index filter score is a function of the number of matches it contains,
- * and how early in the filter they appear.
- * <P>Any exact filter match beats an inexact filter.
- * <P>More exact filter matches beats fewer.
- * <P>Inexact will be selected if there are no exact matches
- *
- * <P>Note that there will be only one inexact match, since once we're in an inexact range we
- * have to scan the entire range (and a later inexact match will be arbitrarily ordered within
- * that range).
- *
- * <P>For example:
- * <pre>
- * user query: "a>? & b=? & c = ?"
- * will be presorted to
- * "b=? & c=? & a>?
- * a, b, c == a[inexact]->2, b->0, c->1
- * d, a, b, c == useless
- * c, d, b == c->1
- * </pre>
- * ...so the "c,d,b" index will win.
- */
- private static class FilterScore<S extends Storable> {
- // Positions of exact matches
- private List<Integer> mExactMatches = new ArrayList<Integer>();
-
- // Properties which have been used for exact matching -- these should
- // show up only once per filter set
- private Set<StorableProperty> mExactMatchProps = new HashSet<StorableProperty>();
-
- // Position of inexact match
- private int mInexactMatchPos;
-
- // Property used for inexact match
- private StorableProperty<S> mInexactMatch;
-
- private boolean mHasRangeStart;
- private boolean mHasRangeEnd;
-
- FilterScore() {
- }
-
- /**
- * Tally up filter score.
- *
- * @param prop property of candidate index
- * @param filter property filter to check for index fitness
- * @param pos position of filter in filter list
- */
- void tally(StorableProperty<S> prop, PropertyFilter<S> filter, int pos) {
- ChainedProperty<S> chained = filter.getChainedProperty();
-
- if (chained.getChainCount() == 0 && chained.getPrimeProperty().equals(prop)) {
- switch (filter.getOperator()) {
- case EQ:
- // Exact match
- if (mInexactMatch == null) {
- mExactMatches.add(pos);
- mExactMatchProps.add(prop);
- }
-
- break;
-
- case LT: case GE: case GT: case LE:
- // Inexact match
-
- if (mInexactMatch == null) {
- // If for some reason the query contains an exact and
- // an inexact match on the same property (a>1 & a=14)
- // we'll never care about the inexact match.
- if (!mExactMatchProps.contains(prop)) {
- mInexactMatchPos = pos;
- mInexactMatch = prop;
- }
- }
-
- // Check for range match
- if (prop.equals(mInexactMatch)) {
- switch (filter.getOperator()) {
- case LT: case LE:
- mHasRangeStart = true;
- break;
- case GT: case GE:
- mHasRangeEnd = true;
- break;
- }
- }
-
- break;
- }
- }
- }
-
- int compareExact(FilterScore<S> candidate) {
- return -intCompare(mExactMatches.size(), candidate.mExactMatches.size());
- }
-
- int compareInexact(FilterScore<S> candidate) {
- if (mInexactMatch == null && candidate.mInexactMatch != null) {
- return 1;
- } else if (mInexactMatch != null && candidate.mInexactMatch == null) {
- return -1;
- }
- return 0;
- }
-
- int compareExactPositions(FilterScore<S> candidate) {
- return listCompare(mExactMatches, candidate.mExactMatches);
- }
-
- int compareInexactPosition(FilterScore<S> candidate) {
- return intCompare(mInexactMatchPos, candidate.mInexactMatchPos);
- }
-
- boolean anyMatches() {
- return mExactMatches.size() > 0 || mInexactMatch != null;
- }
-
- int exactMatches() {
- return mExactMatches.size();
- }
-
- boolean hasRangeMatch() {
- return mHasRangeStart && mHasRangeEnd;
- }
-
- boolean hasInexactMatch() {
- return mInexactMatch != null;
- }
-
- int totalMatches() {
- return mExactMatches.size() + (mInexactMatch == null ? 0 : 1);
- }
-
- public String toString() {
- return "FilterScore [exactMatches=" + mExactMatches
- + ", exactMatchProps=" + mExactMatchProps
- + ", inexactMatch=" + (mInexactMatch == null ? null : mInexactMatch.getName())
- + ", rangeMatch=" + hasRangeMatch()
- + ']';
- }
- }
-
- /**
- * How well does this index help me sort things
- */
- private static class OrderingScore {
- private final int mStartPos;
- private final int mTotalMatches;
-
- OrderingScore(int startPos, int totalMatches) {
- mStartPos = startPos;
- mTotalMatches = totalMatches;
- }
-
- /**
- * Returns start position of index.
- */
- int startPosition() {
- return mStartPos;
- }
-
- boolean anyMatches() {
- return mTotalMatches > 0;
- }
-
- /**
- * Magnitude represents count of matching orderings. If negative
- * result, index produces reversed ordering.
- */
- int totalMatches() {
- return mTotalMatches;
- }
-
- public String toString() {
- return "OrderingScore [startPos=" + mStartPos
- + ", totalMatches=" + mTotalMatches
- + ']';
- }
- }
-
- /**
- * Sorts property filters such that '==' operations come before '!='
- * operations. Assuming a stable sort is used, all other property filters
- * are left in place
- */
- private static class PropertyFilterComparator<S extends Storable>
- implements Comparator<PropertyFilter<S>>
- {
- public int compare(PropertyFilter<S> a, PropertyFilter<S> b) {
- if (a.getOperator() != b.getOperator()) {
- if (a.getOperator() == RelOp.EQ) {
- return -1;
- }
- if (a.getOperator() == RelOp.NE) {
- return 1;
- }
- if (b.getOperator() == RelOp.EQ) {
- return 1;
- }
- if (b.getOperator() == RelOp.NE) {
- return -1;
- }
- }
- return 0;
- }
- }
-}
|