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 with a set of conjunctive predicates and a set of disjunctive predicates;
generating, with a processor, a lookup table for each predicate in the set of conjunctive predicates and the set of disjunctive predicates, wherein the generating includes:
filtering a probe-side table for each of the predicates using a range bloom filter based on at least a corresponding build-side table and adding surviving rows to a corresponding lookup table;
for each row in the probe-side table:
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, wherein:
the row satisfies a conjunctive part of the set of conjunctive predicates;
the row satisfies at least one of the disjuncts of the disjunctive predicates; and
the match is found using at least a priority data queue for the disjunctive results; and
returning the results set.
2. The method of claim 1 , wherein each of the lookup tables comprises a hash table.
3. The method of claim 1 , wherein each of the lookup tables references data associated with a build-side table.
4. The method of claim 3 , wherein each of the lookup tables maps one or more values associated with at least one of the conjunctive predicate and disjunctive predicate columns to a set of references that reference rows associated with the build-side table.
5. The method of claim 1 , wherein the filtering further includes using at least a bloom filter.
6. The method of claim 1 , further comprising:
deduplicating the results set.
7. The method of claim 1 , wherein the query plan includes a join operator for each set of disjunctive predicates.
8. The method of claim 1 , further comprising:
scanning the probe-side table with a condition.
9. The method of claim 1 , further comprising:
scanning the build-side table with a condition.
10. 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 with a set of conjunctive predicates and a set of disjunctive predicates;
generate, with the one or more processors, a lookup table for each predicate in the set of conjunctive predicates and the set of disjunctive predicates, wherein the generating includes:
filtering a probe-side table for each of the predicates using a range bloom filter based on at least a corresponding build-side table and adding surviving rows to a corresponding lookup table;
for each row in the probe-side table:
lookup a value associated with that row in each of the lookup tables; and
add the row to a results set when there is a match, wherein:
the row satisfies a conjunctive part of the set of conjunctive predicates;
the row satisfies at least one of the disjuncts of the disjunctive predicates; and
the match is found using at least a priority data queue for the disjunctive results; and
return the results set.
11. The non-transitory machine-readable medium of claim 10 , wherein each of the lookup tables comprises a hash table.
12. The non-transitory machine-readable medium of claim 10 , wherein each of the lookup tables references data associated with a build-side table.
13. The non-transitory machine-readable medium of claim 12 , wherein each of the lookup tables maps one or more values associated with at least one of the conjunctive predicate and disjunctive predicate columns to a set of references that reference rows associated with the build-side table.
14. The non-transitory machine-readable medium of claim 10 , wherein the filtering further includes using at least a bloom filter.
15. The non-transitory machine-readable medium of claim 10 , further comprising:
deduplicating the results set.
16. The non-transitory machine-readable medium of claim 10 , wherein the query plan includes a join operator for each set of disjunctive predicates.
17. The non-transitory machine-readable medium of claim 10 , further comprising:
scanning the probe-side table with a condition.
18. The non-transitory machine-readable medium of claim 10 , further comprising:
scanning the build-side table with a condition.
19. A system comprising:
a set of storage resources; and
a query processor to,
receive a query with a set of conjunctive predicates and a set of disjunctive predicates,
generate, with the query processor, a lookup table for each predicate in the set of conjunctive predicates and the set of disjunctive predicates, wherein the generating includes:
filtering a probe-side table for each of the predicates using a range bloom filter based on at least a corresponding build-side table and adding surviving rows to a corresponding lookup table,
for each row in a probe-side table,
lookup a value associated with that row in each of the lookup tables; and
add the row to a results set when there is a match, wherein:
the row satisfies a conjunctive part of the set of conjunctive predicates;
the row satisfies at least one of the disjuncts of the disjunctive predicates; and
the match is found using at least a priority data queue for the disjunctive results; and
return the results set.
20. The system of claim 19 , wherein each of the lookup tables comprises a hash table.
21. The system of claim 19 , wherein each of the lookup tables references data associated with a build-side table.
22. The system of claim 21 , wherein each of the lookup tables maps one or more values associated with at least one of the conjunctive predicate and disjunctive predicate columns to a set of references that reference rows associated with the build-side table.
23. The system of claim 19 , wherein the filtering further includes using at least a bloom filter.
24. The system of claim 19 , wherein the query processor further to:
deduplicate the results set.
25. The system of claim 19 , wherein the query plan includes a join operator for each set of disjunctive predicates.
26. The system of claim 19 , wherein the query processor further to:
scan the probe-side table with a condition.
27. The system of claim 19 , wherein the query processor further to:
scan the build-side table with a condition.