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

• US 9,501,527 B1
• Filed: 05/19/2016
• Issued: 11/22/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: Chainani, Naresh K., Chinta, Kiran K., Su, Yuan, Zhang, Liping
• Primary Examiner(s): Yen, Syling
• Application Number:
  US15/158,643
• Time in Patent Office: 187 Days
• Field of Search: 707/706, 707/713, 707/722, 707/736, 707/758, 707/759, 707/764, 707/781, 707999003-999005
• 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, on each node, constructing a Bloom filter by writing a local portion of the complete Bloom filter and then receiving and merging Bloom filter components sent from each node using different startingOffset positions and then, once the Bloom filter is complete at a node, using the complete Bloom filter as a join filter in a table join operation, without regard to Bloom filter construction occurring at other 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:

I) 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;

II) for the specific query, using the at least one processor, at each query processing node as a local node;

a) 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,

b) writing, with at least one thread, the local portion as a first part of a complete Bloom filter,

c) once the writing of the local portion is complete, broadcasting the Bloom filter bitmap containing the portion to others of the query processing nodes as a filter file component of the 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