[C++] Implement hashing, dictionary-encoding for StructArray

[asfimport]

This is a central requirement for hash-aggregations such as

SELECT AGG_FUNCTION(expr)
FROM table
GROUP BY expr1, expr2, ...

The materialized keys in the GROUP BY section form a struct, which can be incrementally hashed to produce dictionary codes suitable for computing aggregates or any other purpose.

There are a few subtasks related to this, such as efficiently constructing a record (that can be hashed quickly) to identify each "row" in the struct. Maybe we should start with that first

Reporter: Wes McKinney / @wesm

Related issues:

• [C++][Compute] Add scalar_hash function (is a parent of)
• [C++] C++ array kernels framework and execution buildout (umbrella issue) (is a child of)

_{Note: This issue was originally created as ARROW-3978. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou: To implement this efficiently, we would need to split the computation of hash values (for an array or morsel) from their use in hashing kernels. It is probably possible to hash struct values efficiently, simply by first hashing the underlying child arrays, then by combining the results.

[asfimport]

Wes McKinney / @wesm: There's different approaches. You might want to look at what an existing columnar database engine like Clickhouse or Dremio is doing for hashing tuples (aka structs). One approach is to "pivot" or "recordize" the data from columnar to record format (similar to NumPy's struct dtype memory layout, but it would need to be generalized of course to account for varbinary, nulls, and nested data – nested data would have to be recursively flattened).

NB the same code paths involved with hashing structs will need to be used for hash joins, hash aggregations, and other algorithms.

@jacques-n do you have any advice for us or pointers to literature about this topic?

[asfimport]

Jacques Nadeau / @jacques-n: Here is some info about what we found worked well. Note that it doesn't go into a lot of detail about the pivot algorithm beyond the basic concepts of fixed and variable vectors.

https://docs.google.com/document/d/1Yk6IvDL28IzEjqcqSkFdevRyMrC8_kwzEatHvcOnawM/edit

 

Main idea around pivot: 

• separate fixed and variable and have each continguous
• coalesce bits for nullability and values together at the start of the data structure (save space, increase likelihood of mismatch early)
• include length of variable in fixed container to reduce likelihood of jumping to variable container.

• Have specialized cases that look at actual existence of nulls for each word and fork behavior based on that to improve performance of common case where things are mostly null or not null.

  The latest code for the Arrow pivot algorithms specifically that we use can be found here:

  Pivots: https://github.com/dremio/dremio-oss/blob/master/sabot/kernel/src/main/java/com/dremio/sabot/op/common/ht2/Pivots.java

  Unpivots: https://github.com/dremio/dremio-oss/blob/master/sabot/kernel/src/main/java/com/dremio/sabot/op/common/ht2/Unpivots.java

  Hash Table: https://github.com/dremio/dremio-oss/blob/master/sabot/kernel/src/main/java/com/dremio/sabot/op/common/ht2/LBlockHashTable.java

  We'd be happy to donate this code/algo to the community as it would probably serve as a good foundation.

   

  Note the doc is probably somewhat out of date with the actual implementation as it was written early on in development.

   

[asfimport]

Francois Saint-Jacques / @fsaintjacques: ClickHouse also uses the pivot method, see

• https://github.com/yandex/ClickHouse/blob/d4f474cd196c1b7dff65f8507e87b380f64e2b53/dbms/src/Common/ColumnsHashing.h#L513-L540
• https://github.com/yandex/ClickHouse/blob/d4f474cd196c1b7dff65f8507e87b380f64e2b53/dbms/src/Interpreters/AggregationCommon.h#L231-L243
• https://github.com/yandex/ClickHouse/blob/d4f474cd196c1b7dff65f8507e87b380f64e2b53/dbms/src/Columns/ColumnVector.cpp#L32-L45

[asfimport]

Wes McKinney / @wesm: Moving out of 0.14.0, but don't let that stop anyone from working on this

[asfimport]

Wes McKinney / @wesm: @bkietz @michalursa seems like this could be supported pretty soon using the new hash table machinery?

[asfimport]

Michal Nowakiewicz / @michalursa: It sounds like this is already implemented as part of hash group by, but we should probably add a documentation about how it works exactly. Also, currently only 32-bit hash is implemented, but we need to add 64-bit hashing as well. 

[asfimport]

Antoine Pitrou / @pitrou: What do you mean with "32-bit hash"?

[asfimport]

Ben Kietzman / @bkietz:

seems like this could be supported pretty soon using the new hash table machinery?

Correct, and I'd say we should try replacing everything in vector_hash.cc with usage of Grouper then compare benchmarks. I think we'd probably get a performance win for dictionary encoding primitives as well as support for dictionary encoding structs

[asfimport]

Aldrin Montana / @drin: I am picking up ARROW-8991 today. @bkietz @pitrou , I assume that this issue is mostly using new mechanisms and then "exposing an interface". I need to build up my understanding, but the "exposing an interface" portion may be addressed by ARROW-8991.

I just wanted to ping here and double check that it makes sense to take this while I work on ARROW-8991. I also wanted to check if there's anything in particular I should look at that hasn't already been mentioned in previous comments.

[asfimport]

Aldrin Montana / @drin: I just wanted to note here that I am trying to handle nested types for ARROW-8991. I realize now that StructArray would be included in that umbrella, so when ARROW-8991 is complete, this would be partially completed.

I don't know the dictionary-encoding infrastructure, but if I get around to that half then I'll pick up this issue.