[
https://issues.apache.org/jira/browse/HIVE-30107?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Denys Kuzmenko updated HIVE-30107:
----------------------------------
Description:
A vectorized hash GROUP BY on a single STRING, CHAR, VARCHAR or BINARY key
takes the general key path: a VectorHashKeyWrapperGeneral per row, and a
java.util.HashMap from the wrapper to the
group's aggregation buffers, comparing key bytes through the wrapper. Master
specializes the key wrappers only for one and two LONG keys (see HIVE-30120).
*Fix*
* VectorGroupByBytesKeyTable maps a single bytes key to its group with open
addressing and linear probing, over a power-of-two slot array that is at most
half full. Entries are numbered in
insertion order.
* An entry keeps the first 16 key bytes as two little-endian words next to
the key's hash and length. A probe therefore decides the equality of keys up to
16 bytes long from one record,
which measured 1.5-1.7x faster than comparing the bytes on 412 short keys.
Longer keys also compare the remaining bytes.
* The key bytes are copied once, when the entry is added. The NULL key has an
entry outside the slot array.
* The operator looks up all keys of a batch first and then maps the rows to
their entries, up to 18% faster than one loop.
* The memory of the table is estimated from its arrays and key bytes, so the
per-entry estimate covers only the aggregation buffers.
* A partial flush visits the entries oldest first, emits those accessed at
most as often as the average and removes them. Removed entries are compacted
once they outnumber the others or fill
the table's free room.
*Measured* (the 1TRC part 1 query shape: one string key with 412 values; min,
max and avg of a decimal(5,2))
* Local (VectorGroupByBytesKeyBench): 412 keys 48.4 -> 13.3 ns/row (3.6x); 5M
keys 474 -> 247 ns/row.
* Cluster (1TRC part 1, 64 x r5d, together with unrelated delete-path
changes): 377.9 -> 158.1 s.
was:
A vectorized hash GROUP BY on a single STRING, CHAR, VARCHAR or BINARY key
takes the general key path: a VectorHashKeyWrapperGeneral per row, and a
java.util.HashMap from the wrapper to the
group's aggregation buffers, comparing key bytes through the wrapper. Master
specializes the key wrappers only for one and two LONG keys (see HIVE-30120).
*Fix*
* VectorGroupByBytesKeyTable maps a single bytes key to its group with open
addressing and linear probing, over a power-of-two slot array that is at most
half full. Entries are numbered in
insertion order.
* An entry keeps the first 16 key bytes as two little-endian words next to
the key's hash and length. A probe therefore decides the equality of keys up to
16 bytes long from one record,
which measured 1.5-1.7x faster than comparing the bytes on 412 short keys.
Longer keys also compare the remaining bytes.
* The key bytes are copied once, when the entry is added. The NULL key has an
entry outside the slot array.
* The operator looks up all keys of a batch first and then maps the rows to
their entries, up to 18% faster than one loop.
* The memory of the table is estimated from its arrays and key bytes, so the
per-entry estimate covers only the aggregation buffers.
* A partial flush visits the entries oldest first, emits those accessed at
most as often as the average and removes them. Removed entries are compacted
once they outnumber the others or fill
the table's free room.
*Measured* (the 1TRC part 1 query shape: one string key with 412 values; min,
max and avg of a decimal(5,2))
* Local (VectorGroupByBytesKeyBench): 412 keys 48.4 -> 13.3 ns/row (3.6x); 5M
keys 474 -> 247 ns/row.
* Cluster (1TRC part 1, 64 x r5d, together with unrelated delete-path
changes): 377.9 -> 158.1 s.
> Look up a single string key in an open-addressing hash table
> ------------------------------------------------------------
>
> Key: HIVE-30107
> URL: https://issues.apache.org/jira/browse/HIVE-30107
> Project: Hive
> Issue Type: Sub-task
> Reporter: Denys Kuzmenko
> Priority: Major
> Labels: performance
>
> A vectorized hash GROUP BY on a single STRING, CHAR, VARCHAR or BINARY key
> takes the general key path: a VectorHashKeyWrapperGeneral per row, and a
> java.util.HashMap from the wrapper to the
> group's aggregation buffers, comparing key bytes through the wrapper.
> Master specializes the key wrappers only for one and two LONG keys (see
> HIVE-30120).
>
>
>
> *Fix*
>
>
> * VectorGroupByBytesKeyTable maps a single bytes key to its group with open
> addressing and linear probing, over a power-of-two slot array that is at most
> half full. Entries are numbered in
> insertion order.
>
>
> * An entry keeps the first 16 key bytes as two little-endian words next to
> the key's hash and length. A probe therefore decides the equality of keys up
> to 16 bytes long from one record,
> which measured 1.5-1.7x faster than comparing the bytes on 412 short keys.
> Longer keys also compare the remaining bytes.
>
> * The key bytes are copied once, when the entry is added. The NULL key has
> an entry outside the slot array.
>
> * The operator looks up all keys of a batch first and then maps the rows to
> their entries, up to 18% faster than one loop.
>
> * The memory of the table is estimated from its arrays and key bytes, so
> the per-entry estimate covers only the aggregation buffers.
>
> * A partial flush visits the entries oldest first, emits those accessed at
> most as often as the average and removes them. Removed entries are compacted
> once they outnumber the others or fill
> the table's free room.
>
>
>
>
>
> *Measured* (the 1TRC part 1 query shape: one string key with 412 values;
> min, max and avg of a decimal(5,2))
>
> * Local (VectorGroupByBytesKeyBench): 412 keys 48.4 -> 13.3 ns/row (3.6x);
> 5M keys 474 -> 247 ns/row.
>
> * Cluster (1TRC part 1, 64 x r5d, together with unrelated delete-path
> changes): 377.9 -> 158.1 s.
>
>
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
