FAST MULTI-TIER INDEXING SUPPORTING DYNAMIC UPDATE

• US 20160283538A1
• Filed: 03/27/2015
• Published: 09/29/2016
• Est. Priority Date: 03/27/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Barber, Ronald J., Leis, Viktor, Lohman, Guy M., Raman, Vijayshankar, Sidle, Richard S.
• Granted Patent: US 10,831,736 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

A method includes performing a lookup using a key into a root node of a multi-tier data structure, to find a partition for performing an insert. A lookup for the key is performed on a first level index that is part of a linked data structure. A payload or reference is added to the linked data structure based on data structure criterion, otherwise the key and the payload are added to the linked data structure if the key is not found. A new first level index is created and added to the linked data structure upon the linked data structure remaining unchanged. The key and the payload or reference are added to the new index. Based on merge criterion, a new second level index is created and a portion of content from selected first level and second level indexes are merged for combining into the new second level index.

Claims

1. A method for inserting an entry into a multi-tier data structure comprising:

performing a lookup using a key of the entry by a hashing processor, into a root node of the multi-tier data structure, to find a partition for performing an insert operation;

performing a lookup for the key, by the hashing processor, on a first level index that is part of a linked data structure holding entries for the found partition;

based on data structure criterion, adding, by the hashing processor, a payload or reference to the payload to the linked data structure upon finding the key, otherwise if the key is not found, adding the key and the payload to the linked data structure;

based on data structure criterion, creating, by a data structure processor, a new first level index and adding the new first level index to the linked data structure upon the linked data structure remaining unchanged since starting the lookup for the key, and adding the key and the payload or the reference to payload to the new index; and

based on a merge criterion, creating, by the data structure processor, a new second level index and merging a portion of content from selected first level and second level indexes into the new second level index.

2. The method of claim 1, further comprising:

updating, by an update processor, the linked data structure by replacing indexes whose content has been fully merged with the one or more new second level indexes,

wherein the selection of first level and second level indexes for merging into a new second level index also marks the selected first level and second level indexes as not accepting further inserts.

3. The method of claim 1, wherein the data structure criterion comprises one or more of sufficient space in an index of the linked data structure, the index being able to accept additional inserts, the index having an imbalanced structure, or lookup efficiency.

4. The method of claim 1, wherein the merge criterion comprises one or more of:

no on-going merge operation exists on the partition,

determining that a merge operation is warranted due to significant content present in the selected first level and second level indexes, or

lookup efficiency.

5. The method of claim 2, wherein:

an upper tier of the multi-tier data structure comprises a single node containing a mutable index data structure that maps indicator values derived from keys onto pointers to nodes in a lower tier of the multi-tier data structure, and

the mutable index structure is efficient for performing individual insert operations.

6. The method of claim 5, wherein:

each node in the lower tier of the multi-tier data structure has one immutable index data structure that is efficient for performing lookup operations and bulk loading;

inserts into the multi-tier data structure comprise performing a lookup operation into the mutable index data structure to select a lower tier node to insert into;

inserts into the lower tier nodes are made into a most recently added mutable index data structure at that node; and

the mutable index data structures are periodically merged into the immutable index data structure, producing a new immutable index data structure.

7. The method of claim 6, wherein the immutable index data structure comprises a concise hash table including a first level of bitmap pages and a second level of leaf pages.

8. The method of claim 1, wherein the lookup uses a hash value, a result buffer and maximum size as input parameters, and returns as value a number of record identifiers found for a desired hash key, and places as many result payloads that fit within the maximum size into the result buffer.

9. A computer program product for inserting an entry into a multi-tier data structure, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

perform a lookup using a key of the entry, by the processor, into a root node of said data structure to find a partition for performing an insert operation;

perform a lookup for the key, by the processor, on a first level index that is part of a linked data structure holding entries for the found partition;

based on data structure criterion, add, by the processor, a payload or reference to the payload to the linked data structure upon finding the key, otherwise if the key is not found, adding the key and the payload to the linked data structure;

based on data structure criterion, create, by a data structure processor, a new first level index and adding the new first level index to the linked data structure upon the linked data structure remaining unchanged since starting the lookup for the key, and adding the key and the payload or the reference to the payload to the new index; and

based on a merge criterion, create, by the data structure processor, a new second level index and merging a portion of content from selected first level and second level indexes into the new second level index.

