Bloom filter construction method for use in a table join operation portion of processing a query to a distributed database
First Claim
1. A method for use in processing database queries performed on a database, having tables made up of outer table data and corresponding inner table data, distributed among storage associated with multiple nodes of a multi-threaded cluster of computers each having at least one processor, the method comprising:
- in response to a specific query of the database, sending the specific query to nodes in the multi-threaded cluster of computers that are query processing nodes, each of the query processing nodes having a NodeID;
for the specific query, using the at least one processor at each query processing node,generating, using at least one thread, a local portion of a Bloom filter bitmap from the specific query based upon inner table data stored in the storage associated with that node, andbroadcasting the Bloom filter bitmap containing the portion to others of the query processing nodes as a filter file component of a complete Bloom filter along with a startingOffset position, the broadcasting beginning at the startingOffset position and continuing until an end of the Bloom filter bitmap containing the portion is reached and then continuing from a start of the Bloom filter bitmap containing the portion until the startingOffset position is reached, the startingOffset position being determined according to the formula
1 Assignment
0 Petitions
Accused Products
Abstract
A method for use in processing database queries performed on a database, having tables made up of outer table data and corresponding inner table data, distributed among storage associated with multiple nodes of a multi-threaded cluster of computers is described. The method involves constructing a Bloom filter at nodes by merging Bloom filter components on each node using different startingOffset positions for each thread and then, once the Bloom filter is complete at a node and using the complete Bloom filter as a join filter in a table join operation, without regard to Bloom filter construction occurring at others of the multiple nodes.
-
Citations
1 Claim
-
1. A method for use in processing database queries performed on a database, having tables made up of outer table data and corresponding inner table data, distributed among storage associated with multiple nodes of a multi-threaded cluster of computers each having at least one processor, the method comprising:
-
in response to a specific query of the database, sending the specific query to nodes in the multi-threaded cluster of computers that are query processing nodes, each of the query processing nodes having a NodeID; for the specific query, using the at least one processor at each query processing node, generating, using at least one thread, a local portion of a Bloom filter bitmap from the specific query based upon inner table data stored in the storage associated with that node, and broadcasting the Bloom filter bitmap containing the portion to others of the query processing nodes as a filter file component of a complete Bloom filter along with a startingOffset position, the broadcasting beginning at the startingOffset position and continuing until an end of the Bloom filter bitmap containing the portion is reached and then continuing from a start of the Bloom filter bitmap containing the portion until the startingOffset position is reached, the startingOffset position being determined according to the formula
-
Specification