HASH JOIN USING COLLABORATIVE PARALLEL FILTERING IN INTELLIGENT STORAGE WITH OFFLOADED BLOOM FILTERS

• US 20100082648A1
• Filed: 09/18/2009
• Published: 04/01/2010
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Jokobsson, Hakan, Lau, Yiu Woon, Kumar, Poojan, Panchaksharaiah, Umesh, Potapov, Dmitry
• Granted Patent: US 8,825,678 B2
• Time in Patent Office: Days
• US Class Current: 707/756
• 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 method comprising:

a database server sending to a data storage system;

a) a request for data, the request identifying one or more data units stored in the data storage subsystem, wherein the one or more data units are data units in which the data storage system stores data for a first table; and

b) metadata describing one or more characteristics of a second table;

wherein the request is a communication that, when interpreted by the data storage system, causes the data storage system to retrieve said one or more data units from storage;

wherein the metadata is metadata that, when interpreted by the data storage system, causes the data storage system to generate filtered data based upon the retrieved one or more data units and the one or more characteristics of the second table, as described in the metadata; and

in response to the request, the database server receiving the filtered data from the data storage system;

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

2. The method of claim 1, further comprising:

prior to sending the metadata to the data storage system, generating a hash table based upon one or more attributes of the second table;

wherein the one or more characteristics comprises said hash table.

3. The method of claim 1, further comprising:

prior to sending the metadata to the data storage system, generating a hash table based upon one or more attributes of the second table;

prior to sending the metadata to the data storage system, generating a bloom filter based upon one or more attributes of the second table;

wherein at least one of the one or more characteristics is based upon the bloom filter.

4. The method of claim 3, further comprising:

prior to sending the metadata to the data storage system, generating at least one predicate based upon the bloom filter;

wherein the one or more characteristics comprises the at least one predicate.

5. The method of claim 1, wherein the one or more data units are raw data units, wherein identifying the one or more data units comprises identifying one or more locations at which the raw data units are stored.

6. The method of claim 5, wherein the filtered data includes one or more raw data units.

7. The method of claim 1, further comprising sending to the data storage system metadata indicating at least a portion of a logical structure for the first table.

8. The method of claim 1, further comprising the database server performing a first join operation on the first table and the second table based on the filtered data.

9. The method of claim 8,

wherein the metadata further describes one or more characteristics of a third table;

wherein the metadata is metadata that, when interpreted by the data storage system, causes the data storage system to generate the filtered data based further upon the one or more characteristics of the third table, as described in the metadata;

the method further comprising the database server performing a second join operation on the first table, the second table, and the third table based on the results of the first join operation.

10. A method for performing a join operation, the method comprising:

a database server sending to a data storage system;

a) a request for data, the request identifying one or more data units stored in the data storage subsystem, wherein the one or more data units are data units in which the data storage system stores data for a first table; and

b) one or more join filtering conditions;

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

the data storage system to retrieving said one or more data units from storage;

the data storage system generating filtered data by applying the one or more join filtering conditions to the retrieved one or more data units; and

in response to the request, the database server receiving the filtered data from the data storage system;

performing the join operation based on the filtered data;

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

11. The method of claim 10, further comprising:

prior to sending the one or more join filtering conditions to the data storage system, generating a hash table based upon one or more attributes of a second table;

prior to sending the one or more join filtering conditions to the data storage system, generating a bloom filter based upon one or more attributes of the second table;

wherein at least one of the one or more join filtering conditions is based upon the bloom filter.

12. The method of claim 11, further comprising:

prior to sending the one or more join filtering conditions to the data storage system, generating at least one predicate based upon the bloom filter;

wherein the one or more join filtering conditions comprises the at least one predicate.

13. The method of claim 10, wherein the one or more data units are raw data units, wherein identifying the one or more data units comprises identifying one or more locations at which the raw data units are stored.

14. The method of claim 13, wherein the filtered data includes one or more raw data units.

15. The method of claim 10, further comprising sending to the data storage system metadata indicating at least a portion of a logical structure for the first table.

