Off-loading star join operations to a storage server

• US 7,885,953 B2
• Filed: 10/03/2007
• Issued: 02/08/2011
• Est. Priority Date: 10/03/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yang, Kouhorng Allen, Narang, Inderpal Singh, Han, Wei, Chen, Ying-lin, Lin, Fen-Ling, Qiao, Lin, Fuh, You-Chin, Raman, Vijayshankar
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Chbouki; Tarek
• Application Number:
  US11/866,907
• Publication Number:
  US 20090094258A1
• Time in Patent Office: 1,224 Days
• Field of Search: None
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A method, storage server, and computer readable medium for off-loading star-join operations from a host information processing system to a storage server. At least a first and second set of keys from a first and second dimension table, respectively are received from a host system. Each of the first and second set of keys is associated with at least one fact table. A set of locations associated with a set of foreign key indexes are received from the host system. A set of fact table indexes are traversed. At least a first set of Row Identifiers (“RIDs”) associated with the first set of keys and at least a second set of RIDs associated with the second set of keys are identified. An operation is performed on the first and second sets of RIDs to identify an intersecting set of RIDs. The intersecting set of RIDs are then stored.

Claims

1. A method for off-loading star join operations from a host information processing system to a storage server, the method on the storage server comprising:

determining, at a storage server, that at least one portion of a query execution plan comprising a plurality of steps to access data in a data store on the storage server is to be off-loaded from a host information processing system to the storage server, wherein the host information processing system is separate and distinct from the storage server;

offloading the at least one portion of the query execution plan from the host information processing system to the storage server, the offloading comprising at least;

receiving, at the storage server from the host information processing system, at least a first set of keys from a first dimension table and at least a second set of keys from a second dimension table, wherein each of the first and second set of keys are associated with at least one fact table;

receiving, at the storage server from the host information processing system, a set of locations associated with a set of foreign key indexes;

traversing, at the storage server in response to the receiving, a set of fact table indexes;

identifying, at the storage server in response to the traversing, at least a first set of Row Identifiers (“

RIDs”

) associated with the first set of keys and at least a second set of RIDs associated with the second set of keys;

performing, at the storage server, an operation on the first set of RIDs and the second set of RIDs to identify an intersecting set of RIDs; and

storing, at the storage server, the intersecting set of RIDs.

2. The method of claim 1, further comprising:

sending the intersecting set of RIDs to the host information processing system.

3. The method of claim 1, further comprising:

performing a first SEMI-JOIN operation on the first set of keys and performing a second SEMI-JOIN operation on the second set of keys.

4. The method of claim 3, wherein the first SEMI-JOIN operation and the second SEMI-JOIN operation each comprise a join operation and a sort operation.

5. The method of claim 1, further comprising:

receiving a probing request from the host information processing system comprising a payload for the operation on the first set of RIDs and the second set of RIDs to identify the intersecting set of RIDs.

6. The method of claim 5, further comprising:

performing, in response to receiving the probing request, a portion of the AND operation.

7. The method of claim 1, wherein the identifying further comprises:

identifying a total number of RIDs associated with the first set of keys and a total number of RIDs associated with the second set of keys; and

sending the total number of RIDs associated with the first set of keys and the total number of RIDs associated with the second set of keys to the host information processing system.

8. A storage server for off-loading star-join operations from a host information processing system, the storage server comprising:

a processor;

a memory communicatively coupled to the processor;

a data store communicatively coupled to the memory and the processor; and

an off-load manager communicatively coupled to the processor and the memory, wherein the off-load manager is adapted to;

determine that at least one portion of a query execution plan comprising a plurality of steps to access data in the data store is to be off-loaded from a host information processing system to the storage server, wherein the host information processing system is separate and distinct from the storage server;

offloading the at least one portion of the query execution plan from the host information processing system to the storage server, the offloading comprising at least;

receiving, from a host information processing system, at least a first set of keys from a first dimension table and at least a second set of keys from a second dimension table, wherein each of the first and second set of keys are associated with at least one fact table;

receiving, from the host information processing system, a set of locations associated with a set of foreign key indexes;

traversing, in response to the receiving the set of locations, a set of fact table indexes;

identifying, in response to the traversing the set of fact table indexes, at least a first set of Row Identifiers (“

RIDs”

) associated with the first set of keys and at least a second set of RIDs associated with the second set of keys;

performing an operation on the first set of RIDs and the second set of RIDs to identify an intersecting set of RIDs; and

storing the intersecting set of RIDs.

9. The storage server of claim 8, wherein the off-load manager is further adapted to:

send the intersecting set of RIDs to the host information processing system.

10. The storage server of claim 8, wherein the off-load manager is further adapted to:

perform a first SEMI-JOIN operation on the first set of keys and performing a second SEMI-JOIN operation on the second set of keys.

11. The storage server of claim 10, wherein the first SEMI-JOIN operation and the second SEMI-JOIN operation each comprise a join operation and a sort operation.

12. The storage server of claim 8, wherein the off-load manager is further adapted to:

receive a probing request from the host information processing system comprising a payload for the AND operation.

13. The storage server of claim 12, wherein the off-load manager is further adapted to:

perform, in response to receiving the probing request, a portion of the AND operation.

14. The storage server of claim 8, wherein the off-load manager is further adapted to identify by:

identifying a total number of RIDs associated with the first set of keys and a total number of RIDs associated with the second set of keys; and

sending the total number of RIDs associated with the first set of keys and the total number of RIDs associated with the second set of keys to the host information processing system.

15. A computer program storage product stored on a computer readable storage medium for off-loading star join operations from a host information processing system to a storage server, the computer program storage product comprising instructions for:

determining, at a storage server, that at least one portion of a query execution plan comprising a plurality of steps to access data in a data store on the storage server is to be off-loaded from a host information processing system to the storage server, wherein the host information processing system is separate and distinct from the storage server;

offloading the at least one portion of the query execution plan from the host information processing system to the storage server, the offloading comprising at least;

receiving at the storage server, from a host information processing system, at least a first set of keys from a first dimension table and at least a second set of keys from a second dimension table, wherein each of the first and second set of keys are associated with at least one fact table;

receiving at the storage server, from the host information processing system, a set of locations associated with a set of foreign key indexes;

traversing at the storage server, in response to the receiving, a set of fact table indexes;

identifying at the storage server, in response to the traversing, at least a first set of Row Identifiers (“

RIDs”

) associated with the first set of keys and at least a second set of RIDs associated with the second set of keys;

performing at the storage server an operation on the first set of RIDs and the second set of RIDs to identify an intersecting set of RIDs; and

sending by the storage server, the intersecting set of RIDs to the host information processing system.

16. The computer program storage product of claim 15, further comprising instructions for:

performing a first SEMI-JOIN operation on the first set of keys and performing a second SEMI-JOIN operation on the second set of keys.

17. The computer program storage product of claim 16, wherein the first SEMI-JOIN operation and the second SEMI-JOIN operation each comprise a join operation and a sort operation.

18. The computer program storage product of claim 15, further comprising instructions for:

receiving a probing request from the host information processing system comprising a payload for the operation on the first set of RIDs and the second set of RIDs to identify an intersecting set of RIDs.

19. The computer program storage product of claim 18, further comprising instructions for:

performing, in response to receiving the probing request, a portion of the AND operation.

20. The computer program storage product of claim 15, wherein the instructions for identifying further comprise instructions for:

identifying a total number of RIDs associated with the first set of keys and a total number of RIDs associated with the second set of keys; and

sending the total number of RIDs associated with the first set of keys and the total number of RIDs associated with the second set of keys to the host information processing system.