Package io.deephaven.engine.table.impl.sources.regioned.kernel

Class BinarySearchKernelHelper

java.lang.Object

io.deephaven.engine.table.impl.sources.regioned.kernel.BinarySearchKernelHelper

public class BinarySearchKernelHelper
extends Object

Helper methods for binary search kernels.

Method Summary

Modifier and Type	Method	Description
static boolean	compareConsistentWithEquality(@NotNull Class<?> dataType)	Whether dataType compares consistently with equality, meaning ObjectComparisons.compare(a, b) == 0 exactly when ObjectComparisons.eq(a, b), for every pair of values.
static void	registerConsistentType(@NotNull Class<?> dataType)	Registers dataType as ordering consistently with equality, letting a sorted binary search answer a match over a column of that type by ordering alone.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

registerConsistentType

public static void registerConsistentType(@NotNull
 @NotNull Class<?> dataType)

Registers dataType as ordering consistently with equality, letting a sorted binary search answer a match over a column of that type by ordering alone. See compareConsistentWithEquality(Class) for what that decides.

The property is not verified; registering a type that lacks it will produce incorrect filter, as-of join, range join, sorted first or last, minimum, maximum, median, percentile, count distinct, distinct and unique results.

Registration is additive and idempotent, and a type cannot be withdrawn. Register types during startup: a search already under way keeps the set it started with.

Parameters:

dataType - the column data type to register

Throws:

IllegalArgumentException - if dataType is not Comparable, since ObjectComparisons.compare(Object, Object) could not order it at all

compareConsistentWithEquality

public static boolean compareConsistentWithEquality(@NotNull
 @NotNull Class<?> dataType)

Whether dataType compares consistently with equality, meaning ObjectComparisons.compare(a, b) == 0 exactly when ObjectComparisons.eq(a, b), for every pair of values.

This decides how a sorted binary search may answer a match. The search navigates by ObjectComparisons.compare(Object, Object), which is Comparable.compareTo(Object), while a match is decided by ObjectComparisons.eq(Object, Object), which is Objects.equals(Object, Object) -- the same relation the chunk filter uses. When the two agree, the ordering-equal run the search locates is exactly the set of matching rows and the search can answer the match outright. When they disagree -- BigDecimal at differing scales, for one -- that run is only a superset, and the matches have to be picked out of it by equality. Sorted pushdown therefore matches a column of a type for which this holds with ObjectRegionBinarySearchKernel.binarySearchMatchWithConsistentEquality(io.deephaven.engine.table.impl.sources.regioned.ColumnRegionObject<?, ?>, long, long, io.deephaven.api.SortColumn, java.lang.Object[]) or ObjectColumnBinarySearchKernel.binarySearchMatchWithConsistentEquality(io.deephaven.engine.table.ElementSource<?>, io.deephaven.engine.rowset.RowSet, io.deephaven.api.SortColumn, java.lang.Object[], boolean), and a column of any other type with ObjectRegionBinarySearchKernel.binarySearchMatchWithGeneralEquality(io.deephaven.engine.table.impl.sources.regioned.ColumnRegionObject<?, ?>, long, long, io.deephaven.api.SortColumn, java.lang.Object[]) or ObjectColumnBinarySearchKernel.binarySearchMatchWithGeneralEquality(io.deephaven.engine.table.ColumnSource<?>, io.deephaven.engine.rowset.RowSet, io.deephaven.api.SortColumn, java.lang.Object[], boolean). BigDecimal is the exception: its match filter matches by BigDecimal.compareTo(java.math.BigDecimal), as the query language's == does, so sorted pushdown matches it by ordering alone too, checking for it by type before consulting this method.

Only this stronger both-ways guarantee is checked, and only where documented, since BigDecimal is a common counterexample. A false answer still assumes the weaker eq(a, b) implies compare(a, b) == 0, which Comparable recommends and without which a type is unusable in any sorted context. An enum qualifies because its ordering is by ordinal and its equality is identity.

The same answer selects between the EqualsConsistentObject and Object segmented sorted array, SSA stamp, duplicate compaction, compaction, segmented sorted multiset, and compact modifications classes, which test equality with equals and with ObjectComparisons.compareEquals(Object, Object) respectively.

The engine's own types are answered here; a type it does not know is answered false until registerConsistentType(Class) says otherwise, so an unrecognized type costs speed rather than correctness.

Parameters:

dataType - the column's data type

Returns:

true if a search by ordering alone decides a match for this type