Hash join using collaborative parallel filtering in intelligent storage with offloaded bloom filters

• US 9,336,275 B2
• Filed: 07/23/2014
• Issued: 05/10/2016
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Potapov, Dmitry, Lau, Yiu Woon, Jakobsson, Hakan, Panchaksharaiah, Umesh, Kumar, Poojan
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): CONYERS, DAWAUNE A
• Application Number:
  US14/339,412
• Publication Number:
  US 20140337314A1
• Time in Patent Office: 657 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Processing resources at a storage system for a database server are utilized to perform aspects of a join operation that would conventionally be performed by the database server. When requesting a range of data units from a storage system, the database server includes join metadata describing aspects of the join operation for which the data is being requested. The join metadata may be, for instance, a bloom filter. The storage system reads the requested data from disk as normal. However, prior to sending the requested data back to the storage system, the storage system analyzes the raw data based on the join metadata, removing a certain amount of data that is guaranteed to be irrelevant to the join operation. The storage system then returns filtered data to the database server. The database system thereby avoids the unnecessary transfer of certain data between the storage system and the database server.

Claims

1. A system comprising:

one or more storage devices storing raw data in data block structures;

a storage server configured to respond to input/output (I/O) requests directly from one or more database servers, but not to respond to database commands received directly from database clients;

wherein the I/O requests are requests for raw data from specified data block structures;

wherein the storage server is configured to respond to the I/O requests from the one or more database servers by reading data blocks from or writing data blocks to the one or more storage devices; and

a database server, connected via a network to the storage server;

wherein the storage server acts as an intermediary for all data transfers between the database server and the one or more storage devices;

wherein the database server is configured to respond to database commands received directly from one or more database clients, but the database server is not capable of directly responding to I/O requests for raw data;

wherein the database server is configured to perform;

identifying one or more data blocks, of the data block structures stored on the one or more storage devices, that store raw data that represents a first table;

generating join metadata based upon one or more attributes of a second table;

sending to the data storage system;

a particular I/O request for the one or more data blocks, and

data indicating the join metadata;

wherein the storage server is further configured to perform;

receiving the particular I/O request for the one or more data blocks;

reading the one or more data blocks from the one or more storage devices;

identifying a portion of the raw data in the one or more data blocks that represents table rows that are guaranteed, based on the join metadata, to not be needed for a join operation with the second table; and

returning, to the database server, a filtered version of the one or more data blocks without at least the identified portion;

wherein the database server is further configured to perform;

receiving the filtered version of the one or more data blocks from the storage server; and

a join operation between the first table and the second table based on the filtered version of the one or more data blocks.

2. The system of claim 1, wherein the storage server is further configured to perform:

generating a virtual data block comprising data block header or transmission information and a payload;

wherein the payload encapsulates a row set;

wherein the row set is comprised of table rows;

wherein the table rows correspond to raw data in the one or more data blocks;

wherein the virtual data block is the filtered version of the one or more data blocks.

3. The system of claim 1, further comprising:

a plurality of database servers, including the database server, configured to perform different sub-operations of the join operation;

a plurality of storage servers, including the storage server, configured to access different data block structures on different storage devices of the one or more storage devices;

wherein the particular I/O request is one of multiple I/O requests to the storage servers for data blocks upon which raw data representing the first table is stored;

wherein at least some of the database servers are configured to send, with the multiple I/O requests, data indicating the join data by referencing a shared location at which the join data is stored.

4. The system of claim 1, wherein the database server is further configured to determine whether to send the data indicating the join metadata to the data storage system based on a costing function that at least considers a performance effect of applying the join metadata at the data storage system.

5. The system of claim 1,

wherein the database server is further configured to send, to the storage server, metadata indicating to the data storage system one or more data block row fields, of the one or more data blocks, that correspond to one or more particular columns of the first table;

wherein the storage server is further configured to identify the portion of the raw data in the one or more data blocks by comparing values of the one or more data block row fields, or results of one or more functions of the values, to the join metadata.

6. The system of claim 1, wherein the join metadata is a hash table.

7. The system of claim 1, wherein the join metadata is a bloom filter.

8. A method comprising:

identifying, at a database server, one or more data blocks in which a data storage system stores raw data that represents a first table;

wherein the database server is configured to respond to database commands from one or more database clients, but the database server is not capable of directly responding to input/output (I/O) requests that are requests for raw data;

wherein the data storage system comprises a storage server that is configured to respond to I/O requests directly from one or more database servers, but not to respond to database commands received directly from database clients;

wherein the storage server acts as an intermediary for all data transfers between the database server and one or more storage devices of the data storage system;

generating join metadata based upon one or more attributes of a second table;

the database server sending to the data storage system;

an input/output (I/O) request for the one or more data blocks; and

data indicating the join metadata;

wherein the I/O request is a communication that, when interpreted by the data storage system, causes;

the data storage system reading the one or more data blocks from the one or more storage devices;

identifying a portion of the raw data in the one or more data blocks that represents table rows that are guaranteed, based on the join metadata, to not be needed for a join operation with the second table; and

