Filtered hash table generation for performing hash joins

• US 10,642,840 B1
• Filed: 03/07/2018
• Issued: 05/05/2020
• Est. Priority Date: 03/07/2018
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Attaluri, Gopi Krishna, Gupta, Kamal Kant, He, Yingjie, Krishnamurthy, Saileshwar, Yoon, Yongsik
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US15/914,921
• Time in Patent Office: 790 Days
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536

Abstract

Filtered generation of hash tables may be implemented as part of performing a hash join. A database query may be received that causes a hash join to be performed in order to join two database tables. A filtered generated from a scan of one of the tables that indicates which data in the table can satisfy a join predicate for the hash join may be applied to generate a hash table from a portion of the other table. The filtered hash table may then be used to evaluate whether portions of the tables can be joined in satisfaction of the join predicate for the hash join.

Claims

1. A system, comprising:

a memory to store program instructions which, if performed by at least one processor, cause the at least one processor to perform a method to at least;

receive a database query that causes a hash join that joins two tables of a database;

identify a first one of the two tables as a build table for the hash join and a second one of the two tables as the probe table for the hash join;

filter data included in a hash table generated from a portion of the build table to perform the hash join according to a filter generated from a scan of the probe table that indicates which data in the probe table can satisfy a predicate for the hash join; and

return a result of the database query based, at least in part, on the performance of the hash join.

2. The system of claim 1, wherein the program instructions further cause the at least one processor to perform the method to generate the filter as part of a scan of the build table to evaluate another hash table generated from another portion of the build table.

3. The system of claim 1, wherein the filter is a bloom filter.

4. The system of claim 1, wherein the database is hosted by a network-based database service, wherein the at least one processor is implemented as part of a host for a database engine head node that performs the method, and wherein data for the database including the build table and the probe table is stored in a separate network-based storage service.

5. A method, comprising:

responsive to a database query that causes a hash join that joins a first table and a second table of a database;

filtering data included in a hash table generated from a portion of the first table to perform the hash join according to a filter generated from a scan of the second table that indicates which data in the second table can satisfy a predicate for the hash join.

6. The method of claim 5, further comprising:

generating the filter as part of a scan of the second table to evaluate another hash table generated from another portion of the first table; and

storing data obtained from the scan of the second table not associated with a portion of the second table that corresponds to the other portion of the first table.

7. The method of claim 6, further comprising obtaining at least some of the stored data from the scan of the second table to evaluate with respect to the hash table to perform the hash join.

8. The method of claim 7, further comprising:

filtering data included in another hash table generated from another portion of the first table to perform the hash join according to the filter; and

obtaining at least some other data of the stored data from the scan of the second table to evaluate with respect to the other hash table to perform the hash join.

9. The method of claim 8, wherein the filtering data included in the hash table, the generating the filter, the storing data obtained from the scan, and the obtaining the at least some stored data from the scan of the second table to evaluate is performed by a first processor or a first processing core, and wherein the filtering the data included in another hash table generated from another portion of the first table and the obtaining the at least some other data of the stored data from the scan of the second table to evaluate with respect to the other hash table is performed by a second processor or a second processing core.

10. The method of claim 7, wherein obtaining the at least some of the stored data from the scan of the second table to evaluate comprises applying a second filter that indicates which data in the first table can satisfy the predicate for the hash join.

11. The method of claim 5,

wherein the database is stored separate from a query engine that receives the database query at a plurality of storage nodes;

and

wherein the method further comprises instructing, by the query engine, the plurality of storage nodes to perform the filtering of the data included in the hash table generated from the portion of the first table to perform the hash join.

12. The method of claim 5, wherein the filter is a combined filter from a plurality of different respective filters generated at the plurality of storage nodes, and wherein the method further comprises sharing data from the second table amongst the plurality of storage nodes that can satisfy the join predicate as indicated by the combined filter to perform the hash join.

13. The method of claim 5, wherein the filter is a bloom filter.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

receiving a database query that causes a hash join that joins a first table and a second table of a database;

filtering data included in a hash table generated from a portion of the first table to perform the hash join according to a filter generated from a scan of the second table that indicates which data in the second table can satisfy a predicate for the hash join; and

returning a result of the database query based, at least in part, on the performance of the hash join.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to implement generating the filter as part of a scan of the second table to evaluate another hash table generated from another portion of the first table.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

generating the filter as part of a scan of the second table to evaluate another hash table generated from another portion of the first table;

storing data obtained from the scan of the second table not associated with a portion of the second table that corresponds to the other portion of the first table;

obtaining at least some of the stored data from the scan of the second table to evaluate with respect to the hash table to perform the hash join;

filtering data included in another hash table generated from another portion of the first table to perform the hash join according to the filter; and

obtaining at least some other data of the stored data from the scan of the second table to evaluate with respect to the other hash table to perform the hash join.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the hash table and the other hash table are stored together in a same memory.

18. The non-transitory, computer-readable storage medium of claim 16,

wherein, in obtaining the at least some of the stored data from the scan of the second table to evaluate, the program instructions cause the one or more computing devices to implement applying a second filter that indicates which data in the first table can satisfy the predicate for the hash join;

and

wherein, in obtaining the at least some other stored data from the scan of the second table to evaluate, the program instructions cause the one or more computing devices to implement applying the second filter that indicates which data in the first table can satisfy the predicate for the hash join.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the filter is a range filter.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the database is hosted by a network-based database service, and wherein data for the database including the build table and the probe table is stored in one or more storage devices attached to the one or more computing devices.