From 35316f62f705ca59ecb40107bebb355d865f60a7 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
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 <S extends Storable> Factory<S> getFactory(Filter<S> filter) {
+ return getFactory(filter, true);
+ }
+
+ @SuppressWarnings("unchecked")
+ private static <S extends Storable> Factory<S> getFactory(Filter<S> filter, boolean optimize) {
if (filter == null) {
throw new IllegalArgumentException();
}
@@ -81,8 +86,16 @@ class FilteredCursorGenerator {
if (factory != null) {
return factory;
}
- Class<Cursor<S>> clazz = generateClass(filter);
- factory = QuickConstructorGenerator.getInstance(clazz, Factory.class);
+
+ Filter<S> optimized;
+ if (optimize && (optimized = ShortCircuitOptimizer.optimize(filter)) != filter) {
+ // Use factory for filter optimized for short-circuit logic.
+ factory = getFactory(optimized, false);
+ } else {
+ Class<Cursor<S>> 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 <S extends Storable> Filter<S> optimize(Filter<S> filter) {
+ return filter.accept(new Walker<S>(), null).mNewFilter;
+ }
+
+ private static class FilterAndCost<S extends Storable> {
+ final Filter<S> mNewFilter;
+ final ChainedProperty<S> mExpensiveProperty;
+
+ FilterAndCost(Filter<S> filter, ChainedProperty<S> expensive) {
+ mNewFilter = filter;
+ mExpensiveProperty = expensive;
+ }
+
+ /**
+ * Returns -1 if this is cheaper, 0 if same, 1 if this is more expensive
+ */
+ int compareCost(FilterAndCost<S> 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<length; i++) {
+ result = joinCompare(mExpensiveProperty.getChainedProperty(i),
+ other.mExpensiveProperty.getChainedProperty(i));
+
+ if (result != 0) {
+ return result;
+ }
+ }
+
+ if (mExpensiveProperty.getChainCount() < other.mExpensiveProperty.getChainCount()) {
+ return -1;
+ }
+ if (mExpensiveProperty.getChainCount() > 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<S extends Storable> extends Visitor<S, FilterAndCost<S>, Object> {
+ public FilterAndCost<S> visit(OrFilter<S> filter, Object param) {
+ FilterAndCost<S> leftCost = filter.getLeftFilter().accept(this, param);
+ FilterAndCost<S> rightCost = filter.getRightFilter().accept(this, param);
+
+ int compare = leftCost.compareCost(rightCost);
+
+ Filter<S> newFilter;
+ ChainedProperty<S> 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<S>(newFilter, expensiveProperty);
+ }
+
+ public FilterAndCost<S> visit(AndFilter<S> filter, Object param) {
+ FilterAndCost<S> leftCost = filter.getLeftFilter().accept(this, param);
+ FilterAndCost<S> rightCost = filter.getRightFilter().accept(this, param);
+
+ int compare = leftCost.compareCost(rightCost);
+
+ Filter<S> newFilter;
+ ChainedProperty<S> 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<S>(newFilter, expensiveProperty);
+ }
+
+ public FilterAndCost<S> visit(PropertyFilter<S> filter, Object param) {
+ return new FilterAndCost<S>(filter, filter.getChainedProperty());
+ }
+
+ public FilterAndCost<S> visit(OpenFilter<S> filter, Object param) {
+ return new FilterAndCost<S>(filter, null);
+ }
+
+ public FilterAndCost<S> visit(ClosedFilter<S> filter, Object param) {
+ return new FilterAndCost<S>(filter, null);
+ }
+ }
+}
--
cgit v1.2.3