16. A method comprising a data storage system performing the steps of:

receiving a request to retrieve data, wherein the request identifies one or more locations of one or more data units in which the requested data is stored at the data storage system;

receiving metadata describing one or more filtering conditions for a join operation to be performed with respect to the requested data;

in response to the request, reading the one or more data units from the one or more locations;

based on the one or more join filtering conditions, filtering data from the one or more data units, thereby generating filtered data;

responding to the request, wherein the response includes the filtered data;

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

17. The method of claim 16, wherein the one or more filtering conditions include a hash table.

18. The method of claim 16, wherein the one or more filtering conditions include a bloom filter.

19. The method of claim 16, wherein the one or more filtering conditions include a predicate based upon a bloom filter.

20. The method of claim 16, further comprising the data storage system performing the steps of:

receiving metadata indicating at least a portion of a logical structure for a table whose data is stored in the one or more data units; and

based on the at least a portion of the logical structure, identifying one or more attribute values represented by the one or more data units;

wherein filtering data from the one or more data units is further based upon applying the one or more filtering conditions to the identified one or more attribute values.

21. The method of claim 16, wherein the response further includes at least one of the one or more data units, wherein the at least one of the one or more data units is not filtered.

22. A method comprising a data storage system performing the steps of:

receiving a request for data from a database server;

wherein the request includes join data indicating an operation to join rows of data stored in data units at the data storage system;

in response to the request;

reading a plurality of data units from storage;

generating response data, wherein generating the response data comprises generating the response data by at least filtering the plurality of data units, based on the join data, to exclude one or more rows that are not to be joined for the indicated operation;

sending the response data to the database server.

23. The method of claim 22, wherein generating the response data further comprises generating the response data by at least joining one or more rows from a first data unit with one or more rows from a second data unit, thereby generating one or more joined rows to be returned to the database server in the response data.

24. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of:

a database server sending to a data storage system;

a) a request for data, the request identifying one or more data units stored in the data storage subsystem, wherein the one or more data units are data units in which the data storage system stores data for a first table; and

b) metadata describing one or more characteristics of a second table;

wherein the request is a communication that, when interpreted by the data storage system, causes the data storage system to retrieve said one or more data units from storage;

wherein the metadata is metadata that, when interpreted by the data storage system, causes the data storage system to generate filtered data based upon the retrieved one or more data units and the one or more characteristics of the second table, as described in the metadata; and

in response to the request, the database server receiving the filtered data from the data storage system;

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

25. The one or more storage media of claim 24, wherein the instructions, when executed by the one or more computing devices, further cause:

prior to sending the metadata to the data storage system, generating a hash table based upon one or more attributes of the second table;

wherein the one or more characteristics comprises said hash table.

26. The one or more storage media of claim 24, wherein the instructions, when executed by the one or more computing devices, further cause:

prior to sending the metadata to the data storage system, generating a hash table based upon one or more attributes of the second table;

prior to sending the metadata to the data storage system, generating a bloom filter based upon one or more attributes of the second table;

wherein at least one of the one or more characteristics is based upon the bloom filter.

27. The one or more storage media of claim 26, wherein the instructions, when executed by the one or more computing devices, further cause:

prior to sending the metadata to the data storage system, generating at least one predicate based upon the bloom filter;

wherein the one or more characteristics comprises the at least one predicate.

28. The one or more storage media of claim 24, wherein the one or more data units are raw data units, wherein identifying the one or more data units comprises identifying one or more locations at which the raw data units are stored.

29. The one or more storage media of claim 28, wherein the filtered data includes one or more raw data units.

30. The one or more storage media of claim 24, wherein the instructions, when executed by the one or more computing devices, further cause sending to the data storage system metadata indicating at least a portion of a logical structure for the first table.

31. The one or more storage media of claim 24, wherein the instructions, when executed by the one or more computing devices, further cause the database server performing a first join operation on the first table and the second table based on the filtered data.

32. The one or more storage media of claim 31,

