Interdistinct Operator

• US 20120011133A1
• Filed: 12/30/2010
• Published: 01/12/2012
• Est. Priority Date: 07/12/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Faerber, Franz, Bensberg, Christian, Fricke, Lars
• Granted Patent: US 9,223,829 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

A computer-implemented system and method for performing distinct operations on multiple tables of shared memory of parallel computing environments are disclosed. A distinct operation is executed on each table of a plurality of tables, each distinct operation eliminating duplicate data from each table, the executing creating a hierarchy of table pairs and distinct results, the distinct results comprising a reduced row set for each table. Duplicates on each reduced row set are detected to complete the distinct operation on the plurality of tables.

Claims

1. A computer-implemented method comprising:

executing a distinct operation on each table of a plurality of tables, each distinct operation eliminating duplicate data from each table, the executing creating a hierarchy of table pairs and distinct results, the distinct results comprising a reduced row set for each table; and

detecting duplicates on each reduced row set to complete the distinct operation on the plurality of tables,

the executing and detecting being performed by one or more processors.

2. The computer-implemented method in accordance with claim 1, further comprising executing, by the one or more processors and for each table pair in the hierarchy of table pairs:

removing values that exist in one or the other table to generate a reduced value set;

generating new dictionaries for each column in the table pair with the reduced value set;

defining a candidate row set from the reduced value;

generating a hash table of the candidate row set based on the new dictionaries as hash values; and

reducing the candidate row set by filtering bit vectors of the hash table to generate the reduced row set.

3. The computer-implemented method in accordance with claim 2, wherein reducing the candidate row set includes filtering with the new dictionaries.

4. The computer-implemented method in accordance with claim 2, wherein the reduced value set comprises a reduced set of attributes with high discrimination value and low dependency between tables of the table pair.

5. The computer-implemented method in accordance with claim 4, wherein the reduced set of attributes are hashed into a collision-free hash table.

6. 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:

execute a distinct operation on each table of a plurality of tables, each distinct operation eliminating duplicate data from each table, the executing creating a hierarchy of table pairs and distinct results, the distinct results comprising a reduced row set for each table;

detect duplicates on each reduced row set to complete the distinct operation on the plurality of tables.

7. The computer program product in accordance with claim 6, wherein the instructions further comprise, for each table pair in the hierarchy of table pairs, operations to:

remove values that exist in one or the other table to generate a reduced value set;

generate new dictionaries for each column in the table pair with the reduced value set;

define a candidate row set from the reduced value;

generate a hash table of the candidate row set based on the new dictionaries as hash values; and

reduce the candidate row set by filtering bit vectors of the hash table to generate the reduced row set.

8. The computer program product in accordance with claim 7, wherein the operation to reduce the candidate row set includes on operation to filter with the new dictionaries.

9. The computer program product in accordance with claim 7, wherein the reduced value set comprises a reduced set of attributes with high discrimination value and low dependency between tables of the table pair.

10. The computer program product in accordance with claim 9, wherein the reduced set of attributes are hashed into a collision-free hash table.

11. A system comprising:

at least one programmable processor; and

a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations comprising;

executing a distinct operation on each table of a plurality of tables, each distinct operation eliminating duplicate data from each table, the executing creating a hierarchy of table pairs and distinct results, the distinct results comprising a reduced row set for each table; and

detecting duplicates on each reduced row set to complete the distinct operation on the plurality of tables.

12. The system in accordance with claim 11, wherein the operations further comprise, for each table pair in the hierarchy of table pairs:

removing values that exist in one or the other table to generate a reduced value set;

generating new dictionaries for each column in the table pair with the reduced value set;

defining a candidate row set from the reduced value;

generating a hash table of the candidate row set based on the new dictionaries as hash values; and

reducing the candidate row set by filtering bit vectors of the hash table to generate the reduced row set.

13. The system in accordance with claim 12, wherein reducing the candidate row set includes filtering with the new dictionaries.

14. The system in accordance with claim 12, wherein the reduced value set comprises a reduced set of attributes with high discrimination value and low dependency between tables of the table pair.

15. The system in accordance with claim 14, wherein the reduced set of attributes are hashed into a collision-free hash table.