returning a filtered version of the one or more data blocks without at least the identified portion;

in response to the I/O request, the database server receiving the filtered version of the one or more data blocks from the data storage system;

the database server performing a join operation between the first table and the second table based on the filtered version of the one or more data blocks;

wherein the method is performed by one or more computing devices.

9. The method of claim 8, wherein the filtered version of the one or more data blocks comprises one or more of:

one or more raw data blocks, one or more filtered data blocks, a row source, a row set, or a table.

10. The method of claim 8, wherein the filtered response comprises a virtual data block, comprising at least:

a payload comprised of a row set, and data block header or transmission information.

11. The method of claim 8, further comprising:

sending multiple I/O requests to one or more data storage systems, including the data storage system, for different sets of one or more data blocks in which the data storage system stores data for the first table, the multiple I/O requests including the I/O request;

wherein at least some of the multiple I/O requests include data that indicate the join metadata using data by which the one or more data storage systems locate a cached copy of the join metadata stored in a shared location accessible to each of the one or more data storage systems.

12. The method of claim 8, further comprising determining whether to send the data indicating the join metadata to the data storage system based on a costing function that at least considers a performance effect of applying the join metadata at the data storage system.

13. The method of claim 8, further comprising:

sending to the data storage system metadata indicating to the data storage system one or more data block row fields, of the one or more data blocks, that correspond to one or more particular columns of the first table, wherein identifying the portion of the raw data in the one or more data blocks comprises comparing values of the one or more data block row fields, or results of one or more functions of the values, to the join metadata.

14. The method of claim 8, wherein the database server is one of a plurality of database servers involved in performing the join operation, the method further comprising:

storing the join metadata; and

other database servers in the plurality of database servers sending I/O requests to one or more data storage systems, including the data storage system, that reference the stored join metadata, instead of the other database servers regenerating the join metadata.

15. The method of claim 8, wherein the join metadata is a hash table.

16. The method of claim 8, wherein the join metadata is a bloom filter.

17. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause:

identifying, at a database server, one or more data blocks in which a data storage system stores raw data that represents a first table;

wherein the database server is configured to respond to database commands from one or more database clients, but the database server is not capable of directly responding to input/output (I/O) requests that are requests for raw data;

wherein the data storage system comprises a storage server that is configured to respond to I/O requests directly from one or more database servers, but not to respond to database commands received directly from database clients;

wherein the storage server acts as an intermediary for all data transfers between the database server and one or more storage devices of the data storage system;

generating join metadata based upon one or more attributes of a second table;

the database server sending to the data storage system;

an input/output (I/O) request for the one or more data blocks; and

data indicating the join metadata;

wherein the I/O request is a communication that, when interpreted by the data storage system, causes;

the data storage system reading the one or more data blocks from the one or more storage devices;

identifying a portion of the raw data in the one or more data blocks that represents table rows that are guaranteed, based on the join metadata, to not be needed for a join operation with the second table; and

returning a filtered version of the one or more data blocks without at least the identified portion;

in response to the I/O request, the database server receiving the filtered version of the one or more data blocks from the data storage system;

the database server performing a join operation between the first table and the second table based on the filtered version of the one or more data blocks.

18. The one or more non-transitory computer-readable storage media of claim 17, wherein the filtered response comprises a virtual data block, comprising at least:

a payload comprised of a row set, and data block header or transmission information.

19. The one or more non-transitory computer-readable storage media of claim 17, wherein the instructions, when executed by the one or more computing devices, further cause:

sending multiple I/O requests to one or more data storage systems, including the data storage system, for different sets of one or more data blocks in which the data storage system stores data for the first table, the multiple I/O requests including the I/O request;

wherein at least some of the multiple I/O requests include data that indicate the join metadata using data by which the one or more data storage systems locate a cached copy of the join metadata stored in a shared location accessible to each of the one or more data storage systems.

20. The one or more non-transitory computer-readable storage media of claim 17, wherein the instructions, when executed by the one or more computing devices, further cause determining whether to send the data indicating the join metadata to the data storage system based on a costing function that at least considers a performance effect of applying the join metadata at the data storage system.

21. The one or more non-transitory computer-readable storage media of claim 17, wherein the instructions, when executed by the one or more computing devices, further cause:

sending to the data storage system metadata indicating to the data storage system one or more data block row fields, of the one or more data blocks, that correspond to one or more particular columns of the first table, wherein identifying the portion of the raw data in the one or more data blocks comprises comparing values of the one or more data block row fields, or results of one or more functions of the values, to the join metadata.

22. The one or more non-transitory computer-readable storage media of claim 17, wherein the database server is one of a plurality of database servers involved in performing the join operation, wherein the instructions, when executed by the one or more computing devices, further cause:

storing the join metadata; and

other database servers in the plurality of database servers sending I/O requests to one or more data storage systems, including the data storage system, that reference the stored join metadata, instead of the other database servers regenerating the join metadata.

23. The one or more non-transitory computer-readable storage media of claim 17, wherein the join metadata is a hash table.

24. The one or more non-transitory computer-readable storage media of claim 17, wherein the join metadata is a bloom filter.