wherein the metadata further describes one or more characteristics of a third table;

wherein the metadata is metadata that, when interpreted by the data storage system, causes the data storage system to generate the filtered data based further upon the one or more characteristics of the third table, as described in the metadata;

the wherein the instructions, when executed by the one or more computing devices, further cause the database server to perform a second join operation on the first table, the second table, and the third table based on the results of the first join operation.

33. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of a join operation, wherein performance of the join operation comprises:

a database server sending to a data storage system;

a) a request for data, the request identifying one or more data units stored in the data storage subsystem, wherein the one or more data units are data units in which the data storage system stores data for a first table; and

b) one or more join filtering conditions;

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

the data storage system to retrieving said one or more data units from storage;

the data storage system generating filtered data by applying the one or more join filtering conditions to the retrieved one or more data units; and

in response to the request, the database server receiving the filtered data from the data storage system;

performing the join operation based on the filtered data.

34. The one or more storage media of claim 33, wherein the instructions, when executed by the one or more computing devices, further cause:

prior to sending the one or more join filtering conditions to the data storage system, generating a hash table based upon one or more attributes of a second table;

prior to sending the one or more join filtering conditions to the data storage system, generating a bloom filter based upon one or more attributes of the second table;

wherein at least one of the one or more join filtering conditions is based upon the bloom filter.

35. The one or more storage media of claim 34, wherein the instructions, when executed by the one or more computing devices, further cause:

prior to sending the one or more join filtering conditions to the data storage system, generating at least one predicate based upon the bloom filter;

wherein the one or more join filtering conditions comprises the at least one predicate.

36. The one or more storage media of claim 33, wherein the one or more data units are raw data units, wherein identifying the one or more data units comprises identifying one or more locations at which the raw data units are stored.

37. The one or more storage media of claim 36, wherein the filtered data includes one or more raw data units.

38. The one or more storage media of claim 33, wherein the instructions, when executed by the one or more computing devices, further cause sending to the data storage system metadata indicating at least a portion of a logical structure for the first table.

39. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of, at a data storage system:

receiving a request to retrieve data, wherein the request identifies one or more locations of one or more data units in which the requested data is stored at the data storage system;

receiving metadata describing one or more filtering conditions for a join operation to be performed with respect to the requested data;

in response to the request, reading the one or more data units from the one or more locations;

based on the one or more join filtering conditions, filtering data from the one or more data units, thereby generating filtered data;

responding to the request, wherein the response includes the filtered data.

40. The one or more storage media of claim 39, wherein the one or more filtering conditions include a hash table.

41. The one or more storage media of claim 39, wherein the one or more filtering conditions include a bloom filter.

42. The one or more storage media of claim 39, wherein the one or more filtering conditions include a predicate based upon a bloom filter.

43. The one or more storage media of claim 39, wherein the instructions, when executed by the one or more computing devices, further cause the data storage system to perform:

receiving metadata indicating at least a portion of a logical structure for a table whose data is stored in the one or more data units; and

based on the at least a portion of the logical structure, identifying one or more attribute values represented by the one or more data units;

wherein filtering data from the one or more data units is further based upon applying the one or more filtering conditions to the identified one or more attribute values.

44. The one or more storage media of claim 39, wherein the response further includes at least one of the one or more data units, wherein the at least one of the one or more data units is not filtered.

45. One or more storage media storing instructions which, when executed by one or more computing devices, cause performance of, at a data storage system:

receiving a request for data from a database server;

wherein the request includes join data indicating an operation to join rows of data stored in data units at the data storage system;

in response to the request;

reading a plurality of data units from storage;

generating response data, wherein generating the response data comprises generating the response data by at least filtering the plurality of data units, based on the join data, to exclude one or more rows that are not to be joined for the indicated operation;

sending the response data to the database server.

46. The one or more storage media of claim 45, wherein generating the response data further comprises generating the response data by at least joining one or more rows from a first data unit with one or more rows from a second data unit, thereby generating one or more joined rows to be returned to the database server in the response data.