Comparisons for values of logical types are not handled correctly throughout the library

mbasmanova commented 3 months ago

Bug description

TIMESTAMP WITH TIME ZONE logical type is backed by BIGINT physical type. The timestamp values are stored in memory as 64-bit integers using an encoding that doesn't allow for direct comparisons of these integers.

https://facebookincubator.github.io/velox/develop/timestamp.html

TimestampWithTimezone physically packs two integers in a single 64 word, using 12 bits for timezone ID, and 52 bits for a millisecond-precision timestamp.

However, many places in the core engine are applying equality and comparisons to the physical value without considering its logical semantics.

One example, is aggregation with grouping keys of type TIMESTAMP WITH TIME ZONE returns incorrect result. '2024-04-10 10:00 America/New_York' and '2024-04-10 07:00 America/Los_Angeles' represent the same timestamp, but appear as different groups in aggregation results:

  auto data = makeRowVector({
      makeFlatVector<std::string>({
          "2024-04-10 10:00 America/New_York",
          "2024-04-10 07:00 America/Los_Angeles",
      }),
  });

  auto plan = PlanBuilder()
                  .values({data})
                  .project({"cast(c0 as timestamp with time zone)"})
                  .singleAggregation({"p0"}, {"count(1)"})
                  .project({"cast(p0 as varchar)", "a0"})
                  .planNode();

  auto results = AssertQueryBuilder(plan).copyResults(pool());
  LOG(ERROR) << results->toString();
  LOG(ERROR) << results->toString(0, 10);

[ROW ROW<p0:VARCHAR,a0:BIGINT>: 2 elements, no nulls]

0: {2024-04-10 10:00:00.000 America/New_York, 1}
1: {2024-04-10 07:00:00.000 America/Los_Angeles, 1}

In Presto,

presto:di> select cast(x as timestamp with time zone), count(1) from unnest(array['2024-04-10 07:00 America/Los_Angeles', '2024-04-10 10:00 America/New_York']) as t(x) group by 1;
                    _col0                    | _col1
---------------------------------------------+-------
 2024-04-10 07:00:00.000 America/Los_Angeles |     2
(1 row)

presto:di> select x, count(1) from unnest(array['2024-04-10 07:00 America/Los_Angeles', '2024-04-10 10:00 America/New_York']) as t(x) group by 1;
                  x                   | _col1
--------------------------------------+-------
 2024-04-10 07:00 America/Los_Angeles |     1
 2024-04-10 10:00 America/New_York    |     1
(2 rows)

All operators that perform comparisons are affected by this issue, e.g. Aggregation, Join, OrderBy.

CC: @kgpai @Yuhta @bikramSingh91 @kagamiori @amitkdutta

System information

n/a

Relevant logs

No response

mbasmanova commented 3 months ago

CC: @wypb

mbasmanova commented 3 months ago

CC: @pedroerp

Yuhta commented 3 months ago

We will probably need a virtual function on logical type to do the comparison. The hard part is how do we avoid calling that virtual function for common logical types to avoid performance regression.

pedroerp commented 3 months ago

Good catch. I suppose we need to provide a plugable API for user to specify equality and comparison functions for custom logical types, sort of like how this is done in C++ (operator==, ...).

Is there anything else that should be expose? I guess at least equality and some form of comparison for sorting?

How does Presto Java does it? Or they just have all types hard coded throughout the codebase?

mbasmanova commented 3 months ago

How does Presto Java does it?

Presto defines a set of operators (add, subtract, etc.) and each type is expected to provide an implementation for a subset of these that are supported.

See

pedroerp commented 3 months ago

I see. That would probably mean each row comparison would incur in a virtual function call? Would be nice if we could come up with a batch/vector oriented API to amortize the cost.

Yuhta commented 3 months ago

I see annotations in Java code so probably some codegen magic is happening. The equivalent in Velox would be template magic.

oerling commented 2 months ago

Specifying Comparison of Extended Types

Extended types, like timestampp with timezone must have special comparison and hashing for hash tables and special comparison in expressions.

This can be implemented by adding virtual functions to Type. These are not defined if type->isExtendedType() is false and are defined otherwise.

The signatures are:

int32_t compare(const BaseVector& left, vector_size_t leftIndex, const BaseVector& right, vector_size_t rightIndex) const;

int32_t compare(const DecodedVector& left, vector_size_t index, void* right) const;

The first compares single elements of vectors. The second compares a DecodedVector to a slot in a RowContainer.

The return value is < 0 for lt, 0 for equals and > 0 for gt.

uint64_t hash(const BaseVector& vector, vector_size_t index) const;

The call sites are

VectorHasher: An extended type forces use of kHash. So only the hash, not the value id methods know about extended types.
Vectors

BBaseVector::equalValueAt and compare need to call the Type virtual function in the case of the vector being of an extended tyope. The type's extendedness should be cached in BaseVector to similarly to the kind, so that the type does not have to be accessed.

HashTable and RowContainer:

HashTable in kHash mode switches on the TypeKind. While there is no TypeKind for extended type, this switch can switch on an extended TypeKind enum that has a value for extended type that goes to Type::compare. This enum (int) is internal to HashTable.

The same logic occurs in spilling, which compares vectors with BaseVector::compare.

OrderBy

This will probably work just by BaseVector supporting the types.

Functions

The vector functions for comparison need a case for extended types. Type could have a vectorized comparison, e.g. compareMultiple(const DecodedVector& left, const DecodedVector& right, const SelectivityVector& rrows, int32_t* result). This is only needed if performance is an issue.

facebookincubator / velox