Cache conscious techniques for generation of quasi-dense grouping codes of compressed columnar data in relational database systems
Herein are techniques for dynamic aggregation of results of a database request, including concurrent grouping of result items in memory based on quasi-dense keys. Each of many computational threads concurrently performs as follows. A hash code is calculated that represents a particular natural grouping key (NGK) for an aggregate result of a database request. Based on the hash code, the thread detects that a set of distinct NGKs that are already stored in the aggregate result does not contain the particular NGK. A distinct dense grouping key for the particular NGK is statefully generated. The dense grouping key is bound to the particular NGK. Based on said binding, the particular NGK is added to the set of distinct NGKs in the aggregate result.
1. A method comprising:
calculating a hash code that represents a particular key value for an aggregation needed for a database request, wherein the hash code contains a first index bit field, a second index bit field, a first key bit field that contains the second index bit field, and a second key bit field;
selecting, based on the first index bit field in the hash code, a first particular bucket in a first hash table in a multilevel hash table that further contains a second hash table;
detecting that the first particular bucket in the first hash table in the multilevel hash table does not have capacity to store the first key bit field that contains the second index bit field;
selecting, based on the second index bit field in the hash code and the first particular bucket in the first hash table in the multilevel hash table, a second particular bucket in the second hash table in the multilevel hash table;
generating a result for the database request based on the second index bit field in the hash code and the second particular bucket in the second hash table in the multilevel hash table.
2. The method of claim 1 wherein the first key bit field contains more bits than the second key bit field.
3. The method of claim 1 wherein:
the first particular bucket and the second particular bucket have a same width;
the first particular bucket and the second particular bucket have different respective internal formats.
4. The method of claim 3 wherein said different respective internal formats comprises the first particular bucket can store fewer than the second particular bucket of at least one selected from a group consisting of: key prefixes, offset values, and pointer suffixes.
5. The method of claim 3 wherein said different respective internal formats comprises the first particular bucket contains larger than the second particular bucket of at least one selected from a group consisting of: key prefixes, and a pointer base.
6. The method of claim 3 wherein:
a third particular bucket in a third hash table in the multilevel hash table has a same width and internal format as the second particular bucket;
the first hash table, the second hash table, and the third hash table are in different respective levels of the multilevel hash table.
7. The method of claim 1 wherein:
adding a new hash table to the multilevel hash table never causes the first hash table to change levels in the multilevel hash table;
said adding said new hash table to the multilevel hash table never causes the second hash table to change levels in the multilevel hash table.
8. The method of claim 1 wherein:
the first particular bucket contains only one hash table pointer;
said only one hash table pointer points to the second hash table;
the second particular bucket contains at most one hash table pointer.
9. The method of claim 8 wherein said only one hash table pointer that points to the second hash table cannot be reassigned.
10. The method of claim 1 wherein the multilevel hash table cannot rebalance.
11. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
calculating a hash code that represents a particular key value for an aggregation needed for a database request, wherein the hash code contains a first index bit field, a second index bit field, a first key bit field that contains the second index bit field, and a second key bit field;
selecting, based on the first index bit field in the hash code, a first particular bucket in a first hash table in a multilevel hash table that further contains a second hash table;
detecting that the first particular bucket in the first hash table in the multilevel hash table does not have capacity to store the first key bit field that contains the second index bit field;
selecting, based on the second index bit field in the hash code and the first particular bucket in the first hash table in the multilevel hash table, a second particular bucket in the second hash table in the multilevel hash table;
generating a result for the database request based on the second index bit field in the hash code and the second particular bucket in the second hash table in the multilevel hash table.
12. The one or more non-transitory computer-readable media of claim 11 wherein the first key bit field contains more bits than the second key bit field.
13. The one or more non-transitory computer-readable media of claim 11 wherein:
the first particular bucket and the second particular bucket have a same width;
the first particular bucket and the second particular bucket have different respective internal formats.
14. The one or more non-transitory computer-readable media of claim 13 wherein said different respective internal formats comprises the first particular bucket can store fewer than the second particular bucket of at least one selected from a group consisting of: key prefixes, offset values, and pointer suffixes.
15. The one or more non-transitory computer-readable media of claim 13 wherein said different respective internal formats comprises the first particular bucket contains larger than the second particular bucket of at least one selected from a group consisting of: key prefixes, and a pointer base.
16. The one or more non-transitory computer-readable media of claim 13 wherein:
a third particular bucket in a third hash table in the multilevel hash table has a same width and internal format as the second particular bucket;
the first hash table, the second hash table, and the third hash table are in different respective levels of the multilevel hash table.
17. The one or more non-transitory computer-readable media of claim 11 wherein:
adding a new hash table to the multilevel hash table never causes the first hash table to change levels in the multilevel hash table;
said adding said new hash table to the multilevel hash table never causes the second hash table to change levels in the multilevel hash table.
18. The one or more non-transitory computer-readable media of claim 11 wherein:
the first particular bucket contains only one hash table pointer;
said only one hash table pointer points to the second hash table;
the second particular bucket contains at most one hash table pointer.
19. The one or more non-transitory computer-readable media of claim 18 wherein said only one hash table pointer that points to the second hash table cannot be reassigned.
20. The one or more non-transitory computer-readable media of claim 11 wherein the multilevel hash table cannot rebalance.