You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by su...@apache.org on 2021/01/20 16:59:53 UTC
[druid] branch master updated: Retain order of AND,
OR filter children. (#10758)
This is an automated email from the ASF dual-hosted git repository.
suneet pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/druid.git
The following commit(s) were added to refs/heads/master by this push:
new 8b808c4 Retain order of AND, OR filter children. (#10758)
8b808c4 is described below
commit 8b808c48799b04b53e763fd49c766e1e6a26d1cb
Author: Gian Merlino <gi...@gmail.com>
AuthorDate: Wed Jan 20 08:59:20 2021 -0800
Retain order of AND, OR filter children. (#10758)
* Retain order of AND, OR filter children.
If we retain the order, it enables short-circuiting. People can put a
more selective filter earlier in the list and lower the chance that
later filters will need to be evaluated.
Short-circuiting was working before #9608, which switched to unordered
sets to solve a different problem. This patch tries to solve that
problem a different way.
This patch moves filter simplification logic from "optimize" to
"toFilter", because that allows the code to be shared with Filters.and
and Filters.or. The simplification has become more complicated and so
it's useful to share it.
This patch also removes code from CalciteCnfHelper that is no longer
necessary because Filters.and and Filters.or are now doing the work.
* Fixes for inspections.
* Fix tests.
* Back to a Set.
---
.../apache/druid/query/filter/AndDimFilter.java | 25 ++--
.../apache/druid/query/filter/BooleanFilter.java | 9 +-
.../org/apache/druid/query/filter/OrDimFilter.java | 25 ++--
.../segment/QueryableIndexStorageAdapter.java | 9 +-
.../org/apache/druid/segment/filter/AndFilter.java | 25 ++--
.../apache/druid/segment/filter/BoundFilter.java | 7 +
.../org/apache/druid/segment/filter/Filters.java | 144 ++++++++++++++-----
.../org/apache/druid/segment/filter/OrFilter.java | 21 ++-
.../druid/segment/filter/cnf/CalciteCnfHelper.java | 155 ++-------------------
.../druid/segment/filter/cnf/HiveCnfHelper.java | 56 +++++---
.../segment/join/filter/JoinFilterAnalyzer.java | 14 +-
.../druid/query/filter/AndDimFilterTest.java | 18 +--
.../apache/druid/query/filter/OrDimFilterTest.java | 14 +-
.../segment/filter/FilterCnfConversionTest.java | 148 ++++++++++----------
.../druid/segment/join/JoinFilterAnalyzerTest.java | 22 +--
15 files changed, 320 insertions(+), 372 deletions(-)
diff --git a/processing/src/main/java/org/apache/druid/query/filter/AndDimFilter.java b/processing/src/main/java/org/apache/druid/query/filter/AndDimFilter.java
index 9e29658..0f04629 100644
--- a/processing/src/main/java/org/apache/druid/query/filter/AndDimFilter.java
+++ b/processing/src/main/java/org/apache/druid/query/filter/AndDimFilter.java
@@ -26,16 +26,15 @@ import com.google.common.base.Preconditions;
import com.google.common.collect.RangeSet;
import com.google.common.collect.TreeRangeSet;
import org.apache.druid.java.util.common.StringUtils;
-import org.apache.druid.segment.filter.AndFilter;
import org.apache.druid.segment.filter.Filters;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
-import java.util.stream.Collectors;
/**
+ *
*/
public class AndDimFilter extends AbstractOptimizableDimFilter implements DimFilter
{
@@ -73,26 +72,22 @@ public class AndDimFilter extends AbstractOptimizableDimFilter implements DimFil
@Override
public DimFilter optimize()
{
- List<DimFilter> elements = DimFilters.optimize(fields)
- .stream()
- .filter(filter -> !(filter instanceof TrueDimFilter))
- .collect(Collectors.toList());
- if (elements.isEmpty()) {
- // All elements were TrueDimFilter after optimization
- return TrueDimFilter.instance();
- } else if (elements.size() == 1) {
- return elements.get(0);
- } else if (elements.stream().anyMatch(filter -> filter instanceof FalseDimFilter)) {
- return FalseDimFilter.instance();
+ // This method optimizes children, but doesn't do any special AND-related stuff like flattening or duplicate
+ // removal. That will happen in "toFilter", which allows us to share code with Filters.and(...).
+
+ final List<DimFilter> newFields = DimFilters.optimize(fields);
+
+ if (newFields.size() == 1) {
+ return newFields.get(0);
} else {
- return new AndDimFilter(elements);
+ return new AndDimFilter(newFields);
}
}
@Override
public Filter toFilter()
{
- return new AndFilter(Filters.toFilters(fields));
+ return Filters.and(Filters.toFilters(fields));
}
@Override
diff --git a/processing/src/main/java/org/apache/druid/query/filter/BooleanFilter.java b/processing/src/main/java/org/apache/druid/query/filter/BooleanFilter.java
index e11153e..f0ae210 100644
--- a/processing/src/main/java/org/apache/druid/query/filter/BooleanFilter.java
+++ b/processing/src/main/java/org/apache/druid/query/filter/BooleanFilter.java
@@ -23,13 +23,20 @@ import org.apache.druid.segment.ColumnSelector;
import org.apache.druid.segment.ColumnSelectorFactory;
import java.util.HashSet;
+import java.util.LinkedHashSet;
import java.util.Set;
public interface BooleanFilter extends Filter
{
ValueMatcher[] EMPTY_VALUE_MATCHER_ARRAY = new ValueMatcher[0];
- Set<Filter> getFilters();
+ /**
+ * Returns the child filters for this filter.
+ *
+ * This is a LinkedHashSet because we don't want duplicates, but the order is also important in some cases (such
+ * as when filters are provided in an order that encourages short-circuiting.)
+ */
+ LinkedHashSet<Filter> getFilters();
/**
* Get a ValueMatcher that applies this filter to row values.
diff --git a/processing/src/main/java/org/apache/druid/query/filter/OrDimFilter.java b/processing/src/main/java/org/apache/druid/query/filter/OrDimFilter.java
index d758d15..aec244a 100644
--- a/processing/src/main/java/org/apache/druid/query/filter/OrDimFilter.java
+++ b/processing/src/main/java/org/apache/druid/query/filter/OrDimFilter.java
@@ -27,16 +27,15 @@ import com.google.common.collect.RangeSet;
import com.google.common.collect.TreeRangeSet;
import org.apache.druid.java.util.common.StringUtils;
import org.apache.druid.segment.filter.Filters;
-import org.apache.druid.segment.filter.OrFilter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
-import java.util.stream.Collectors;
/**
+ *
*/
public class OrDimFilter extends AbstractOptimizableDimFilter implements DimFilter
{
@@ -81,26 +80,22 @@ public class OrDimFilter extends AbstractOptimizableDimFilter implements DimFilt
@Override
public DimFilter optimize()
{
- List<DimFilter> elements = DimFilters.optimize(fields)
- .stream()
- .filter(filter -> !(filter instanceof FalseDimFilter))
- .collect(Collectors.toList());
- if (elements.isEmpty()) {
- // All elements were FalseDimFilter after optimization
- return FalseDimFilter.instance();
- } else if (elements.size() == 1) {
- return elements.get(0);
- } else if (elements.stream().anyMatch(filter -> filter instanceof TrueDimFilter)) {
- return TrueDimFilter.instance();
+ // This method optimizes children, but doesn't do any special AND-related stuff like flattening or duplicate
+ // removal. That will happen in "toFilter", which allows us to share code with Filters.or(...).
+
+ final List<DimFilter> newFields = DimFilters.optimize(fields);
+
+ if (newFields.size() == 1) {
+ return newFields.get(0);
} else {
- return new OrDimFilter(elements);
+ return new OrDimFilter(newFields);
}
}
@Override
public Filter toFilter()
{
- return new OrFilter(Filters.toFilters(fields));
+ return Filters.or(Filters.toFilters(fields));
}
@Override
diff --git a/processing/src/main/java/org/apache/druid/segment/QueryableIndexStorageAdapter.java b/processing/src/main/java/org/apache/druid/segment/QueryableIndexStorageAdapter.java
index fcd541f..8d97206 100644
--- a/processing/src/main/java/org/apache/druid/segment/QueryableIndexStorageAdapter.java
+++ b/processing/src/main/java/org/apache/druid/segment/QueryableIndexStorageAdapter.java
@@ -54,7 +54,6 @@ import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
-import java.util.Set;
/**
*
@@ -391,13 +390,13 @@ public class QueryableIndexStorageAdapter implements StorageAdapter
*
* Any subfilters that cannot be processed entirely with bitmap indexes will be moved to the post-filtering stage.
*/
- final Set<Filter> preFilters;
+ final List<Filter> preFilters;
final List<Filter> postFilters = new ArrayList<>();
int preFilteredRows = totalRows;
if (filter == null) {
- preFilters = Collections.emptySet();
+ preFilters = Collections.emptyList();
} else {
- preFilters = new HashSet<>();
+ preFilters = new ArrayList<>();
if (filter instanceof AndFilter) {
// If we get an AndFilter, we can split the subfilters across both filtering stages
@@ -445,7 +444,7 @@ public class QueryableIndexStorageAdapter implements StorageAdapter
queryMetrics.reportPreFilteredRows(preFilteredRows);
}
- return new FilterAnalysis(preFilterBitmap, Filters.and(postFilters));
+ return new FilterAnalysis(preFilterBitmap, Filters.maybeAnd(postFilters).orElse(null));
}
@VisibleForTesting
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/AndFilter.java b/processing/src/main/java/org/apache/druid/segment/filter/AndFilter.java
index 696bd8b..9f03f25 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/AndFilter.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/AndFilter.java
@@ -40,35 +40,36 @@ import org.apache.druid.segment.ColumnSelectorFactory;
import org.apache.druid.segment.vector.VectorColumnSelectorFactory;
import java.util.ArrayList;
-import java.util.HashSet;
+import java.util.Collection;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
-import java.util.Set;
/**
+ *
*/
public class AndFilter implements BooleanFilter
{
private static final Joiner AND_JOINER = Joiner.on(" && ");
- private final Set<Filter> filters;
+ private final LinkedHashSet<Filter> filters;
- @VisibleForTesting
- public AndFilter(List<Filter> filters)
+ public AndFilter(LinkedHashSet<Filter> filters)
{
- this(new HashSet<>(filters));
+ Preconditions.checkArgument(filters.size() > 0, "Can't construct empty AndFilter");
+ this.filters = filters;
}
- public AndFilter(Set<Filter> filters)
+ @VisibleForTesting
+ public AndFilter(List<Filter> filters)
{
- Preconditions.checkArgument(filters.size() > 0, "Can't construct empty AndFilter");
- this.filters = filters;
+ this(new LinkedHashSet<>(filters));
}
public static <T> ImmutableBitmap getBitmapIndex(
BitmapIndexSelector selector,
BitmapResultFactory<T> bitmapResultFactory,
- Set<Filter> filters
+ List<Filter> filters
)
{
return bitmapResultFactory.toImmutableBitmap(getBitmapResult(selector, bitmapResultFactory, filters));
@@ -77,7 +78,7 @@ public class AndFilter implements BooleanFilter
private static <T> T getBitmapResult(
BitmapIndexSelector selector,
BitmapResultFactory<T> bitmapResultFactory,
- Set<Filter> filters
+ Collection<Filter> filters
)
{
if (filters.size() == 1) {
@@ -165,7 +166,7 @@ public class AndFilter implements BooleanFilter
}
@Override
- public Set<Filter> getFilters()
+ public LinkedHashSet<Filter> getFilters()
{
return filters;
}
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/BoundFilter.java b/processing/src/main/java/org/apache/druid/segment/filter/BoundFilter.java
index 58225e3..10a1767 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/BoundFilter.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/BoundFilter.java
@@ -147,6 +147,7 @@ public class BoundFilter implements Filter
{
return selector.getBitmapIndex(boundDimFilter.getDimension()) != null;
}
+
@Override
public boolean shouldUseBitmapIndex(BitmapIndexSelector selector)
{
@@ -313,6 +314,12 @@ public class BoundFilter implements Filter
return Objects.hash(boundDimFilter, extractionFn, filterTuning);
}
+ @Override
+ public String toString()
+ {
+ return boundDimFilter.toString();
+ }
+
@VisibleForTesting
static class BoundDimFilterDruidPredicateFactory implements DruidPredicateFactory
{
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/Filters.java b/processing/src/main/java/org/apache/druid/segment/filter/Filters.java
index 91d3409..03209d0 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/Filters.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/Filters.java
@@ -22,10 +22,12 @@ package org.apache.druid.segment.filter;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
import it.unimi.dsi.fastutil.ints.IntIterable;
import it.unimi.dsi.fastutil.ints.IntIterator;
import it.unimi.dsi.fastutil.ints.IntList;
import org.apache.druid.collections.bitmap.ImmutableBitmap;
+import org.apache.druid.java.util.common.IAE;
import org.apache.druid.query.BitmapResultFactory;
import org.apache.druid.query.Query;
import org.apache.druid.query.QueryContexts;
@@ -50,11 +52,14 @@ import org.apache.druid.segment.join.filter.AllNullColumnSelectorFactory;
import javax.annotation.Nullable;
import java.io.IOException;
import java.io.UncheckedIOException;
+import java.util.ArrayList;
+import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
-import java.util.Set;
+import java.util.Optional;
import java.util.stream.Collectors;
/**
@@ -71,9 +76,9 @@ public class Filters
*
* @return list of Filters
*/
- public static Set<Filter> toFilters(List<DimFilter> dimFilters)
+ public static List<Filter> toFilters(List<DimFilter> dimFilters)
{
- return dimFilters.stream().map(DimFilter::toFilter).collect(Collectors.toSet());
+ return dimFilters.stream().map(Filters::toFilter).collect(Collectors.toList());
}
/**
@@ -480,56 +485,93 @@ public class Filters
}
/**
- * Create a filter representing an AND relationship across a list of filters.
+ * Create a filter representing an AND relationship across a list of filters. Deduplicates filters, flattens stacks,
+ * and removes literal "false" filters.
*
- * @param filterList List of filters
+ * @param filters List of filters
*
- * @return If filterList has more than one element, return an AND filter composed of the filters from filterList
- * If filterList has a single element, return that element alone
- * If filterList is empty, return null
+ * @return If "filters" has more than one filter remaining after processing, returns {@link AndFilter}.
+ * If "filters" has a single element remaining after processing, return that filter alone.
+ *
+ * @throws IllegalArgumentException if "filters" is empty
*/
- @Nullable
- public static Filter and(List<Filter> filterList)
+ public static Filter and(final List<Filter> filters)
{
- if (filterList.isEmpty()) {
- return null;
- }
+ return maybeAnd(filters).orElseThrow(() -> new IAE("Expected nonempty filters list"));
+ }
- if (filterList.size() == 1) {
- return filterList.get(0);
+ /**
+ * Like {@link #and}, but returns an empty Optional instead of throwing an exception if "filters" is empty.
+ */
+ public static Optional<Filter> maybeAnd(List<Filter> filters)
+ {
+ if (filters.isEmpty()) {
+ return Optional.empty();
}
- return new AndFilter(filterList);
+ final LinkedHashSet<Filter> filtersToUse = flattenAndChildren(filters);
+
+ if (filtersToUse.isEmpty()) {
+ assert !filters.isEmpty();
+ // Original "filters" list must have been 100% literally-true filters.
+ return Optional.of(TrueFilter.instance());
+ } else if (filtersToUse.stream().anyMatch(filter -> filter instanceof FalseFilter)) {
+ // AND of FALSE with anything is FALSE.
+ return Optional.of(FalseFilter.instance());
+ } else if (filtersToUse.size() == 1) {
+ return Optional.of(Iterables.getOnlyElement(filtersToUse));
+ } else {
+ return Optional.of(new AndFilter(filtersToUse));
+ }
}
/**
- * Create a filter representing an OR relationship across a set of filters.
+ * Create a filter representing an OR relationship across a list of filters. Deduplicates filters, flattens stacks,
+ * and removes literal "false" filters.
*
- * @param filterSet Set of filters
+ * @param filters List of filters
*
- * @return If filterSet has more than one element, return an OR filter composed of the filters from filterSet
- * If filterSet has a single element, return that element alone
- * If filterSet is empty, return null
+ * @return If "filters" has more than one filter remaining after processing, returns {@link OrFilter}.
+ * If "filters" has a single element remaining after processing, return that filter alone.
+ *
+ * @throws IllegalArgumentException if "filters" is empty
*/
- @Nullable
- public static Filter or(Set<Filter> filterSet)
+ public static Filter or(final List<Filter> filters)
{
- if (filterSet.isEmpty()) {
- return null;
- }
+ return maybeOr(filters).orElseThrow(() -> new IAE("Expected nonempty filters list"));
+ }
- if (filterSet.size() == 1) {
- return filterSet.iterator().next();
+ /**
+ * Like {@link #or}, but returns an empty Optional instead of throwing an exception if "filters" is empty.
+ */
+ public static Optional<Filter> maybeOr(final List<Filter> filters)
+ {
+ if (filters.isEmpty()) {
+ return Optional.empty();
}
- return new OrFilter(filterSet);
+ final LinkedHashSet<Filter> filtersToUse = flattenOrChildren(filters);
+
+ if (filtersToUse.isEmpty()) {
+ assert !filters.isEmpty();
+ // Original "filters" list must have been 100% literally-false filters.
+ return Optional.of(FalseFilter.instance());
+ } else if (filtersToUse.stream().anyMatch(filter -> filter instanceof TrueFilter)) {
+ // OR of TRUE with anything is TRUE.
+ return Optional.of(TrueFilter.instance());
+ } else if (filtersToUse.size() == 1) {
+ return Optional.of(Iterables.getOnlyElement(filtersToUse));
+ } else {
+ return Optional.of(new OrFilter(filtersToUse));
+ }
}
/**
* @param filter the filter.
+ *
* @return The normalized or clauses for the provided filter.
*/
- public static Set<Filter> toNormalizedOrClauses(Filter filter)
+ public static List<Filter> toNormalizedOrClauses(Filter filter)
{
Filter normalizedFilter = Filters.toCnf(filter);
@@ -537,11 +579,11 @@ public class Filters
// CNF normalization will generate either
// - an AND filter with multiple subfilters
// - or a single non-AND subfilter which cannot be split further
- Set<Filter> normalizedOrClauses;
+ List<Filter> normalizedOrClauses;
if (normalizedFilter instanceof AndFilter) {
- normalizedOrClauses = ((AndFilter) normalizedFilter).getFilters();
+ normalizedOrClauses = new ArrayList<>(((AndFilter) normalizedFilter).getFilters());
} else {
- normalizedOrClauses = Collections.singleton(normalizedFilter);
+ normalizedOrClauses = Collections.singletonList(normalizedFilter);
}
return normalizedOrClauses;
}
@@ -552,4 +594,40 @@ public class Filters
ValueMatcher valueMatcher = filter.makeMatcher(ALL_NULL_COLUMN_SELECTOR_FACTORY);
return valueMatcher.matches();
}
+
+ /**
+ * Flattens children of an AND, removes duplicates, and removes literally-true filters.
+ */
+ private static LinkedHashSet<Filter> flattenAndChildren(final Collection<Filter> filters)
+ {
+ final LinkedHashSet<Filter> retVal = new LinkedHashSet<>();
+
+ for (Filter child : filters) {
+ if (child instanceof AndFilter) {
+ retVal.addAll(flattenAndChildren(((AndFilter) child).getFilters()));
+ } else if (!(child instanceof TrueFilter)) {
+ retVal.add(child);
+ }
+ }
+
+ return retVal;
+ }
+
+ /**
+ * Flattens children of an OR, removes duplicates, and removes literally-false filters.
+ */
+ private static LinkedHashSet<Filter> flattenOrChildren(final Collection<Filter> filters)
+ {
+ final LinkedHashSet<Filter> retVal = new LinkedHashSet<>();
+
+ for (Filter child : filters) {
+ if (child instanceof OrFilter) {
+ retVal.addAll(flattenOrChildren(((OrFilter) child).getFilters()));
+ } else if (!(child instanceof FalseFilter)) {
+ retVal.add(child);
+ }
+ }
+
+ return retVal;
+ }
}
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/OrFilter.java b/processing/src/main/java/org/apache/druid/segment/filter/OrFilter.java
index 4369d3d..7e532c8 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/OrFilter.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/OrFilter.java
@@ -19,7 +19,6 @@
package org.apache.druid.segment.filter;
-import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Joiner;
import com.google.common.base.Preconditions;
import com.google.common.collect.Iterables;
@@ -40,30 +39,28 @@ import org.apache.druid.segment.ColumnSelectorFactory;
import org.apache.druid.segment.vector.VectorColumnSelectorFactory;
import java.util.ArrayList;
-import java.util.HashSet;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
-import java.util.Set;
/**
+ *
*/
public class OrFilter implements BooleanFilter
{
private static final Joiner OR_JOINER = Joiner.on(" || ");
- private final Set<Filter> filters;
+ private final LinkedHashSet<Filter> filters;
- @VisibleForTesting
- public OrFilter(List<Filter> filters)
+ public OrFilter(LinkedHashSet<Filter> filters)
{
- this(new HashSet<>(filters));
+ Preconditions.checkArgument(filters.size() > 0, "Can't construct empty OrFilter (the universe does not exist)");
+ this.filters = filters;
}
- public OrFilter(Set<Filter> filters)
+ public OrFilter(List<Filter> filters)
{
- Preconditions.checkArgument(filters.size() > 0, "Can't construct empty OrFilter (the universe does not exist)");
-
- this.filters = filters;
+ this(new LinkedHashSet<>(filters));
}
@Override
@@ -140,7 +137,7 @@ public class OrFilter implements BooleanFilter
}
@Override
- public Set<Filter> getFilters()
+ public LinkedHashSet<Filter> getFilters()
{
return filters;
}
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/cnf/CalciteCnfHelper.java b/processing/src/main/java/org/apache/druid/segment/filter/cnf/CalciteCnfHelper.java
index 0685948..18c7e43 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/cnf/CalciteCnfHelper.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/cnf/CalciteCnfHelper.java
@@ -24,18 +24,16 @@ import com.google.common.collect.Iterables;
import org.apache.druid.query.filter.Filter;
import org.apache.druid.segment.filter.AndFilter;
import org.apache.druid.segment.filter.FalseFilter;
+import org.apache.druid.segment.filter.Filters;
import org.apache.druid.segment.filter.OrFilter;
import org.apache.druid.segment.filter.TrueFilter;
-import javax.annotation.Nonnull;
import java.util.ArrayList;
import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
-import java.util.Objects;
-import java.util.Set;
/**
* All functions in this class were basically adopted from Apache Calcite and modified to use them in Druid.
@@ -46,7 +44,7 @@ public class CalciteCnfHelper
{
public static Filter pull(Filter rex)
{
- final Set<Filter> operands;
+ final LinkedHashSet<Filter> operands;
if (rex instanceof AndFilter) {
operands = ((AndFilter) rex).getFilters();
return and(pullList(operands));
@@ -73,7 +71,7 @@ public class CalciteCnfHelper
}
}
- private static List<Filter> pullList(Set<Filter> nodes)
+ private static List<Filter> pullList(Collection<Filter> nodes)
{
final List<Filter> list = new ArrayList<>();
for (Filter node : nodes) {
@@ -87,9 +85,9 @@ public class CalciteCnfHelper
return list;
}
- private static Map<Filter, Filter> commonFactors(Set<Filter> nodes)
+ private static Map<Filter, Filter> commonFactors(Collection<Filter> nodes)
{
- final Map<Filter, Filter> map = new HashMap<>();
+ final Map<Filter, Filter> map = new LinkedHashMap<>();
int i = 0;
for (Filter node : nodes) {
if (i++ == 0) {
@@ -116,137 +114,12 @@ public class CalciteCnfHelper
private static Filter and(Iterable<? extends Filter> nodes)
{
- return composeConjunction(nodes);
+ return Filters.maybeAnd(ImmutableList.copyOf(nodes)).orElse(TrueFilter.instance());
}
private static Filter or(Iterable<? extends Filter> nodes)
{
- return composeDisjunction(nodes);
- }
-
- /** As {@link #composeConjunction(Iterable, boolean)} but never
- * returns null. */
- public static @Nonnull Filter composeConjunction(Iterable<? extends Filter> nodes)
- {
- final Filter e = composeConjunction(nodes, false);
- return Objects.requireNonNull(e);
- }
-
- /**
- * Converts a collection of expressions into an AND.
- * If there are zero expressions, returns TRUE.
- * If there is one expression, returns just that expression.
- * If any of the expressions are FALSE, returns FALSE.
- * Removes expressions that always evaluate to TRUE.
- * Returns null only if {@code nullOnEmpty} and expression is TRUE.
- */
- public static Filter composeConjunction(Iterable<? extends Filter> nodes, boolean nullOnEmpty)
- {
- ImmutableList<Filter> list = flattenAnd(nodes);
- switch (list.size()) {
- case 0:
- return nullOnEmpty
- ? null
- : TrueFilter.instance();
- case 1:
- return list.get(0);
- default:
- return new AndFilter(list);
- }
- }
-
- /** Flattens a list of AND nodes.
- *
- * <p>Treats null nodes as literal TRUE (i.e. ignores them). */
- public static ImmutableList<Filter> flattenAnd(Iterable<? extends Filter> nodes)
- {
- if (nodes instanceof Collection && ((Collection) nodes).isEmpty()) {
- // Optimize common case
- return ImmutableList.of();
- }
- final ImmutableList.Builder<Filter> builder = ImmutableList.builder();
- final Set<Filter> set = new HashSet<>(); // to eliminate duplicates
- for (Filter node : nodes) {
- if (node != null) {
- addAnd(builder, set, node);
- }
- }
- return builder.build();
- }
-
- private static void addAnd(ImmutableList.Builder<Filter> builder, Set<Filter> digests, Filter node)
- {
- if (node instanceof AndFilter) {
- for (Filter operand : ((AndFilter) node).getFilters()) {
- addAnd(builder, digests, operand);
- }
- } else {
- if (!(node instanceof TrueFilter) && digests.add(node)) {
- builder.add(node);
- }
- }
- }
-
- /**
- * Converts a collection of expressions into an OR.
- * If there are zero expressions, returns FALSE.
- * If there is one expression, returns just that expression.
- * If any of the expressions are TRUE, returns TRUE.
- * Removes expressions that always evaluate to FALSE.
- * Flattens expressions that are ORs.
- */
- @Nonnull public static Filter composeDisjunction(Iterable<? extends Filter> nodes)
- {
- final Filter e = composeDisjunction(nodes, false);
- return Objects.requireNonNull(e);
- }
-
- /**
- * Converts a collection of expressions into an OR,
- * optionally returning null if the list is empty.
- */
- public static Filter composeDisjunction(Iterable<? extends Filter> nodes, boolean nullOnEmpty)
- {
- ImmutableList<Filter> list = flattenOr(nodes);
- switch (list.size()) {
- case 0:
- return nullOnEmpty ? null : FalseFilter.instance();
- case 1:
- return list.get(0);
- default:
- if (containsTrue(list)) {
- return TrueFilter.instance();
- }
- return new OrFilter(list);
- }
- }
-
- /** Flattens a list of OR nodes. */
- public static ImmutableList<Filter> flattenOr(Iterable<? extends Filter> nodes)
- {
- if (nodes instanceof Collection && ((Collection) nodes).isEmpty()) {
- // Optimize common case
- return ImmutableList.of();
- }
- final ImmutableList.Builder<Filter> builder = ImmutableList.builder();
- final Set<Filter> set = new HashSet<>(); // to eliminate duplicates
- for (Filter node : nodes) {
- addOr(builder, set, node);
- }
- return builder.build();
- }
-
- private static void addOr(ImmutableList.Builder<Filter> builder, Set<Filter> set, Filter node)
- {
- if (node instanceof OrFilter) {
- for (Filter operand : ((OrFilter) node).getFilters()) {
- addOr(builder, set, operand);
- }
- } else {
- if (set.add(node)) {
- builder.add(node);
- }
- }
+ return Filters.maybeOr(ImmutableList.copyOf(nodes)).orElse(FalseFilter.instance());
}
/**
@@ -283,16 +156,6 @@ public class CalciteCnfHelper
}
}
- private static boolean containsTrue(Iterable<Filter> nodes)
- {
- for (Filter node : nodes) {
- if (node instanceof TrueFilter) {
- return true;
- }
- }
- return false;
- }
-
private CalciteCnfHelper()
{
}
diff --git a/processing/src/main/java/org/apache/druid/segment/filter/cnf/HiveCnfHelper.java b/processing/src/main/java/org/apache/druid/segment/filter/cnf/HiveCnfHelper.java
index e5669b8..5c5ca10 100644
--- a/processing/src/main/java/org/apache/druid/segment/filter/cnf/HiveCnfHelper.java
+++ b/processing/src/main/java/org/apache/druid/segment/filter/cnf/HiveCnfHelper.java
@@ -22,13 +22,13 @@ package org.apache.druid.segment.filter.cnf;
import org.apache.druid.query.filter.BooleanFilter;
import org.apache.druid.query.filter.Filter;
import org.apache.druid.segment.filter.AndFilter;
+import org.apache.druid.segment.filter.Filters;
import org.apache.druid.segment.filter.NotFilter;
import org.apache.druid.segment.filter.OrFilter;
import java.util.ArrayList;
-import java.util.HashSet;
+import java.util.Collections;
import java.util.List;
-import java.util.Set;
/**
* All functions in this class were basically adopted from Apache Hive and modified to use them in Druid.
@@ -45,35 +45,35 @@ public class HiveCnfHelper
return pushDownNot(((NotFilter) child).getBaseFilter());
}
if (child instanceof AndFilter) {
- Set<Filter> children = new HashSet<>();
+ List<Filter> children = new ArrayList<>();
for (Filter grandChild : ((AndFilter) child).getFilters()) {
children.add(pushDownNot(new NotFilter(grandChild)));
}
- return new OrFilter(children);
+ return Filters.or(children);
}
if (child instanceof OrFilter) {
- Set<Filter> children = new HashSet<>();
+ List<Filter> children = new ArrayList<>();
for (Filter grandChild : ((OrFilter) child).getFilters()) {
children.add(pushDownNot(new NotFilter(grandChild)));
}
- return new AndFilter(children);
+ return Filters.and(children);
}
}
if (current instanceof AndFilter) {
- Set<Filter> children = new HashSet<>();
+ List<Filter> children = new ArrayList<>();
for (Filter child : ((AndFilter) current).getFilters()) {
children.add(pushDownNot(child));
}
- return new AndFilter(children);
+ return Filters.and(children);
}
if (current instanceof OrFilter) {
- Set<Filter> children = new HashSet<>();
+ List<Filter> children = new ArrayList<>();
for (Filter child : ((OrFilter) current).getFilters()) {
children.add(pushDownNot(child));
}
- return new OrFilter(children);
+ return Filters.or(children);
}
return current;
}
@@ -84,17 +84,17 @@ public class HiveCnfHelper
return new NotFilter(convertToCnf(((NotFilter) current).getBaseFilter()));
}
if (current instanceof AndFilter) {
- Set<Filter> children = new HashSet<>();
+ List<Filter> children = new ArrayList<>();
for (Filter child : ((AndFilter) current).getFilters()) {
children.add(convertToCnf(child));
}
- return new AndFilter(children);
+ return Filters.and(children);
}
if (current instanceof OrFilter) {
// a list of leaves that weren't under AND expressions
- List<Filter> nonAndList = new ArrayList<Filter>();
+ List<Filter> nonAndList = new ArrayList<>();
// a list of AND expressions that we need to distribute
- List<Filter> andList = new ArrayList<Filter>();
+ List<Filter> andList = new ArrayList<>();
for (Filter child : ((OrFilter) current).getFilters()) {
if (child instanceof AndFilter) {
andList.add(child);
@@ -106,9 +106,9 @@ public class HiveCnfHelper
}
}
if (!andList.isEmpty()) {
- Set<Filter> result = new HashSet<>();
+ List<Filter> result = new ArrayList<>();
generateAllCombinations(result, andList, nonAndList);
- return new AndFilter(result);
+ return Filters.and(result);
}
}
return current;
@@ -125,7 +125,7 @@ public class HiveCnfHelper
// do we need to flatten?
if (child.getClass() == root.getClass() && !(child instanceof NotFilter)) {
boolean first = true;
- Set<Filter> grandKids = ((BooleanFilter) child).getFilters();
+ List<Filter> grandKids = new ArrayList<>(((BooleanFilter) child).getFilters());
for (Filter grandkid : grandKids) {
// for the first grandkid replace the original parent
if (first) {
@@ -156,26 +156,28 @@ public class HiveCnfHelper
// A helper function adapted from Apache Hive, see:
// https://github.com/apache/hive/blob/branch-2.0/storage-api/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java
private static void generateAllCombinations(
- Set<Filter> result,
+ List<Filter> result,
List<Filter> andList,
List<Filter> nonAndList
)
{
- Set<Filter> children = ((AndFilter) andList.get(0)).getFilters();
+ List<Filter> children = new ArrayList<>(((AndFilter) andList.get(0)).getFilters());
if (result.isEmpty()) {
for (Filter child : children) {
- Set<Filter> a = new HashSet<>(nonAndList);
+ List<Filter> a = new ArrayList<>(nonAndList);
a.add(child);
- result.add(new OrFilter(a));
+ // Result must receive an actual OrFilter, so wrap if Filters.or managed to un-OR it.
+ result.add(idempotentOr(Filters.or(a)));
}
} else {
List<Filter> work = new ArrayList<>(result);
result.clear();
for (Filter child : children) {
for (Filter or : work) {
- Set<Filter> a = new HashSet<>((((OrFilter) or).getFilters()));
+ List<Filter> a = new ArrayList<>((((OrFilter) or).getFilters()));
a.add(child);
- result.add(new OrFilter(a));
+ // Result must receive an actual OrFilter.
+ result.add(idempotentOr(Filters.or(a)));
}
}
}
@@ -184,6 +186,14 @@ public class HiveCnfHelper
}
}
+ /**
+ * Return filter as-is if it is an OR, otherwise wrap in an OR.
+ */
+ private static OrFilter idempotentOr(final Filter filter)
+ {
+ return filter instanceof OrFilter ? (OrFilter) filter : new OrFilter(Collections.singletonList(filter));
+ }
+
private HiveCnfHelper()
{
}
diff --git a/processing/src/main/java/org/apache/druid/segment/join/filter/JoinFilterAnalyzer.java b/processing/src/main/java/org/apache/druid/segment/join/filter/JoinFilterAnalyzer.java
index d3dd5cf..cc9f244 100644
--- a/processing/src/main/java/org/apache/druid/segment/join/filter/JoinFilterAnalyzer.java
+++ b/processing/src/main/java/org/apache/druid/segment/join/filter/JoinFilterAnalyzer.java
@@ -100,7 +100,7 @@ public class JoinFilterAnalyzer
return preAnalysisBuilder.build();
}
- Set<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(key.getFilter());
+ List<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(key.getFilter());
List<Filter> normalizedBaseTableClauses = new ArrayList<>();
List<Filter> normalizedJoinTableClauses = new ArrayList<>();
@@ -183,8 +183,8 @@ public class JoinFilterAnalyzer
}
return new JoinFilterSplit(
- Filters.and(leftFilters),
- Filters.and(rightFilters),
+ Filters.maybeAnd(leftFilters).orElse(null),
+ Filters.maybeAnd(rightFilters).orElse(null),
new HashSet<>(pushDownVirtualColumnsForLhsExprs.values())
);
}
@@ -309,7 +309,7 @@ public class JoinFilterAnalyzer
return new JoinFilterAnalysis(
false,
filterClause,
- Filters.and(newFilters)
+ Filters.maybeAnd(newFilters).orElse(null)
);
}
@@ -329,7 +329,7 @@ public class JoinFilterAnalyzer
Map<Expr, VirtualColumn> pushDownVirtualColumnsForLhsExprs
)
{
- Set<Filter> newFilters = new HashSet<>();
+ List<Filter> newFilters = new ArrayList<>();
boolean retainRhs = false;
for (Filter filter : orFilter.getFilters()) {
@@ -369,7 +369,7 @@ public class JoinFilterAnalyzer
return new JoinFilterAnalysis(
retainRhs,
orFilter,
- Filters.or(newFilters)
+ Filters.maybeOr(newFilters).orElse(null)
);
}
@@ -473,7 +473,7 @@ public class JoinFilterAnalyzer
return new JoinFilterAnalysis(
true,
selectorFilter,
- Filters.and(newFilters)
+ Filters.maybeAnd(newFilters).orElse(null)
);
}
diff --git a/processing/src/test/java/org/apache/druid/query/filter/AndDimFilterTest.java b/processing/src/test/java/org/apache/druid/query/filter/AndDimFilterTest.java
index e45ed29..5e83682 100644
--- a/processing/src/test/java/org/apache/druid/query/filter/AndDimFilterTest.java
+++ b/processing/src/test/java/org/apache/druid/query/filter/AndDimFilterTest.java
@@ -21,7 +21,9 @@ package org.apache.druid.query.filter;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
+import org.apache.druid.segment.filter.FalseFilter;
import org.apache.druid.segment.filter.FilterTestUtils;
+import org.apache.druid.segment.filter.TrueFilter;
import org.apache.druid.testing.InitializedNullHandlingTest;
import org.junit.Assert;
import org.junit.Test;
@@ -67,37 +69,37 @@ public class AndDimFilterTest extends InitializedNullHandlingTest
}
@Test
- public void testOptimieShortCircuitWithFalseFilter()
+ public void testToFilterShortCircuitWithFalseFilter()
{
DimFilter filter = DimFilterTestUtils.and(
DimFilterTestUtils.selector("col1", "1"),
FalseDimFilter.instance()
);
- Assert.assertTrue(filter.optimize() instanceof FalseDimFilter);
+ Assert.assertTrue(filter.toFilter() instanceof FalseFilter);
}
@Test
- public void testOptimizeOringTrueFilters()
+ public void testToFilterOringTrueFilters()
{
DimFilter filter = DimFilterTestUtils.and(TrueDimFilter.instance(), TrueDimFilter.instance());
- Assert.assertSame(TrueDimFilter.instance(), filter.optimize());
+ Assert.assertSame(TrueFilter.instance(), filter.toFilter());
}
@Test
- public void testOptimizeAndOfSingleFilterUnwrapAnd()
+ public void testToFilterAndOfSingleFilterUnwrapAnd()
{
DimFilter expected = DimFilterTestUtils.selector("col1", "1");
DimFilter filter = DimFilterTestUtils.and(expected);
- Assert.assertEquals(expected, filter.optimize());
+ Assert.assertEquals(expected.toFilter(), filter.toFilter());
}
@Test
- public void testOptimizeAndOfMultipleFiltersReturningAsItIs()
+ public void testToFilterAndOfMultipleFiltersReturningAsItIs()
{
DimFilter filter = DimFilterTestUtils.and(
DimFilterTestUtils.selector("col1", "1"),
DimFilterTestUtils.selector("col1", "2")
);
- Assert.assertEquals(filter, filter.optimize());
+ Assert.assertEquals(filter.toFilter(), filter.toFilter());
}
}
diff --git a/processing/src/test/java/org/apache/druid/query/filter/OrDimFilterTest.java b/processing/src/test/java/org/apache/druid/query/filter/OrDimFilterTest.java
index fe080db..c9d87a0 100644
--- a/processing/src/test/java/org/apache/druid/query/filter/OrDimFilterTest.java
+++ b/processing/src/test/java/org/apache/druid/query/filter/OrDimFilterTest.java
@@ -19,7 +19,9 @@
package org.apache.druid.query.filter;
+import org.apache.druid.segment.filter.FalseFilter;
import org.apache.druid.segment.filter.FilterTestUtils;
+import org.apache.druid.segment.filter.TrueFilter;
import org.apache.druid.testing.InitializedNullHandlingTest;
import org.junit.Assert;
import org.junit.Test;
@@ -52,20 +54,20 @@ public class OrDimFilterTest extends InitializedNullHandlingTest
}
@Test
- public void testOptimieShortCircuitWithTrueFilter()
+ public void testToFilterShortCircuitWithTrueFilter()
{
DimFilter filter = DimFilterTestUtils.or(
DimFilterTestUtils.selector("col1", "1"),
TrueDimFilter.instance()
);
- Assert.assertTrue(filter.optimize() instanceof TrueDimFilter);
+ Assert.assertTrue(filter.toFilter() instanceof TrueFilter);
}
@Test
- public void testOptimizeOringFalseFilters()
+ public void testToFilterOringFalseFilters()
{
DimFilter filter = DimFilterTestUtils.or(FalseDimFilter.instance(), FalseDimFilter.instance());
- Assert.assertSame(FalseDimFilter.instance(), filter.optimize());
+ Assert.assertSame(FalseFilter.instance(), filter.toFilter());
}
@Test
@@ -73,7 +75,7 @@ public class OrDimFilterTest extends InitializedNullHandlingTest
{
DimFilter expected = DimFilterTestUtils.selector("col1", "1");
DimFilter filter = DimFilterTestUtils.or(expected);
- Assert.assertEquals(expected, filter.optimize());
+ Assert.assertEquals(expected.toFilter(), filter.toFilter());
}
@Test
@@ -83,6 +85,6 @@ public class OrDimFilterTest extends InitializedNullHandlingTest
DimFilterTestUtils.selector("col1", "1"),
DimFilterTestUtils.selector("col1", "2")
);
- Assert.assertEquals(filter, filter.optimize());
+ Assert.assertEquals(filter.toFilter(), filter.toFilter());
}
}
diff --git a/processing/src/test/java/org/apache/druid/segment/filter/FilterCnfConversionTest.java b/processing/src/test/java/org/apache/druid/segment/filter/FilterCnfConversionTest.java
index c12c012..e9b5304 100644
--- a/processing/src/test/java/org/apache/druid/segment/filter/FilterCnfConversionTest.java
+++ b/processing/src/test/java/org/apache/druid/segment/filter/FilterCnfConversionTest.java
@@ -19,8 +19,8 @@
package org.apache.druid.segment.filter;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
import org.apache.druid.java.util.common.ISE;
import org.apache.druid.java.util.common.StringUtils;
import org.apache.druid.query.dimension.DimensionSpec;
@@ -194,11 +194,11 @@ public class FilterCnfConversionTest
)
)
);
- final Set<Filter> expected = ImmutableSet.of(
+ final List<Filter> expected = ImmutableList.of(
FilterTestUtils.selector("col1", "val1"),
FilterTestUtils.selector("col2", "val2")
);
- final Set<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(muchReducible);
+ final List<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(muchReducible);
Assert.assertEquals(expected, normalizedOrClauses);
}
@@ -253,54 +253,54 @@ public class FilterCnfConversionTest
)
);
final Filter expected = FilterTestUtils.and(
+ // The below OR filter could be eliminated because this filter also has
+ // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
+ // The reduction process would be
+ // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
+ // However, we don't have this reduction now, so we have a filter in a suboptimized CNF.
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.selector("col2", "val22"),
- FilterTestUtils.selector("col3", "val3")
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col2", "val2"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col2", "val2")
),
FilterTestUtils.or(
FilterTestUtils.not(FilterTestUtils.selector("col2", "val2")),
- FilterTestUtils.selector("col3", "val3")
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col3", "val3"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4"))
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col2", "val2")),
+ FilterTestUtils.selector("col3", "val3")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col3", "val3"),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.selector("col3", "val3")
),
- FilterTestUtils.not(FilterTestUtils.selector("col1", "val11")),
- // The below OR filter could be eliminated because this filter also has
- // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
- // The reduction process would be
- // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
- // However, we don't have this reduction now, so we have a filter in a suboptimized CNF.
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col3", "val3")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col2", "val2"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
- )
+ FilterTestUtils.selector("col1", "val1"),
+ FilterTestUtils.selector("col2", "val22"),
+ FilterTestUtils.selector("col3", "val3")
+ ),
+ FilterTestUtils.not(FilterTestUtils.selector("col1", "val11"))
);
final Filter cnf = Filters.toCnf(filter);
assertFilter(filter, expected, cnf);
@@ -356,65 +356,65 @@ public class FilterCnfConversionTest
)
)
);
- final Set<Filter> expected = ImmutableSet.of(
+ final List<Filter> expected = ImmutableList.of(
+ // The below OR filter could be eliminated because this filter also has
+ // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
+ // The reduction process would be
+ // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5))
+ // => (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
+ // However, we don't have this reduction now, so we have a filter in a suboptimized CNF.
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.selector("col2", "val22"),
- FilterTestUtils.selector("col3", "val3")
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col2", "val2"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col2", "val2")
),
FilterTestUtils.or(
FilterTestUtils.not(FilterTestUtils.selector("col2", "val2")),
- FilterTestUtils.selector("col3", "val3")
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col3", "val3"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4"))
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col1", "val1")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col2", "val2")),
+ FilterTestUtils.selector("col3", "val3")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col3", "val3"),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
+ FilterTestUtils.selector("col3", "val3")
),
- FilterTestUtils.not(FilterTestUtils.selector("col1", "val11")),
- // The below OR filter could be eliminated because this filter also has
- // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
- // The reduction process would be
- // (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5)) && (col1 = val1 || ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 && ~(col4 = val4) || ~(col5 = val5))
- // => (col1 = val1 || ~(col4 = val4)) && (col1 = val1 || ~(col5 = val5)).
- // However, we don't have this reduction now, so we have a filter in a suboptimized CNF.
FilterTestUtils.or(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
+ FilterTestUtils.not(FilterTestUtils.selector("col5", "val5")),
+ FilterTestUtils.selector("col3", "val3")
),
FilterTestUtils.or(
- FilterTestUtils.selector("col2", "val2"),
- FilterTestUtils.not(FilterTestUtils.selector("col4", "val4")),
- FilterTestUtils.not(FilterTestUtils.selector("col5", "val5"))
- )
+ FilterTestUtils.selector("col1", "val1"),
+ FilterTestUtils.selector("col2", "val22"),
+ FilterTestUtils.selector("col3", "val3")
+ ),
+ FilterTestUtils.not(FilterTestUtils.selector("col1", "val11"))
);
- final Set<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(filter);
+ final List<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(filter);
Assert.assertEquals(expected, normalizedOrClauses);
}
@Test
public void testToCnfCollapsibleBigFilter()
{
- Set<Filter> ands = new HashSet<>();
- Set<Filter> ors = new HashSet<>();
+ List<Filter> ands = new ArrayList<>();
+ List<Filter> ors = new ArrayList<>();
for (int i = 0; i < 12; i++) {
ands.add(
FilterTestUtils.and(
@@ -432,11 +432,11 @@ public class FilterCnfConversionTest
FilterTestUtils.selector("col2", "val2")
);
final Filter expectedCnf = FilterTestUtils.and(
- FilterTestUtils.selector("col1", "val1"),
- FilterTestUtils.selector("col2", "val2"),
FilterTestUtils.selector("col3", "val3"),
FilterTestUtils.selector("col4", "val4"),
- new OrFilter(ors)
+ new OrFilter(ors),
+ FilterTestUtils.selector("col1", "val1"),
+ FilterTestUtils.selector("col2", "val2")
);
final Filter cnf = Filters.toCnf(bigFilter);
assertFilter(bigFilter, expectedCnf, cnf);
@@ -513,8 +513,8 @@ public class FilterCnfConversionTest
FilterTestUtils.selector("col1", "val1"),
FilterTestUtils.selector("col2", "val2")
);
- Set<Filter> expected = Collections.singleton(filter);
- Set<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(filter);
+ List<Filter> expected = Collections.singletonList(filter);
+ List<Filter> normalizedOrClauses = Filters.toNormalizedOrClauses(filter);
Assert.assertEquals(expected, normalizedOrClauses);
}
@@ -642,13 +642,13 @@ public class FilterCnfConversionTest
private Filter visitSelectorFilters(Filter filter, Function<SelectorFilter, Filter> visitAction)
{
if (filter instanceof AndFilter) {
- Set<Filter> newChildren = new HashSet<>();
+ List<Filter> newChildren = new ArrayList<>();
for (Filter child : ((AndFilter) filter).getFilters()) {
newChildren.add(visitSelectorFilters(child, visitAction));
}
return new AndFilter(newChildren);
} else if (filter instanceof OrFilter) {
- Set<Filter> newChildren = new HashSet<>();
+ List<Filter> newChildren = new ArrayList<>();
for (Filter child : ((OrFilter) filter).getFilters()) {
newChildren.add(visitSelectorFilters(child, visitAction));
}
diff --git a/processing/src/test/java/org/apache/druid/segment/join/JoinFilterAnalyzerTest.java b/processing/src/test/java/org/apache/druid/segment/join/JoinFilterAnalyzerTest.java
index ed7e7c7..72eb42f 100644
--- a/processing/src/test/java/org/apache/druid/segment/join/JoinFilterAnalyzerTest.java
+++ b/processing/src/test/java/org/apache/druid/segment/join/JoinFilterAnalyzerTest.java
@@ -2358,12 +2358,12 @@ public class JoinFilterAnalyzerTest extends BaseHashJoinSegmentStorageAdapterTes
);
String rewrittenCountryIsoCodeColumnName = hasLhsExpressionInJoinCondition
- ? "JOIN-FILTER-PUSHDOWN-VIRTUAL-COLUMN-0"
+ ? "JOIN-FILTER-PUSHDOWN-VIRTUAL-COLUMN-1"
: "countryIsoCode";
String rewrittenRegionIsoCodeColumnName = hasLhsExpressionInJoinCondition
- ? "JOIN-FILTER-PUSHDOWN-VIRTUAL-COLUMN-1"
+ ? "JOIN-FILTER-PUSHDOWN-VIRTUAL-COLUMN-0"
: "regionIsoCode";
Set<VirtualColumn> expectedVirtualColumns;
@@ -2410,6 +2410,7 @@ public class JoinFilterAnalyzerTest extends BaseHashJoinSegmentStorageAdapterTes
ImmutableList.of(
new SelectorFilter(rewrittenRegionIsoCodeColumnName, "ON"),
new SelectorFilter(rewrittenCountryIsoCodeColumnName, "CA"),
+ new InDimFilter(rewrittenCountryIsoCodeColumnName, ImmutableSet.of("CA"), null, null).toFilter(),
new BoundFilter(new BoundDimFilter(
rewrittenCountryIsoCodeColumnName,
"CA",
@@ -2426,7 +2427,6 @@ public class JoinFilterAnalyzerTest extends BaseHashJoinSegmentStorageAdapterTes
null,
null
).toFilter(),
- new InDimFilter(rewrittenCountryIsoCodeColumnName, ImmutableSet.of("CA"), null, null).toFilter(),
new OrFilter(
ImmutableList.of(
new SelectorFilter("channel", "#fr.wikipedia"),
@@ -2545,18 +2545,10 @@ public class JoinFilterAnalyzerTest extends BaseHashJoinSegmentStorageAdapterTes
JoinFilterSplit expectedFilterSplit = new JoinFilterSplit(
new AndFilter(
ImmutableList.of(
- new AndFilter(
- ImmutableList.of(
- new InDimFilter("countryIsoCode", ImmutableSet.of("MMMM", "AAAA"), null, null).toFilter(),
- new InDimFilter("regionIsoCode", ImmutableSet.of("MMMM", "AAAA"), null, null).toFilter()
- )
- ),
- new AndFilter(
- ImmutableList.of(
- new InDimFilter("countryIsoCode", ImmutableSet.of("US"), null, null).toFilter(),
- new InDimFilter("regionIsoCode", ImmutableSet.of("CA"), null, null).toFilter()
- )
- )
+ new InDimFilter("countryIsoCode", ImmutableSet.of("US"), null, null).toFilter(),
+ new InDimFilter("regionIsoCode", ImmutableSet.of("CA"), null, null).toFilter(),
+ new InDimFilter("countryIsoCode", ImmutableSet.of("MMMM", "AAAA"), null, null).toFilter(),
+ new InDimFilter("regionIsoCode", ImmutableSet.of("MMMM", "AAAA"), null, null).toFilter()
)
),
originalFilter,
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org