From b53f2a2c22a5cda5801cc48e230d31b12c3adfc8 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Wed, 30 Aug 2006 02:13:43 +0000 Subject: Add new query engine --- .../com/amazon/carbonado/qe/AbstractQuery.java | 144 +++++ .../amazon/carbonado/qe/AbstractQueryExecutor.java | 91 +++ .../carbonado/qe/ArraySortedQueryExecutor.java | 52 ++ .../java/com/amazon/carbonado/qe/BoundaryType.java | 33 + .../com/amazon/carbonado/qe/CompositeScore.java | 187 ++++++ .../carbonado/qe/DelegatedQueryExecutor.java | 131 ++++ .../java/com/amazon/carbonado/qe/EmptyQuery.java | 279 +++++++++ .../amazon/carbonado/qe/FilteredQueryExecutor.java | 90 +++ .../com/amazon/carbonado/qe/FilteringScore.java | 677 +++++++++++++++++++++ .../carbonado/qe/FullScanIndexedQueryExecutor.java | 87 +++ .../amazon/carbonado/qe/FullScanQueryExecutor.java | 86 +++ .../com/amazon/carbonado/qe/IndexProvider.java | 37 ++ .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 480 +++++++++++++++ .../amazon/carbonado/qe/IndexedQueryExecutor.java | 266 ++++++++ .../amazon/carbonado/qe/IterableQueryExecutor.java | 48 ++ .../amazon/carbonado/qe/JoinedQueryExecutor.java | 230 +++++++ .../com/amazon/carbonado/qe/KeyQueryExecutor.java | 111 ++++ .../com/amazon/carbonado/qe/OrderingScore.java | 455 ++++++++++++++ .../amazon/carbonado/qe/PropertyFilterList.java | 120 ++++ .../com/amazon/carbonado/qe/QueryExecutor.java | 87 +++ .../amazon/carbonado/qe/SortedQueryExecutor.java | 142 +++++ .../amazon/carbonado/qe/UnionQueryAnalyzer.java | 238 ++++++++ .../amazon/carbonado/qe/UnionQueryExecutor.java | 123 ++++ .../java/com/amazon/carbonado/qe/package-info.java | 24 + 24 files changed, 4218 insertions(+) create mode 100644 src/main/java/com/amazon/carbonado/qe/AbstractQuery.java create mode 100644 src/main/java/com/amazon/carbonado/qe/AbstractQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/ArraySortedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/BoundaryType.java create mode 100644 src/main/java/com/amazon/carbonado/qe/CompositeScore.java create mode 100644 src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/EmptyQuery.java create mode 100644 src/main/java/com/amazon/carbonado/qe/FilteredQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/FilteringScore.java create mode 100644 src/main/java/com/amazon/carbonado/qe/FullScanIndexedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/IndexProvider.java create mode 100644 src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java create mode 100644 src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/OrderingScore.java create mode 100644 src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java create mode 100644 src/main/java/com/amazon/carbonado/qe/QueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java create mode 100644 src/main/java/com/amazon/carbonado/qe/UnionQueryExecutor.java create mode 100644 src/main/java/com/amazon/carbonado/qe/package-info.java (limited to 'src/main/java/com') diff --git a/src/main/java/com/amazon/carbonado/qe/AbstractQuery.java b/src/main/java/com/amazon/carbonado/qe/AbstractQuery.java new file mode 100644 index 0000000..4549151 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/AbstractQuery.java @@ -0,0 +1,144 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; +import java.lang.reflect.UndeclaredThrowableException; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.FetchMultipleException; +import com.amazon.carbonado.FetchNoneException; +import com.amazon.carbonado.PersistException; +import com.amazon.carbonado.PersistNoneException; +import com.amazon.carbonado.Query; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; + +import com.amazon.carbonado.info.OrderedProperty; + +import com.amazon.carbonado.util.Appender; + +/** + * AbstractQuery implements a small set of common Query methods. Subclasses + * should consider overriding some of these methods, if it provides better + * performance. + * + * @author Brian S O'Neill + */ +public abstract class AbstractQuery implements Query, Appender { + 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 and(String filter) throws FetchException { + return and(Filter.filterFor(getStorableType(), filter)); + } + + public Query or(String filter) throws FetchException { + return or(Filter.filterFor(getStorableType(), filter)); + } + + public S loadOne() throws FetchException { + S obj = tryLoadOne(); + if (obj == null) { + throw new FetchNoneException(toString()); + } + return obj; + } + + public S tryLoadOne() throws FetchException { + Cursor cursor = fetch(); + try { + if (cursor.hasNext()) { + S obj = cursor.next(); + if (cursor.hasNext()) { + throw new FetchMultipleException(toString()); + } + return obj; + } else { + return null; + } + } finally { + cursor.close(); + } + } + + public void deleteOne() throws PersistException { + if (!tryDeleteOne()) { + throw new PersistNoneException(toString()); + } + } + + public boolean printNative() { + try { + return printNative(System.out); + } catch (IOException e) { + // Shouldn't happen since PrintStream suppresses exceptions. + throw new UndeclaredThrowableException(e); + } + } + + public boolean printNative(Appendable app) throws IOException { + return printNative(app, 0); + } + + public boolean printPlan() { + try { + return printPlan(System.out); + } catch (IOException e) { + // Shouldn't happen since PrintStream suppresses exceptions. + throw new UndeclaredThrowableException(e); + } + } + + public boolean printPlan(Appendable app) throws IOException { + return printPlan(app, 0); + } + + /** + * Implementation calls appendTo. + */ + @Override + public String toString() { + StringBuilder b = new StringBuilder(); + try { + appendTo(b); + } catch (IOException e) { + // Not gonna happen + } + return b.toString(); + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/AbstractQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/AbstractQueryExecutor.java new file mode 100644 index 0000000..01b4c57 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/AbstractQueryExecutor.java @@ -0,0 +1,91 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.FilterValues; + +/** + * AbstractQueryExecutor implements a small set of common QueryExecutor methods. + * + * @author Brian S O'Neill + */ +public abstract class AbstractQueryExecutor implements QueryExecutor { + public Class getStorableType() { + return getFilter().getStorableType(); + } + + /** + * Counts results by opening a cursor and skipping entries. + */ + public long count(FilterValues values) throws FetchException { + Cursor 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(); + } + } + + /** + * Does nothing and returns false. + */ + public boolean printNative(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + return false; + } + + /** + * Appends spaces to the given appendable. Useful for implementing + * printNative and printPlan. + */ + protected void indent(Appendable app, int indentLevel) throws IOException { + for (int i=0; i extends SortedQueryExecutor { + /** + * @param executor executor to wrap + * @throws IllegalArgumentException if executor is null or if remainder + * orderings is empty + */ + public ArraySortedQueryExecutor(QueryExecutor executor, + List> handledOrderings, + List> remainderOrderings) + { + super(executor, handledOrderings, remainderOrderings); + } + + protected SortBuffer createSortBuffer() { + return new ArraySortBuffer(); + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/BoundaryType.java b/src/main/java/com/amazon/carbonado/qe/BoundaryType.java new file mode 100644 index 0000000..753b17f --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/BoundaryType.java @@ -0,0 +1,33 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +/** + * Describes a value range boundary. + * + * @author Brian S O'Neill + */ +public enum BoundaryType { + /** Range boundary is open */ + OPEN, + /** Range boundary is inclusive */ + INCLUSIVE, + /** Range boundary is exclusive */ + EXCLUSIVE; +} diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java new file mode 100644 index 0000000..7028c54 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -0,0 +1,187 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.Comparator; +import java.util.List; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; + +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Evaluates an index for how well it matches a query's desired filtering and + * ordering. A composite score is not a single absolute value \u2013 instead it + * has a relative weight when compared to other scores. + * + * @author Brian S O'Neill + * @see FilteringScore + * @see OrderingScore + */ +public class CompositeScore { + /** + * Evaluates the given index for its filtering and ordering capabilities + * against the given filter and order-by properties. + * + * @param index index to evaluate + * @param filter optional filter which cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static CompositeScore evaluate(StorableIndex index, + Filter filter, + OrderedProperty... orderings) + { + if (index == null) { + throw new IllegalArgumentException("Index required"); + } + + return evaluate(index.getOrderedProperties(), + index.isUnique(), + index.isClustered(), + filter, + orderings); + } + + /** + * Evaluates the given index properties for its filtering and ordering + * capabilities against the given filter and order-by properties. + * + * @param indexProperties index properties to evaluate + * @param unique true if index is unique + * @param clustered true if index is clustered + * @param filter optional filter which cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static CompositeScore evaluate + (OrderedProperty[] indexProperties, + boolean unique, + boolean clustered, + Filter filter, + OrderedProperty... orderings) + { + FilteringScore filteringScore = FilteringScore + .evaluate(indexProperties, unique, clustered, filter); + + OrderingScore orderingScore = OrderingScore + .evaluate(indexProperties, unique, clustered, filter, orderings); + + return new CompositeScore(filteringScore, orderingScore); + } + + /** + * Returns a comparator which determines which CompositeScores are + * better. It compares identity matches, range matches, ordering, open + * range matches, property arrangement and index cost estimate. It does not + * matter if the scores were evaluated for different indexes or storable + * types. The comparator returns {@code <0} if first score is better, + * {@code 0} if equal, or {@code >0} if second is better. + */ + public static Comparator> fullComparator() { + return Full.INSTANCE; + } + + private final FilteringScore mFilteringScore; + private final OrderingScore mOrderingScore; + + private CompositeScore(FilteringScore filteringScore, OrderingScore orderingScore) { + mFilteringScore = filteringScore; + mOrderingScore = orderingScore; + } + + /** + * Returns the score on how well the evaluated index performs the desired + * filtering. + */ + public FilteringScore getFilteringScore() { + return mFilteringScore; + } + + /** + * Returns the score on how well the evaluated index performs the desired + * ordering. + */ + public OrderingScore getOrderingScore() { + return mOrderingScore; + } + + /** + * Returns true if the filtering score can merge its remainder filter and + * the ordering score can merge its remainder orderings. + */ + public boolean canMergeRemainder(CompositeScore other) { + return getFilteringScore().canMergeRemainderFilter(other.getFilteringScore()) + && getOrderingScore().canMergeRemainderOrderings(other.getOrderingScore()); + } + + /** + * Merges the remainder filter of this score with the one given using an + * 'or' operation. Call canMergeRemainder first to verify if the merge + * makes any sense. + */ + public Filter mergeRemainderFilter(CompositeScore other) { + return getFilteringScore().mergeRemainderFilter(other.getFilteringScore()); + } + + /** + * Merges the remainder orderings of this score with the one given. Call + * canMergeRemainder first to verify if the merge makes any sense. + */ + public List> mergeRemainderOrderings(CompositeScore other) { + return getOrderingScore().mergeRemainderOrderings(other.getOrderingScore()); + } + + public String toString() { + return "CompositeScore {" + getFilteringScore() + ", " + getOrderingScore() + '}'; + } + + private static class Full implements Comparator> { + static final Comparator> INSTANCE = new Full(); + + public int compare(CompositeScore first, CompositeScore second) { + int result = FilteringScore.nullCompare(first, second); + if (result != 0) { + return result; + } + + result = FilteringScore.rangeComparator() + .compare(first.getFilteringScore(), second.getFilteringScore()); + + if (result != 0) { + return result; + } + + result = OrderingScore.fullComparator() + .compare(first.getOrderingScore(), second.getOrderingScore()); + + if (result != 0) { + return result; + } + + result = FilteringScore.fullComparator() + .compare(first.getFilteringScore(), second.getFilteringScore()); + + return result; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutor.java new file mode 100644 index 0000000..8bde825 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutor.java @@ -0,0 +1,131 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Query; +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.Storage; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * QueryExecutor which delegates by executing a Query on a Storage. + * + * @author Brian S O'Neill + */ +public class DelegatedQueryExecutor implements QueryExecutor { + private final QueryExecutor mExecutor; + private final Storage mStorage; + private final Query mQuery; + + /** + * @param executor executor to emulate + * @param storage storage to query + * @throws IllegalArgumentException if any parameter is null + */ + public DelegatedQueryExecutor(QueryExecutor executor, Storage storage) + throws FetchException + { + if (executor == null || storage == null) { + throw new IllegalStateException(); + } + + mExecutor = executor; + mStorage = storage; + + Filter filter = executor.getFilter(); + + Query query; + if (filter == null) { + query = storage.query(); + } else { + query = storage.query(filter); + } + + List> ordering = executor.getOrdering(); + if (ordering.size() > 0) { + String[] orderBy = new String[ordering.size()]; + for (int i=0; i getStorableType() { + return mStorage.getStorableType(); + } + + public Cursor openCursor(FilterValues values) throws FetchException { + return applyFilterValues(values).fetch(); + } + + public long count(FilterValues values) throws FetchException { + return applyFilterValues(values).count(); + } + + public Filter getFilter() { + return mExecutor.getFilter(); + } + + public List> getOrdering() { + return mExecutor.getOrdering(); + } + + public boolean printNative(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + return applyFilterValues(values).printNative(app, indentLevel); + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + Query query; + try { + query = applyFilterValues(values); + } catch (IllegalStateException e) { + query = mQuery; + } + return query.printPlan(app, indentLevel); + } + + private Query applyFilterValues(FilterValues values) { + // FIXME: figure out how to transfer values directly to query. + + Query query = mQuery; + Filter 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; + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java new file mode 100644 index 0000000..60b027f --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java @@ -0,0 +1,279 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.IsolationLevel; +import com.amazon.carbonado.PersistNoneException; +import com.amazon.carbonado.Storage; +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.Query; + +import com.amazon.carbonado.cursor.EmptyCursor; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * Special query implementation that fetches nothing. + * + * @author Brian S O'Neill + */ +public final class EmptyQuery extends AbstractQuery { + private final Storage mStorage; + + // Properties that this query is ordered by. + private final String[] mOrderings; + + /** + * @param storage required storage object + * @param orderings optional order-by properties + */ + public EmptyQuery(Storage storage, OrderedProperty[] orderings) { + if (storage == null) { + throw new IllegalArgumentException(); + } + mStorage = storage; + mOrderings = extractOrderingNames(orderings); + } + + /** + * @param storage required storage object + * @param orderings optional order-by properties + */ + public EmptyQuery(Storage storage, String[] orderings) { + if (storage == null) { + throw new IllegalArgumentException(); + } + mStorage = storage; + mOrderings = orderings == null ? EMPTY_ORDERINGS : orderings; + } + + public Class getStorableType() { + return mStorage.getStorableType(); + } + + /** + * Always returns a {@link com.amazon.carbonado.filter.ClosedFilter ClosedFilter}. + */ + public Filter getFilter() { + return Filter.getClosedFilter(mStorage.getStorableType()); + } + + /** + * Always returns null. + */ + public FilterValues getFilterValues() { + return null; + } + + /** + * Always returns zero. + */ + public int getBlankParameterCount() { + return 0; + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(int value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(long value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(float value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(double value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(boolean value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(char value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(byte value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(short value) { + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query with(Object value) { + throw error(); + } + + /** + * Throws an IllegalStateException unless no values passed in. + */ + public Query withValues(Object... values) { + if (values == null || values.length == 0) { + return this; + } + throw error(); + } + + /** + * Always throws an IllegalStateException. + */ + public Query and(Filter filter) { + throw new IllegalStateException("Query is already guaranteed to fetch nothing"); + } + + public Query or(Filter filter) throws FetchException { + return mStorage.query(filter); + } + + public Query not() throws FetchException { + Query query = mStorage.query(); + String[] orderings = mOrderings; + if (orderings.length > 0) { + query = query.orderBy(orderings); + } + return query; + } + + public Query orderBy(String property) throws FetchException { + // This allows property to be checked for validity. + return mStorage.query().orderBy(property).not(); + } + + public Query orderBy(String... properties) throws FetchException { + // This allows properties to be checked for validity. + return mStorage.query().orderBy(properties).not(); + } + + /** + * Always returns an {@link EmptyCursor}. + */ + public Cursor fetch() { + return EmptyCursor.getEmptyCursor(); + } + + /** + * Always returns an {@link EmptyCursor}. + */ + public Cursor fetchAfter(S start) { + return EmptyCursor.getEmptyCursor(); + } + + /** + * Always throws {@link PersistNoneException}. + */ + public void deleteOne() throws PersistNoneException { + throw new PersistNoneException(); + } + + /** + * Always returns false. + */ + public boolean tryDeleteOne() { + return false; + } + + /** + * Does nothing. + */ + public void deleteAll() { + } + + /** + * Always returns zero. + */ + public long count() { + return 0; + } + + public void appendTo(Appendable app) throws IOException { + app.append("Query {type="); + app.append(mStorage.getStorableType().getName()); + app.append(", filter="); + getFilter().appendTo(app); + + if (mOrderings != null && mOrderings.length > 0) { + app.append(", orderBy=["); + for (int i=0; i 0) { + app.append(", "); + } + app.append(mOrderings[i]); + } + app.append(']'); + } + + app.append('}'); + } + + /** + * Always returns false. + */ + public boolean printNative(Appendable app, int indentLevel) { + return false; + } + + /** + * Always returns false. + */ + public boolean printPlan(Appendable app, int indentLevel) { + return false; + } + + private IllegalStateException error() { + return new IllegalStateException("Query doesn't have any parameters"); + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/FilteredQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/FilteredQueryExecutor.java new file mode 100644 index 0000000..4da38d9 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/FilteredQueryExecutor.java @@ -0,0 +1,90 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.cursor.FilteredCursor; + +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.info.OrderedProperty; + +/** + * QueryExecutor which wraps another and filters results. + * + * @author Brian S O'Neill + * @see FilteredCursor + */ +public class FilteredQueryExecutor extends AbstractQueryExecutor { + private final QueryExecutor mExecutor; + private final Filter mFilter; + + /** + * @param executor executor to wrap + * @param filter filter to apply to cursor + * @throws IllegalArgumentException if any argument is null or filter is open or closed + */ + public FilteredQueryExecutor(QueryExecutor executor, Filter filter) { + if (executor == null) { + throw new IllegalArgumentException(); + } + if (filter == null || filter instanceof OpenFilter || filter instanceof ClosedFilter) { + throw new IllegalArgumentException(); + } + mExecutor = executor; + // Ensure filter is same as what will be provided by values. + mFilter = filter.initialFilterValues().getFilter(); + } + + public Cursor openCursor(FilterValues values) throws FetchException { + return FilteredCursor.applyFilter(mFilter, values, mExecutor.openCursor(values)); + } + + /** + * Returns the combined filter of the wrapped executor and the extra filter. + */ + public Filter getFilter() { + return mExecutor.getFilter().and(mFilter); + } + + public List> getOrdering() { + return mExecutor.getOrdering(); + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("filter: "); + mFilter.appendTo(app, values); + newline(app); + mExecutor.printPlan(app, increaseIndent(indentLevel), values); + return true; + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/FilteringScore.java b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java new file mode 100644 index 0000000..5ca9d04 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/FilteringScore.java @@ -0,0 +1,677 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.RelOp; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.Direction; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Evaluates an index for how well it matches a query's desired filtering. A + * filtering score is not a single absolute value \u2013 instead it has a + * relative weight when compared to other scores. + * + *

An index matches a desired filtering if the arrangement of properties and + * its relational operator matches. A matching {@link RelOp#EQ =} operator is + * an identity match. A range match is determined by a matching operator of + * {@link RelOp#GT >}, {@link RelOp#GE >=}, {@link RelOp#LT <}, or {@link + * RelOp#LE <=}. Filters with a {@link RelOp#NE !=} operator are + * ignored. Although not all index properties need to be used, the first must + * be and no gaps are allowed. + * + *

A FilteringScore measures the number of filter properties that are + * matched and the number that are remaining. If there are remainder + * properties, then the user of the evaluated index will need to perform an + * additional filtering operation to achieve the desired results. + * + *

In general, a FilteringScore is better than another if it has more + * matched properties and fewer remainder properties. Matching more identity + * properties is given preference over matching range properties. Index + * clustering is also considered for score comparison. + * + * @author Brian S O'Neill + * @see OrderingScore + * @see CompositeScore + */ +public class FilteringScore { + /** + * Evaluates the given index for its filtering capabilities against the + * given filter. + * + * @param index index to evaluate + * @param filter filter which cannot contain any logical 'or' operations. + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static FilteringScore evaluate(StorableIndex index, + Filter filter) + { + if (index == null) { + throw new IllegalArgumentException("Index required"); + } + + return evaluate(index.getOrderedProperties(), + index.isUnique(), + index.isClustered(), + filter); + } + + /** + * Evaluates the given index properties for its filtering capabilities + * against the given filter. + * + * @param indexProperties index properties to evaluate + * @param unique true if index is unique + * @param clustered true if index is clustered + * @param filter filter which cannot contain any logical 'or' operations. + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static FilteringScore evaluate + (OrderedProperty[] indexProperties, + boolean unique, + boolean clustered, + Filter filter) + { + if (indexProperties == null) { + throw new IllegalArgumentException("Index properties required"); + } + + // List is ordered such that '=' operations are first and '!=' + // operations are last. + List> filterList = PropertyFilterList.get(filter); + + // Copy so it so that matching elements can be removed. + filterList = new ArrayList>(filterList); + + // First find the identity matches. + + List> identityFilters = new ArrayList>(); + int arrangementScore = 0; + + int indexPropPos; + int lastFilterPos = 0; + + identityMatches: + for (indexPropPos = 0; indexPropPos < indexProperties.length; indexPropPos++) { + ChainedProperty indexProp = indexProperties[indexPropPos].getChainedProperty(); + + for (int pos = 0; pos < filterList.size(); pos++) { + PropertyFilter subFilter = filterList.get(pos); + if (subFilter.getOperator() != RelOp.EQ) { + // No more '=' operators will be seen so short-circuit. + break identityMatches; + } + if (subFilter.getChainedProperty().equals(indexProp)) { + identityFilters.add(subFilter); + if (pos >= lastFilterPos) { + arrangementScore++; + } + filterList.remove(pos); + lastFilterPos = pos; + continue identityMatches; + } + } + + // Consecutive index property not used, so stop searching for identity matches. + break identityMatches; + } + + // Index property following identity matches can only be used for + // supporting range matches. Multiple filters may match, but their + // property must be the same as the index property. + + List> rangeStartFilters; + List> rangeEndFilters; + + boolean shouldReverseRange; + + if (indexPropPos >= indexProperties.length) { + rangeStartFilters = Collections.emptyList(); + rangeEndFilters = Collections.emptyList(); + shouldReverseRange = false; + } else { + ChainedProperty indexProp = indexProperties[indexPropPos].getChainedProperty(); + + rangeStartFilters = new ArrayList>(); + rangeEndFilters = new ArrayList>(); + + rangeMatches: + for (int pos = 0; pos < filterList.size(); pos++) { + PropertyFilter subFilter = filterList.get(pos); + RelOp op = subFilter.getOperator(); + + switch (op) { + case NE: + // No more range operators will be seen so short-circuit. + break rangeMatches; + + case GT: case GE: case LT: case LE: + if (subFilter.getChainedProperty().equals(indexProp)) { + switch (op) { + case GT: case GE: + rangeStartFilters.add(subFilter); + break; + default: + rangeEndFilters.add(subFilter); + break; + } + + filterList.remove(pos); + + // Loop correction after removing element. + pos--; + } + break; + } + } + + shouldReverseRange = (rangeStartFilters.size() > 0 || rangeEndFilters.size() > 0) && + indexProperties[indexPropPos].getDirection() == Direction.DESCENDING; + } + + return new FilteringScore(clustered, + unique, + indexProperties.length, + identityFilters, + rangeStartFilters, + rangeEndFilters, + arrangementScore, + filterList, + shouldReverseRange); + } + + /** + * Returns a partial comparator which determines which FilteringScores are + * better by examining only identity and range matches. It does not matter + * if the scores were evaluated for different indexes or storable + * types. The comparator returns {@code <0} if first score is better, + * {@code 0} if equal, or {@code >0} if second is better. + */ + public static Comparator> rangeComparator() { + return Range.INSTANCE; + } + + /** + * Returns a comparator which determines which FilteringScores are + * better. It compares identity matches, range matches, open range matches, + * property arrangement and index cost estimate. It does not matter if the + * scores were evaluated for different indexes or storable types. The + * comparator returns {@code <0} if first score is better, {@code 0} if + * equal, or {@code >0} if second is better. + */ + public static Comparator> fullComparator() { + return Full.INSTANCE; + } + + static List prepareList(List list) { + if (list == null || list.size() == 0) { + return Collections.emptyList(); + } + return Collections.unmodifiableList(list); + } + + /** + * Comparison orders null high. + */ + static int nullCompare(Object first, Object second) { + if (first == null) { + if (second != null) { + return 1; + } + } else if (second == null) { + return -1; + } + return 0; + } + + private final boolean mIndexClustered; + private final boolean mIndexUnique; + private final int mIndexPropertyCount; + + private final List> mIdentityFilters; + + private final List> mRangeStartFilters; + private final List> mRangeEndFilters; + + private final int mArrangementScore; + + private final List> mRemainderFilters; + + private final boolean mShouldReverseRange; + + private transient Filter mIdentityFilter; + private transient Filter mRemainderFilter; + + private FilteringScore(boolean indexClustered, + boolean indexUnique, + int indexPropertyCount, + List> identityFilters, + List> rangeStartFilters, + List> rangeEndFilters, + int arrangementScore, + List> remainderFilters, + boolean shouldReverseRange) + { + mIndexClustered = indexClustered; + mIndexUnique = indexUnique; + mIndexPropertyCount = indexPropertyCount; + mIdentityFilters = prepareList(identityFilters); + mRangeStartFilters = prepareList(rangeStartFilters); + mRangeEndFilters = prepareList(rangeEndFilters); + mArrangementScore = arrangementScore; + mRemainderFilters = prepareList(remainderFilters); + mShouldReverseRange = shouldReverseRange; + } + + /** + * Returns true if evaluated index is clustered. Scans of clustered indexes + * are generally faster. + */ + public boolean isIndexClustered() { + return mIndexClustered; + } + + /** + * Returns true if evaluated index is unique. + */ + public boolean isIndexUnique() { + return mIndexUnique; + } + + /** + * Returns the amount of properties in the evaluated index. + */ + public int getIndexPropertyCount() { + return mIndexPropertyCount; + } + + /** + * Returns number of consecutive left-aligned index properties which match + * property filters with an operator of {@link RelOp#EQ}. + */ + public int getIdentityCount() { + return mIdentityFilters.size(); + } + + /** + * Returns the identity property filters supported by the evaluated + * index. The order of the list matches the order in which the properties + * appear in the index. The operator of each filter is {@link RelOp#EQ}. + */ + public List> getIdentityFilters() { + return mIdentityFilters; + } + + /** + * Returns the composite identity filter, or null if no identity property + * filters. + */ + public Filter getIdentityFilter() { + if (mIdentityFilter == null) { + mIdentityFilter = buildCompositeFilter(getIdentityFilters()); + } + return mIdentityFilter; + } + + /** + * Returns true if any property filter with an operator of {@link RelOp#GT} + * or {@link RelOp#GE} matches an index property. The index property used + * for the range is the first one following the identity count. + */ + public boolean hasRangeStart() { + return mRangeStartFilters.size() > 0; + } + + /** + * Returns the range start property filters supported by the evaluated + * index. The operator of each filter is either {@link RelOp#GT} or {@link + * RelOp#GE}. The property of each filter is identical, and the properties + * are also identical to any range end filters. + */ + public List> getRangeStartFilters() { + return mRangeStartFilters; + } + + /** + * Returns the range start property filters supported by the evaluated + * index whose operator is only {@link RelOp#GT}. This list is a subset of + * those returned by {@link #getRangeStartFilters}. + */ + public List> getExclusiveRangeStartFilters() { + return reduce(getRangeStartFilters(), RelOp.GT); + } + + /** + * Returns the range start property filters supported by the evaluated + * index whose operator is only {@link RelOp#GE}. This list is a subset of + * those returned by {@link #getRangeStartFilters}. + */ + public List> getInclusiveRangeStartFilters() { + return reduce(getRangeStartFilters(), RelOp.GE); + } + + /** + * Returns true if any property filter with an operator of {@link RelOp#LT} + * or {@link RelOp#LE} matches an index property. The index property used + * for the range is the first one following the identity count. + */ + public boolean hasRangeEnd() { + return mRangeEndFilters.size() > 0; + } + + /** + * Returns the range end property filters supported by the evaluated + * index. The operator of each filter is either {@link RelOp#LT} or {@link + * RelOp#LE}. The property of each filter is identical, and the properties + * are also identical to any range start filters. + */ + public List> getRangeEndFilters() { + return mRangeEndFilters; + } + + /** + * Returns the range end property filters supported by the evaluated + * index whose operator is only {@link RelOp#LT}. This list is a subset of + * those returned by {@link #getRangeEndFilters}. + */ + public List> getExclusiveRangeEndFilters() { + return reduce(getRangeEndFilters(), RelOp.LT); + } + + /** + * Returns the range end property filters supported by the evaluated + * index whose operator is only {@link RelOp#LE}. This list is a subset of + * those returned by {@link #getRangeEndFilters}. + */ + public List> getInclusiveRangeEndFilters() { + return reduce(getRangeEndFilters(), RelOp.LE); + } + + /** + * Returns true if there is both a range start and range end. + */ + public boolean hasRangeMatch() { + return hasRangeStart() && hasRangeEnd(); + } + + /** + * Returns true if the identity count is greater than zero or if there is a + * range match. + */ + public boolean hasAnyMatches() { + return getIdentityCount() > 0 || hasRangeStart() || hasRangeEnd(); + } + + /** + * Returns a value which indicates how well the index property order + * matches the property filter specification order. A higher value + * can indicate that the index is a slightly better match. + * + * @return arrangement value, never negative + */ + public int getArrangementScore() { + return mArrangementScore; + } + + /** + * Returns number of property filters not supported by the evaluated index. + */ + public int getRemainderCount() { + return mRemainderFilters.size(); + } + + /** + * Returns the filters not supported by the evaluated index. + */ + public List> getRemainderFilters() { + return mRemainderFilters; + } + + /** + * Returns the composite remainder filter not supported by the evaluated + * index, or null if no remainder. + */ + public Filter getRemainderFilter() { + if (mRemainderFilter == null) { + mRemainderFilter = buildCompositeFilter(getRemainderFilters()); + } + return mRemainderFilter; + } + + /** + * Returns true if evaluated index is unique and each of its properties has + * an identity match. When index and filter are used in a query, expect at + * most one result. + */ + public boolean isKeyMatch() { + return isIndexUnique() && getIndexPropertyCount() == getIdentityCount(); + } + + /** + * Returns true if there is a range start or end match, but natural order + * of matching property is descending. + */ + public boolean shouldReverseRange() { + return mShouldReverseRange; + } + + /** + * Returns true if the given score uses an index exactly the same as this + * one. The only allowed differences are in the remainder filter. + */ + public boolean canMergeRemainderFilter(FilteringScore other) { + if (this == other || (!hasAnyMatches() && !other.hasAnyMatches())) { + return true; + } + + return isIndexClustered() == other.isIndexClustered() + && isIndexUnique() == other.isIndexUnique() + && getIndexPropertyCount() == other.getIndexPropertyCount() + && getArrangementScore() == other.getArrangementScore() + && shouldReverseRange() == other.shouldReverseRange() + // List comparisons assume identical ordering, but this is + // not strictly required. Since the different scores likely + // originated from the same complex filter, the ordering + // likely matches. A set equality test is not needed. + && getIdentityFilters().equals(other.getIdentityFilters()) + && getRangeStartFilters().equals(other.getRangeStartFilters()) + && getRangeEndFilters().equals(other.getRangeEndFilters()); + } + + /** + * Merges the remainder filter of this score with the one given using an + * 'or' operation. Call canMergeRemainderFilter first to verify if the + * merge makes any sense. Returns null if no remainder filter at all. + */ + public Filter mergeRemainderFilter(FilteringScore other) { + Filter thisRemainderFilter = getRemainderFilter(); + + if (this == other) { + return thisRemainderFilter; + } + + Filter otherRemainderFilter = other.getRemainderFilter(); + + if (thisRemainderFilter == null) { + if (otherRemainderFilter == null) { + return null; + } else { + return otherRemainderFilter; + } + } else if (otherRemainderFilter == null) { + return thisRemainderFilter; + } else if (thisRemainderFilter.equals(otherRemainderFilter)) { + return thisRemainderFilter; + } else { + return thisRemainderFilter.or(otherRemainderFilter); + } + } + + public String toString() { + return "FilteringScore {identityCount=" + getIdentityCount() + + ", hasRangeStart=" + hasRangeStart() + + ", hasRangeEnd=" + hasRangeEnd() + + ", remainderCount=" + getRemainderCount() + + '}'; + } + + private List> reduce(List> filters, RelOp op) { + List> reduced = null; + + for (int i=0; i filter = filters.get(i); + if (filter.getOperator() != op) { + if (reduced == null) { + reduced = new ArrayList>(filters.size()); + for (int j=0; j buildCompositeFilter(List> filterList) { + if (filterList.size() == 0) { + return null; + } + Filter composite = filterList.get(0); + for (int i=1; i> { + static final Comparator> INSTANCE = new Range(); + + public int compare(FilteringScore first, FilteringScore second) { + if (first == second) { + return 0; + } + + int result = nullCompare(first, second); + if (result != 0) { + return result; + } + + // Compare identity matches. + if (first.getIdentityCount() > second.getIdentityCount()) { + return -1; + } + if (first.getIdentityCount() < second.getIdentityCount()) { + return 1; + } + + // Compare range match. (index can have at most one range match) + if (first.hasRangeMatch()) { + if (second.hasRangeMatch()) { + // Both have range match, favor clustered index. + if (first.isIndexClustered()) { + if (!second.isIndexClustered()) { + return -1; + } + } else if (second.isIndexClustered()) { + return 1; + } + } else { + return -1; + } + } else if (second.hasRangeMatch()) { + return 1; + } + + // If any identity matches, favor clustered index. + if (first.getIdentityCount() > 0) { + if (first.isIndexClustered()) { + if (!second.isIndexClustered()) { + return -1; + } + } else if (second.isIndexClustered()) { + return 1; + } + } + + return 0; + } + } + + private static class Full implements Comparator> { + static final Comparator> INSTANCE = new Full(); + + public int compare(FilteringScore first, FilteringScore second) { + int result = Range.INSTANCE.compare(first, second); + if (result != 0) { + return result; + } + + // Favor index that has any matches. + if (first.hasAnyMatches()) { + if (!second.hasAnyMatches()) { + return -1; + } + } else if (second.hasAnyMatches()) { + return 1; + } + + // Favor index that best matches specified property arrangement of filter. + if (first.getArrangementScore() > second.getArrangementScore()) { + return -1; + } + if (first.getArrangementScore() < second.getArrangementScore()) { + return 1; + } + + // Favor clustered index. + if (first.isIndexClustered()) { + if (!second.isIndexClustered()) { + return -1; + } + } else if (second.isIndexClustered()) { + return 1; + } + + // Favor index with fewer properties, under the assumption that fewer + // properties means smaller sized records that need to be read in. + if (first.getIndexPropertyCount() < second.getIndexPropertyCount()) { + return -1; + } else if (first.getIndexPropertyCount() > second.getIndexPropertyCount()) { + return 1; + } + + return 0; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/FullScanIndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/FullScanIndexedQueryExecutor.java new file mode 100644 index 0000000..33cd1c2 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/FullScanIndexedQueryExecutor.java @@ -0,0 +1,87 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Abstract QueryExecutor which fully scans all Storables of a given type, + * referencing an index. + * + * @author Brian S O'Neill + */ +public abstract class FullScanIndexedQueryExecutor + extends FullScanQueryExecutor +{ + private static Class getType(StorableIndex index) { + if (index == null) { + throw new IllegalArgumentException(); + } + return index.getStorableType(); + } + + private final StorableIndex mIndex; + + /** + * @param index index to use, which may be a primary key index + * @throws IllegalArgumentException if index is null + */ + public FullScanIndexedQueryExecutor(StorableIndex index) { + super(getType(index)); + mIndex = index; + } + + @Override + public Cursor openCursor(FilterValues values) throws FetchException { + return openCursor(mIndex); + } + + /** + * Returns the natural order of the index. + */ + @Override + public List> getOrdering() { + return Collections.unmodifiableList(Arrays.asList(mIndex.getOrderedProperties())); + } + + protected Cursor openCursor() throws FetchException { + return openCursor(mIndex); + } + + /** + * Return a new Cursor instance referenced by the given index. + * + * @param index index to open, which may be a primary key index + */ + protected abstract Cursor openCursor(StorableIndex index) throws FetchException; +} diff --git a/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java new file mode 100644 index 0000000..e5072ce --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java @@ -0,0 +1,86 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.Collections; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * Abstract QueryExecutor which fully scans all Storables of a given type. + * + * @author Brian S O'Neill + */ +public abstract class FullScanQueryExecutor extends AbstractQueryExecutor { + private final Class mType; + + /** + * @param type type of Storable + * @throws IllegalArgumentException if type is null + */ + public FullScanQueryExecutor(Class type) { + if (type == null) { + throw new IllegalArgumentException(); + } + mType = type; + } + + /** + * Returns an open filter. + */ + public Filter getFilter() { + return Filter.getOpenFilter(mType); + } + + public Cursor openCursor(FilterValues values) throws FetchException { + return openCursor(); + } + + /** + * Returns an empty list. + */ + public List> getOrdering() { + return Collections.emptyList(); + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("full scan: "); + app.append(mType.getName()); + newline(app); + return true; + } + + /** + * Return a new Cursor instance. + */ + protected abstract Cursor openCursor() throws FetchException; +} diff --git a/src/main/java/com/amazon/carbonado/qe/IndexProvider.java b/src/main/java/com/amazon/carbonado/qe/IndexProvider.java new file mode 100644 index 0000000..69277e4 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/IndexProvider.java @@ -0,0 +1,37 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.Collection; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.info.StorableIndex; + +/** + * An index provider is typically a repository implementation. + * + * @author Brian S O'Neill + */ +public interface IndexProvider { + /** + * Returns all the available indexes for the given type. + */ + Collection> indexesFor(Class type); +} diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java new file mode 100644 index 0000000..dfe13cc --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -0,0 +1,480 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.RelOp; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; +import com.amazon.carbonado.info.StorableProperty; + +/** + * Analyzes a simple query specification and determines which index is best + * suited for its execution. Query filters passed to this analyzer cannot + * contain any 'or' operations. + * + *

IndexedQueryAnalyzer is sharable and thread-safe. An instance for a + * particular Storable type can be cached, avoiding repeated construction + * cost. In addition, the analyzer caches learned foreign indexes. + * + * @author Brian S O'Neill + * @see UnionQueryAnalyzer + */ +public class IndexedQueryAnalyzer { + private final Class mType; + private final IndexProvider mIndexProvider; + + // Growable cache which maps join properties to lists of usable foreign indexes. + private Map, ForeignIndexes> mForeignIndexCache; + + /** + * @param type type of storable being queried + * @param indexProvider + * @throws IllegalArgumentException if type or indexProvider is null + */ + public IndexedQueryAnalyzer(Class type, IndexProvider indexProvider) { + if (type == null || indexProvider == null) { + throw new IllegalArgumentException(); + } + mType = type; + mIndexProvider = indexProvider; + } + + public Class getStorableType() { + return mType; + } + + /** + * @param filter optional filter which which must be {@link Filter#isBound + * bound} and cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if filter is not supported + */ + public Result analyze(Filter filter, OrderedProperty... orderings) { + if (!filter.isBound()) { + // Strictly speaking, this is not required, but it detects the + // mistake of not properly calling initialFilterValues. + throw new IllegalArgumentException("Filter must be bound"); + } + + final Comparator> comparator = CompositeScore.fullComparator(); + + // First find best local index. + CompositeScore bestScore = null; + StorableIndex bestLocalIndex = null; + + Collection> localIndexes = mIndexProvider.indexesFor(mType); + if (localIndexes != null) { + for (StorableIndex index : localIndexes) { + CompositeScore candidateScore = + CompositeScore.evaluate(index, filter, orderings); + + if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { + bestScore = candidateScore; + bestLocalIndex = index; + } + } + } + + // Now try to find better foreign index. + StorableIndex bestForeignIndex = null; + ChainedProperty bestForeignProperty = null; + + for (PropertyFilter propFilter : PropertyFilterList.get(filter)) { + ChainedProperty chainedProp = propFilter.getChainedProperty(); + + if (chainedProp.getChainCount() == 0) { + // Cannot possibly be a join, so move on. + continue; + } + + ForeignIndexes foreignIndexes = getForeignIndexes(chainedProp); + if (foreignIndexes == null) { + continue; + } + + for (StorableIndex index : foreignIndexes.mIndexes) { + CompositeScore candidateScore = CompositeScore.evaluate + (foreignIndexes.getVirtualIndex(index), + index.isUnique(), + index.isClustered(), + filter, + orderings); + + if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { + bestScore = candidateScore; + bestLocalIndex = null; + bestForeignIndex = index; + bestForeignProperty = foreignIndexes.mProperty; + } + } + } + + return new Result(filter, + bestScore, + bestLocalIndex, + bestForeignIndex, + bestForeignProperty); + } + + /** + * @return null if no foreign indexes for property + */ + private synchronized ForeignIndexes getForeignIndexes(ChainedProperty chainedProp) { + // Remove the last property as it is expected to be a simple storable + // property instead of a joined Storable. + chainedProp = chainedProp.trim(); + + ForeignIndexes foreignIndexes = null; + if (mForeignIndexCache != null) { + foreignIndexes = mForeignIndexCache.get(chainedProp); + if (foreignIndexes != null || mForeignIndexCache.containsKey(chainedProp)) { + return foreignIndexes; + } + } + + // Check if property chain is properly joined and indexed along the way. + evaluate: { + if (!isProperJoin(chainedProp.getPrimeProperty())) { + break evaluate; + } + + int count = chainedProp.getChainCount(); + for (int i=0; i> indexes = mIndexProvider.indexesFor(foreignType); + + foreignIndexes = new ForeignIndexes(chainedProp, indexes); + } + + if (mForeignIndexCache == null) { + mForeignIndexCache = Collections.synchronizedMap + (new HashMap, ForeignIndexes>()); + } + + mForeignIndexCache.put(chainedProp, foreignIndexes); + + return foreignIndexes; + } + + /** + * Checks if the property is a join and its internal properties are fully + * indexed. + */ + private boolean isProperJoin(StorableProperty property) { + if (!property.isJoin() || property.isQuery()) { + return false; + } + + // Make up a filter over the join's internal properties and then search + // for an index that filters with no remainder. + Filter filter = Filter.getOpenFilter((Class) property.getType()); + int count = property.getJoinElementCount(); + for (int i=0; i boolean simpleAnalyze(Filter filter) { + Collection> indexes = mIndexProvider.indexesFor(filter.getStorableType()); + + if (indexes != null) { + for (StorableIndex index : indexes) { + FilteringScore score = FilteringScore.evaluate(index, filter); + if (score.getRemainderCount() == 0) { + return true; + } + } + } + + return false; + } + + public class Result { + private final Filter mFilter; + + private final CompositeScore mScore; + private final StorableIndex mLocalIndex; + private final StorableIndex mForeignIndex; + private final ChainedProperty mForeignProperty; + + private final Filter mRemainderFilter; + private final List> mRemainderOrderings; + + Result(Filter filter, + CompositeScore score, + StorableIndex localIndex, + StorableIndex foreignIndex, + ChainedProperty foreignProperty) + { + mFilter = filter; + mScore = score; + mLocalIndex = localIndex; + mForeignIndex = foreignIndex; + mForeignProperty = foreignProperty; + mRemainderFilter = score.getFilteringScore().getRemainderFilter(); + mRemainderOrderings = score.getOrderingScore().getRemainderOrderings(); + } + + // Called by mergeRemainder. + private Result(Result result, + Filter remainderFilter, + List> remainderOrderings) + { + mFilter = result.mFilter == null ? remainderFilter + : (remainderFilter == null ? result.mFilter : result.mFilter.or(remainderFilter)); + + mScore = result.mScore; + mLocalIndex = result.mLocalIndex; + mForeignIndex = result.mForeignIndex; + mForeignProperty = result.mForeignProperty; + mRemainderFilter = remainderFilter; + mRemainderOrderings = remainderOrderings; + } + + /** + * Returns true if the selected index does anything at all to filter + * results or to order them. If not, a filtered and sorted full scan + * makes more sense. + */ + public boolean handlesAnything() { + return mScore.getFilteringScore().hasAnyMatches() == true + || mScore.getOrderingScore().getHandledCount() > 0; + } + + /** + * Returns combined handled and remainder filter for this result. + */ + public Filter getFilter() { + return mFilter; + } + + /** + * Returns combined handled and remainder orderings for this result. + */ + public List> getOrderings() { + List> handled = mScore.getOrderingScore().getHandledOrderings(); + List> remainder = getRemainderOrderings(); + + if (handled.size() == 0) { + return remainder; + } + if (remainder.size() == 0) { + return handled; + } + + List> combined = + new ArrayList>(handled.size() + remainder.size()); + + combined.addAll(handled); + combined.addAll(remainder); + + return combined; + } + + /** + * Returns the score on how well the selected index performs the + * desired filtering and ordering. When building a query executor, do + * not use the remainder filter and orderings available in the + * composite score. Instead, get them directly from this result object. + */ + public CompositeScore getCompositeScore() { + return mScore; + } + + /** + * Remainder filter which overrides that in composite score. + */ + public Filter getRemainderFilter() { + return mRemainderFilter; + } + + /** + * Remainder orderings which override that in composite score. + */ + public List> getRemainderOrderings() { + return mRemainderOrderings; + } + + /** + * Returns the local index that was selected, or null if a foreign + * index was selected. + */ + public StorableIndex getLocalIndex() { + return mLocalIndex; + } + + /** + * Returns the foreign index that was selected, or null if a local + * index was selected. If a foreign index has been selected, then a + * {@link JoinedQueryExecutor} is needed. + */ + public StorableIndex getForeignIndex() { + return mForeignIndex; + } + + /** + * Returns the simple or chained property that maps to the selected + * foreign index. Returns null if foreign index was not selected. This + * property corresponds to the "bToAProperty" of {@link + * JoinedQueryExecutor}. + */ + public ChainedProperty getForeignProperty() { + return mForeignProperty; + } + + /** + * Returns true if the given result uses the same index as this, and in + * the same way. The only allowed differences are in the remainder + * filter and orderings. + */ + public boolean canMergeRemainder(Result other) { + if (this == other || (!handlesAnything() && !other.handlesAnything())) { + return true; + } + + if (equals(getLocalIndex(), other.getLocalIndex()) + && equals(getForeignIndex(), other.getForeignIndex()) + && equals(getForeignProperty(), other.getForeignProperty())) + { + return getCompositeScore().canMergeRemainder(other.getCompositeScore()); + } + + return false; + } + + /** + * Merges the remainder filter and orderings of this result with the + * one given, returning a new result. Call canMergeRemainder first to + * verify if the merge makes any sense. + */ + public Result mergeRemainder(Result other) { + if (this == other) { + return this; + } + + return new Result + (this, + getCompositeScore().mergeRemainderFilter(other.getCompositeScore()), + getCompositeScore().mergeRemainderOrderings(other.getCompositeScore())); + } + + /** + * Merges the remainder filter of this result with the given filter, + * returning a new result. If handlesAnything return true, then it + * doesn't make sense to call this method. + */ + public Result mergeRemainder(Filter filter) { + Filter remainderFilter = getRemainderFilter(); + if (remainderFilter == null) { + remainderFilter = filter; + } else if (filter != null) { + remainderFilter = remainderFilter.or(filter); + } + + return new Result(this, remainderFilter, getRemainderOrderings()); + } + + private boolean equals(Object a, Object b) { + return a == null ? (b == null) : (a.equals(b)); + } + } + + private static class ForeignIndexes { + final ChainedProperty mProperty; + + final List> mIndexes; + + // Cache of virtual indexes. + private final Map, OrderedProperty[]> mVirtualIndexMap; + + /** + * @param property type of property must be a joined Storable + */ + ForeignIndexes(ChainedProperty property, Collection> indexes) { + mProperty = property; + if (indexes == null || indexes.size() == 0) { + mIndexes = Collections.emptyList(); + } else { + mIndexes = new ArrayList>(indexes); + } + mVirtualIndexMap = new HashMap, OrderedProperty[]>(); + } + + /** + * Prepends local chained property with names of index elements, + * producing a virtual index on local storable. This allows + * CompositeScore to evaluate it. + */ + synchronized OrderedProperty[] getVirtualIndex(StorableIndex index) { + OrderedProperty[] virtualProps = mVirtualIndexMap.get(index); + if (virtualProps != null) { + return virtualProps; + } + + OrderedProperty[] realProps = index.getOrderedProperties(); + virtualProps = new OrderedProperty[realProps.length]; + + for (int i=realProps.length; --i>=0; ) { + OrderedProperty realProp = realProps[i]; + ChainedProperty virtualChained = + mProperty.append(realProp.getChainedProperty()); + virtualProps[i] = OrderedProperty.get(virtualChained, realProp.getDirection()); + } + + mVirtualIndexMap.put(index, virtualProps); + + return virtualProps; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java new file mode 100644 index 0000000..7249164 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -0,0 +1,266 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; +import com.amazon.carbonado.filter.PropertyFilter; + +import com.amazon.carbonado.info.StorableIndex; +import com.amazon.carbonado.info.OrderedProperty; + +/** + * Abstract QueryExecutor which utilizes an index. + * + * @author Brian S O'Neill + */ +public abstract class IndexedQueryExecutor extends AbstractQueryExecutor { + /** + * 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 StorableIndex mIndex; + private final Filter mIdentityFilter; + private final List> mExclusiveRangeStartFilters; + private final List> mInclusiveRangeStartFilters; + private final List> mExclusiveRangeEndFilters; + private final List> mInclusiveRangeEndFilters; + private final boolean mReverseOrder; + private final boolean mReverseRange; + + /** + * @param index index to use, which may be a primary key index + * @param score score determines how best to utilize the index + * @throws IllegalArgumentException if index or score is null + */ + public IndexedQueryExecutor(StorableIndex index, CompositeScore score) { + if (index == null || score == null) { + throw new IllegalArgumentException(); + } + + mIndex = index; + + FilteringScore fScore = score.getFilteringScore(); + + mIdentityFilter = fScore.getIdentityFilter(); + mExclusiveRangeStartFilters = fScore.getExclusiveRangeStartFilters(); + mInclusiveRangeStartFilters = fScore.getInclusiveRangeStartFilters(); + mExclusiveRangeEndFilters = fScore.getExclusiveRangeEndFilters(); + mInclusiveRangeEndFilters = fScore.getInclusiveRangeEndFilters(); + + mReverseOrder = score.getOrderingScore().shouldReverseOrder(); + mReverseRange = fScore.shouldReverseRange(); + } + + @Override + public Class getStorableType() { + // Storable type of filter may differ if index is used along with a + // join. The type of the index is the correct storable type. + return mIndex.getStorableType(); + } + + public Cursor openCursor(FilterValues values) throws FetchException { + Object[] identityValues = null; + Object rangeStartValue = null; + Object rangeEndValue = null; + BoundaryType rangeStartBoundary = BoundaryType.OPEN; + BoundaryType rangeEndBoundary = BoundaryType.OPEN; + + if (values != null) { + if (mIdentityFilter != null) { + identityValues = values.getValuesFor(mIdentityFilter); + } + + // 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 (int i=mExclusiveRangeStartFilters.size(); --i>=0; ) { + Object value = values.getValue(mExclusiveRangeStartFilters.get(i)); + if (rangeStartBoundary == BoundaryType.OPEN || + compareWithNullHigh(value, rangeStartValue) > 0) + { + rangeStartValue = value; + rangeStartBoundary = BoundaryType.EXCLUSIVE; + } + } + + for (int i=mInclusiveRangeStartFilters.size(); --i>=0; ) { + Object value = values.getValue(mInclusiveRangeStartFilters.get(i)); + if (rangeStartBoundary == BoundaryType.OPEN || + compareWithNullHigh(value, rangeStartValue) > 0) + { + rangeStartValue = value; + rangeStartBoundary = BoundaryType.INCLUSIVE; + } + } + + for (int i=mExclusiveRangeEndFilters.size(); --i>=0; ) { + Object value = values.getValue(mExclusiveRangeEndFilters.get(i)); + if (rangeEndBoundary == BoundaryType.OPEN || + compareWithNullHigh(value, rangeEndValue) < 0) + { + rangeEndValue = value; + rangeEndBoundary = BoundaryType.EXCLUSIVE; + } + } + + for (int i=mInclusiveRangeEndFilters.size(); --i>=0; ) { + Object value = values.getValue(mInclusiveRangeEndFilters.get(i)); + if (rangeEndBoundary == BoundaryType.OPEN || + compareWithNullHigh(value, rangeEndValue) < 0) + { + rangeEndValue = value; + rangeEndBoundary = BoundaryType.INCLUSIVE; + } + } + } + + return openCursor(mIndex, identityValues, + rangeStartBoundary, rangeStartValue, + rangeEndBoundary, rangeEndValue, + mReverseRange, + mReverseOrder); + } + + public Filter getFilter() { + Filter filter = mIdentityFilter; + + for (PropertyFilter p : mExclusiveRangeStartFilters) { + filter = filter == null ? p : filter.and(p); + } + for (PropertyFilter p : mInclusiveRangeStartFilters) { + filter = filter == null ? p : filter.and(p); + } + for (PropertyFilter p : mExclusiveRangeEndFilters) { + filter = filter == null ? p : filter.and(p); + } + for (PropertyFilter p : mInclusiveRangeEndFilters) { + filter = filter == null ? p : filter.and(p); + } + + return filter; + } + + public List> getOrdering() { + return Collections.unmodifiableList(Arrays.asList(mIndex.getOrderedProperties())); + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + if (mReverseOrder) { + app.append("reverse "); + } + if (mIndex.isClustered()) { + app.append("clustered "); + } + app.append("index scan: "); + app.append(mIndex.getStorableType().getName()); + newline(app); + indent(app, indentLevel); + app.append("...index: "); + mIndex.appendTo(app); + newline(app); + if (mIdentityFilter != null) { + indent(app, indentLevel); + app.append("...identity filter: "); + mIdentityFilter.appendTo(app, values); + newline(app); + } + if (mInclusiveRangeStartFilters.size() > 0 || mExclusiveRangeStartFilters.size() > 0 || + mInclusiveRangeEndFilters.size() > 0 || mExclusiveRangeEndFilters.size() > 0) + { + indent(app, indentLevel); + app.append("...range filter: "); + int count = 0; + for (PropertyFilter p : mExclusiveRangeStartFilters) { + if (count++ > 0) { + app.append(" & "); + } + p.appendTo(app, values); + } + for (PropertyFilter p : mInclusiveRangeStartFilters) { + if (count++ > 0) { + app.append(" & "); + } + p.appendTo(app, values); + } + for (PropertyFilter p : mExclusiveRangeEndFilters) { + if (count++ > 0) { + app.append(" & "); + } + p.appendTo(app, values); + } + for (PropertyFilter p : mInclusiveRangeEndFilters) { + if (count++ > 0) { + app.append(" & "); + } + p.appendTo(app, values); + } + newline(app); + } + return true; + } + + /** + * 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 a primary key index + * @param identityValues 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 whose + * natural order is descending. Only the code that opens the physical + * cursor should examine this parameter. If true, then the range start and + * end parameter pairs need to be swapped. + * @param reverseOrder when true, iteration should be reversed from its + * natural order + */ + protected abstract Cursor openCursor(StorableIndex index, + Object[] identityValues, + BoundaryType rangeStartBoundary, + Object rangeStartValue, + BoundaryType rangeEndBoundary, + Object rangeEndValue, + boolean reverseRange, + boolean reverseOrder) + throws FetchException; +} diff --git a/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java new file mode 100644 index 0000000..7788fba --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java @@ -0,0 +1,48 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.cursor.IteratorCursor; + +/** + * QueryExecutor which fully scans an iterable collection. + * + * @author Brian S O'Neill + * @see IteratorCursor + */ +public class IterableQueryExecutor extends FullScanQueryExecutor { + private final Iterable mIterable; + + /** + * @param type type of Storable + * @param iterable collection to iterate over, or null for empty cursor + * @throws IllegalArgumentException if type is null + */ + public IterableQueryExecutor(Class type, Iterable iterable) { + super(type); + mIterable = iterable; + } + + protected Cursor openCursor() { + return new IteratorCursor(mIterable); + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java new file mode 100644 index 0000000..4d8f48d --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java @@ -0,0 +1,230 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Repository; +import com.amazon.carbonado.RepositoryException; +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.SupportException; + +import com.amazon.carbonado.cursor.JoinedCursorFactory; + +import com.amazon.carbonado.filter.AndFilter; +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.OrFilter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.Visitor; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableInfo; +import com.amazon.carbonado.info.StorableIntrospector; + +/** + * QueryExecutor which wraps an executor for type A, follows a join, and + * produces type B. + * + * @author Brian S O'Neill + * @see JoinedCursorFactory + */ +public class JoinedQueryExecutor + extends AbstractQueryExecutor +{ + private static List> + transformOrdering(Class bType, + String bToAProperty, + QueryExecutor aExecutor) + { + StorableInfo bInfo = StorableIntrospector.examine(bType); + + List> aOrdering = aExecutor.getOrdering(); + int size = aOrdering.size(); + List> bOrdering = new ArrayList>(size); + + for (int i=0; i aProp = aOrdering.get(i); + String bName = bToAProperty + '.' + aProp.getChainedProperty(); + OrderedProperty bProp = OrderedProperty + .get(ChainedProperty.parse(bInfo, bName), aProp.getDirection()); + bOrdering.add(bProp); + } + + return Collections.unmodifiableList(bOrdering); + } + + private final JoinedCursorFactory mFactory; + private final QueryExecutor mAExecutor; + + private final FilterValues mAFilterValues; + private final Filter mBFilter; + private final List> mBOrdering; + + /** + * @param repo access to storage instances for properties + * @param bType type of B instances + * @param bToAProperty property of B type which maps to instances of + * A type. + * @param aExecutor executor for A instances + * @throws IllegalArgumentException if property type is not A + */ + public JoinedQueryExecutor(Repository repo, + Class bType, + String bToAProperty, + QueryExecutor aExecutor) + throws SupportException, FetchException, RepositoryException + { + mFactory = new JoinedCursorFactory + (repo, bType, bToAProperty, aExecutor.getStorableType()); + mAExecutor = aExecutor; + + Filter aFilter = aExecutor.getFilter(); + + mAFilterValues = aFilter.initialFilterValues(); + mBFilter = aFilter.accept(new FilterTransformer(bType, bToAProperty), null); + + mBOrdering = transformOrdering(bType, bToAProperty, aExecutor); + } + + /** + * @param repo access to storage instances for properties + * @param bToAProperty property of B type which maps to instances of + * A type. + * @param aExecutor executor for A instances + * @throws IllegalArgumentException if property type is not A + */ + public JoinedQueryExecutor(Repository repo, + ChainedProperty bToAProperty, + QueryExecutor aExecutor) + throws SupportException, FetchException, RepositoryException + { + mFactory = new JoinedCursorFactory + (repo, bToAProperty, aExecutor.getStorableType()); + mAExecutor = aExecutor; + + Filter aFilter = aExecutor.getFilter(); + + mAFilterValues = aFilter.initialFilterValues(); + mBFilter = aFilter.accept(new FilterTransformer(bToAProperty), null); + + mBOrdering = transformOrdering(bToAProperty.getPrimeProperty().getEnclosingType(), + bToAProperty.toString(), aExecutor); + } + + public Filter getFilter() { + return mBFilter; + } + + public Cursor openCursor(FilterValues values) throws FetchException { + return mFactory.join(mAExecutor.openCursor(transferValues(values))); + } + + public List> getOrdering() { + return mBOrdering; + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("join: "); + app.append(getStorableType().getName()); + newline(app); + mAExecutor.printPlan(app, increaseIndent(indentLevel), transferValues(values)); + return true; + } + + private FilterValues transferValues(FilterValues values) { + if (values == null || mAFilterValues == null) { + return null; + } + return mAFilterValues.withValues(values.getSuppliedValues()); + } + + private class FilterTransformer extends Visitor, Object> { + private final Class mBType; + private final String mBToAProperty; + + FilterTransformer(Class bType, String bToAProperty) { + mBType = bType; + mBToAProperty = bToAProperty; + } + + FilterTransformer(ChainedProperty bToAProperty) { + mBType = bToAProperty.getPrimeProperty().getEnclosingType(); + mBToAProperty = bToAProperty.toString(); + } + + public Filter visit(OrFilter aFilter, Object param) { + return aFilter.getLeftFilter().accept(this, param) + .and(aFilter.getRightFilter().accept(this, param)); + } + + public Filter visit(AndFilter aFilter, Object param) { + return aFilter.getLeftFilter().accept(this, param) + .or(aFilter.getRightFilter().accept(this, param)); + } + + public Filter visit(PropertyFilter aFilter, Object param) { + String name; + + ChainedProperty aChainedProp = aFilter.getChainedProperty(); + if (mBType == aChainedProp.getPrimeProperty().getEnclosingType()) { + // If type if A is already B, (which violates generic type + // signature) then it came from join index analysis. + name = aChainedProp.toString(); + } else { + StringBuilder nameBuilder = new StringBuilder(mBToAProperty).append('.'); + try { + aChainedProp.appendTo(nameBuilder); + } catch (IOException e) { + // Not gonna happen + } + name = nameBuilder.toString(); + } + + Filter bFilter = Filter.getOpenFilter(mBType); + if (aFilter.isConstant()) { + bFilter = bFilter.and(name, aFilter.getOperator(), aFilter.constant()); + } else { + bFilter = bFilter.and(name, aFilter.getOperator()); + } + + return bFilter; + } + + public Filter visit(OpenFilter aFilter, Object param) { + return Filter.getOpenFilter(mBType); + } + + public Filter visit(ClosedFilter aFilter, Object param) { + return Filter.getClosedFilter(mBType); + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java new file mode 100644 index 0000000..e2d692d --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java @@ -0,0 +1,111 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.Collections; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Abstract QueryExecutor which has a fully specified key, and so cursors + * produce at most one result. + * + * @author Brian S O'Neill + */ +public abstract class KeyQueryExecutor extends AbstractQueryExecutor { + private final StorableIndex mIndex; + private final Filter mKeyFilter; + + /** + * @param index index to use, which may be a primary key index + * @param score score determines how best to utilize the index + * @throws IllegalArgumentException if any parameter is null or if index is + * not unique or if score is not a key match + */ + public KeyQueryExecutor(StorableIndex index, FilteringScore score) { + if (index == null || score == null) { + throw new IllegalArgumentException(); + } + if (!index.isUnique() || !score.isKeyMatch()) { + throw new IllegalArgumentException(); + } + mIndex = index; + mKeyFilter = score.getIdentityFilter(); + } + + @Override + public Class getStorableType() { + // Storable type of filter may differ if index is used along with a + // join. The type of the index is the correct storable type. + return mIndex.getStorableType(); + } + + public Cursor openCursor(FilterValues values) throws FetchException { + return openCursor(mIndex, values.getValuesFor(mKeyFilter)); + } + + public Filter getFilter() { + return mKeyFilter; + } + + /** + * Returns an empty list. + */ + public List> getOrdering() { + return Collections.emptyList(); + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("index key: "); + app.append(mIndex.getStorableType().getName()); + newline(app); + indent(app, indentLevel); + app.append("...index: "); + mIndex.appendTo(app); + newline(app); + indent(app, indentLevel); + app.append("...key filter: "); + mKeyFilter.appendTo(app, values); + newline(app); + return true; + } + + /** + * Return a new Cursor instance referenced by the given index. + * + * @param index index to open, which may be a primary key index + * @param keyValues list of exactly matching values to apply to index + */ + protected abstract Cursor openCursor(StorableIndex index, Object[] keyValues) + throws FetchException; +} diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java new file mode 100644 index 0000000..76b273f --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java @@ -0,0 +1,455 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.Collections; +import java.util.HashSet; +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.PropertyFilter; +import com.amazon.carbonado.filter.RelOp; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.Direction; +import static com.amazon.carbonado.info.Direction.*; +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Evaluates an index for how well it matches a query's desired ordering. An + * ordering score is not a single absolute value \u2013 instead it has a relative + * weight when compared to other scores. + * + *

An index matches a desired ordering if the arrangement of properties + * matches. Not all properties of the index need to be used, however. Also, + * gaps in the arrangement are allowed if a property identity filter + * matches. An property identity filter is of the form {@code "a = ?"}. + * + *

An OrderingScore measures the number of ordering properties that are + * matched and the number that are remaining. If there are remainder + * properties, then the user of the evaluated index will need to perform a + * post-sort operation to achieve the desired results. + * + *

In general, an OrderingScore is better than another if it has more + * matched properties and fewer remainder properties. Index clustering, + * property count, and natural order is also considered. + * + * @author Brian S O'Neill + * @see FilteringScore + * @see CompositeScore + */ +public class OrderingScore { + /** + * Evaluates the given index for its ordering capabilities against the + * given filter and order-by properties. + * + * @param index index to evaluate + * @param filter optional filter which cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static OrderingScore evaluate(StorableIndex index, + Filter filter, + OrderedProperty... orderings) + { + if (index == null) { + throw new IllegalArgumentException("Index required"); + } + + return evaluate(index.getOrderedProperties(), + index.isUnique(), + index.isClustered(), + filter, + orderings); + } + + /** + * Evaluates the given index properties for its ordering capabilities + * against the given filter and order-by properties. + * + * @param indexProperties index properties to evaluate + * @param unique true if index is unique + * @param clustered true if index is clustered + * @param filter optional filter which cannot contain any logical 'or' operations. + * @param orderings properties which define desired ordering + * @throws IllegalArgumentException if index is null or filter is not supported + */ + public static OrderingScore evaluate + (OrderedProperty[] indexProperties, + boolean unique, + boolean clustered, + Filter filter, + OrderedProperty... orderings) + { + if (indexProperties == null) { + throw new IllegalArgumentException("Index properties required"); + } + + // Get filter list early to detect errors. + List> filterList = PropertyFilterList.get(filter); + + if (orderings == null || orderings.length == 0) { + return new OrderingScore(clustered, indexProperties.length, null, null, false); + } + + // Ordering properties which match identity filters don't affect order + // results. Build up this set to find them quickly. + Set> identityPropSet = + new HashSet>(filterList.size()); + + for (PropertyFilter propFilter : filterList) { + if (propFilter.getOperator() == RelOp.EQ) { + identityPropSet.add(propFilter.getChainedProperty()); + } + } + + // If index is unique and every property is matched by an identity + // filter, then there won't be any handled or remainder properties. + uniquelyCheck: + if (unique) { + for (int i=0; i indexProp = indexProperties[i].getChainedProperty(); + if (!identityPropSet.contains(indexProp)) { + // Missed a property, so ordering is still relevent. + break uniquelyCheck; + } + } + + return new OrderingScore(clustered, + indexProperties.length, + null, // no handled properties + null, // no remainder properties + false); // no need to reverse order + } + + List> handledProperties = new ArrayList>(); + List> remainderProperties = new ArrayList>(); + + Boolean shouldReverseOrder = null; + + Set> seen = new HashSet>(); + + int indexPos = 0; + calcScore: + for (int i=0; i property = orderings[i]; + ChainedProperty chained = property.getChainedProperty(); + + if (seen.contains(chained)) { + // Redundant property doesn't affect ordering. + continue calcScore; + } + + seen.add(chained); + + if (identityPropSet.contains(chained)) { + // Doesn't affect ordering. + continue calcScore; + } + + indexPosMatch: + while (indexPos < indexProperties.length) { + OrderedProperty indexProp = indexProperties[indexPos]; + ChainedProperty indexChained = indexProp.getChainedProperty(); + + if (chained.equals(indexChained)) { + if (property.getDirection() != UNSPECIFIED) { + Direction indexDir = indexProp.getDirection(); + if (indexDir == UNSPECIFIED) { + indexDir = ASCENDING; + } + + if (shouldReverseOrder == null) { + shouldReverseOrder = indexDir != property.getDirection(); + } else if ((indexDir != property.getDirection()) ^ shouldReverseOrder) { + // Direction mismatch, so cannot be handled. + break indexPosMatch; + } + } + + handledProperties.add(property); + + indexPos++; + continue calcScore; + } + + if (identityPropSet.contains(indexChained)) { + // Even though ordering did not match index at current + // position, the search for handled propertes can continue if + // index gap matches an identity filter. + indexPos++; + continue indexPosMatch; + } + + // Index gap, so cannot be handled. + break indexPosMatch; + } + + // Property not handled and not an identity filter. + remainderProperties.add(property); + indexPos = Integer.MAX_VALUE; + } + + if (shouldReverseOrder == null) { + shouldReverseOrder = false; + } + + return new OrderingScore(clustered, + indexProperties.length, + handledProperties, + remainderProperties, + shouldReverseOrder); + } + + /** + * Returns a comparator which determines which OrderingScores are + * better. It does not matter if the scores were evaluated for different + * indexes or storable types. The comparator returns {@code <0} if first + * score is better, {@code 0} if equal, or {@code >0} if second is better. + */ + public static Comparator> fullComparator() { + return Full.INSTANCE; + } + + private final boolean mIndexClustered; + private final int mIndexPropertyCount; + + private final List> mHandledOrderings; + private final List> mRemainderOrderings; + + private final boolean mShouldReverseOrder; + + private OrderingScore(boolean indexClustered, + int indexPropertyCount, + List> handledOrderings, + List> remainderOrderings, + boolean shouldReverseOrder) + { + mIndexClustered = indexClustered; + mIndexPropertyCount = indexPropertyCount; + mHandledOrderings = FilteringScore.prepareList(handledOrderings); + mRemainderOrderings = FilteringScore.prepareList(remainderOrderings); + mShouldReverseOrder = shouldReverseOrder; + } + + /** + * Returns true if evaluated index is clustered. Scans of clustered indexes + * are generally faster. + */ + public boolean isIndexClustered() { + return mIndexClustered; + } + + /** + * Returns the amount of properties in the evaluated index. + */ + public int getIndexPropertyCount() { + return mIndexPropertyCount; + } + + /** + * Returns the number of desired orderings the evaluated index supports. + */ + public int getHandledCount() { + return mHandledOrderings.size(); + } + + /** + * Returns the ordering properties that the evaluated index supports. + * + * @return handled orderings, never null + */ + public List> getHandledOrderings() { + return mHandledOrderings; + } + + /** + * Returns the number of desired orderings the evaluated index does not + * support. When non-zero, a query plan which uses the evaluated index must + * perform a sort. + */ + public int getRemainderCount() { + return mRemainderOrderings.size(); + } + + /** + * Returns the ordering properties that the evaluated index does not + * support. + * + * @return remainder orderings, never null + */ + public List> getRemainderOrderings() { + return mRemainderOrderings; + } + + /** + * Returns true if evaluated index must be iterated in reverse to achieve + * the desired ordering. + */ + public boolean shouldReverseOrder() { + return mShouldReverseOrder; + } + + /** + * Returns true if the given score uses an index exactly the same as this + * one. The only allowed differences are in the count of remainder + * orderings. + */ + public boolean canMergeRemainderOrderings(OrderingScore other) { + if (this == other || (getHandledCount() == 0 && other.getHandledCount() == 0)) { + return true; + } + + if (isIndexClustered() == other.isIndexClustered() + && getIndexPropertyCount() == other.getIndexPropertyCount() + && shouldReverseOrder() == other.shouldReverseOrder() + && getHandledOrderings().equals(other.getHandledOrderings())) + { + // The remainder orderings cannot conflict. + List> thisRemainderOrderings = getRemainderOrderings(); + List> otherRemainderOrderings = other.getRemainderOrderings(); + + int size = Math.min(thisRemainderOrderings.size(), otherRemainderOrderings.size()); + for (int i=0; i> mergeRemainderOrderings(OrderingScore other) { + List> thisRemainderOrderings = getRemainderOrderings(); + + if (this == other) { + return thisRemainderOrderings; + } + + List> otherRemainderOrderings = other.getRemainderOrderings(); + + // Choose the longer list. + + if (thisRemainderOrderings.size() == 0) { + return otherRemainderOrderings; + } else { + if (otherRemainderOrderings.size() == 0) { + return thisRemainderOrderings; + } else if (thisRemainderOrderings.size() >= otherRemainderOrderings.size()) { + return thisRemainderOrderings; + } else { + return otherRemainderOrderings; + } + } + } + + public String toString() { + return "OrderingScore {handledCount=" + getHandledCount() + + ", remainderCount=" + getRemainderCount() + + ", shouldReverseOrder=" + shouldReverseOrder() + + '}'; + } + + private static class Full implements Comparator> { + static final Comparator> INSTANCE = new Full(); + + public int compare(OrderingScore first, OrderingScore second) { + if (first == second) { + return 0; + } + + int result = FilteringScore.nullCompare(first, second); + if (result != 0) { + return result; + } + + double firstRatio, otherRatio; + + { + int total = first.getHandledCount() + first.getRemainderCount(); + firstRatio = ((double) first.getHandledCount()) / total; + } + + { + int total = second.getHandledCount() + second.getRemainderCount(); + otherRatio = ((double) second.getHandledCount()) / total; + } + + // Choose index with more handled properties. + if (firstRatio > otherRatio) { + return -1; + } else if (firstRatio < otherRatio) { + return 1; + } + + // Choose index with any handled properties over the one with + // neither handled nor remainder properties. + if (Double.isNaN(firstRatio)) { + if (!Double.isNaN(otherRatio)) { + return 1; + } + } else if (Double.isNaN(otherRatio)) { + return -1; + } + + // Choose clustered index, under the assumption than it can be + // scanned more quickly. + if (first.isIndexClustered()) { + if (!second.isIndexClustered()) { + return -1; + } + } else if (second.isIndexClustered()) { + return 1; + } + + // Choose index with fewer properties, under the assumption that fewer + // properties means smaller sized records that need to be read in. + if (first.getIndexPropertyCount() < second.getIndexPropertyCount()) { + return -1; + } else if (first.getIndexPropertyCount() > second.getIndexPropertyCount()) { + return 1; + } + + // Choose index whose natural order matches desired order. + if (first.shouldReverseOrder()) { + if (!second.shouldReverseOrder()) { + return 1; + } + } else if (second.shouldReverseOrder()) { + return -1; + } + + return 0; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java b/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java new file mode 100644 index 0000000..5842ef2 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/PropertyFilterList.java @@ -0,0 +1,120 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; +import java.util.Map; + +import org.cojen.util.SoftValuedHashMap; + +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; + +/** + * Produces unmodifable lists of PropertyFilters which were originally all + * 'and'ed together. The filters are ordered such that all '=' operators are + * first and all '!=' operators are last. + * + * @author Brian S O'Neill + */ +class PropertyFilterList { + private static Map, List> cCache; + + static { + cCache = new SoftValuedHashMap(); + } + + /** + * @param filter filter to break up into separate PropertyFilters. + * @return unmodifiable list of PropertyFilters, which is empty if input filter was null + * @throws IllegalArgumentException if filter has any operators other than 'and'. + */ + static List> get(Filter filter) { + List> list; + + synchronized (cCache) { + list = (List>) cCache.get(filter); + } + + if (list != null) { + return list; + } + + if (filter == null) { + list = Collections.emptyList(); + } else if (filter instanceof PropertyFilter) { + list = Collections.singletonList((PropertyFilter) filter); + } else { + list = new ArrayList>(); + final List> flist = list; + + filter.accept(new Visitor() { + public Object visit(OrFilter filter, Object param) { + throw new IllegalArgumentException("Logical 'or' not allowed"); + } + + public Object visit(PropertyFilter filter, Object param) { + flist.add(filter); + return null; + } + }, null); + + Collections.sort(list, new PropertyFilterComparator()); + + ((ArrayList) list).trimToSize(); + list = Collections.unmodifiableList(list); + } + + synchronized (cCache) { + cCache.put(filter, list); + } + + return list; + } + + private static class PropertyFilterComparator + implements Comparator> + { + public int compare(PropertyFilter a, PropertyFilter 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; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/QueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/QueryExecutor.java new file mode 100644 index 0000000..6861b2c --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/QueryExecutor.java @@ -0,0 +1,87 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * Performs all the actual work of executing a query. QueryExecutors are linked + * together forming a query plan. + * + * @author Brian S O'Neill + */ +public interface QueryExecutor { + /** + * Returns the storable type that this executor operates on. + */ + Class getStorableType(); + + /** + * Returns a new cursor using the given filter values. + */ + Cursor openCursor(FilterValues values) throws FetchException; + + /** + * Counts the query results using the given filter values. + */ + long count(FilterValues values) throws FetchException; + + /** + * Returns the filter used by this QueryExecutor. + * + * @return query filter, never null + */ + Filter getFilter(); + + /** + * Returns the result ordering of this QueryExecutor. + * + * @return query ordering in an unmodifiable list + */ + List> getOrdering(); + + /** + * Prints the native query to any appendable, if applicable. + * + * @param values optional + * @return false if not implemented + */ + boolean printNative(Appendable app, int indentLevel, FilterValues values) + throws IOException; + + /** + * Prints the query plan to any appendable, if applicable. + * + * @param values optional + * @return false if not implemented + */ + boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException; +} diff --git a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java new file mode 100644 index 0000000..5c5258a --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java @@ -0,0 +1,142 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.cursor.SortBuffer; +import com.amazon.carbonado.cursor.SortedCursor; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * Abstract QueryExecutor which wraps another and sorts the results. + * + * @author Brian S O'Neill + * @see SortedCursor + */ +public abstract class SortedQueryExecutor extends AbstractQueryExecutor { + private final QueryExecutor mExecutor; + + private final Comparator mHandledComparator; + private final Comparator mFinisherComparator; + + private final List> mHandledOrderings; + private final List> mRemainderOrderings; + + /** + * @param executor executor to wrap + * @throws IllegalArgumentException if executor is null or if remainder + * orderings is empty + */ + public SortedQueryExecutor(QueryExecutor executor, + List> handledOrderings, + List> remainderOrderings) + { + if (executor == null) { + throw new IllegalArgumentException(); + } + mExecutor = executor; + + if (handledOrderings != null && handledOrderings.size() == 0) { + handledOrderings = null; + } + if (remainderOrderings != null && remainderOrderings.size() == 0) { + remainderOrderings = null; + } + + if (remainderOrderings == null) { + throw new IllegalArgumentException(); + } + + if (handledOrderings == null) { + mHandledComparator = null; + mHandledOrderings = Collections.emptyList(); + } else { + mHandledComparator = SortedCursor.createComparator(handledOrderings); + mHandledOrderings = handledOrderings; + } + + mFinisherComparator = SortedCursor.createComparator(remainderOrderings); + mRemainderOrderings = remainderOrderings; + } + + public Cursor openCursor(FilterValues values) throws FetchException { + Cursor cursor = mExecutor.openCursor(values); + SortBuffer buffer = createSortBuffer(); + return new SortedCursor(cursor, buffer, mHandledComparator, mFinisherComparator); + } + + @Override + public long count(FilterValues values) throws FetchException { + return mExecutor.count(values); + } + + public Filter getFilter() { + return mExecutor.getFilter(); + } + + public List> getOrdering() { + if (mHandledOrderings.size() == 0) { + return mRemainderOrderings; + } + if (mRemainderOrderings.size() == 0) { + return mHandledOrderings; + } + List> ordering = new ArrayList> + (mHandledOrderings.size() + mRemainderOrderings.size()); + + ordering.addAll(mHandledOrderings); + ordering.addAll(mRemainderOrderings); + + return ordering; + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + if (mHandledOrderings.size() == 0) { + app.append("full sort: "); + } else { + app.append("finish sort: "); + } + app.append(mRemainderOrderings.toString()); + newline(app); + mExecutor.printPlan(app, increaseIndent(indentLevel), values); + return true; + } + + /** + * Implementation must return an empty buffer for sorting. + */ + protected abstract SortBuffer createSortBuffer(); +} diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java new file mode 100644 index 0000000..9563097 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java @@ -0,0 +1,238 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.util.ArrayList; +import java.util.List; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.AndFilter; +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.OrFilter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.Visitor; + +import com.amazon.carbonado.info.OrderedProperty; +import com.amazon.carbonado.info.StorableIndex; + +/** + * Analyzes a query specification and determines how it can be executed as a + * union of smaller queries. If necessary, the UnionQueryAnalyzer will alter + * the query slightly, imposing a total ordering. Internally, an {@link + * IndexedQueryAnalyzer} is used for selecting the best indexes. + * + *

UnionQueryAnalyzer is sharable and thread-safe. An instance for a + * particular Storable type can be cached, avoiding repeated construction + * cost. In addition, the analyzer caches learned foreign indexes. + * + * @author Brian S O'Neill + */ +public class UnionQueryAnalyzer { + final IndexedQueryAnalyzer mIndexAnalyzer; + + /** + * @param type type of storable being queried + * @param indexProvider + * @throws IllegalArgumentException if type or indexProvider is null + */ + public UnionQueryAnalyzer(Class type, IndexProvider indexProvider) { + mIndexAnalyzer = new IndexedQueryAnalyzer(type, indexProvider); + } + + /** + * @param filter optional filter which must be {@link Filter#isBound bound} + * @param orderings properties which define desired ordering + */ + public Result analyze(Filter filter, OrderedProperty... orderings) { + if (!filter.isBound()) { + // Strictly speaking, this is not required, but it detects the + // mistake of not properly calling initialFilterValues. + throw new IllegalArgumentException("Filter must be bound"); + } + + // Required for split to work. + filter = filter.disjunctiveNormalForm(); + + List.Result> subResults = splitIntoSubResults(filter, orderings); + + if (subResults.size() > 1) { + // If more than one, then a total ordering is required. + + // FIXME + } + + return new Result(subResults); + } + + private List> isTotalOrdering() { + // FIXME + return null; + } + + private List.Result> + splitIntoSubResults(Filter filter, OrderedProperty... orderings) + { + Splitter splitter = new Splitter(orderings); + filter.accept(splitter, null); + + List.Result> subResults = splitter.mSubResults; + + // Check if any sub-result handles nothing. If so, a full scan is the + // best option for the entire query and all sub-results merge into a + // single sub-result. Any sub-results which filter anything and contain + // a join property in the filter are exempt from the merge. This is + // because fewer joins are read then if a full scan is performed for + // the entire query. The resulting union has both a full scan and an + // index scan. + + IndexedQueryAnalyzer.Result full = null; + for (IndexedQueryAnalyzer.Result result : subResults) { + if (!result.handlesAnything()) { + full = result; + break; + } + } + + if (full == null) { + // Okay, no full scan needed. + return subResults; + } + + List.Result> mergedResults = + new ArrayList.Result>(); + + for (IndexedQueryAnalyzer.Result result : subResults) { + if (result == full) { + // Add after everything has been merged into it. + continue; + } + + boolean exempt = result.getCompositeScore().getFilteringScore().hasAnyMatches(); + // FIXME: check for joins + + if (exempt) { + subResults.add(result); + } else { + full = full.mergeRemainder(result.getFilter()); + } + } + + mergedResults.add(full); + + return mergedResults; + } + + public class Result { + // FIXME: User of QueryAnalyzer results needs to identify what actual + // storage is used by an index. It is also responsible for grouping + // unions together if storage differs. If foreign index is selected, + // then join is needed. + + private final List.Result> mSubResults; + + Result(List.Result> subResults) { + mSubResults = subResults; + } + + /** + * Returns results for each sub-query to be executed in the union. If + * only one result is returned, then no union needs to be performed. + */ + public List.Result> getSubResults() { + return mSubResults; + } + + /** + * If more than one sub-result, then a total ordering is + * imposed. Otherwise, null is returned. + */ + public List> getTotalOrdering() { + // FIXME + return null; + } + } + + /** + * Analyzes a disjunctive normal filter into sub-results over filters that + * only contain 'and' operations. + */ + private class Splitter extends Visitor { + private final OrderedProperty[] mOrderings; + + final List.Result> mSubResults; + + Splitter(OrderedProperty... orderings) { + mOrderings = orderings; + mSubResults = new ArrayList.Result>(); + } + + @Override + public Object visit(OrFilter filter, Object param) { + Filter left = filter.getLeftFilter(); + if (!(left instanceof OrFilter)) { + subAnalyze(left); + } else { + left.accept(this, param); + } + Filter right = filter.getRightFilter(); + if (!(right instanceof OrFilter)) { + subAnalyze(right); + } else { + right.accept(this, param); + } + return null; + } + + // This method should only be called if root filter has no 'or' operators. + @Override + public Object visit(AndFilter filter, Object param) { + subAnalyze(filter); + return null; + } + + // This method should only be called if root filter has no logical operators. + @Override + public Object visit(PropertyFilter filter, Object param) { + subAnalyze(filter); + return null; + } + + private void subAnalyze(Filter subFilter) { + IndexedQueryAnalyzer.Result subResult = + mIndexAnalyzer.analyze(subFilter, mOrderings); + + // Rather than blindly add to mSubResults, try to merge with + // another result. This in turn reduces the number of cursors + // needed by the union. + + int size = mSubResults.size(); + for (int i=0; i.Result existing = mSubResults.get(i); + if (existing.canMergeRemainder(subResult)) { + mSubResults.set(i, existing.mergeRemainder(subResult)); + return; + } + } + + // Couldn't merge, so add a new entry. + mSubResults.add(subResult); + } + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryExecutor.java new file mode 100644 index 0000000..cc3d366 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryExecutor.java @@ -0,0 +1,123 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.qe; + +import java.io.IOException; + +import java.util.Arrays; +import java.util.Comparator; +import java.util.List; + +import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.FetchException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.cursor.SortedCursor; +import com.amazon.carbonado.cursor.UnionCursor; + +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.FilterValues; + +import com.amazon.carbonado.info.OrderedProperty; + +/** + * QueryExecutor which wraps several others and unions the results. + * + * @author Brian S O'Neill + * @see UnionCursor + */ +public class UnionQueryExecutor extends AbstractQueryExecutor { + private static E ensureNotNull(E e) { + if (e == null) { + throw new IllegalArgumentException(); + } + return e; + } + + private final QueryExecutor[] mExecutors; + private final List> mTotalOrderings; + private final Comparator mOrderComparator; + + /** + * @param executors executors to wrap, each must have the exact same total ordering + * @throws IllegalArgumentException if any parameter is null or if ordering doesn't match + */ + public UnionQueryExecutor(QueryExecutor... executors) { + this(Arrays.asList(ensureNotNull(executors))); + } + + /** + * @param executors executors to wrap, each must have the exact same total ordering + * @throws IllegalArgumentException if any parameter is null or if ordering doesn't match + */ + public UnionQueryExecutor(List> executors) { + if (executors == null || executors.size() == 0) { + throw new IllegalArgumentException(); + } + List> totalOrderings = executors.get(0).getOrdering(); + // Compare for consistency. + for (int i=1; i openCursor(FilterValues values) throws FetchException { + Cursor cursor = null; + for (QueryExecutor executor : mExecutors) { + Cursor subCursor = executor.openCursor(values); + cursor = (cursor == null) ? subCursor + : new UnionCursor(cursor, subCursor, mOrderComparator); + } + return cursor; + } + + /** + * Returns the combined filter of the wrapped executors. + */ + public Filter getFilter() { + Filter filter = null; + for (QueryExecutor executor : mExecutors) { + Filter subFilter = executor.getFilter(); + filter = filter == null ? subFilter : filter.or(subFilter); + } + return filter; + } + + public List> getOrdering() { + return mTotalOrderings; + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("union"); + newline(app); + for (QueryExecutor executor : mExecutors) { + executor.printPlan(app, increaseIndent(indentLevel), values); + } + return true; + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/package-info.java b/src/main/java/com/amazon/carbonado/qe/package-info.java new file mode 100644 index 0000000..6aae5e6 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/package-info.java @@ -0,0 +1,24 @@ +/* + * 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. + */ + +/** + * Support for implementing a Query Engine. Repositories are free to use this + * package to aid in their implementation, but user-level applications have no + * need to use this package. + */ +package com.amazon.carbonado.qe; -- cgit v1.2.3