Join Order Optimization Using Setsketch

A computer-implemented method for joining tables in a database system, comprising:

• a) receiving, by a computer processor, a request to join three or more tables according to a join query, where the join query specifies a set of join operations and each join operation joins two tables with each other;
• b) generating, by the computer processor, a probabilistic data structure for each table specified in the set of join operations, where the probabilistic data structure is partitioned into a plurality of registers and configuration parameters for the probabilistic data structure includes a first recording parameter, base, that controls recording of data into the probabilistic data structure;
• c) for each join operation in the set of join operations, calculating, by the computer processor, a cardinality estimate of table resulting from a particular join operation using the probabilistic data structures for the tables to be joined;
• d) selecting, by the computer processor, a join operation in the set of join operations, where the selected join operation has the lowest cardinality estimate amongst the join operations in the set of join operations;
• e) performing, by the computer processor, the selected join operation to form a new table and generating a probabilistic data structure for the new table;
• f) removing, by the computer processor, the selected join operation from the set of join operations;
• g) replacing, by the computer processor, the tables to be joined with the new table in the set of join operations;
• h) repeating, by the computer processor, steps c) to g) until the set of join operations comprises a single join operation, thereby joining tables in the join query.

A computer-implemented method for joining tables in a database system, comprising:

• a) receiving, by a computer processor, a request to join three or more tables according to a join query, where the join query specifies a set of join operations and each join operation joins two tables with each other;
• b) generating, by the computer processor, a SetSketch data structure for each table specified in the set of join operations;
• c) for each join operation in the set of join operations, calculating, by the computer processor, a cardinality estimate of table resulting from a particular join operation using the SetSketch data structures for the tables to be joined;
• d) selecting, by the computer processor, a join operation in the set of join operations, where the selected join operation has the lowest cardinality estimate amongst the join operations in the set of join operations;
• e) removing, by the computer processor, the selected join operation from the set of join operations;
• f) replacing, by the computer processor, the tables to be joined by the selected join operation with the joint of these tables in the set of join operations;
• and
• g) repeating, by the computer processor, steps c) to f) until the set of join operations comprises a single join operation, thereby defining an order for joining tables in the join query.