Sarg.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to you 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 org.apache.calcite.util;
import org.apache.calcite.linq4j.Ord;
import org.apache.calcite.rex.RexUnknownAs;
import org.apache.calcite.sql.fun.SqlStdOperatorTable;
import com.google.common.collect.ImmutableRangeSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Range;
import com.google.common.collect.RangeSet;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.util.function.BiConsumer;
import static java.util.Objects.requireNonNull;
/** Set of values (or ranges) that are the target of a search.
*
* <p>The name is derived from <b>S</b>earch <b>arg</b>ument, an ancient
* concept in database implementation; see Access Path Selection in a Relational
* Database Management System — Selinger et al. 1979 or the
* "<a href="https://blog.acolyer.org/2016/01/04/access-path-selection/">morning
* paper summary</a>.
*
* <p>In RexNode, a Sarg only occur as the right-hand operand in a call to
* {@link SqlStdOperatorTable#SEARCH}, wrapped in a
* {@link org.apache.calcite.rex.RexLiteral}. Lifecycle methods:
*
* <ul>
* <li>{@link org.apache.calcite.rex.RexUtil#expandSearch} removes
* calls to SEARCH and the included Sarg, converting them to comparisons;
* <li>{@link org.apache.calcite.rex.RexSimplify} converts complex comparisons
* on the same argument into SEARCH calls with an included Sarg;
* <li>Various {@link org.apache.calcite.tools.RelBuilder} methods,
* including {@link org.apache.calcite.tools.RelBuilder#in}
* and {@link org.apache.calcite.tools.RelBuilder#between}
* call {@link org.apache.calcite.rex.RexBuilder}
* methods {@link org.apache.calcite.rex.RexBuilder#makeIn}
* and {@link org.apache.calcite.rex.RexBuilder#makeBetween}
* that create Sarg instances directly;
* <li>{@link org.apache.calcite.rel.rel2sql.SqlImplementor} converts
* {@link org.apache.calcite.rex.RexCall}s
* to SEARCH into {@link org.apache.calcite.sql.SqlNode} AST expressions
* such as comparisons, {@code BETWEEN} and {@code IN}.
* </ul>
*
* @param <C> Value type
*
* @see SqlStdOperatorTable#SEARCH
*/
@SuppressWarnings("type.argument.type.incompatible")
public class Sarg<C extends Comparable<C>> implements Comparable<Sarg<C>> {
public final RangeSet<C> rangeSet;
public final RexUnknownAs nullAs;
public final int pointCount;
/** Returns FALSE for all null and not-null values.
*
* <p>{@code SEARCH(x, FALSE)} is equivalent to {@code FALSE}. */
private static final SpecialSarg FALSE =
new SpecialSarg(ImmutableRangeSet.of(), RexUnknownAs.FALSE,
"Sarg[FALSE]", 2);
/** Returns TRUE for all not-null values, FALSE for null.
*
* <p>{@code SEARCH(x, IS_NOT_NULL)} is equivalent to
* {@code x IS NOT NULL}. */
private static final SpecialSarg IS_NOT_NULL =
new SpecialSarg(ImmutableRangeSet.of().complement(), RexUnknownAs.FALSE,
"Sarg[IS NOT NULL]", 3);
/** Returns FALSE for all not-null values, TRUE for null.
*
* <p>{@code SEARCH(x, IS_NULL)} is equivalent to {@code x IS NULL}. */
private static final SpecialSarg IS_NULL =
new SpecialSarg(ImmutableRangeSet.of(), RexUnknownAs.TRUE,
"Sarg[IS NULL]", 4);
/** Returns TRUE for all null and not-null values.
*
* <p>{@code SEARCH(x, TRUE)} is equivalent to {@code TRUE}. */
private static final SpecialSarg TRUE =
new SpecialSarg(ImmutableRangeSet.of().complement(), RexUnknownAs.TRUE,
"Sarg[TRUE]", 5);
/** Returns FALSE for all not-null values, UNKNOWN for null.
*
* <p>{@code SEARCH(x, NOT_EQUAL)} is equivalent to {@code x <> x}. */
private static final SpecialSarg NOT_EQUAL =
new SpecialSarg(ImmutableRangeSet.of(), RexUnknownAs.UNKNOWN,
"Sarg[<>]", 6);
/** Returns TRUE for all not-null values, UNKNOWN for null.
*
* <p>{@code SEARCH(x, EQUAL)} is equivalent to {@code x = x}. */
private static final SpecialSarg EQUAL =
new SpecialSarg(ImmutableRangeSet.of().complement(), RexUnknownAs.UNKNOWN,
"Sarg[=]", 7);
private Sarg(ImmutableRangeSet<C> rangeSet, RexUnknownAs nullAs) {
this.rangeSet = requireNonNull(rangeSet, "rangeSet");
this.nullAs = requireNonNull(nullAs, "nullAs");
this.pointCount = RangeSets.countPoints(rangeSet);
}
@Deprecated // to be removed before 2.0
public static <C extends Comparable<C>> Sarg<C> of(boolean containsNull,
RangeSet<C> rangeSet) {
return of(containsNull ? RexUnknownAs.TRUE : RexUnknownAs.UNKNOWN,
rangeSet);
}
/** Creates a search argument. */
public static <C extends Comparable<C>> Sarg<C> of(RexUnknownAs nullAs,
RangeSet<C> rangeSet) {
if (rangeSet.isEmpty()) {
switch (nullAs) {
case FALSE:
return FALSE;
case TRUE:
return IS_NULL;
default:
return NOT_EQUAL;
}
}
if (rangeSet.equals(RangeSets.rangeSetAll())) {
switch (nullAs) {
case FALSE:
return IS_NOT_NULL;
case TRUE:
return TRUE;
default:
return EQUAL;
}
}
return new Sarg<>(ImmutableRangeSet.copyOf(rangeSet), nullAs);
}
/**
* {@inheritDoc}
*
* <p>Produces a similar result to {@link RangeSet},
* but adds "; NULL AS FALSE" or "; NULL AS TRUE" to indicate {@link #nullAs},
* and simplifies point ranges.
*
* <p>For example, the Sarg that allows the range set
*
* <blockquote>{@code [[7..7], [9..9], (10..+���)]}</blockquote>
*
* <p>and also null is printed as
*
* <blockquote>{@code Sarg[7, 9, (10..+���); NULL AS TRUE]}</blockquote>
*/
@Override public String toString() {
final StringBuilder sb = new StringBuilder();
printTo(sb, StringBuilder::append);
return sb.toString();
}
/** Prints this Sarg to a StringBuilder, using the given printer to deal
* with each embedded value. */
public StringBuilder printTo(StringBuilder sb,
BiConsumer<StringBuilder, C> valuePrinter) {
sb.append("Sarg[");
final RangeSets.Consumer<C> printer = RangeSets.printer(sb, valuePrinter);
Ord.forEach(rangeSet.asRanges(), (r, i) -> {
if (i > 0) {
sb.append(", ");
}
RangeSets.forEach(r, printer);
});
switch (nullAs) {
case FALSE:
return sb.append("; NULL AS FALSE]");
case TRUE:
return sb.append("; NULL AS TRUE]");
case UNKNOWN:
return sb.append("]");
default:
throw new AssertionError();
}
}
@Override public int compareTo(Sarg<C> o) {
return RangeSets.compare(rangeSet, o.rangeSet);
}
@Override public int hashCode() {
return RangeSets.hashCode(rangeSet) * 31 + nullAs.ordinal();
}
@Override public boolean equals(@Nullable Object o) {
return o == this
|| o instanceof Sarg
&& nullAs == ((Sarg) o).nullAs
&& rangeSet.equals(((Sarg) o).rangeSet);
}
/** Returns whether this Sarg includes all values (including or not including
* null). */
public boolean isAll() {
return false;
}
/** Returns whether this Sarg includes no values (including or not including
* null). */
public boolean isNone() {
return false;
}
/** Returns whether this Sarg is a collection of 1 or more
* points (and perhaps an {@code IS NULL} if
* {@code nullAs == RexUnknownAs.TRUE}).
*
* <p>Such sargs could be translated as {@code ref = value}
* or {@code ref IN (value1, ...)}. */
public boolean isPoints() {
return pointCount == rangeSet.asRanges().size();
}
/** Returns whether this Sarg, when negated, is a collection of 1 or more
* points (and perhaps an {@code IS NULL} if
* {@code nullAs == RexUnknownAs.TRUE}).
*
* <p>Such sargs could be translated as {@code ref <> value}
* or {@code ref NOT IN (value1, ...)}. */
public boolean isComplementedPoints() {
return rangeSet.span().encloses(Range.all())
&& !rangeSet.equals(RangeSets.rangeSetAll())
&& rangeSet.complement().asRanges().stream()
.allMatch(RangeSets::isPoint);
}
/** Returns a measure of the complexity of this expression.
*
* <p>It is basically the number of values that need to be checked against
* (including NULL).
*
* <p>Examples:
* <ul>
* <li>{@code x = 1}, {@code x <> 1}, {@code x > 1} have complexity 1
* <li>{@code x > 1 or x is null} has complexity 2
* <li>{@code x in (2, 4, 6) or x > 20} has complexity 4
* <li>{@code x between 3 and 8 or x between 10 and 20} has complexity 2
* </ul>
*/
public int complexity() {
int complexity;
if (rangeSet.asRanges().size() == 2
&& rangeSet.complement().asRanges().size() == 1
&& RangeSets.isPoint(
Iterables.getOnlyElement(rangeSet.complement().asRanges()))) {
// The complement of a point is a range set with two elements.
// For example, "x <> 1" is "[(-inf, 1), (1, inf)]".
// We want this to have complexity 1.
complexity = 1;
} else {
complexity = rangeSet.asRanges().size();
}
if (nullAs == RexUnknownAs.TRUE) {
++complexity;
}
return complexity;
}
/** Returns a Sarg that matches a value if and only this Sarg does not. */
public Sarg negate() {
return Sarg.of(nullAs.negate(), rangeSet.complement());
}
/** Sarg whose range is all or none.
*
* <p>There are only 6 instances: {all, none} * {true, false, unknown}.
*
* @param <C> Value type */
private static class SpecialSarg<C extends Comparable<C>> extends Sarg<C> {
final String name;
final int ordinal;
SpecialSarg(ImmutableRangeSet<C> rangeSet, RexUnknownAs nullAs, String name,
int ordinal) {
super(rangeSet, nullAs);
this.name = name;
this.ordinal = ordinal;
assert rangeSet.isEmpty() == ((ordinal & 1) == 0);
assert rangeSet.equals(RangeSets.rangeSetAll()) == ((ordinal & 1) == 1);
}
@Override public boolean equals(@Nullable Object o) {
return this == o;
}
@Override public int hashCode() {
return ordinal;
}
@Override public boolean isAll() {
return (ordinal & 1) == 1;
}
@Override public boolean isNone() {
return (ordinal & 1) == 0;
}
@Override public int complexity() {
switch (ordinal) {
case 2: // Sarg[FALSE]
return 0; // for backwards compatibility
case 5: // Sarg[TRUE]
return 2; // for backwards compatibility
default:
return 1;
}
}
@Override public StringBuilder printTo(StringBuilder sb,
BiConsumer<StringBuilder, C> valuePrinter) {
return sb.append(name);
}
@Override public String toString() {
return name;
}
}
}