10. The computer program product of claim 9, further comprising program code executable by the processor to:

update, by an update processor, the linked data structure by replacing indexes whose content has been fully merged with the one or more new second level indexes,

wherein the selection of first level and second level indexes for merging into a new second level index also marks the selected first level and second level indexes as not accepting further inserts.

11. The computer program product of claim 10, wherein the data structure criterion comprises one or more of sufficient space in an index of the linked data structure, the index being able to accept additional inserts, the index having an imbalanced structure, or lookup efficiency.

12. The computer program product of claim 11, wherein the merge criterion comprises one or more of:

no on-going merge operation exists on the partition,

determining that a merge operation is warranted due to significant content present in the selected first level and second level indexes, or

lookup efficiency.

13. The computer program product of claim 9, wherein:

an upper tier of the multi-tier data structure comprises a single node containing a mutable index data structure that maps indicator values derived from keys onto pointers to nodes in a lower tier of the multi-tier data structure, and

the mutable index data structure is efficient for performing individual insert operations.

14. The computer program product of claim 10, wherein:

each node in the lower tier of the multi-tier data structure has one immutable index data structure that is efficient for performing lookup operations and bulk loading;

inserts into the multi-tier data structure comprise performing a lookup operation into the mutable index data structure to select a lower tier node to insert into;

inserts into the lower tier nodes are made into a most recently added mutable index data structure at that node; and

the mutable index data structures are periodically merged into the immutable index data structure, producing a new immutable index data structure.

15. The computer program product of claim 14, wherein the immutable index data structure comprises a concise hash table including a first level of bitmap pages and a second level of leaf pages.

16. The computer program product of claim 9, wherein the lookup uses a hash value, a result buffer and maximum size as input parameters, and returns as value a number of record identifiers found for a desired hash key, and places as many result payloads that fit within the maximum size into the result buffer.

17. A system comprising:

a hashing processor that performs a lookup using a key of an entry into a root node of a multi-tier data structure to find a partition for performing an insert operation, performs a lookup for the key on a first level index that is part of a linked data structure holding entries for the found partition, and based on data structure criterion, adds a payload or a reference to the payload to the linked data structure upon finding the key, otherwise if the key is not found, adding the key and the payload to the linked data structure; and

a data structure processor that, based on data structure criterion, creates a new first level index and adds the new first level index to the linked data structure upon the linked data structure remaining unchanged since starting the lookup for the key, and adds the key and the payload or to the reference to the payload to the new index, and based on a merge criterion, creates a new second level index and merges a portion of content from selected first level and second level indexes into the new second level index.

18. The system of claim 17, further comprising an update processor that updates the linked data structure by replacing indexes whose content has been fully merged with the one or more new second level indexes,

wherein the selection of first level and second level indexes for merging into a new second level index also marks the selected first level and second level indexes as not accepting further inserts.

19. The system of claim 18, wherein:

the data structure criterion comprises one or more of sufficient space in an index of the linked data structure, the index being able to accept additional inserts, the index having an imbalanced structure, or lookup efficiency

the merge criterion comprises one or more of;

no on-going merge operation exists on the partition,

determining that a merge operation is warranted due to significant content present in the selected first level and second level indexes, or

lookup efficiency;

an upper tier of the multi-tier data structure comprises a single node containing a mutable index data structure that maps indicator values derived from keys onto pointers to nodes in a lower tier of the multi-tier data structure;

the mutable index data structure is efficient for performing individual insert operations;

each node in the lower tier of the multi-tier data structure has one immutable index data structure that is efficient for performing lookup operations and bulk loading;

inserts into the multi-tier data structure comprise the data structure processor performing a lookup operation into the mutable index data structure to select a lower tier node to insert into;

inserts into the lower tier nodes are made by the data structure processor into a most recently added mutable index data structure at that node; and

the mutable index data structures are periodically merged by the data structure processor into the immutable index data structure, producing a new immutable index data structure.

20. The system of claim 19, wherein:

the immutable index data structure comprises a concise hash table including a first level of bitmap pages and a second level of leaf pages; and

the lookup uses a hash value, a result buffer and maximum size as input parameters, and returns as value a number of record identifiers found for a desired hash key, and places as many result payloads that fit within the maximum size into the result buffer.