Bloom filter construction method for use in a table join operation portion of processing a query to a distributed database

• US 9,372,892 B1
• Filed: 12/28/2015
• Issued: 06/21/2016
• Est. Priority Date: 12/28/2015
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Su, Yuan, Chainani, Naresh K., Chinta, Kiran K., Zhang, Liping
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/981,215
• Time in Patent Office: 176 Days
• Field of Search: 707/706, 707/713, 707/722, 707/736, 707/758, 707/759, 707/764, 707/781
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries

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.

Claims

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