diff options
| author | Brian S. O'Neill <bronee@gmail.com> | 2006-08-30 02:13:43 +0000 |
|---|---|---|
| committer | Brian S. O'Neill <bronee@gmail.com> | 2006-08-30 02:13:43 +0000 |
| commit | b53f2a2c22a5cda5801cc48e230d31b12c3adfc8 (patch) | |
| tree | fbd48505e470db1248f429d86bdc93c84bb7a184 | |
| parent | 60e2cc6786962037e5c6ee09b7dc3eae38ee5db7 (diff) | |
Add new query engine
24 files changed, 4218 insertions, 0 deletions
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<S extends Storable> implements Query<S>, 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<orderingStrings.length; i++) {
+ orderingStrings[i] = orderings[i].toString().intern();
+ }
+ return orderingStrings;
+ }
+
+ // Note: Since constructor takes no parameters, this class is called
+ // Abstract instead of Base.
+ protected AbstractQuery() {
+ }
+
+ public Query<S> and(String filter) throws FetchException {
+ return and(Filter.filterFor(getStorableType(), filter));
+ }
+
+ public Query<S> 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<S> 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<S extends Storable> implements QueryExecutor<S> {
+ public Class<S> getStorableType() {
+ return getFilter().getStorableType();
+ }
+
+ /**
+ * Counts results by opening a cursor and skipping entries.
+ */
+ public long count(FilterValues<S> values) throws FetchException {
+ Cursor<S> cursor = openCursor(values);
+ try {
+ long count = cursor.skipNext(Integer.MAX_VALUE);
+ if (count == Integer.MAX_VALUE) {
+ int amt;
+ while ((amt = cursor.skipNext(Integer.MAX_VALUE)) > 0) {
+ count += amt;
+ }
+ }
+ return count;
+ } finally {
+ cursor.close();
+ }
+ }
+
+ /**
+ * Does nothing and returns false.
+ */
+ public boolean printNative(Appendable app, int indentLevel, FilterValues<S> 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<indentLevel; i++) {
+ app.append(' ');
+ }
+ }
+
+ /**
+ * Appends a newline character.
+ */
+ protected void newline(Appendable app) throws IOException {
+ app.append('\n');
+ }
+
+ /**
+ * Adds a constant amount to the given indent level. Useful for
+ * implementing printNative and printPlan.
+ */
+ protected int increaseIndent(int indentLevel) {
+ return indentLevel + 2;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/qe/ArraySortedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/ArraySortedQueryExecutor.java new file mode 100644 index 0000000..1ca2965 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/ArraySortedQueryExecutor.java @@ -0,0 +1,52 @@ +/*
+ * 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.List;
+
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.cursor.ArraySortBuffer;
+import com.amazon.carbonado.cursor.SortBuffer;
+
+import com.amazon.carbonado.info.OrderedProperty;
+
+/**
+ * QueryExecutor which wraps another and sorts the results within an array.
+ *
+ * @author Brian S O'Neill
+ * @see ArraySortBuffer
+ */
+public class ArraySortedQueryExecutor<S extends Storable> extends SortedQueryExecutor<S> {
+ /**
+ * @param executor executor to wrap
+ * @throws IllegalArgumentException if executor is null or if remainder
+ * orderings is empty
+ */
+ public ArraySortedQueryExecutor(QueryExecutor<S> executor,
+ List<OrderedProperty<S>> handledOrderings,
+ List<OrderedProperty<S>> remainderOrderings)
+ {
+ super(executor, handledOrderings, remainderOrderings);
+ }
+
+ protected SortBuffer<S> createSortBuffer() {
+ return new ArraySortBuffer<S>();
+ }
+}
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<S extends Storable> {
+ /**
+ * 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 <S extends Storable> CompositeScore<S> evaluate(StorableIndex<S> index,
+ Filter<S> filter,
+ OrderedProperty<S>... 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 <S extends Storable> CompositeScore<S> evaluate
+ (OrderedProperty<S>[] indexProperties,
+ boolean unique,
+ boolean clustered,
+ Filter<S> filter,
+ OrderedProperty<S>... orderings)
+ {
+ FilteringScore<S> filteringScore = FilteringScore
+ .evaluate(indexProperties, unique, clustered, filter);
+
+ OrderingScore<S> orderingScore = OrderingScore
+ .evaluate(indexProperties, unique, clustered, filter, orderings);
+
+ return new CompositeScore<S>(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<CompositeScore<?>> fullComparator() {
+ return Full.INSTANCE;
+ }
+
+ private final FilteringScore<S> mFilteringScore;
+ private final OrderingScore<S> mOrderingScore;
+
+ private CompositeScore(FilteringScore<S> filteringScore, OrderingScore<S> orderingScore) {
+ mFilteringScore = filteringScore;
+ mOrderingScore = orderingScore;
+ }
+
+ /**
+ * Returns the score on how well the evaluated index performs the desired
+ * filtering.
+ */
+ public FilteringScore<S> getFilteringScore() {
+ return mFilteringScore;
+ }
+
+ /**
+ * Returns the score on how well the evaluated index performs the desired
+ * ordering.
+ */
+ public OrderingScore<S> 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<S> 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<S> mergeRemainderFilter(CompositeScore<S> 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<OrderedProperty<S>> mergeRemainderOrderings(CompositeScore<S> other) {
+ return getOrderingScore().mergeRemainderOrderings(other.getOrderingScore());
+ }
+
+ public String toString() {
+ return "CompositeScore {" + getFilteringScore() + ", " + getOrderingScore() + '}';
+ }
+
+ private static class Full implements Comparator<CompositeScore<?>> {
+ static final Comparator<CompositeScore<?>> 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<S extends Storable> implements QueryExecutor<S> {
+ private final QueryExecutor<S> mExecutor;
+ private final Storage<S> mStorage;
+ private final Query<S> mQuery;
+
+ /**
+ * @param executor executor to emulate
+ * @param storage storage to query
+ * @throws IllegalArgumentException if any parameter is null
+ */
+ public DelegatedQueryExecutor(QueryExecutor<S> executor, Storage<S> storage)
+ throws FetchException
+ {
+ if (executor == null || storage == null) {
+ throw new IllegalStateException();
+ }
+
+ mExecutor = executor;
+ mStorage = storage;
+
+ Filter<S> filter = executor.getFilter();
+
+ Query<S> query;
+ if (filter == null) {
+ query = storage.query();
+ } else {
+ query = storage.query(filter);
+ }
+
+ List<OrderedProperty<S>> ordering = executor.getOrdering();
+ if (ordering.size() > 0) {
+ String[] orderBy = new String[ordering.size()];
+ for (int i=0; i<orderBy.length; i++) {
+ orderBy[i] = ordering.get(i).toString();
+ }
+ query = query.orderBy(orderBy);
+ }
+
+ mQuery = query;
+ }
+
+ public Class<S> getStorableType() {
+ return mStorage.getStorableType();
+ }
+
+ public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
+ return applyFilterValues(values).fetch();
+ }
+
+ public long count(FilterValues<S> values) throws FetchException {
+ return applyFilterValues(values).count();
+ }
+
+ public Filter<S> getFilter() {
+ return mExecutor.getFilter();
+ }
+
+ public List<OrderedProperty<S>> getOrdering() {
+ return mExecutor.getOrdering();
+ }
+
+ public boolean printNative(Appendable app, int indentLevel, FilterValues<S> values)
+ throws IOException
+ {
+ return applyFilterValues(values).printNative(app, indentLevel);
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
+ throws IOException
+ {
+ Query<S> query;
+ try {
+ query = applyFilterValues(values);
+ } catch (IllegalStateException e) {
+ query = mQuery;
+ }
+ return query.printPlan(app, indentLevel);
+ }
+
+ private Query<S> applyFilterValues(FilterValues<S> values) {
+ // FIXME: figure out how to transfer values directly to query.
+
+ Query<S> query = mQuery;
+ Filter<S> filter = query.getFilter();
+ // FIXME: this code can get confused if filter has constants.
+ if (values != null && filter != null && query.getBlankParameterCount() != 0) {
+ query = query.withValues(values.getValuesFor(filter));
+ }
+ return query;
+ }
+}
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<S extends Storable> extends AbstractQuery<S> {
+ private final Storage<S> 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<S> 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<S> storage, String[] orderings) {
+ if (storage == null) {
+ throw new IllegalArgumentException();
+ }
+ mStorage = storage;
+ mOrderings = orderings == null ? EMPTY_ORDERINGS : orderings;
+ }
+
+ public Class<S> getStorableType() {
+ return mStorage.getStorableType();
+ }
+
+ /**
+ * Always returns a {@link com.amazon.carbonado.filter.ClosedFilter ClosedFilter}.
+ */
+ public Filter<S> getFilter() {
+ return Filter.getClosedFilter(mStorage.getStorableType());
+ }
+
+ /**
+ * Always returns null.
+ */
+ public FilterValues<S> getFilterValues() {
+ return null;
+ }
+
+ /**
+ * Always returns zero.
+ */
+ public int getBlankParameterCount() {
+ return 0;
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(int value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(long value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(float value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(double value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(boolean value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(char value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(byte value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(short value) {
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> with(Object value) {
+ throw error();
+ }
+
+ /**
+ * Throws an IllegalStateException unless no values passed in.
+ */
+ public Query<S> withValues(Object... values) {
+ if (values == null || values.length == 0) {
+ return this;
+ }
+ throw error();
+ }
+
+ /**
+ * Always throws an IllegalStateException.
+ */
+ public Query<S> and(Filter<S> filter) {
+ throw new IllegalStateException("Query is already guaranteed to fetch nothing");
+ }
+
+ public Query<S> or(Filter<S> filter) throws FetchException {
+ return mStorage.query(filter);
+ }
+
+ public Query<S> not() throws FetchException {
+ Query<S> query = mStorage.query();
+ String[] orderings = mOrderings;
+ if (orderings.length > 0) {
+ query = query.orderBy(orderings);
+ }
+ return query;
+ }
+
+ public Query<S> orderBy(String property) throws FetchException {
+ // This allows property to be checked for validity.
+ return mStorage.query().orderBy(property).not();
+ }
+
+ public Query<S> 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<S> fetch() {
+ return EmptyCursor.getEmptyCursor();
+ }
+
+ /**
+ * Always returns an {@link EmptyCursor}.
+ */
+ public Cursor<S> 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<mOrderings.length; i++) {
+ if (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<S extends Storable> extends AbstractQueryExecutor<S> {
+ private final QueryExecutor<S> mExecutor;
+ private final Filter<S> 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<S> executor, Filter<S> 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<S> openCursor(FilterValues<S> 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<S> getFilter() {
+ return mExecutor.getFilter().and(mFilter);
+ }
+
+ public List<OrderedProperty<S>> getOrdering() {
+ return mExecutor.getOrdering();
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> 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.
+ *
+ * <p>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.
+ *
+ * <p>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.
+ *
+ * <p>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<S extends Storable> {
+ /**
+ * 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 <S extends Storable> FilteringScore<S> evaluate(StorableIndex<S> index,
+ Filter<S> 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 <S extends Storable> FilteringScore<S> evaluate
+ (OrderedProperty<S>[] indexProperties,
+ boolean unique,
+ boolean clustered,
+ Filter<S> filter)
+ {
+ if (indexProperties == null) {
+ throw new IllegalArgumentException("Index properties required");
+ }
+
+ // List is ordered such that '=' operations are first and '!='
+ // operations are last.
+ List<PropertyFilter<S>> filterList = PropertyFilterList.get(filter);
+
+ // Copy so it so that matching elements can be removed.
+ filterList = new ArrayList<PropertyFilter<S>>(filterList);
+
+ // First find the identity matches.
+
+ List<PropertyFilter<S>> identityFilters = new ArrayList<PropertyFilter<S>>();
+ int arrangementScore = 0;
+
+ int indexPropPos;
+ int lastFilterPos = 0;
+
+ identityMatches:
+ for (indexPropPos = 0; indexPropPos < indexProperties.length; indexPropPos++) {
+ ChainedProperty<S> indexProp = indexProperties[indexPropPos].getChainedProperty();
+
+ for (int pos = 0; pos < filterList.size(); pos++) {
+ PropertyFilter<S> 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<PropertyFilter<S>> rangeStartFilters;
+ List<PropertyFilter<S>> rangeEndFilters;
+
+ boolean shouldReverseRange;
+
+ if (indexPropPos >= indexProperties.length) {
+ rangeStartFilters = Collections.emptyList();
+ rangeEndFilters = Collections.emptyList();
+ shouldReverseRange = false;
+ } else {
+ ChainedProperty<S> indexProp = indexProperties[indexPropPos].getChainedProperty();
+
+ rangeStartFilters = new ArrayList<PropertyFilter<S>>();
+ rangeEndFilters = new ArrayList<PropertyFilter<S>>();
+
+ rangeMatches:
+ for (int pos = 0; pos < filterList.size(); pos++) {
+ PropertyFilter<S> 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<S>(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<FilteringScore<?>> 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<FilteringScore<?>> fullComparator() {
+ return Full.INSTANCE;
+ }
+
+ static <E> List<E> prepareList(List<E> 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<PropertyFilter<S>> mIdentityFilters;
+
+ private final List<PropertyFilter<S>> mRangeStartFilters;
+ private final List<PropertyFilter<S>> mRangeEndFilters;
+
+ private final int mArrangementScore;
+
+ private final List<PropertyFilter<S>> mRemainderFilters;
+
+ private final boolean mShouldReverseRange;
+
+ private transient Filter<S> mIdentityFilter;
+ private transient Filter<S> mRemainderFilter;
+
+ private FilteringScore(boolean indexClustered,
+ boolean indexUnique,
+ int indexPropertyCount,
+ List<PropertyFilter<S>> identityFilters,
+ List<PropertyFilter<S>> rangeStartFilters,
+ List<PropertyFilter<S>> rangeEndFilters,
+ int arrangementScore,
+ List<PropertyFilter<S>> 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<PropertyFilter<S>> getIdentityFilters() {
+ return mIdentityFilters;
+ }
+
+ /**
+ * Returns the composite identity filter, or null if no identity property
+ * filters.
+ */
+ public Filter<S> 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<PropertyFilter<S>> 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<PropertyFilter<S>> 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<PropertyFilter<S>> 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<PropertyFilter<S>> 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<PropertyFilter<S>> 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<PropertyFilter<S>> 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<PropertyFilter<S>> getRemainderFilters() {
+ return mRemainderFilters;
+ }
+
+ /**
+ * Returns the composite remainder filter not supported by the evaluated
+ * index, or null if no remainder.
+ */
+ public Filter<S> 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<S> 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<S> mergeRemainderFilter(FilteringScore<S> other) {
+ Filter<S> thisRemainderFilter = getRemainderFilter();
+
+ if (this == other) {
+ return thisRemainderFilter;
+ }
+
+ Filter<S> 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<PropertyFilter<S>> reduce(List<PropertyFilter<S>> filters, RelOp op) {
+ List<PropertyFilter<S>> reduced = null;
+
+ for (int i=0; i<filters.size(); i++) {
+ PropertyFilter<S> filter = filters.get(i);
+ if (filter.getOperator() != op) {
+ if (reduced == null) {
+ reduced = new ArrayList<PropertyFilter<S>>(filters.size());
+ for (int j=0; j<i; j++) {
+ reduced.add(filters.get(j));
+ }
+ }
+ } else if (reduced != null) {
+ reduced.add(filter);
+ }
+ }
+
+ return reduced == null ? filters : reduced;
+ }
+
+ private Filter<S> buildCompositeFilter(List<PropertyFilter<S>> filterList) {
+ if (filterList.size() == 0) {
+ return null;
+ }
+ Filter<S> composite = filterList.get(0);
+ for (int i=1; i<filterList.size(); i++) {
+ composite = composite.and(filterList.get(i));
+ }
+ return composite;
+ }
+
+ private static class Range implements Comparator<FilteringScore<?>> {
+ static final Comparator<FilteringScore<?>> 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<FilteringScore<?>> {
+ static final Comparator<FilteringScore<?>> 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<S extends Storable>
+ extends FullScanQueryExecutor<S>
+{
+ private static <S extends Storable> Class<S> getType(StorableIndex<S> index) {
+ if (index == null) {
+ throw new IllegalArgumentException();
+ }
+ return index.getStorableType();
+ }
+
+ private final StorableIndex<S> mIndex;
+
+ /**
+ * @param index index to use, which may be a primary key index
+ * @throws IllegalArgumentException if index is null
+ */
+ public FullScanIndexedQueryExecutor(StorableIndex<S> index) {
+ super(getType(index));
+ mIndex = index;
+ }
+
+ @Override
+ public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
+ return openCursor(mIndex);
+ }
+
+ /**
+ * Returns the natural order of the index.
+ */
+ @Override
+ public List<OrderedProperty<S>> getOrdering() {
+ return Collections.unmodifiableList(Arrays.asList(mIndex.getOrderedProperties()));
+ }
+
+ protected Cursor<S> 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<S> openCursor(StorableIndex<S> 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<S extends Storable> extends AbstractQueryExecutor<S> {
+ private final Class<S> mType;
+
+ /**
+ * @param type type of Storable
+ * @throws IllegalArgumentException if type is null
+ */
+ public FullScanQueryExecutor(Class<S> type) {
+ if (type == null) {
+ throw new IllegalArgumentException();
+ }
+ mType = type;
+ }
+
+ /**
+ * Returns an open filter.
+ */
+ public Filter<S> getFilter() {
+ return Filter.getOpenFilter(mType);
+ }
+
+ public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
+ return openCursor();
+ }
+
+ /**
+ * Returns an empty list.
+ */
+ public List<OrderedProperty<S>> getOrdering() {
+ return Collections.emptyList();
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> 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<S> 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.
+ */
+ <S extends Storable> Collection<StorableIndex<S>> indexesFor(Class<S> 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.
+ *
+ * <p>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<S extends Storable> {
+ private final Class<S> mType;
+ private final IndexProvider mIndexProvider;
+
+ // Growable cache which maps join properties to lists of usable foreign indexes.
+ private Map<ChainedProperty<S>, ForeignIndexes<S>> mForeignIndexCache;
+
+ /**
+ * @param type type of storable being queried
+ * @param indexProvider
+ * @throws IllegalArgumentException if type or indexProvider is null
+ */
+ public IndexedQueryAnalyzer(Class<S> type, IndexProvider indexProvider) {
+ if (type == null || indexProvider == null) {
+ throw new IllegalArgumentException();
+ }
+ mType = type;
+ mIndexProvider = indexProvider;
+ }
+
+ public Class<S> 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<S> filter, OrderedProperty<S>... 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<CompositeScore<?>> comparator = CompositeScore.fullComparator();
+
+ // First find best local index.
+ CompositeScore<S> bestScore = null;
+ StorableIndex<S> bestLocalIndex = null;
+
+ Collection<StorableIndex<S>> localIndexes = mIndexProvider.indexesFor(mType);
+ if (localIndexes != null) {
+ for (StorableIndex<S> index : localIndexes) {
+ CompositeScore<S> 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<S> bestForeignProperty = null;
+
+ for (PropertyFilter<S> propFilter : PropertyFilterList.get(filter)) {
+ ChainedProperty<S> chainedProp = propFilter.getChainedProperty();
+
+ if (chainedProp.getChainCount() == 0) {
+ // Cannot possibly be a join, so move on.
+ continue;
+ }
+
+ ForeignIndexes<S> foreignIndexes = getForeignIndexes(chainedProp);
+ if (foreignIndexes == null) {
+ continue;
+ }
+
+ for (StorableIndex<?> index : foreignIndexes.mIndexes) {
+ CompositeScore<S> 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<S> getForeignIndexes(ChainedProperty<S> chainedProp) {
+ // Remove the last property as it is expected to be a simple storable
+ // property instead of a joined Storable.
+ chainedProp = chainedProp.trim();
+
+ ForeignIndexes<S> 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<count; i++) {
+ if (!isProperJoin(chainedProp.getChainedProperty(i))) {
+ break evaluate;
+ }
+ }
+
+ // All foreign indexes are available for use.
+ Class foreignType = chainedProp.getLastProperty().getType();
+ Collection<StorableIndex<?>> indexes = mIndexProvider.indexesFor(foreignType);
+
+ foreignIndexes = new ForeignIndexes<S>(chainedProp, indexes);
+ }
+
+ if (mForeignIndexCache == null) {
+ mForeignIndexCache = Collections.synchronizedMap
+ (new HashMap<ChainedProperty<S>, ForeignIndexes<S>>());
+ }
+
+ 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<? extends Storable>) property.getType());
+ int count = property.getJoinElementCount();
+ for (int i=0; i<count; i++) {
+ filter = filter.and(property.getInternalJoinElement(i).getName(), RelOp.EQ);
+ }
+
+ // Java generics are letting me down. I cannot use proper specification
+ // because compiler gets confused with all the wildcards.
+ Collection indexes = mIndexProvider.indexesFor(filter.getStorableType());
+
+ if (indexes != null) {
+ for (Object index : indexes) {
+ FilteringScore score = FilteringScore.evaluate((StorableIndex) index, filter);
+ if (score.getRemainderCount() == 0) {
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ private <F extends Storable> boolean simpleAnalyze(Filter<F> filter) {
+ Collection<StorableIndex<F>> indexes = mIndexProvider.indexesFor(filter.getStorableType());
+
+ if (indexes != null) {
+ for (StorableIndex<F> index : indexes) {
+ FilteringScore<F> score = FilteringScore.evaluate(index, filter);
+ if (score.getRemainderCount() == 0) {
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ public class Result {
+ private final Filter<S> mFilter;
+
+ private final CompositeScore<S> mScore;
+ private final StorableIndex<S> mLocalIndex;
+ private final StorableIndex<?> mForeignIndex;
+ private final ChainedProperty<S> mForeignProperty;
+
+ private final Filter<S> mRemainderFilter;
+ private final List<OrderedProperty<S>> mRemainderOrderings;
+
+ Result(Filter<S> filter,
+ CompositeScore<S> score,
+ StorableIndex<S> localIndex,
+ StorableIndex<?> foreignIndex,
+ ChainedProperty<S> 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<S> remainderFilter,
+ List<OrderedProperty<S>> 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<S> getFilter() {
+ return mFilter;
+ }
+
+ /**
+ * Returns combined handled and remainder orderings for this result.
+ */
+ public List<OrderedProperty<S>> getOrderings() {
+ List<OrderedProperty<S>> handled = mScore.getOrderingScore().getHandledOrderings();
+ List<OrderedProperty<S>> remainder = getRemainderOrderings();
+
+ if (handled.size() == 0) {
+ return remainder;
+ }
+ if (remainder.size() == 0) {
+ return handled;
+ }
+
+ List<OrderedProperty<S>> combined =
+ new ArrayList<OrderedProperty<S>>(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<S> getCompositeScore() {
+ return mScore;
+ }
+
+ /**
+ * Remainder filter which overrides that in composite score.
+ */
+ public Filter<S> getRemainderFilter() {
+ return mRemainderFilter;
+ }
+
+ /**
+ * Remainder orderings which override that in composite score.
+ */
+ public List<OrderedProperty<S>> getRemainderOrderings() {
+ return mRemainderOrderings;
+ }
+
+ /**
+ * Returns the local index that was selected, or null if a foreign
+ * index was selected.
+ */
+ public StorableIndex<S> 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<S> 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<S> filter) {
+ Filter<S> 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<S extends Storable> {
+ final ChainedProperty<S> mProperty;
+
+ final List<StorableIndex<?>> mIndexes;
+
+ // Cache of virtual indexes.
+ private final Map<StorableIndex<?>, OrderedProperty<S>[]> mVirtualIndexMap;
+
+ /**
+ * @param property type of property must be a joined Storable
+ */
+ ForeignIndexes(ChainedProperty<S> property, Collection<StorableIndex<?>> indexes) {
+ mProperty = property;
+ if (indexes == null || indexes.size() == 0) {
+ mIndexes = Collections.emptyList();
+ } else {
+ mIndexes = new ArrayList<StorableIndex<?>>(indexes);
+ }
+ mVirtualIndexMap = new HashMap<StorableIndex<?>, OrderedProperty<S>[]>();
+ }
+
+ /**
+ * Prepends local chained property with names of index elements,
+ * producing a virtual index on local storable. This allows
+ * CompositeScore to evaluate it.
+ */
+ synchronized OrderedProperty<S>[] getVirtualIndex(StorableIndex<?> index) {
+ OrderedProperty<S>[] 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<S> 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<S extends Storable> extends AbstractQueryExecutor<S> {
+ /**
+ * 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<S> mIndex;
+ private final Filter<S> mIdentityFilter;
+ private final List<PropertyFilter<S>> mExclusiveRangeStartFilters;
+ private final List<PropertyFilter<S>> mInclusiveRangeStartFilters;
+ private final List<PropertyFilter<S>> mExclusiveRangeEndFilters;
+ private final List<PropertyFilter<S>> 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<S> index, CompositeScore<S> score) {
+ if (index == null || score == null) {
+ throw new IllegalArgumentException();
+ }
+
+ mIndex = index;
+
+ FilteringScore<S> 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<S> 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<S> openCursor(FilterValues<S> 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<S> getFilter() {
+ Filter<S> filter = mIdentityFilter;
+
+ for (PropertyFilter<S> p : mExclusiveRangeStartFilters) {
+ filter = filter == null ? p : filter.and(p);
+ }
+ for (PropertyFilter<S> p : mInclusiveRangeStartFilters) {
+ filter = filter == null ? p : filter.and(p);
+ }
+ for (PropertyFilter<S> p : mExclusiveRangeEndFilters) {
+ filter = filter == null ? p : filter.and(p);
+ }
+ for (PropertyFilter<S> p : mInclusiveRangeEndFilters) {
+ filter = filter == null ? p : filter.and(p);
+ }
+
+ return filter;
+ }
+
+ public List<OrderedProperty<S>> getOrdering() {
+ return Collections.unmodifiableList(Arrays.asList(mIndex.getOrderedProperties()));
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
+ throws IOException
+ {
+ indent(app, indentLevel);
+ if (mReverseOrder) {
+ app.append("reverse ");
+ }
+ if (mIndex.isClustered()) {
+ app.append("clustered ");
+ }
+ app.append("index scan: ");
+ app.append(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<S> p : mExclusiveRangeStartFilters) {
+ if (count++ > 0) {
+ app.append(" & ");
+ }
+ p.appendTo(app, values);
+ }
+ for (PropertyFilter<S> p : mInclusiveRangeStartFilters) {
+ if (count++ > 0) {
+ app.append(" & ");
+ }
+ p.appendTo(app, values);
+ }
+ for (PropertyFilter<S> p : mExclusiveRangeEndFilters) {
+ if (count++ > 0) {
+ app.append(" & ");
+ }
+ p.appendTo(app, values);
+ }
+ for (PropertyFilter<S> p : mInclusiveRangeEndFilters) {
+ if (count++ > 0) {
+ app.append(" & ");
+ }
+ p.appendTo(app, values);
+ }
+ 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<S> openCursor(StorableIndex<S> 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<S extends Storable> extends FullScanQueryExecutor<S> {
+ private final Iterable<S> 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<S> type, Iterable<S> iterable) {
+ super(type);
+ mIterable = iterable;
+ }
+
+ protected Cursor<S> openCursor() {
+ return new IteratorCursor<S>(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 <i>A</i>, follows a join, and
+ * produces type <i>B</i>.
+ *
+ * @author Brian S O'Neill
+ * @see JoinedCursorFactory
+ */
+public class JoinedQueryExecutor<A extends Storable, B extends Storable>
+ extends AbstractQueryExecutor<B>
+{
+ private static <A extends Storable, B extends Storable> List<OrderedProperty<B>>
+ transformOrdering(Class<B> bType,
+ String bToAProperty,
+ QueryExecutor<A> aExecutor)
+ {
+ StorableInfo<B> bInfo = StorableIntrospector.examine(bType);
+
+ List<OrderedProperty<A>> aOrdering = aExecutor.getOrdering();
+ int size = aOrdering.size();
+ List<OrderedProperty<B>> bOrdering = new ArrayList<OrderedProperty<B>>(size);
+
+ for (int i=0; i<size; i++) {
+ OrderedProperty<A> aProp = aOrdering.get(i);
+ String bName = bToAProperty + '.' + aProp.getChainedProperty();
+ OrderedProperty<B> bProp = OrderedProperty
+ .get(ChainedProperty.parse(bInfo, bName), aProp.getDirection());
+ bOrdering.add(bProp);
+ }
+
+ return Collections.unmodifiableList(bOrdering);
+ }
+
+ private final JoinedCursorFactory<A, B> mFactory;
+ private final QueryExecutor<A> mAExecutor;
+
+ private final FilterValues<A> mAFilterValues;
+ private final Filter<B> mBFilter;
+ private final List<OrderedProperty<B>> mBOrdering;
+
+ /**
+ * @param repo access to storage instances for properties
+ * @param bType type of <i>B</i> instances
+ * @param bToAProperty property of <i>B</i> type which maps to instances of
+ * <i>A</i> type.
+ * @param aExecutor executor for <i>A</i> instances
+ * @throws IllegalArgumentException if property type is not <i>A</i>
+ */
+ public JoinedQueryExecutor(Repository repo,
+ Class<B> bType,
+ String bToAProperty,
+ QueryExecutor<A> aExecutor)
+ throws SupportException, FetchException, RepositoryException
+ {
+ mFactory = new JoinedCursorFactory<A, B>
+ (repo, bType, bToAProperty, aExecutor.getStorableType());
+ mAExecutor = aExecutor;
+
+ Filter<A> 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 <i>B</i> type which maps to instances of
+ * <i>A</i> type.
+ * @param aExecutor executor for <i>A</i> instances
+ * @throws IllegalArgumentException if property type is not <i>A</i>
+ */
+ public JoinedQueryExecutor(Repository repo,
+ ChainedProperty<B> bToAProperty,
+ QueryExecutor<A> aExecutor)
+ throws SupportException, FetchException, RepositoryException
+ {
+ mFactory = new JoinedCursorFactory<A, B>
+ (repo, bToAProperty, aExecutor.getStorableType());
+ mAExecutor = aExecutor;
+
+ Filter<A> aFilter = aExecutor.getFilter();
+
+ mAFilterValues = aFilter.initialFilterValues();
+ mBFilter = aFilter.accept(new FilterTransformer(bToAProperty), null);
+
+ mBOrdering = transformOrdering(bToAProperty.getPrimeProperty().getEnclosingType(),
+ bToAProperty.toString(), aExecutor);
+ }
+
+ public Filter<B> getFilter() {
+ return mBFilter;
+ }
+
+ public Cursor<B> openCursor(FilterValues<B> values) throws FetchException {
+ return mFactory.join(mAExecutor.openCursor(transferValues(values)));
+ }
+
+ public List<OrderedProperty<B>> getOrdering() {
+ return mBOrdering;
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<B> 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<A> transferValues(FilterValues<B> values) {
+ if (values == null || mAFilterValues == null) {
+ return null;
+ }
+ return mAFilterValues.withValues(values.getSuppliedValues());
+ }
+
+ private class FilterTransformer extends Visitor<A, Filter<B>, Object> {
+ private final Class<B> mBType;
+ private final String mBToAProperty;
+
+ FilterTransformer(Class<B> bType, String bToAProperty) {
+ mBType = bType;
+ mBToAProperty = bToAProperty;
+ }
+
+ FilterTransformer(ChainedProperty<B> bToAProperty) {
+ mBType = bToAProperty.getPrimeProperty().getEnclosingType();
+ mBToAProperty = bToAProperty.toString();
+ }
+
+ public Filter<B> visit(OrFilter<A> aFilter, Object param) {
+ return aFilter.getLeftFilter().accept(this, param)
+ .and(aFilter.getRightFilter().accept(this, param));
+ }
+
+ public Filter<B> visit(AndFilter<A> aFilter, Object param) {
+ return aFilter.getLeftFilter().accept(this, param)
+ .or(aFilter.getRightFilter().accept(this, param));
+ }
+
+ public Filter<B> visit(PropertyFilter<A> aFilter, Object param) {
+ String name;
+
+ ChainedProperty<A> 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<B> 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<B> visit(OpenFilter<A> aFilter, Object param) {
+ return Filter.getOpenFilter(mBType);
+ }
+
+ public Filter<B> visit(ClosedFilter<A> 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<S extends Storable> extends AbstractQueryExecutor<S> {
+ private final StorableIndex<S> mIndex;
+ private final Filter<S> 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<S> index, FilteringScore<S> 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<S> 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<S> openCursor(FilterValues<S> values) throws FetchException {
+ return openCursor(mIndex, values.getValuesFor(mKeyFilter));
+ }
+
+ public Filter<S> getFilter() {
+ return mKeyFilter;
+ }
+
+ /**
+ * Returns an empty list.
+ */
+ public List<OrderedProperty<S>> getOrdering() {
+ return Collections.emptyList();
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> 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<S> openCursor(StorableIndex<S> 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.
+ *
+ * <p>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 = ?"}.
+ *
+ * <p>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.
+ *
+ * <p>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<S extends Storable> {
+ /**
+ * 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 <S extends Storable> OrderingScore<S> evaluate(StorableIndex<S> index,
+ Filter<S> filter,
+ OrderedProperty<S>... 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 <S extends Storable> OrderingScore<S> evaluate
+ (OrderedProperty<S>[] indexProperties,
+ boolean unique,
+ boolean clustered,
+ Filter<S> filter,
+ OrderedProperty<S>... orderings)
+ {
+ if (indexProperties == null) {
+ throw new IllegalArgumentException("Index properties required");
+ }
+
+ // Get filter list early to detect errors.
+ List<PropertyFilter<S>> filterList = PropertyFilterList.get(filter);
+
+ if (orderings == null || orderings.length == 0) {
+ return new OrderingScore<S>(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<ChainedProperty<S>> identityPropSet =
+ new HashSet<ChainedProperty<S>>(filterList.size());
+
+ for (PropertyFilter<S> 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<indexProperties.length; i++) {
+ ChainedProperty<S> indexProp = indexProperties[i].getChainedProperty();
+ if (!identityPropSet.contains(indexProp)) {
+ // Missed a property, so ordering is still relevent.
+ break uniquelyCheck;
+ }
+ }
+
+ return new OrderingScore<S>(clustered,
+ indexProperties.length,
+ null, // no handled properties
+ null, // no remainder properties
+ false); // no need to reverse order
+ }
+
+ List<OrderedProperty<S>> handledProperties = new ArrayList<OrderedProperty<S>>();
+ List<OrderedProperty<S>> remainderProperties = new ArrayList<OrderedProperty<S>>();
+
+ Boolean shouldReverseOrder = null;
+
+ Set<ChainedProperty<S>> seen = new HashSet<ChainedProperty<S>>();
+
+ int indexPos = 0;
+ calcScore:
+ for (int i=0; i<orderings.length; i++) {
+ OrderedProperty<S> property = orderings[i];
+ ChainedProperty<S> 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<S> indexProp = indexProperties[indexPos];
+ ChainedProperty<S> 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<S>(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<OrderingScore<?>> fullComparator() {
+ return Full.INSTANCE;
+ }
+
+ private final boolean mIndexClustered;
+ private final int mIndexPropertyCount;
+
+ private final List<OrderedProperty<S>> mHandledOrderings;
+ private final List<OrderedProperty<S>> mRemainderOrderings;
+
+ private final boolean mShouldReverseOrder;
+
+ private OrderingScore(boolean indexClustered,
+ int indexPropertyCount,
+ List<OrderedProperty<S>> handledOrderings,
+ List<OrderedProperty<S>> 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<OrderedProperty<S>> 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<OrderedProperty<S>> 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<S> 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<OrderedProperty<S>> thisRemainderOrderings = getRemainderOrderings();
+ List<OrderedProperty<S>> otherRemainderOrderings = other.getRemainderOrderings();
+
+ int size = Math.min(thisRemainderOrderings.size(), otherRemainderOrderings.size());
+ for (int i=0; i<size; i++) {
+ if (!thisRemainderOrderings.get(i).equals(otherRemainderOrderings.get(i))) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ return false;
+ }
+
+ /**
+ * Merges the remainder orderings of this score with the one given. Call
+ * canMergeRemainderOrderings first to verify if the merge makes any sense.
+ */
+ public List<OrderedProperty<S>> mergeRemainderOrderings(OrderingScore<S> other) {
+ List<OrderedProperty<S>> thisRemainderOrderings = getRemainderOrderings();
+
+ if (this == other) {
+ return thisRemainderOrderings;
+ }
+
+ List<OrderedProperty<S>> 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<OrderingScore<?>> {
+ static final Comparator<OrderingScore<?>> 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<Filter<?>, 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 <S extends Storable> List<PropertyFilter<S>> get(Filter<S> filter) {
+ List<PropertyFilter<S>> list;
+
+ synchronized (cCache) {
+ list = (List<PropertyFilter<S>>) cCache.get(filter);
+ }
+
+ if (list != null) {
+ return list;
+ }
+
+ if (filter == null) {
+ list = Collections.emptyList();
+ } else if (filter instanceof PropertyFilter) {
+ list = Collections.singletonList((PropertyFilter<S>) filter);
+ } else {
+ list = new ArrayList<PropertyFilter<S>>();
+ final List<PropertyFilter<S>> flist = list;
+
+ filter.accept(new Visitor<S, Object, Object>() {
+ public Object visit(OrFilter<S> filter, Object param) {
+ throw new IllegalArgumentException("Logical 'or' not allowed");
+ }
+
+ public Object visit(PropertyFilter<S> filter, Object param) {
+ flist.add(filter);
+ return null;
+ }
+ }, null);
+
+ Collections.sort(list, new PropertyFilterComparator<S>());
+
+ ((ArrayList) list).trimToSize();
+ list = Collections.unmodifiableList(list);
+ }
+
+ synchronized (cCache) {
+ cCache.put(filter, list);
+ }
+
+ return list;
+ }
+
+ private static class PropertyFilterComparator<S extends Storable>
+ implements Comparator<PropertyFilter<S>>
+ {
+ public int compare(PropertyFilter<S> a, PropertyFilter<S> b) {
+ if (a.getOperator() != b.getOperator()) {
+ if (a.getOperator() == RelOp.EQ) {
+ return -1;
+ }
+ if (a.getOperator() == RelOp.NE) {
+ return 1;
+ }
+ if (b.getOperator() == RelOp.EQ) {
+ return 1;
+ }
+ if (b.getOperator() == RelOp.NE) {
+ return -1;
+ }
+ }
+ return 0;
+ }
+ }
+}
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 <i>query plan</i>.
+ *
+ * @author Brian S O'Neill
+ */
+public interface QueryExecutor<S extends Storable> {
+ /**
+ * Returns the storable type that this executor operates on.
+ */
+ Class<S> getStorableType();
+
+ /**
+ * Returns a new cursor using the given filter values.
+ */
+ Cursor<S> openCursor(FilterValues<S> values) throws FetchException;
+
+ /**
+ * Counts the query results using the given filter values.
+ */
+ long count(FilterValues<S> values) throws FetchException;
+
+ /**
+ * Returns the filter used by this QueryExecutor.
+ *
+ * @return query filter, never null
+ */
+ Filter<S> getFilter();
+
+ /**
+ * Returns the result ordering of this QueryExecutor.
+ *
+ * @return query ordering in an unmodifiable list
+ */
+ List<OrderedProperty<S>> 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<S> 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<S> 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<S extends Storable> extends AbstractQueryExecutor<S> {
+ private final QueryExecutor<S> mExecutor;
+
+ private final Comparator<S> mHandledComparator;
+ private final Comparator<S> mFinisherComparator;
+
+ private final List<OrderedProperty<S>> mHandledOrderings;
+ private final List<OrderedProperty<S>> mRemainderOrderings;
+
+ /**
+ * @param executor executor to wrap
+ * @throws IllegalArgumentException if executor is null or if remainder
+ * orderings is empty
+ */
+ public SortedQueryExecutor(QueryExecutor<S> executor,
+ List<OrderedProperty<S>> handledOrderings,
+ List<OrderedProperty<S>> 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<S> openCursor(FilterValues<S> values) throws FetchException {
+ Cursor<S> cursor = mExecutor.openCursor(values);
+ SortBuffer<S> buffer = createSortBuffer();
+ return new SortedCursor<S>(cursor, buffer, mHandledComparator, mFinisherComparator);
+ }
+
+ @Override
+ public long count(FilterValues<S> values) throws FetchException {
+ return mExecutor.count(values);
+ }
+
+ public Filter<S> getFilter() {
+ return mExecutor.getFilter();
+ }
+
+ public List<OrderedProperty<S>> getOrdering() {
+ if (mHandledOrderings.size() == 0) {
+ return mRemainderOrderings;
+ }
+ if (mRemainderOrderings.size() == 0) {
+ return mHandledOrderings;
+ }
+ List<OrderedProperty<S>> ordering = new ArrayList<OrderedProperty<S>>
+ (mHandledOrderings.size() + mRemainderOrderings.size());
+
+ ordering.addAll(mHandledOrderings);
+ ordering.addAll(mRemainderOrderings);
+
+ return ordering;
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> 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<S> 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.
+ *
+ * <p>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<S extends Storable> {
+ final IndexedQueryAnalyzer<S> mIndexAnalyzer;
+
+ /**
+ * @param type type of storable being queried
+ * @param indexProvider
+ * @throws IllegalArgumentException if type or indexProvider is null
+ */
+ public UnionQueryAnalyzer(Class<S> type, IndexProvider indexProvider) {
+ mIndexAnalyzer = new IndexedQueryAnalyzer<S>(type, indexProvider);
+ }
+
+ /**
+ * @param filter optional filter which must be {@link Filter#isBound bound}
+ * @param orderings properties which define desired ordering
+ */
+ public Result analyze(Filter<S> filter, OrderedProperty<S>... 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<IndexedQueryAnalyzer<S>.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<OrderedProperty<S>> isTotalOrdering() {
+ // FIXME
+ return null;
+ }
+
+ private List<IndexedQueryAnalyzer<S>.Result>
+ splitIntoSubResults(Filter<S> filter, OrderedProperty<S>... orderings)
+ {
+ Splitter splitter = new Splitter(orderings);
+ filter.accept(splitter, null);
+
+ List<IndexedQueryAnalyzer<S>.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<S>.Result full = null;
+ for (IndexedQueryAnalyzer<S>.Result result : subResults) {
+ if (!result.handlesAnything()) {
+ full = result;
+ break;
+ }
+ }
+
+ if (full == null) {
+ // Okay, no full scan needed.
+ return subResults;
+ }
+
+ List<IndexedQueryAnalyzer<S>.Result> mergedResults =
+ new ArrayList<IndexedQueryAnalyzer<S>.Result>();
+
+ for (IndexedQueryAnalyzer<S>.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<IndexedQueryAnalyzer<S>.Result> mSubResults;
+
+ Result(List<IndexedQueryAnalyzer<S>.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<IndexedQueryAnalyzer<S>.Result> getSubResults() {
+ return mSubResults;
+ }
+
+ /**
+ * If more than one sub-result, then a total ordering is
+ * imposed. Otherwise, null is returned.
+ */
+ public List<OrderedProperty<S>> getTotalOrdering() {
+ // FIXME
+ return null;
+ }
+ }
+
+ /**
+ * Analyzes a disjunctive normal filter into sub-results over filters that
+ * only contain 'and' operations.
+ */
+ private class Splitter extends Visitor<S, Object, Object> {
+ private final OrderedProperty<S>[] mOrderings;
+
+ final List<IndexedQueryAnalyzer<S>.Result> mSubResults;
+
+ Splitter(OrderedProperty<S>... orderings) {
+ mOrderings = orderings;
+ mSubResults = new ArrayList<IndexedQueryAnalyzer<S>.Result>();
+ }
+
+ @Override
+ public Object visit(OrFilter<S> filter, Object param) {
+ Filter<S> left = filter.getLeftFilter();
+ if (!(left instanceof OrFilter)) {
+ subAnalyze(left);
+ } else {
+ left.accept(this, param);
+ }
+ Filter<S> 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<S> 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<S> filter, Object param) {
+ subAnalyze(filter);
+ return null;
+ }
+
+ private void subAnalyze(Filter<S> subFilter) {
+ IndexedQueryAnalyzer<S>.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<size; i++) {
+ IndexedQueryAnalyzer<S>.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<S extends Storable> extends AbstractQueryExecutor<S> {
+ private static <E> E ensureNotNull(E e) {
+ if (e == null) {
+ throw new IllegalArgumentException();
+ }
+ return e;
+ }
+
+ private final QueryExecutor<S>[] mExecutors;
+ private final List<OrderedProperty<S>> mTotalOrderings;
+ private final Comparator<S> 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<S>... 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<QueryExecutor<S>> executors) {
+ if (executors == null || executors.size() == 0) {
+ throw new IllegalArgumentException();
+ }
+ List<OrderedProperty<S>> totalOrderings = executors.get(0).getOrdering();
+ // Compare for consistency.
+ for (int i=1; i<executors.size(); i++) {
+ if (!totalOrderings.equals(executors.get(i).getOrdering())) {
+ throw new IllegalArgumentException("Ordering doesn't match");
+ }
+ }
+ mExecutors = new QueryExecutor[executors.size()];
+ executors.toArray(mExecutors);
+ mTotalOrderings = totalOrderings;
+ mOrderComparator = SortedCursor.createComparator(totalOrderings);
+ }
+
+ public Cursor<S> openCursor(FilterValues<S> values) throws FetchException {
+ Cursor<S> cursor = null;
+ for (QueryExecutor<S> executor : mExecutors) {
+ Cursor<S> subCursor = executor.openCursor(values);
+ cursor = (cursor == null) ? subCursor
+ : new UnionCursor<S>(cursor, subCursor, mOrderComparator);
+ }
+ return cursor;
+ }
+
+ /**
+ * Returns the combined filter of the wrapped executors.
+ */
+ public Filter<S> getFilter() {
+ Filter<S> filter = null;
+ for (QueryExecutor<S> executor : mExecutors) {
+ Filter<S> subFilter = executor.getFilter();
+ filter = filter == null ? subFilter : filter.or(subFilter);
+ }
+ return filter;
+ }
+
+ public List<OrderedProperty<S>> getOrdering() {
+ return mTotalOrderings;
+ }
+
+ public boolean printPlan(Appendable app, int indentLevel, FilterValues<S> values)
+ throws IOException
+ {
+ indent(app, indentLevel);
+ app.append("union");
+ newline(app);
+ for (QueryExecutor<S> 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;
|