From 35316f62f705ca59ecb40107bebb355d865f60a7 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sat, 4 Aug 2007 23:38:00 +0000 Subject: Add filtering short-circuit optimization. --- .../carbonado/cursor/FilteredCursorGenerator.java | 17 +- .../carbonado/cursor/ShortCircuitOptimizer.java | 191 +++++++++++++++++++++ 2 files changed, 206 insertions(+), 2 deletions(-) create mode 100644 src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java (limited to 'src/main/java/com/amazon/carbonado/cursor') diff --git a/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java b/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java index 9b2a945..71aaf5b 100644 --- a/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java +++ b/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java @@ -73,6 +73,11 @@ class FilteredCursorGenerator { */ @SuppressWarnings("unchecked") static Factory getFactory(Filter filter) { + return getFactory(filter, true); + } + + @SuppressWarnings("unchecked") + private static Factory getFactory(Filter filter, boolean optimize) { if (filter == null) { throw new IllegalArgumentException(); } @@ -81,8 +86,16 @@ class FilteredCursorGenerator { if (factory != null) { return factory; } - Class> clazz = generateClass(filter); - factory = QuickConstructorGenerator.getInstance(clazz, Factory.class); + + Filter optimized; + if (optimize && (optimized = ShortCircuitOptimizer.optimize(filter)) != filter) { + // Use factory for filter optimized for short-circuit logic. + factory = getFactory(optimized, false); + } else { + Class> clazz = generateClass(filter); + factory = QuickConstructorGenerator.getInstance(clazz, Factory.class); + } + cCache.put(filter, factory); return factory; } diff --git a/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java b/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java new file mode 100644 index 0000000..1a46d1e --- /dev/null +++ b/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java @@ -0,0 +1,191 @@ +/* + * Copyright 2007 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 com.amazon.carbonado.Storable; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.StorableProperty; + +import com.amazon.carbonado.filter.AndFilter; +import com.amazon.carbonado.filter.ClosedFilter; +import com.amazon.carbonado.filter.Filter; +import com.amazon.carbonado.filter.OpenFilter; +import com.amazon.carbonado.filter.OrFilter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.Visitor; + +/** + * Optimizes a Filter such that simpler tests are performed before more complex + * tests which may need to follow joins. This takes advantage of the + * short-circuit logic used by FilteredCursorGenerator. + * + * @author Brian S O'Neill + */ +class ShortCircuitOptimizer { + + public static Filter optimize(Filter filter) { + return filter.accept(new Walker(), null).mNewFilter; + } + + private static class FilterAndCost { + final Filter mNewFilter; + final ChainedProperty mExpensiveProperty; + + FilterAndCost(Filter filter, ChainedProperty expensive) { + mNewFilter = filter; + mExpensiveProperty = expensive; + } + + /** + * Returns -1 if this is cheaper, 0 if same, 1 if this is more expensive + */ + int compareCost(FilterAndCost other) { + if (mExpensiveProperty == null) { + if (other.mExpensiveProperty == null) { + return 0; + } + return -1; + } else if (other.mExpensiveProperty == null) { + return 1; + } + + if (mExpensiveProperty.equals(other.mExpensiveProperty)) { + return 0; + } + + int result = joinCompare(mExpensiveProperty.getPrimeProperty(), + other.mExpensiveProperty.getPrimeProperty()); + + if (result != 0) { + return result; + } + + if (mExpensiveProperty.getChainCount() == 0) { + if (other.mExpensiveProperty.getChainCount() == 0) { + return 0; + } + } else if (other.mExpensiveProperty.getChainCount() == 0) { + return 1; + } + + int length = Math.min(mExpensiveProperty.getChainCount(), + other.mExpensiveProperty.getChainCount()); + + for (int i=0; i other.mExpensiveProperty.getChainCount()) { + return 1; + } + + return 0; + } + + /** + * Returns -1 if "a" has cheaper join, 0 if same, 1 if "a" has more expensive join + */ + private int joinCompare(StorableProperty a, StorableProperty b) { + if (a.isQuery()) { + if (b.isQuery()) { + return 0; + } + return 1; + } else if (b.isQuery()) { + return -1; + } + if (a.isJoin()) { + if (b.isJoin()) { + return 0; + } + return 1; + } else if (b.isJoin()) { + return -1; + } + return 0; + } + } + + private static class Walker extends Visitor, Object> { + public FilterAndCost visit(OrFilter filter, Object param) { + FilterAndCost leftCost = filter.getLeftFilter().accept(this, param); + FilterAndCost rightCost = filter.getRightFilter().accept(this, param); + + int compare = leftCost.compareCost(rightCost); + + Filter newFilter; + ChainedProperty expensiveProperty; + + if (compare <= 0) { + // Current arrangement is fine. + newFilter = leftCost.mNewFilter.or(rightCost.mNewFilter); + expensiveProperty = rightCost.mExpensiveProperty; + } else { + // Swap nodes such that the expensive one is checked later. + newFilter = rightCost.mNewFilter.or(leftCost.mNewFilter); + expensiveProperty = leftCost.mExpensiveProperty; + } + + return new FilterAndCost(newFilter, expensiveProperty); + } + + public FilterAndCost visit(AndFilter filter, Object param) { + FilterAndCost leftCost = filter.getLeftFilter().accept(this, param); + FilterAndCost rightCost = filter.getRightFilter().accept(this, param); + + int compare = leftCost.compareCost(rightCost); + + Filter newFilter; + ChainedProperty expensiveProperty; + + if (compare <= 0) { + // Current arrangement is fine. + newFilter = leftCost.mNewFilter.and(rightCost.mNewFilter); + expensiveProperty = rightCost.mExpensiveProperty; + } else { + // Swap nodes such that the expensive one is checked later. + newFilter = rightCost.mNewFilter.and(leftCost.mNewFilter); + expensiveProperty = leftCost.mExpensiveProperty; + } + + return new FilterAndCost(newFilter, expensiveProperty); + } + + public FilterAndCost visit(PropertyFilter filter, Object param) { + return new FilterAndCost(filter, filter.getChainedProperty()); + } + + public FilterAndCost visit(OpenFilter filter, Object param) { + return new FilterAndCost(filter, null); + } + + public FilterAndCost visit(ClosedFilter filter, Object param) { + return new FilterAndCost(filter, null); + } + } +} -- cgit v1.2.3