System and method for disjunctive joins using a lookup table
Joining data using a disjunctive operator using a lookup table is described. An example computer-implemented method can include receiving a query with a set of conjunctive predicates and a set of disjunctive predicates. The method may also include generating a lookup table for each predicate in the sets of conjunctive predicates and disjunctive predicates. The method, for each row in a probe-side table, may also further include looking up a value associated with that row in each of the lookup tables and adding the row to a results set when there is a match. Additionally, the method may also include returning the results set.
1. A method, comprising:
receiving a query comprising a set of predicates;
for each predicate of the set of predicates, generating, with a processor, a lookup table by filtering a probe-side table using a range bloom filter based on a corresponding build-side table and adding surviving rows to the lookup table, wherein each lookup table maps a value associated with a conjunctive predicate column or a disjunctive predicate column to a set of references that reference rows associated with the build-side table;
for each row in the probe-side table:
identifying a matching row in each of the lookup tables; and
adding the row to a result set using a priority data queue for disjunctive results, wherein:
the row satisfies a conjunctive predicate of the set of predicates; or
the row satisfies a disjunctive predicate of the set of predicates; and
returning the result set.
2. The method of claim 1 , wherein each lookup table comprises a hash table.
3. The method of claim 1 , wherein the lookup tables share a copy of the build-side table.
4. The method of claim 1 , wherein the filtering further includes using at least a bloom filter.
5. The method of claim 1 , further comprising deduplicating the result set.
6. The method of claim 1 , wherein the query includes a join operator for each set of disjunctive predicates.
7. The method of claim 1 , further comprising scanning the probe-side table with a condition.
8. The method of claim 1 , further comprising scanning the build-side table with a condition.
9. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a computing device, cause the one or more processors to:
receive a query comprising a set of predicates;
for each predicate of the set of predicates, generate, with a processor, a lookup table by filtering a probe-side table using a range bloom filter based on a corresponding build-side table and adding surviving rows to the lookup table, wherein each lookup table maps a value associated with a conjunctive predicate column or a disjunctive predicate column to a set of references that reference rows associated with the build-side table;
for each row in the probe-side table:
identify a matching row in each of the lookup tables; and
add the row to a result set using a priority data queue for disjunctive results, wherein:
the row satisfies a conjunctive predicate of the set of predicates; or
the row satisfies a disjunctive predicate of the set of predicates; and
return the result set.
10. The non-transitory machine-readable medium of claim 9 , wherein each lookup table comprises a hash table.
11. The non-transitory machine-readable medium of claim 9 , wherein the lookup tables share a copy of the build-side table.
12. The non-transitory machine-readable medium of claim 9 , wherein the filtering further includes using at least a bloom filter.
13. The non-transitory machine-readable medium of claim 9 , further comprising deduplicating the result set.
14. The non-transitory machine-readable medium of claim 9 , wherein the query includes a join operator for each set of disjunctive predicates.
15. The non-transitory machine-readable medium of claim 9 , further comprising scanning the probe-side table with a condition.
16. The non-transitory machine-readable medium of claim 9 , further comprising scanning the build-side table with a condition.
17. A system comprising:
a set of storage resources; and
a query processor to,
receive a query comprising a set of predicates;
for each predicate of the set of predicates, generate, with a processor, a lookup table by filtering a probe-side table using a range bloom filter based on a corresponding build-side table and adding surviving rows to the lookup table, wherein each lookup table maps a value associated with a conjunctive predicate column or a disjunctive predicate column to a set of references that reference rows associated with the build-side table;
for each row in the probe-side table:
identify a matching row in each of the lookup tables; and
add the row to a result set using a priority data queue for disjunctive results, wherein:
the row satisfies a conjunctive predicate of the set of predicates; or
the row satisfies a disjunctive predicate of the set of predicates; and
return the result set.
18. The system of claim 17 , wherein each lookup table comprises a hash table.
19. The system of claim 17 , wherein the lookup tables share a copy of the build-side table.
20. The system of claim 17 , wherein the filtering further includes using a bloom filter.
21. The system of claim 17 , wherein the query processor is further to deduplicate the result set.
22. The system of claim 17 , wherein the query includes a join operator for each set of disjunctive predicates.
23. The system of claim 17 , wherein the query processor is further to scan the probe-side table with a condition.
24. The system of claim 17 , wherein the query processor is further to scan the build-side table with a condition.