LOCK-FREE GENERATION OF COLUMNS WITH MINIMAL DICTIONARIES AFTER PARALLEL AGGREGATION

• US 20150149401A1
• Filed: 06/10/2014
• Published: 05/28/2015
• Est. Priority Date: 11/26/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Stammerjohann, Kai, Kottler, Stephan, Bohnsack, Nico
• Granted Patent: US 9,569,497 B2
• Time in Patent Office: Days
• US Class Current: 707/602
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A new dictionary can be created for a result column in a query plan operation executed on a database. The result column can be generated by multiple worker jobs running in parallel to read tasks from a shared queue as part of a query plan operation that includes a group-by column within an input set of input columns. The group-by column can include an original dictionary for all values contained within the group-by column If the new dictionary has fewer entries than the original dictionary for the group-by column such that mapping is required between old value identifiers within the group-by column and new value identifiers within the result column, the old value identifiers are renamed to the new value identifiers using a mapping vector.

Claims

1. A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

generating a result column, the generating comprising a plurality of worker jobs running in parallel to read tasks from a shared queue as part of a query plan operation, the query plan operation comprising a group-by column within an input set of input columns, the group-by column comprising an original dictionary for all values contained within the group-by column;

creating a new dictionary for the result column, the new dictionary preserving a same ordering as the original dictionary;

determining that the new dictionary has fewer entries than the original dictionary for the group-by column such that mapping is required between old value identifiers within the group-by column and new value identifiers within the result column; and

renaming the old value identifiers to the new value identifiers using a mapping vector.

2. A computer program product as in claim 1, wherein the query plan operation comprises a plurality of group-by columns, the plurality of group-by columns comprising the group-by column, and wherein the operations further comprise creating an additional new dictionary for each result column of the group-by columns in the plurality of group-by columns.

3. A computer program product as in claim 1, wherein the new dictionary contains only values that are used in the result column at least once, and wherein the new dictionary preserves a same ordering as the original dictionary.

4. A computer program product as in claim 1, wherein the operations further comprise:

executing the multiple worker jobs by an online analytical processing engine; and

distributing the result column over a plurality of parts.

5. A computer program product as in claim 1, wherein the generating of the new dictionary comprises the multiple worker jobs indicating use or non-use of entries in the original dictionary.

6. A computer program product as in claim 1, wherein the mapping vector comprises a bitvector that is shared among all of the plurality of worker jobs, and wherein when a worker job of the plurality of worker jobs registers a value identifier, that worker job attempts to set a corresponding bit in the bitvector by an atomic compare and swap operation.

7. A system comprising:

computer hardware configured to perform operations comprising;

generating a result column, the generating comprising a plurality of worker jobs running in parallel to read tasks from a shared queue as part of a query plan operation, the query plan operation comprising a group-by column within an input set of input columns, the group-by column comprising an original dictionary for all values contained within the group-by column;

creating a new dictionary for the result column, the new dictionary preserving a same ordering as the original dictionary;

determining that the new dictionary has fewer entries than the original dictionary for the group-by column such that mapping is required between old value identifiers within the group-by column and new value identifiers within the result column; and

renaming the old value identifiers to the new value identifiers using a mapping vector.

8. A system as in claim 7, wherein the query plan operation comprises a plurality of group-by columns, the plurality of group-by columns comprising the group-by column, and wherein the operations further comprise creating an additional new dictionary for each result column of the group-by columns in the plurality of group-by columns.

9. A system as in claim 7, wherein the new dictionary contains only values that are used in the result column at least once, and wherein the new dictionary preserves a same ordering as the original dictionary.

10. A system as in claim 7, wherein the operations further comprise:

executing the multiple worker jobs by an online analytical processing engine; and

distributing the result column over a plurality of parts.

11. A system as in claim 7, wherein the generating of the new dictionary comprises the multiple worker jobs indicating use or non-use of entries in the original dictionary.

12. A system as in claim 7, wherein the mapping vector comprises a bitvector that is shared among all of the plurality of worker jobs, and wherein when a worker job of the plurality of worker jobs registers a value identifier, that worker job attempts to set a corresponding bit in the bitvector by an atomic compare and swap operation.

13. A system as in claim 7, wherein the computer hardware comprises:

a programmable processor; and

a machine-readable medium storing instructions that, when executed by the programmable processor, cause the programmable processor to perform at least some of the operations.

14. A computer-implemented method comprising:

generating a result column, the generating comprising a plurality of worker jobs running in parallel to read tasks from a shared queue as part of a query plan operation, the query plan operation comprising a group-by column within an input set of input columns, the group-by column comprising an original dictionary for all values contained within the group-by column;

creating a new dictionary for the result column, the new dictionary preserving a same ordering as the original dictionary;

determining that the new dictionary has fewer entries than the original dictionary for the group-by column such that mapping is required between old value identifiers within the group-by column and new value identifiers within the result column; and

renaming the old value identifiers to the new value identifiers using a mapping vector.

15. A computer-implemented method as in claim 14, wherein the query plan operation comprises a plurality of group-by columns, the plurality of group-by columns comprising the group-by column, and wherein the operations further comprise creating an additional new dictionary for each result column of the group-by columns in the plurality of group-by columns.

16. A computer-implemented method as in claim 14, wherein the new dictionary contains only values that are used in the result column at least once, and wherein the new dictionary preserves a same ordering as the original dictionary.

17. A computer-implemented method as in claim 14, further comprising:

executing the multiple worker jobs by an online analytical processing engine; and

distributing the result column over a plurality of parts.

18. A computer-implemented method as in claim 14, wherein the generating of the new dictionary comprises the multiple worker jobs indicating use or non-use of entries in the original dictionary.

19. A computer-implemented method as in claim 14, wherein the mapping vector comprises a bitvector that is shared among all of the plurality of worker jobs, and wherein when a worker job of the plurality of worker jobs registers a value identifier, that worker job attempts to set a corresponding bit in the bitvector by an atomic compare and swap operation.

20. A computer-implemented method as in claim 14, wherein at least one of the generating, the creating, the determining, and the renaming are performed by computer hardware.