From f5a69fbf5e7e343d094687263604ce18b7b6dae5 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sat, 30 Sep 2006 23:07:46 +0000 Subject: Finished join optimization. --- .../carbonado/cursor/JoinedCursorFactory.java | 467 --------------- .../carbonado/cursor/MultiTransformedCursor.java | 1 - .../amazon/carbonado/cursor/TransformedCursor.java | 1 - .../com/amazon/carbonado/qe/CompositeScore.java | 38 +- .../qe/DelegatedQueryExecutorFactory.java | 51 ++ .../amazon/carbonado/qe/FullScanQueryExecutor.java | 6 + .../amazon/carbonado/qe/IndexedQueryAnalyzer.java | 130 +++-- .../amazon/carbonado/qe/IndexedQueryExecutor.java | 32 +- .../amazon/carbonado/qe/IterableQueryExecutor.java | 2 +- .../amazon/carbonado/qe/JoinedQueryExecutor.java | 643 ++++++++++++++++----- .../com/amazon/carbonado/qe/KeyQueryExecutor.java | 6 + .../java/com/amazon/carbonado/qe/OrderingList.java | 17 + .../java/com/amazon/carbonado/qe/QueryEngine.java | 12 +- .../amazon/carbonado/qe/QueryExecutorFactory.java | 2 - .../amazon/carbonado/qe/SortedQueryExecutor.java | 7 + .../com/amazon/carbonado/qe/StorageAccess.java | 5 + .../carbonado/repo/indexed/IndexedStorage.java | 5 + .../com/amazon/carbonado/spi/CodeBuilderUtil.java | 6 + 18 files changed, 754 insertions(+), 677 deletions(-) delete mode 100644 src/main/java/com/amazon/carbonado/cursor/JoinedCursorFactory.java create mode 100644 src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutorFactory.java (limited to 'src/main/java') diff --git a/src/main/java/com/amazon/carbonado/cursor/JoinedCursorFactory.java b/src/main/java/com/amazon/carbonado/cursor/JoinedCursorFactory.java deleted file mode 100644 index b689c7e..0000000 --- a/src/main/java/com/amazon/carbonado/cursor/JoinedCursorFactory.java +++ /dev/null @@ -1,467 +0,0 @@ -/* - * Copyright 2006 Amazon Technologies, Inc. or its affiliates. - * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks - * of Amazon Technologies, Inc. or its affiliates. All rights reserved. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.amazon.carbonado.cursor; - -import java.lang.reflect.Field; - -import java.util.Map; - -import org.cojen.classfile.ClassFile; -import org.cojen.classfile.CodeBuilder; -import org.cojen.classfile.FieldInfo; -import org.cojen.classfile.Label; -import org.cojen.classfile.LocalVariable; -import org.cojen.classfile.MethodInfo; -import org.cojen.classfile.Modifiers; -import org.cojen.classfile.TypeDesc; - -import org.cojen.util.ClassInjector; -import org.cojen.util.KeyFactory; -import org.cojen.util.SoftValuedHashMap; -import org.cojen.util.WeakIdentityMap; - -import com.amazon.carbonado.Cursor; -import com.amazon.carbonado.FetchException; -import com.amazon.carbonado.Query; -import com.amazon.carbonado.Repository; -import com.amazon.carbonado.RepositoryException; -import com.amazon.carbonado.Storable; -import com.amazon.carbonado.Storage; -import com.amazon.carbonado.SupportException; - -import com.amazon.carbonado.info.ChainedProperty; -import com.amazon.carbonado.info.StorableInfo; -import com.amazon.carbonado.info.StorableIntrospector; -import com.amazon.carbonado.info.StorableProperty; - -import com.amazon.carbonado.util.QuickConstructorGenerator; - -import com.amazon.carbonado.spi.CodeBuilderUtil; -import static com.amazon.carbonado.spi.CommonMethodNames.*; - -/** - * Given two joined types source and target, this factory - * converts a cursor over type source into a cursor over type - * target. For example, consider two storable types, Employer and - * Person. A query filter for persons with a given employer might look like: - * {@code "employer.name = ?" } The join can be manually implemented by - * querying for employers (the source) and then using this factory to produce - * persons (the target): - * - * 
- * JoinedCursorFactory<Employer, Person> factory = new JoinedCursorFactory<Employer, Person>
- *     (repo, Person.class, "employer", Employer.class);
- *
- * Cursor<Employer> employerCursor = repo.storageFor(Employer.class)
- *     .query("name = ?").with(...).fetch();
- *
- * Cursor<Person> personCursor = factory.join(employerCursor);
- *
- * - * Chained properties are supported as well. A query filter for persons with an - * employer in a given state might look like: {@code "employer.address.state = ?" } - * The join can be manually implemented as: - * - * 
- * JoinedCursorFactory<Address, Person> factory = new JoinedCursorFactory<Address, Person>
- *     (repo, Person.class, "employer.address", Address.class);
- *
- * Cursor<Address> addressCursor = repo.storageFor(Address.class)
- *     .query("state = ?").with(...).fetch();
- *
- * Cursor<Person> personCursor = factory.join(addressCursor);
- *
- * - * @author Brian S O'Neill - * @see TransformedCursor - * @see MultiTransformedCursor - * @param source type, can be anything - * @param target type, must be a Storable - */ -public class JoinedCursorFactory { - private static final String STORAGE_FIELD_NAME = "storage"; - private static final String QUERY_FIELD_NAME = "query"; - private static final String QUERY_FILTER_FIELD_NAME = "queryFilter"; - private static final String ACTIVE_SOURCE_FIELD_NAME = "active"; - - private static final Map cJoinerCursorClassCache; - - static { - cJoinerCursorClassCache = new SoftValuedHashMap(); - } - - private static synchronized Joiner - newBasicJoiner(StorableProperty targetToSourceProperty, Storage targetStorage) - throws FetchException - { - Class sourceType = targetToSourceProperty.getType(); - - final Object key = KeyFactory.createKey - (new Object[] {sourceType, - targetToSourceProperty.getEnclosingType(), - targetToSourceProperty.getName()}); - - Class clazz = cJoinerCursorClassCache.get(key); - - if (clazz == null) { - clazz = generateBasicJoinerCursor(sourceType, targetToSourceProperty); - cJoinerCursorClassCache.put(key, clazz); - } - - // Transforming cursor class may need a Query to operate on. - Query targetQuery = null; - try { - String filter = (String) clazz.getField(QUERY_FILTER_FIELD_NAME).get(null); - targetQuery = targetStorage.query(filter); - } catch (NoSuchFieldException e) { - } catch (IllegalAccessException e) { - } - - BasicJoiner.Factory factory = (BasicJoiner.Factory) QuickConstructorGenerator - .getInstance(clazz, BasicJoiner.Factory.class); - - return new BasicJoiner(factory, targetStorage, targetQuery); - } - - private static Class> - generateBasicJoinerCursor(Class sourceType, StorableProperty targetToSourceProperty) - { - final int propCount = targetToSourceProperty.getJoinElementCount(); - - // Determine if join is one-to-one, in which case slightly more optimal - // code can be generated. - boolean isOneToOne = true; - for (int i=0; i targetType = targetToSourceProperty.getEnclosingType(); - - String packageName; - { - String name = targetType.getName(); - int index = name.lastIndexOf('.'); - if (index >= 0) { - packageName = name.substring(0, index); - } else { - packageName = ""; - } - } - - ClassLoader loader = targetType.getClassLoader(); - - ClassInjector ci = ClassInjector.create(packageName + ".JoinedCursor", loader); - Class superclass = isOneToOne ? TransformedCursor.class : MultiTransformedCursor.class; - ClassFile cf = new ClassFile(ci.getClassName(), superclass); - cf.markSynthetic(); - cf.setSourceFile(JoinedCursorFactory.class.getName()); - cf.setTarget("1.5"); - - final TypeDesc queryType = TypeDesc.forClass(Query.class); - final TypeDesc cursorType = TypeDesc.forClass(Cursor.class); - final TypeDesc storageType = TypeDesc.forClass(Storage.class); - final TypeDesc storableType = TypeDesc.forClass(Storable.class); - - if (isOneToOne) { - cf.addField(Modifiers.PRIVATE.toFinal(true), STORAGE_FIELD_NAME, storageType); - } else { - // Field to hold query which fetches type T. - cf.addField(Modifiers.PRIVATE.toFinal(true), QUERY_FIELD_NAME, queryType); - } - - boolean canSetSourceReference = targetToSourceProperty.getWriteMethod() != null; - - if (canSetSourceReference && !isOneToOne) { - // Field to hold active S storable. - cf.addField(Modifiers.PRIVATE, ACTIVE_SOURCE_FIELD_NAME, - TypeDesc.forClass(sourceType)); - } - - // Constructor accepts a Storage and Query, but Storage is only used - // for one-to-one, and Query is only used for one-to-many. - { - MethodInfo mi = cf.addConstructor(Modifiers.PUBLIC, - new TypeDesc[] {cursorType, storageType, queryType}); - CodeBuilder b = new CodeBuilder(mi); - - b.loadThis(); - b.loadLocal(b.getParameter(0)); // pass S cursor to superclass - b.invokeSuperConstructor(new TypeDesc[] {cursorType}); - - if (isOneToOne) { - b.loadThis(); - b.loadLocal(b.getParameter(1)); // push T storage to stack - b.storeField(STORAGE_FIELD_NAME, storageType); - } else { - b.loadThis(); - b.loadLocal(b.getParameter(2)); // push T query to stack - b.storeField(QUERY_FIELD_NAME, queryType); - } - - b.returnVoid(); - } - - // For one-to-many, a query is needed. Save the query filter in a - // public static field to be grabbed later. - if (!isOneToOne) { - StringBuilder queryBuilder = new StringBuilder(); - - for (int i=0; i 0) { - queryBuilder.append(" & "); - } - queryBuilder.append(targetToSourceProperty.getInternalJoinElement(i).getName()); - queryBuilder.append(" = ?"); - } - - FieldInfo fi = cf.addField(Modifiers.PUBLIC.toStatic(true).toFinal(true), - QUERY_FILTER_FIELD_NAME, TypeDesc.STRING); - fi.setConstantValue(queryBuilder.toString()); - } - - // Implement the transform method. - if (isOneToOne) { - MethodInfo mi = cf.addMethod(Modifiers.PROTECTED, "transform", TypeDesc.OBJECT, - new TypeDesc[] {TypeDesc.OBJECT}); - mi.addException(TypeDesc.forClass(FetchException.class)); - CodeBuilder b = new CodeBuilder(mi); - - LocalVariable sourceVar = b.createLocalVariable(null, storableType); - b.loadLocal(b.getParameter(0)); - b.checkCast(TypeDesc.forClass(sourceType)); - b.storeLocal(sourceVar); - - // Prepare T storable. - b.loadThis(); - b.loadField(STORAGE_FIELD_NAME, storageType); - b.invokeInterface(storageType, PREPARE_METHOD_NAME, storableType, null); - LocalVariable targetVar = b.createLocalVariable(null, storableType); - b.checkCast(TypeDesc.forClass(targetType)); - b.storeLocal(targetVar); - - // Copy pk property values from S to T. - for (int i=0; i internal = targetToSourceProperty.getInternalJoinElement(i); - StorableProperty external = targetToSourceProperty.getExternalJoinElement(i); - - b.loadLocal(targetVar); - b.loadLocal(sourceVar); - b.invoke(external.getReadMethod()); - b.invoke(internal.getWriteMethod()); - } - - // tryLoad target. - b.loadLocal(targetVar); - b.invokeInterface(storableType, TRY_LOAD_METHOD_NAME, TypeDesc.BOOLEAN, null); - Label wasLoaded = b.createLabel(); - b.ifZeroComparisonBranch(wasLoaded, "!="); - - b.loadNull(); - b.returnValue(storableType); - - wasLoaded.setLocation(); - - if (canSetSourceReference) { - b.loadLocal(targetVar); - b.loadLocal(sourceVar); - b.invoke(targetToSourceProperty.getWriteMethod()); - } - - b.loadLocal(targetVar); - b.returnValue(storableType); - } else { - MethodInfo mi = cf.addMethod(Modifiers.PROTECTED, "transform", cursorType, - new TypeDesc[] {TypeDesc.OBJECT}); - mi.addException(TypeDesc.forClass(FetchException.class)); - CodeBuilder b = new CodeBuilder(mi); - - LocalVariable sourceVar = b.createLocalVariable(null, storableType); - b.loadLocal(b.getParameter(0)); - b.checkCast(TypeDesc.forClass(sourceType)); - b.storeLocal(sourceVar); - - if (canSetSourceReference) { - b.loadThis(); - b.loadLocal(sourceVar); - b.storeField(ACTIVE_SOURCE_FIELD_NAME, TypeDesc.forClass(sourceType)); - } - - // Populate query parameters. - b.loadThis(); - b.loadField(QUERY_FIELD_NAME, queryType); - - for (int i=0; i external = targetToSourceProperty.getExternalJoinElement(i); - b.loadLocal(sourceVar); - b.invoke(external.getReadMethod()); - - TypeDesc bindType = CodeBuilderUtil.bindQueryParam(external.getType()); - CodeBuilderUtil.convertValue(b, external.getType(), bindType.toClass()); - b.invokeInterface(queryType, WITH_METHOD_NAME, queryType, - new TypeDesc[] {bindType}); - } - - // Now fetch and return. - b.invokeInterface(queryType, FETCH_METHOD_NAME, cursorType, null); - b.returnValue(cursorType); - } - - if (canSetSourceReference && !isOneToOne) { - // Override the "next" method to set S object on T. - MethodInfo mi = cf.addMethod(Modifiers.PUBLIC, "next", TypeDesc.OBJECT, null); - mi.addException(TypeDesc.forClass(FetchException.class)); - CodeBuilder b = new CodeBuilder(mi); - - b.loadThis(); - b.invokeSuper(TypeDesc.forClass(MultiTransformedCursor.class), - "next", TypeDesc.OBJECT, null); - b.checkCast(TypeDesc.forClass(targetType)); - b.dup(); - - b.loadThis(); - b.loadField(ACTIVE_SOURCE_FIELD_NAME, TypeDesc.forClass(sourceType)); - b.invoke(targetToSourceProperty.getWriteMethod()); - - b.returnValue(storableType); - } - - return (Class>) ci.defineClass(cf); - } - - private final Joiner mJoiner; - - /** - * @param repo access to storage instances for properties - * @param targetType type of target instances - * @param targetToSourceProperty property of target type which maps - * to instances of source type. - * @param sourceType type of source instances - * @throws IllegalArgumentException if property type is not source - */ - public JoinedCursorFactory(Repository repo, - Class targetType, - String targetToSourceProperty, - Class sourceType) - throws SupportException, FetchException, RepositoryException - { - this(repo, - ChainedProperty.parse(StorableIntrospector.examine(targetType), - targetToSourceProperty), - sourceType); - } - - /** - * @param repo access to storage instances for properties - * @param targetToSourceProperty property of target type which maps - * to instances of source type. - * @param sourceType type of source instances - * @throws IllegalArgumentException if property type is not source - */ - public JoinedCursorFactory(Repository repo, - ChainedProperty targetToSourceProperty, - Class sourceType) - throws SupportException, FetchException, RepositoryException - { - if (targetToSourceProperty.getType() != sourceType) { - throw new IllegalArgumentException - ("Property is not of type \"" + sourceType.getName() + "\": " + - targetToSourceProperty); - } - - StorableProperty primeTarget = targetToSourceProperty.getPrimeProperty(); - Storage primeTargetStorage = repo.storageFor(primeTarget.getEnclosingType()); - - Joiner joiner = newBasicJoiner(primeTarget, primeTargetStorage); - - int chainCount = targetToSourceProperty.getChainCount(); - for (int i=0; i) joiner; - } - - /** - * Given a cursor over type source, returns a new cursor over joined - * property of type target. - */ - public Cursor join(Cursor cursor) { - return mJoiner.join(cursor); - } - - private static interface Joiner { - Cursor join(Cursor cursor); - } - - /** - * Support for joins without an intermediate hop. - */ - private static class BasicJoiner implements Joiner { - private final Factory mJoinerFactory; - private final Storage mTargetStorage; - private final Query mTargetQuery; - - BasicJoiner(Factory factory, Storage targetStorage, Query targetQuery) { - mJoinerFactory = factory; - mTargetStorage = targetStorage; - mTargetQuery = targetQuery; - } - - public Cursor join(Cursor cursor) { - return mJoinerFactory.newJoinedCursor(cursor, mTargetStorage, mTargetQuery); - } - - /** - * Needs to be public for {@link QuickConstructorGenerator}. - */ - public static interface Factory { - Cursor newJoinedCursor(Cursor cursor, - Storage targetStorage, Query targetQuery); - } - } - - /** - * Support for joins with an intermediate hop -- multi-way joins. - */ - private static class MultiJoiner - implements Joiner - { - private final Joiner mSourceToMid; - private final Joiner mMidToTarget; - - MultiJoiner(Joiner sourceToMidJoiner, Joiner midToTargetJoiner) { - mSourceToMid = sourceToMidJoiner; - mMidToTarget = midToTargetJoiner; - } - - public Cursor join(Cursor cursor) { - return mMidToTarget.join(mSourceToMid.join(cursor)); - } - } -} diff --git a/src/main/java/com/amazon/carbonado/cursor/MultiTransformedCursor.java b/src/main/java/com/amazon/carbonado/cursor/MultiTransformedCursor.java index 3f06421..7606eab 100644 --- a/src/main/java/com/amazon/carbonado/cursor/MultiTransformedCursor.java +++ b/src/main/java/com/amazon/carbonado/cursor/MultiTransformedCursor.java @@ -31,7 +31,6 @@ import com.amazon.carbonado.FetchInterruptedException; * joins. * * @author Brian S O'Neill - * @see JoinedCursorFactory * @param source type, can be anything * @param target type, can be anything */ diff --git a/src/main/java/com/amazon/carbonado/cursor/TransformedCursor.java b/src/main/java/com/amazon/carbonado/cursor/TransformedCursor.java index 428e74e..70161cc 100644 --- a/src/main/java/com/amazon/carbonado/cursor/TransformedCursor.java +++ b/src/main/java/com/amazon/carbonado/cursor/TransformedCursor.java @@ -30,7 +30,6 @@ import com.amazon.carbonado.FetchInterruptedException; * one-to-one joins. Use {@link MultiTransformedCursor} for one-to-many joins. * * @author Brian S O'Neill - * @see JoinedCursorFactory * @param source type, can be anything * @param target type, can be anything */ diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java index 6d0fad5..eba6106 100644 --- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java +++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java @@ -91,6 +91,18 @@ public class CompositeScore { return new CompositeScore(filteringScore, orderingScore); } + /** + * Returns a partial comparator suited for comparing local indexes to + * foreign indexes. It determines which CompositeScores are better by + * examining identity matches, range matches and ordering. 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> localForeignComparator() { + return Comp.LOCAL_FOREIGN; + } + /** * Returns a comparator which determines which CompositeScores are * better. It compares identity matches, range matches, ordering, open @@ -100,7 +112,7 @@ public class CompositeScore { * {@code 0} if equal, or {@code >0} if second is better. */ public static Comparator> fullComparator() { - return Full.INSTANCE; + return Comp.FULL; } private final FilteringScore mFilteringScore; @@ -157,8 +169,15 @@ public class CompositeScore { return "CompositeScore {" + getFilteringScore() + ", " + getOrderingScore() + '}'; } - private static class Full implements Comparator> { - static final Comparator> INSTANCE = new Full(); + private static class Comp implements Comparator> { + static final Comparator> LOCAL_FOREIGN = new Comp(false); + static final Comparator> FULL = new Comp(true); + + private final boolean mFull; + + private Comp(boolean full) { + mFull = full; + } public int compare(CompositeScore first, CompositeScore second) { int result = FilteringScore.nullCompare(first, second); @@ -189,7 +208,18 @@ public class CompositeScore { } } - result = FilteringScore.fullComparator().compare(firstScore, secondScore); + if (mFull) { + result = FilteringScore.fullComparator().compare(firstScore, secondScore); + } else { + // Favor index that has any matches. + if (firstScore.hasAnyMatches()) { + if (!secondScore.hasAnyMatches()) { + return -1; + } + } else if (secondScore.hasAnyMatches()) { + return 1; + } + } return result; } diff --git a/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutorFactory.java b/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutorFactory.java new file mode 100644 index 0000000..fae22b4 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/qe/DelegatedQueryExecutorFactory.java @@ -0,0 +1,51 @@ +/* + * 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.FetchException; +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.Storage; + +import com.amazon.carbonado.filter.Filter; + +/** + * QueryExecutorFactory which produces executors which delegate via {@link DelegatedQueryExecutor}. + * + * @author Brian S O'Neill + */ +public class DelegatedQueryExecutorFactory implements QueryExecutorFactory { + private final Storage mStorage; + + public DelegatedQueryExecutorFactory(Storage rootStorage) { + if (rootStorage == null) { + throw new IllegalArgumentException(); + } + mStorage = rootStorage; + } + + public Class getStorableType() { + return mStorage.getStorableType(); + } + + public QueryExecutor executor(Filter filter, OrderingList ordering) + throws FetchException + { + return new DelegatedQueryExecutor(mStorage, filter, ordering); + } +} diff --git a/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java index b8035f0..f0e4517 100644 --- a/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/FullScanQueryExecutor.java @@ -45,6 +45,9 @@ public class FullScanQueryExecutor extends AbstractQueryExec * @throws IllegalArgumentException if support is null */ public FullScanQueryExecutor(Support support) { + if (support == null && this instanceof Support) { + support = (Support) this; + } if (support == null) { throw new IllegalArgumentException(); } @@ -88,6 +91,9 @@ public class FullScanQueryExecutor extends AbstractQueryExec return true; } + /** + * Provides support for {@link FullScanQueryExecutor}. + */ public static interface Support { Class getStorableType(); diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java index dfa76ac..219400c 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java @@ -90,26 +90,35 @@ public class IndexedQueryAnalyzer { throw new IllegalArgumentException("Filter must be bound"); } - final Comparator> comparator = CompositeScore.fullComparator(); - // First find best local index. - CompositeScore bestScore = null; + CompositeScore bestLocalScore = null; StorableIndex bestLocalIndex = null; + final Comparator> fullComparator = CompositeScore.fullComparator(); + Collection> localIndexes = indexesFor(getStorableType()); if (localIndexes != null) { for (StorableIndex index : localIndexes) { CompositeScore candidateScore = CompositeScore.evaluate(index, filter, ordering); - if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { - bestScore = candidateScore; + if (bestLocalScore == null + || fullComparator.compare(candidateScore, bestLocalScore) < 0) + { + bestLocalScore = candidateScore; bestLocalIndex = index; } } } - // Now try to find better foreign index. + // Now try to find best foreign index. + + if (bestLocalScore.getFilteringScore().isKeyMatch()) { + // Don't bother checking foreign indexes. The local one is perfect. + return new Result(filter, bestLocalScore, bestLocalIndex, null, null); + } + + CompositeScore bestForeignScore = null; StorableIndex bestForeignIndex = null; ChainedProperty bestForeignProperty = null; @@ -134,20 +143,47 @@ public class IndexedQueryAnalyzer { filter, ordering); - if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { - bestScore = candidateScore; - bestLocalIndex = null; + if (bestForeignScore == null + || fullComparator.compare(candidateScore, bestForeignScore) < 0) + { + bestForeignScore = candidateScore; bestForeignIndex = index; bestForeignProperty = foreignIndexes.mProperty; } } } - return new Result(filter, - bestScore, - bestLocalIndex, - bestForeignIndex, - bestForeignProperty); + // Check if foreign index is better than local index. + + if (bestLocalScore != null && bestForeignScore != null) { + // When comparing local index to foreign index, use a slightly less + // discriminating comparator, to prevent foreign indexes from + // looking too good. + + Comparator> comp = CompositeScore.localForeignComparator(); + + if (comp.compare(bestForeignScore, bestLocalScore) < 0) { + // Foreign is better. + bestLocalScore = null; + } else { + // Local is better. + bestForeignScore = null; + } + } + + CompositeScore bestScore; + + if (bestLocalScore != null) { + bestScore = bestLocalScore; + bestForeignIndex = null; + bestForeignProperty = null; + } else { + bestScore = bestForeignScore; + bestLocalIndex = null; + } + + return new Result + (filter, bestScore, bestLocalIndex, bestForeignIndex, bestForeignProperty); } /** @@ -233,23 +269,6 @@ public class IndexedQueryAnalyzer { return false; } - private boolean simpleAnalyze(Filter filter) - throws SupportException, RepositoryException - { - Collection> indexes = indexesFor(filter.getStorableType()); - - if (indexes != null) { - for (StorableIndex index : indexes) { - FilteringScore score = FilteringScore.evaluate(index, filter); - if (score.getRemainderCount() == 0) { - return true; - } - } - } - - return false; - } - private Collection> indexesFor(Class type) throws SupportException, RepositoryException { @@ -363,7 +382,7 @@ public class IndexedQueryAnalyzer { /** * 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 + * property corresponds to the "targetToSourceProperty" of {@link * JoinedQueryExecutor}. */ public ChainedProperty getForeignProperty() { @@ -475,7 +494,12 @@ public class IndexedQueryAnalyzer { } } - QueryExecutor executor = baseExecutor(localAccess); + QueryExecutor executor = baseLocalExecutor(localAccess); + + if (executor == null) { + return JoinedQueryExecutor.build + (mRepoAccess, getForeignProperty(), getFilter(), getOrdering()); + } Filter remainderFilter = getRemainderFilter(); if (remainderFilter != null) { @@ -494,9 +518,10 @@ public class IndexedQueryAnalyzer { return executor; } - private QueryExecutor baseExecutor(StorageAccess localAccess) - throws SupportException, FetchException, RepositoryException - { + /** + * Returns local executor or null if foreign executor should be used. + */ + private QueryExecutor baseLocalExecutor(StorageAccess localAccess) { if (!handlesAnything()) { return new FullScanQueryExecutor(localAccess); } @@ -504,34 +529,15 @@ public class IndexedQueryAnalyzer { StorableIndex localIndex = getLocalIndex(); if (localIndex != null) { - return indexExecutor(localAccess, localIndex); - } - - StorableIndex foreignIndex = getForeignIndex(); - StorageAccess foreignAccess = mRepoAccess - .storageAccessFor(foreignIndex.getStorableType()); - - QueryExecutor foreignExecutor; - Storage delegate = foreignAccess.storageDelegate(foreignIndex); - if (delegate != null) { - foreignExecutor = new DelegatedQueryExecutor(delegate, getFilter(), getOrdering()); - } else { - foreignExecutor = indexExecutor(foreignAccess, foreignIndex); + CompositeScore score = getCompositeScore(); + FilteringScore fScore = score.getFilteringScore(); + if (fScore.isKeyMatch()) { + return new KeyQueryExecutor(localAccess, localIndex, fScore); + } + return new IndexedQueryExecutor(localAccess, localIndex, score); } - return new JoinedQueryExecutor - (mRepoAccess.getRootRepository(), getForeignProperty(), foreignExecutor); - } - - private QueryExecutor indexExecutor(StorageAccess access, - StorableIndex index) - { - CompositeScore score = getCompositeScore(); - FilteringScore fScore = score.getFilteringScore(); - if (fScore.isKeyMatch()) { - return new KeyQueryExecutor(access, index, fScore); - } - return new IndexedQueryExecutor(access, index, score); + return null; } public String toString() { diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java index fd3ab4f..46527bf 100644 --- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryExecutor.java @@ -52,6 +52,7 @@ public class IndexedQueryExecutor extends AbstractQueryExecu private final Support mSupport; private final StorableIndex mIndex; + private final int mHandledCount; private final int mIdentityCount; private final Filter mIdentityFilter; private final List> mExclusiveRangeStartFilters; @@ -70,6 +71,9 @@ public class IndexedQueryExecutor extends AbstractQueryExecu StorableIndex index, CompositeScore score) { + if (support == null && this instanceof Support) { + support = (Support) this; + } if (support == null || index == null || score == null) { throw new IllegalArgumentException(); } @@ -78,6 +82,9 @@ public class IndexedQueryExecutor extends AbstractQueryExecu mIndex = index; FilteringScore fScore = score.getFilteringScore(); + OrderingScore oScore = score.getOrderingScore(); + + mHandledCount = oScore.getHandledCount(); mIdentityCount = fScore.getIdentityCount(); mIdentityFilter = fScore.getIdentityFilter(); @@ -86,7 +93,7 @@ public class IndexedQueryExecutor extends AbstractQueryExecu mExclusiveRangeEndFilters = fScore.getExclusiveRangeEndFilters(); mInclusiveRangeEndFilters = fScore.getInclusiveRangeEndFilters(); - mReverseOrder = score.getOrderingScore().shouldReverseOrder(); + mReverseOrder = oScore.shouldReverseOrder(); mReverseRange = fScore.shouldReverseRange(); } @@ -185,12 +192,20 @@ public class IndexedQueryExecutor extends AbstractQueryExecu } public OrderingList getOrdering() { - OrderingList list = OrderingList.get(mIndex.getOrderedProperties()); - if (mIdentityCount > 0) { - list = OrderingList.get(list.subList(mIdentityCount, list.size())); - } - if (mReverseOrder) { - list = list.reverseDirections(); + OrderingList list; + if (mHandledCount == 0) { + list = OrderingList.emptyList(); + } else { + list = OrderingList.get(mIndex.getOrderedProperties()); + if (mIdentityCount > 0) { + list = list.subList(mIdentityCount, list.size()); + } + if (mHandledCount < list.size()) { + list = list.subList(0, mHandledCount); + } + if (mReverseOrder) { + list = list.reverseDirections(); + } } return list; } @@ -253,6 +268,9 @@ public class IndexedQueryExecutor extends AbstractQueryExecu return true; } + /** + * Provides support for {@link IndexedQueryExecutor}. + */ public static interface Support { /** * Perform an index scan of a subset of Storables referenced by an diff --git a/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java index de0864f..a1b636d 100644 --- a/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/IterableQueryExecutor.java @@ -87,7 +87,7 @@ public class IterableQueryExecutor extends AbstractQueryExec throws IOException { indent(app, indentLevel); - app.append("iterable: "); + app.append("collection iterator: "); app.append(mType.getName()); newline(app); return true; diff --git a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java index 11df215..62aab14 100644 --- a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java @@ -20,14 +20,29 @@ package com.amazon.carbonado.qe; import java.io.IOException; +import java.util.Comparator; +import java.util.Map; + +import org.cojen.classfile.ClassFile; +import org.cojen.classfile.CodeBuilder; +import org.cojen.classfile.FieldInfo; +import org.cojen.classfile.Label; +import org.cojen.classfile.LocalVariable; +import org.cojen.classfile.MethodInfo; +import org.cojen.classfile.Modifiers; +import org.cojen.classfile.TypeDesc; + +import org.cojen.util.ClassInjector; +import org.cojen.util.SoftValuedHashMap; + 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.Storage; -import com.amazon.carbonado.cursor.JoinedCursorFactory; +import com.amazon.carbonado.cursor.MultiTransformedCursor; import com.amazon.carbonado.filter.AndFilter; import com.amazon.carbonado.filter.ClosedFilter; @@ -36,205 +51,571 @@ 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.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.StorableInfo; import com.amazon.carbonado.info.StorableIntrospector; import com.amazon.carbonado.info.StorableProperty; +import com.amazon.carbonado.util.QuickConstructorGenerator; + +import com.amazon.carbonado.spi.CodeBuilderUtil; + /** - * QueryExecutor which wraps an executor for type source, follows a - * join, and produces type target. + * QueryExecutor which joins a source and target executor, + * producing results of target type. The source executor is called once per + * fetch (outer loop), but the target executor is called once per source result + * (inner loop). * * @author Brian S O'Neill - * @see JoinedCursorFactory * @param source type * @param target type */ public class JoinedQueryExecutor extends AbstractQueryExecutor { + /** + * Builds and returns a complex joined excutor against a chained property, + * supporting multi-way joins. Filtering and ordering may also be supplied, + * in order to better distribute work throughout the join. + * + * @param repoAccess used to create query executors for outer and inner loops + * @param targetToSourceProperty join property of target type which maps + * to instances of source type + * @param targetFilter optional filter for fetching target instances + * @param targetOrdering optional ordering to apply to target executor + * @throws IllegalArgumentException if any parameter is null or if join + * property is not a Storable type + * @throws RepositoryException from RepositoryAccess + */ + public static QueryExecutor + build(RepositoryAccess repoAccess, + ChainedProperty targetToSourceProperty, + Filter targetFilter, + OrderingList targetOrdering) + throws RepositoryException + { + if (targetOrdering == null) { + targetOrdering = OrderingList.emptyList(); + } + + QueryExecutor executor = + buildJoin(repoAccess, targetToSourceProperty, targetFilter, targetOrdering); + + OrderingList handledOrdering = executor.getOrdering(); + + // Apply sort if any remaining ordering properties. + int handledCount = commonOrderingCount(handledOrdering, targetOrdering); + + OrderingList remainderOrdering = + targetOrdering.subList(handledCount, targetOrdering.size()); + + if (remainderOrdering.size() > 0) { + SortedQueryExecutor.Support support = repoAccess + .storageAccessFor(targetToSourceProperty.getPrimeProperty().getEnclosingType()); + executor = new SortedQueryExecutor + (support, executor, handledOrdering, remainderOrdering); + } + + return executor; + } + + private static JoinedQueryExecutor + buildJoin(RepositoryAccess repoAccess, + ChainedProperty targetToSourceProperty, + Filter targetFilter, + OrderingList targetOrdering) + throws RepositoryException + { + StorableProperty primeTarget = targetToSourceProperty.getPrimeProperty(); + + Filter tailFilter; + if (targetFilter == null) { + tailFilter = null; + } else { + Filter.NotJoined nj = targetFilter.notJoinedFrom(ChainedProperty.get(primeTarget)); + tailFilter = nj.getNotJoinedFilter(); + targetFilter = nj.getRemainderFilter(); + } + + // Determine the most ordering properties the source (outer loop + // executor) can provide. It may use less if its selected index does + // not provide the ordering for free. + final OrderingList outerLoopOrdering = mostOrdering(primeTarget, targetOrdering); + + QueryExecutor outerLoopExecutor; + if (targetToSourceProperty.getChainCount() > 0) { + ChainedProperty tailProperty = targetToSourceProperty.tail(); + outerLoopExecutor = buildJoin(repoAccess, tailProperty, tailFilter, outerLoopOrdering); + } else { + Class sourceType = targetToSourceProperty.getType(); + + if (!Storable.class.isAssignableFrom(sourceType)) { + throw new IllegalArgumentException + ("Property type is not a Storable: " + targetToSourceProperty); + } + + StorageAccess sourceAccess = repoAccess.storageAccessFor(sourceType); + + OrderingList expectedOrdering = + expectedOrdering(sourceAccess, tailFilter, outerLoopOrdering); + + QueryExecutorFactory outerLoopExecutorFactory = sourceAccess.getQueryExecutorFactory(); + + outerLoopExecutor = outerLoopExecutorFactory.executor(tailFilter, expectedOrdering); + } + + if (targetOrdering.size() > 0) { + // If outer loop handles some of the ordering, then it can be + // removed from the target ordering. This simplifies or eliminates + // a final sort operation. + + int handledCount = + commonOrderingCount(outerLoopExecutor.getOrdering(), outerLoopOrdering); + + targetOrdering = targetOrdering.subList(handledCount, targetOrdering.size()); + } + + Class targetType = primeTarget.getEnclosingType(); + StorageAccess targetAccess = repoAccess.storageAccessFor(targetType); + + QueryExecutorFactory innerLoopExecutorFactory = targetAccess.getQueryExecutorFactory(); + + return new JoinedQueryExecutor(outerLoopExecutor, + innerLoopExecutorFactory, + primeTarget, + targetFilter, + targetOrdering, + targetAccess); + } + + private static final String INNER_LOOP_EX_FIELD_NAME = "innerLoopExecutor"; + private static final String INNER_LOOP_FV_FIELD_NAME = "innerLoopFilterValues"; + private static final String ACTIVE_SOURCE_FIELD_NAME = "active"; + + private static final Map cJoinerCursorClassCache; + + static { + cJoinerCursorClassCache = new SoftValuedHashMap(); + } + + private static synchronized Joiner.Factory + getJoinerFactory(StorableProperty targetToSourceProperty) + { + Class clazz = cJoinerCursorClassCache.get(targetToSourceProperty); + + if (clazz == null) { + clazz = generateJoinerCursor(targetToSourceProperty); + cJoinerCursorClassCache.put(targetToSourceProperty, clazz); + } + + return (Joiner.Factory) QuickConstructorGenerator + .getInstance(clazz, Joiner.Factory.class); + } + + private static Class> + generateJoinerCursor(StorableProperty targetToSourceProperty) + { + final Class sourceType = targetToSourceProperty.getType(); + final Class targetType = targetToSourceProperty.getEnclosingType(); + + String packageName; + { + String name = targetType.getName(); + int index = name.lastIndexOf('.'); + if (index >= 0) { + packageName = name.substring(0, index); + } else { + packageName = ""; + } + } + + ClassLoader loader = targetType.getClassLoader(); + + ClassInjector ci = ClassInjector.create(packageName + ".JoinedCursor", loader); + ClassFile cf = new ClassFile(ci.getClassName(), MultiTransformedCursor.class); + cf.markSynthetic(); + cf.setSourceFile(JoinedQueryExecutor.class.getName()); + cf.setTarget("1.5"); + + final TypeDesc cursorType = TypeDesc.forClass(Cursor.class); + final TypeDesc queryExecutorType = TypeDesc.forClass(QueryExecutor.class); + final TypeDesc filterValuesType = TypeDesc.forClass(FilterValues.class); + + // Define fields for inner loop executor and filter values, which are + // passed into the constructor. + cf.addField(Modifiers.PRIVATE.toFinal(true), INNER_LOOP_EX_FIELD_NAME, queryExecutorType); + cf.addField(Modifiers.PRIVATE.toFinal(true), INNER_LOOP_FV_FIELD_NAME, filterValuesType); + + // If target storable can set a reference to the joined source + // storable, then stash a copy of it as we go. This way, when user of + // target storable accesses the joined property, it costs nothing. + boolean canSetSourceReference = targetToSourceProperty.getWriteMethod() != null; + + if (canSetSourceReference) { + // Field to hold active source storable. + cf.addField(Modifiers.PRIVATE, ACTIVE_SOURCE_FIELD_NAME, + TypeDesc.forClass(sourceType)); + } + + // Define constructor. + { + TypeDesc[] params = {cursorType, queryExecutorType, filterValuesType}; + + MethodInfo mi = cf.addConstructor(Modifiers.PUBLIC, params); + CodeBuilder b = new CodeBuilder(mi); + + b.loadThis(); + b.loadLocal(b.getParameter(0)); // pass source cursor to superclass + b.invokeSuperConstructor(new TypeDesc[] {cursorType}); + + b.loadThis(); + b.loadLocal(b.getParameter(1)); + b.storeField(INNER_LOOP_EX_FIELD_NAME, queryExecutorType); + + b.loadThis(); + b.loadLocal(b.getParameter(2)); + b.storeField(INNER_LOOP_FV_FIELD_NAME, filterValuesType); + + b.returnVoid(); + } + + // Implement the transform method. + { + MethodInfo mi = cf.addMethod(Modifiers.PROTECTED, "transform", cursorType, + new TypeDesc[] {TypeDesc.OBJECT}); + mi.addException(TypeDesc.forClass(FetchException.class)); + CodeBuilder b = new CodeBuilder(mi); + + LocalVariable sourceVar = b.createLocalVariable(null, TypeDesc.forClass(sourceType)); + b.loadLocal(b.getParameter(0)); + b.checkCast(TypeDesc.forClass(sourceType)); + b.storeLocal(sourceVar); + + if (canSetSourceReference) { + b.loadThis(); + b.loadLocal(sourceVar); + b.storeField(ACTIVE_SOURCE_FIELD_NAME, TypeDesc.forClass(sourceType)); + } + + // Prepare to call fetch on innerLoopExecutor. + b.loadThis(); + b.loadField(INNER_LOOP_EX_FIELD_NAME, queryExecutorType); + + // Fill in values for innerLoopFilterValues. + b.loadThis(); + b.loadField(INNER_LOOP_FV_FIELD_NAME, filterValuesType); + + int propCount = targetToSourceProperty.getJoinElementCount(); + for (int i=0; i external = targetToSourceProperty.getExternalJoinElement(i); + b.loadLocal(sourceVar); + b.invoke(external.getReadMethod()); + + TypeDesc bindType = CodeBuilderUtil.bindQueryParam(external.getType()); + CodeBuilderUtil.convertValue(b, external.getType(), bindType.toClass()); + b.invokeVirtual(filterValuesType, "with", filterValuesType, + new TypeDesc[] {bindType}); + } + + // Now fetch and return. + b.invokeInterface(queryExecutorType, "fetch", cursorType, + new TypeDesc[] {filterValuesType}); + b.returnValue(cursorType); + } + + if (canSetSourceReference) { + // Override the "next" method to set source object on target. + MethodInfo mi = cf.addMethod(Modifiers.PUBLIC, "next", TypeDesc.OBJECT, null); + mi.addException(TypeDesc.forClass(FetchException.class)); + CodeBuilder b = new CodeBuilder(mi); + + b.loadThis(); + b.invokeSuper(TypeDesc.forClass(MultiTransformedCursor.class), + "next", TypeDesc.OBJECT, null); + b.checkCast(TypeDesc.forClass(targetType)); + b.dup(); + + b.loadThis(); + b.loadField(ACTIVE_SOURCE_FIELD_NAME, TypeDesc.forClass(sourceType)); + b.invoke(targetToSourceProperty.getWriteMethod()); + + b.returnValue(TypeDesc.OBJECT); + } + + return (Class>) ci.defineClass(cf); + } + private static OrderingList transformOrdering(Class targetType, String targetToSourceProperty, QueryExecutor sourceExecutor) { + OrderingList targetOrdering = OrderingList.emptyList(); StorableInfo targetInfo = StorableIntrospector.examine(targetType); - OrderingList sourceOrdering = sourceExecutor.getOrdering(); - int size = sourceOrdering.size(); - OrderedProperty[] targetOrdering = new OrderedProperty[size]; - - for (int i=0; i sourceProp = sourceOrdering.get(i); + for (OrderedProperty sourceProp : sourceExecutor.getOrdering()) { String targetName = targetToSourceProperty + '.' + sourceProp.getChainedProperty(); OrderedProperty targetProp = OrderedProperty .get(ChainedProperty.parse(targetInfo, targetName), sourceProp.getDirection()); - targetOrdering[i] = targetProp; + targetOrdering = targetOrdering.concat(targetProp); } - return OrderingList.get(targetOrdering); + return targetOrdering; } - private final ChainedProperty mTargetToSourceProperty; - private final JoinedCursorFactory mFactory; - private final QueryExecutor mSourceExecutor; + /** + * Given a list of chained ordering properties, returns the properties + * stripped of the matching chain prefix for the targetToSourceProperty. As + * the target ordering is scanned left-to-right, if any property is found + * which doesn't match the targetToSourceProperty, the building of the new + * list stops. In other words, it returns a consecutive run of matching + * properties. + */ + private static OrderingList + mostOrdering(StorableProperty primeTarget, OrderingList targetOrdering) + { + OrderingList handledOrdering = OrderingList.emptyList(); + for (OrderedProperty targetProp : targetOrdering) { + ChainedProperty chainedProp = targetProp.getChainedProperty(); + if (chainedProp.getPrimeProperty().equals(primeTarget)) { + handledOrdering = handledOrdering + // I hate Java generics. Note the stupid cast. I have finally + // realized the core problem: the wildcard model is broken. + .concat(OrderedProperty + .get((ChainedProperty) chainedProp.tail(), + targetProp.getDirection())); + } else { + break; + } + } - private final FilterValues mSourceFilterValues; - private final Filter mTargetFilter; - private final OrderingList mTargetOrdering; + return handledOrdering; + } /** - * @param repo access to storage instances for properties - * @param targetType type of target instances - * @param targetToSourceProperty property of target type which maps - * to instances of source type. - * @param sourceExecutor executor for source instances - * @throws IllegalArgumentException if property type is not source + * Examines the given ordering against available indexes, returning the + * ordering that the best index can provide for free. */ - public JoinedQueryExecutor(Repository repo, - Class targetType, - String targetToSourceProperty, - QueryExecutor sourceExecutor) - throws SupportException, FetchException, RepositoryException + private static OrderingList + expectedOrdering(StorageAccess access, Filter filter, OrderingList ordering) { - this(repo, - ChainedProperty.parse(StorableIntrospector.examine(targetType), - targetToSourceProperty), - sourceExecutor); + Comparator comparator = CompositeScore.fullComparator(); + + CompositeScore bestScore = null; + for (StorableIndex index : access.getAllIndexes()) { + CompositeScore candidateScore = CompositeScore.evaluate(index, filter, ordering); + if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) { + bestScore = candidateScore; + } + } + + // Reduce source ordering to that which can be handled for + // free. Otherwise, a sort would be performed which is a waste of time + // if some source results will later be filtered out. + int handledCount = bestScore == null ? 0 : bestScore.getOrderingScore().getHandledCount(); + return ordering.subList(0, handledCount); } /** - * @param repo access to storage instances for properties - * @param targetToSourceProperty property of target type which maps - * to instances of source type. - * @param aExecutor executor for A instances - * @throws IllegalArgumentException if property type is not A + * Returns the count of exactly matching properties from the two + * orderings. The match must be consecutive and start at the first + * property. */ - public JoinedQueryExecutor(Repository repo, - ChainedProperty targetToSourceProperty, - QueryExecutor sourceExecutor) - throws SupportException, FetchException, RepositoryException + private static int + commonOrderingCount(OrderingList orderingA, OrderingList orderingB) { - mTargetToSourceProperty = targetToSourceProperty; - mFactory = new JoinedCursorFactory - (repo, targetToSourceProperty, sourceExecutor.getStorableType()); - mSourceExecutor = sourceExecutor; + int commonCount = Math.min(orderingA.size(), orderingB.size()); - Filter sourceFilter = sourceExecutor.getFilter(); - - mSourceFilterValues = sourceFilter.initialFilterValues(); - mTargetFilter = sourceFilter.accept(new FilterTransformer(), null); + for (int i=0; i getFilter() { - return mTargetFilter; - } + private final Filter mTargetFilter; + private final StorableProperty mTargetToSourceProperty; - public Cursor fetch(FilterValues values) throws FetchException { - return mFactory.join(mSourceExecutor.fetch(transferValues(values))); - } + private final QueryExecutor mOuterLoopExecutor; + private final FilterValues mOuterLoopFilterValues; - public OrderingList getOrdering() { - return mTargetOrdering; - } + private final QueryExecutor mInnerLoopExecutor; + private final FilterValues mInnerLoopFilterValues; - public boolean printPlan(Appendable app, int indentLevel, FilterValues values) - throws IOException + private final Filter mSourceFilterAsFromTarget; + private final Filter mCombinedFilter; + private final OrderingList mCombinedOrdering; + + private final Joiner.Factory mJoinerFactory; + + /** + * @param outerLoopExecutor executor for source instances + * @param innerLoopExecutorFactory used to construct inner loop executor + * @param targetToSourceProperty join property of target type which maps + * to instances of source type + * @param targetFilter optional initial filter for fetching target instances + * @param targetOrdering optional desired ordering to apply to + * target executor + * @param targetAccess used with target ordering to determine actual + * ordering which an index provides for free + * @throws IllegalArgumentException if any parameter is null or if join + * property is not of source type + * @throws RepositoryException from innerLoopExecutorFactory + */ + private JoinedQueryExecutor(QueryExecutor outerLoopExecutor, + QueryExecutorFactory innerLoopExecutorFactory, + StorableProperty targetToSourceProperty, + Filter targetFilter, + OrderingList targetOrdering, + StorageAccess targetAccess) + throws RepositoryException { - int chainCount = mTargetToSourceProperty.getChainCount(); + if (targetToSourceProperty == null || outerLoopExecutor == null) { + throw new IllegalArgumentException("Null parameter"); + } - for (int i = -1; i < chainCount; i++) { - indent(app, indentLevel); - app.append("join: "); + Class sourceType = outerLoopExecutor.getStorableType(); + if (targetToSourceProperty.getType() != sourceType) { + throw new IllegalArgumentException + ("Property is not of type \"" + sourceType.getName() + "\": " + + targetToSourceProperty); + } - StorableProperty prop; - if (i == -1) { - prop = mTargetToSourceProperty.getPrimeProperty(); - } else { - prop = mTargetToSourceProperty.getChainedProperty(i); - } + if (!targetToSourceProperty.isJoin()) { + throw new IllegalArgumentException + ("Property is not a join: " + targetToSourceProperty); + } - app.append(prop.getEnclosingType().getName()); - newline(app); - indent(app, indentLevel); - app.append("...via property: "); - app.append(prop.getName()); - newline(app); - indentLevel = increaseIndent(indentLevel); + if (targetFilter != null && !targetFilter.isBound()) { + throw new IllegalArgumentException("Target filter must be bound"); } - mSourceExecutor.printPlan(app, indentLevel, transferValues(values)); - return true; - } + if (!outerLoopExecutor.getFilter().isBound()) { + throw new IllegalArgumentException("Outer loop executor filter must be bound"); + } - private FilterValues transferValues(FilterValues values) { - if (values == null || mSourceFilterValues == null) { - return null; + if (targetFilter instanceof OpenFilter) { + targetFilter = null; } - return mSourceFilterValues.withValues(values.getSuppliedValues()); - } - private class FilterTransformer extends Visitor, Object> { - private final Class mTargetType; + mTargetFilter = targetFilter; + mTargetToSourceProperty = targetToSourceProperty; + mOuterLoopExecutor = outerLoopExecutor; + mOuterLoopFilterValues = outerLoopExecutor.getFilter().initialFilterValues(); + + Class targetType = targetToSourceProperty.getEnclosingType(); - FilterTransformer() { - mTargetType = mTargetToSourceProperty.getPrimeProperty().getEnclosingType(); + // Prepare inner loop filter which is and'd by the join property elements. + Filter innerLoopExecutorFilter = Filter.getOpenFilter(targetType); + if (targetFilter != null) { + innerLoopExecutorFilter = innerLoopExecutorFilter.and(targetFilter); } + int count = targetToSourceProperty.getJoinElementCount(); + for (int i=0; i visit(OrFilter sourceFilter, Object param) { - return sourceFilter.getLeftFilter().accept(this, param) - .and(sourceFilter.getRightFilter().accept(this, param)); + // Only perform requested ordering if it index provides it for free. + if (targetOrdering != null) { + targetOrdering = + expectedOrdering(targetAccess, innerLoopExecutorFilter, targetOrdering); } - public Filter visit(AndFilter sourceFilter, Object param) { - return sourceFilter.getLeftFilter().accept(this, param) - .or(sourceFilter.getRightFilter().accept(this, param)); + mInnerLoopExecutor = innerLoopExecutorFactory + .executor(innerLoopExecutorFilter, targetOrdering); + + Filter filter = outerLoopExecutor.getFilter() + .asJoinedFrom(ChainedProperty.get(targetToSourceProperty)); + + mSourceFilterAsFromTarget = filter; + + if (targetFilter != null) { + filter = filter.and(targetFilter); } - public Filter visit(PropertyFilter sourceFilter, Object param) { - String name; + mCombinedFilter = filter; - ChainedProperty sourceChainedProp = sourceFilter.getChainedProperty(); - if (mTargetType == sourceChainedProp.getPrimeProperty().getEnclosingType()) { - // If type of S is already T, (which violates generic type - // signature) then it came from join index analysis. - name = sourceChainedProp.toString(); - } else { - StringBuilder nameBuilder = new StringBuilder(); - try { - mTargetToSourceProperty.appendTo(nameBuilder); - nameBuilder.append('.'); - sourceChainedProp.appendTo(nameBuilder); - } catch (IOException e) { - // Not gonna happen - } - name = nameBuilder.toString(); - } + // Prepare combined ordering. + OrderingList ordering = transformOrdering + (targetType, targetToSourceProperty.getName(), outerLoopExecutor); - Filter targetFilter = Filter.getOpenFilter(mTargetType); - if (sourceFilter.isConstant()) { - targetFilter = targetFilter - .and(name, sourceFilter.getOperator(), sourceFilter.constant()); - } else { - targetFilter = targetFilter.and(name, sourceFilter.getOperator()); - } + if (targetOrdering != null) { + ordering = ordering.concat(targetOrdering); + } + + mCombinedOrdering = ordering; + + mJoinerFactory = getJoinerFactory(targetToSourceProperty); + } + + public Cursor fetch(FilterValues values) throws FetchException { + FilterValues innerLoopFilterValues = mInnerLoopFilterValues; - return targetFilter; + if (mTargetFilter != null) { + // Prepare this before opening source cursor, in case an exception is thrown. + innerLoopFilterValues = innerLoopFilterValues + .withValues(values.getValuesFor(mTargetFilter)); } - public Filter visit(OpenFilter sourceFilter, Object param) { - return Filter.getOpenFilter(mTargetType); + Cursor outerLoopCursor = mOuterLoopExecutor.fetch(transferValues(values)); + + return mJoinerFactory.newJoinedCursor + (outerLoopCursor, mInnerLoopExecutor, innerLoopFilterValues); + } + + public Filter getFilter() { + return mCombinedFilter; + } + + public OrderingList getOrdering() { + return mCombinedOrdering; + } + + public boolean printPlan(Appendable app, int indentLevel, FilterValues values) + throws IOException + { + indent(app, indentLevel); + app.append("join: "); + app.append(mTargetToSourceProperty.getEnclosingType().getName()); + newline(app); + indent(app, indentLevel); + app.append("...inner loop: "); + app.append(mTargetToSourceProperty.getName()); + newline(app); + mInnerLoopExecutor.printPlan(app, increaseIndent(indentLevel), values); + indent(app, indentLevel); + app.append("...outer loop"); + newline(app); + mOuterLoopExecutor.printPlan(app, increaseIndent(indentLevel), transferValues(values)); + return true; + } + + private FilterValues transferValues(FilterValues values) { + if (values == null) { + return null; } + return mOuterLoopFilterValues.withValues(values.getValuesFor(mSourceFilterAsFromTarget)); + } - public Filter visit(ClosedFilter sourceFilter, Object param) { - return Filter.getClosedFilter(mTargetType); + private static interface Joiner { + /** + * Needs to be public for {@link QuickConstructorGenerator}, but hide + * it inside a private interface. + */ + public static interface Factory { + Cursor newJoinedCursor(Cursor outerLoopCursor, + QueryExecutor innerLoopExecutor, + FilterValues innerLoopFilterValues); } } } diff --git a/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java index d8436c0..fcf728d 100644 --- a/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/KeyQueryExecutor.java @@ -51,6 +51,9 @@ public class KeyQueryExecutor extends AbstractQueryExecutor< * not unique or if score is not a key match */ public KeyQueryExecutor(Support support, StorableIndex index, FilteringScore score) { + if (support == null && this instanceof Support) { + support = (Support) this; + } if (support == null || index == null || score == null) { throw new IllegalArgumentException(); } @@ -101,6 +104,9 @@ public class KeyQueryExecutor extends AbstractQueryExecutor< return true; } + /** + * Provides support for {@link KeyQueryExecutor}. + */ public static interface Support { /** * Select at most one Storable referenced by an index. The identity diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingList.java b/src/main/java/com/amazon/carbonado/qe/OrderingList.java index f6366e5..d100cc9 100644 --- a/src/main/java/com/amazon/carbonado/qe/OrderingList.java +++ b/src/main/java/com/amazon/carbonado/qe/OrderingList.java @@ -246,6 +246,23 @@ public class OrderingList extends AbstractList subList(int fromIndex, int toIndex) { + // Check for optimization opportunity. + if (fromIndex == 0 && toIndex >= 0 && toIndex <= mSize) { + if (toIndex == 0) { + return emptyList(); + } + OrderingList list = this; + while (toIndex < list.mSize) { + list = list.mParent; + } + return list; + } + + return get(super.subList(fromIndex, toIndex)); + } + /** * This method is not public because the array is not a clone. */ diff --git a/src/main/java/com/amazon/carbonado/qe/QueryEngine.java b/src/main/java/com/amazon/carbonado/qe/QueryEngine.java index 1362045..59c9872 100644 --- a/src/main/java/com/amazon/carbonado/qe/QueryEngine.java +++ b/src/main/java/com/amazon/carbonado/qe/QueryEngine.java @@ -19,9 +19,11 @@ package com.amazon.carbonado.qe; import com.amazon.carbonado.IsolationLevel; +import com.amazon.carbonado.RepositoryException; import com.amazon.carbonado.Storable; import com.amazon.carbonado.Transaction; +import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.FilterValues; /** @@ -29,7 +31,9 @@ import com.amazon.carbonado.filter.FilterValues; * * @author Brian S O'Neill */ -public class QueryEngine extends StandardQueryFactory { +public class QueryEngine extends StandardQueryFactory + implements QueryExecutorFactory +{ final RepositoryAccess mRepoAccess; final QueryExecutorFactory mExecutorFactory; @@ -39,6 +43,12 @@ public class QueryEngine extends StandardQueryFactory { mExecutorFactory = new QueryExecutorCache(new UnionQueryAnalyzer(type, access)); } + public QueryExecutor executor(Filter filter, OrderingList ordering) + throws RepositoryException + { + return mExecutorFactory.executor(filter, ordering); + } + protected StandardQuery createQuery(FilterValues values, OrderingList ordering) { return new Query(values, ordering); } diff --git a/src/main/java/com/amazon/carbonado/qe/QueryExecutorFactory.java b/src/main/java/com/amazon/carbonado/qe/QueryExecutorFactory.java index 1b1e680..5568f01 100644 --- a/src/main/java/com/amazon/carbonado/qe/QueryExecutorFactory.java +++ b/src/main/java/com/amazon/carbonado/qe/QueryExecutorFactory.java @@ -23,8 +23,6 @@ import com.amazon.carbonado.Storable; import com.amazon.carbonado.filter.Filter; -import com.amazon.carbonado.info.OrderedProperty; - /** * Produces {@link QueryExecutor} instances from a query specification. * diff --git a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java index cae03d8..38a8e36 100644 --- a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java +++ b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java @@ -64,9 +64,13 @@ public class SortedQueryExecutor extends AbstractQueryExecut OrderingList handledOrdering, OrderingList remainderOrdering) { + if (support == null && this instanceof Support) { + support = (Support) this; + } if (executor == null) { throw new IllegalArgumentException(); } + mSupport = support; mExecutor = executor; @@ -128,6 +132,9 @@ public class SortedQueryExecutor extends AbstractQueryExecut return true; } + /** + * Provides support for {@link SortedQueryExecutor}. + */ public static interface Support { /** * Implementation must return an empty buffer for sorting. diff --git a/src/main/java/com/amazon/carbonado/qe/StorageAccess.java b/src/main/java/com/amazon/carbonado/qe/StorageAccess.java index 2ab2313..643d61c 100644 --- a/src/main/java/com/amazon/carbonado/qe/StorageAccess.java +++ b/src/main/java/com/amazon/carbonado/qe/StorageAccess.java @@ -46,6 +46,11 @@ public interface StorageAccess */ Class getStorableType(); + /** + * Returns a QueryExecutorFactory instance for storage. + */ + QueryExecutorFactory getQueryExecutorFactory(); + /** * Returns all the available indexes. */ diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java index 2901ea0..fde1952 100644 --- a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java +++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java @@ -59,6 +59,7 @@ import com.amazon.carbonado.cursor.SortBuffer; import com.amazon.carbonado.qe.BoundaryType; import com.amazon.carbonado.qe.QueryEngine; +import com.amazon.carbonado.qe.QueryExecutorFactory; import com.amazon.carbonado.qe.StorageAccess; import com.amazon.carbonado.spi.RepairExecutor; @@ -266,6 +267,10 @@ class IndexedStorage implements Storage, StorageAccess return accessors.toArray(new IndexEntryAccessor[accessors.size()]); } + public QueryExecutorFactory getQueryExecutorFactory() { + return mQueryEngine; + } + public Collection> getAllIndexes() { return mIndexSet; } diff --git a/src/main/java/com/amazon/carbonado/spi/CodeBuilderUtil.java b/src/main/java/com/amazon/carbonado/spi/CodeBuilderUtil.java index 4e2e777..e3b24bd 100644 --- a/src/main/java/com/amazon/carbonado/spi/CodeBuilderUtil.java +++ b/src/main/java/com/amazon/carbonado/spi/CodeBuilderUtil.java @@ -385,6 +385,8 @@ public class CodeBuilderUtil { * Determines which overloaded "with" method on Query should be bound to. */ public static TypeDesc bindQueryParam(Class clazz) { + // This method is a bit vestigial. Once upon a time the Query class did + // not support all primitive types. if (clazz.isPrimitive()) { TypeDesc type = TypeDesc.forClass(clazz); switch (type.getTypeCode()) { @@ -392,6 +394,10 @@ public class CodeBuilderUtil { case TypeDesc.LONG_CODE: case TypeDesc.FLOAT_CODE: case TypeDesc.DOUBLE_CODE: + case TypeDesc.BOOLEAN_CODE: + case TypeDesc.CHAR_CODE: + case TypeDesc.BYTE_CODE: + case TypeDesc.SHORT_CODE: return type; } } -- cgit v1.2.3