Index page with latch-free access

• US 10,558,636 B2
• Filed: 04/27/2016
• Issued: 02/11/2020
• Est. Priority Date: 04/27/2016
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: She, Zheng-wei, Qian, Xu-dong, Xiong, Zhi-ping
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Caiado, Antonio J
• Application Number:
  US15/139,963
• Publication Number:
  US 20170316042A1
• Time in Patent Office: 1,385 Days
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans

Abstract

Disclosed herein are system, method, and computer program product embodiments for providing read queries latch-free access to an index page. In an embodiment, a processor receives a request from a read query to access one or more records of an index page. The index page includes an update pointer and a slot array. The processor locates one or more updates prepended to the index page by locating a most recently prepended update indicated by the update pointer. Then, the processor generates a local offset table with entries in the slot array and the located one or more updates. The generated local offset table enables the processor to provide the read query access to the one or more records of the index page.

Claims

1. A computer-implemented method, comprising:

receiving a request from a read query to access one or more records of a database table implementing an index on one or more columns of the table, wherein the index comprises an index page that includes a slot array and a header comprising an update pointer;

locating one or more updates prepended to the index page by locating a most recently prepended update indicated by the update pointer;

generating a local offset table with entries updates in the slot array and the located one or more updates;

determining an isolation level that indicates whether the read query is precluded from accessing new prepended updates received after the read query; and

providing latch-free access to the one or more records to the read query from the local offset table based on the isolation level, wherein an update query has concurrent access to the one or more records;

while performing the accessing, concurrently applying an update from an update query by prepending the update to the located one or more updates;

determining to regenerate the local offset table for the read query based on the isolation level and information of each prepended update; and

maintaining the generated local offset table when the isolation level precludes reading the prepended update or records requested by the read access are absent from the information,

wherein at least one of the receiving, locating, generating, and accessing are performed by one or more computers.

2. The method of claim 1, further comprising:

performing the locating and the generating for each read query to enable the read query to access the index page concurrently with another read query or an update query.

3. The method of claim 2, wherein the update query is concurrently accessing the index page, further comprising:

consolidating the index page with the one or more prepended updates when either a number of the prepended updates exceed a threshold count or storing the one or more prepended updates requires memory exceeding a threshold amount; and

providing subsequent queries access to the consolidated index page instead of the index page.

4. The method of claim 3, further comprising:

storing, within the index page, a query count indicating a number of queries currently accessing the index page; and

responsive to generating the consolidated index page, garbage collecting the index page when the query count reaches zero.

5. The method of claim 1, further comprising:

changing the update pointer to a pointer of the applied update.

6. The method of claim 5, further comprising:

receiving a timestamp associated with the access request;

associating the one or more prepended updates with corresponding update timestamps; and

determining whether to regenerate the local offset table for the read query by comparing the access timestamp with one or more of the update timestamps.

7. The method of claim 1, further comprising:

based on how much memory is available in the index page, storing the local offset table in the index page as a stored offset table; and

enabling a subsequent read query to locate and access records associated with the index page by using the stored offset table without requiring a subsequent local offset table to be generated for the subsequent read query.

14. The method of claim 1, further comprising a linked list of delta updates, wherein each delta update includes a pointer to a next recently prepended delta, and wherein a link of each delta includes a pointer to the index page.

15. The method of claim 1, wherein the determining whether to regenerate comprises:

regenerating the local offset table for the read query based upon both the isolation level indicating that the read query can access the new prepended updates and receiving a new prepended update received after the read query.

16. The method of claim 1, further comprising:

determining a selection of one or more of the prepended updates that correspond to records being requested by the read query, wherein one or more other of the prepended updates do not correspond to the records being requested by the read query; and

regenerating the local offset with the determined selection of the one or more prepended updates that correspond to records being requested by the read query.

8. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to;

receive a request from a read query to access one or more records of a database table implementing an index on one or more columns of the table, wherein the index comprises an index page that includes a slot array and a header comprising an update pointer;

locate one or more updates prepended to the index page by locating a most recently prepended update indicated by the update pointer;

generate a local offset table with entries in the slot array and the located one or more updates;

determine an isolation level that indicates whether the read query is precluded from accessing new prepended updates received after the read query; and

provide latch-free access to the one or more records to the read query from the local offset table based on the isolation level, wherein an update query has concurrent access to the one or more records;

while performing the accessing, concurrently applying an update from an update query by prependinq the update to the located one or more updates;

determine to regenerate the local offset table for the read query based on the isolation level and information of each prepended update; and

maintain the generated local offset table when the isolation level precludes reading the prepended update or records requested by the read access are absent from the information.

9. The system of claim 8, wherein the update query is concurrently accessing the index page, the at least one processor further configured to:

perform the locate and the generate for each read request to enable the read query to access the index page concurrently with another read query or an update query;

consolidate the index page with the one or more prepended updates when either a number of the prepended updates exceed a threshold count or storing the one or more prepended updates requires memory exceeding a threshold amount; and

provide subsequent queries access to the consolidated index page instead of the index page.

10. The system of claim 8, the at least one processor further configured to:

change the update pointer to a pointer of the applied update.

11. The system of claim 10, the at least one processor further configured to:

receive a timestamp associated with the access request;

associate the one or more prepended updates with corresponding update timestamps; and

determine whether to regenerate the local offset table for the read query by comparing the access timestamp with one or more of the update timestamps.

12. A tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

receiving a request from a read query to access one or more records of a database table implementing an index on one or more columns of the table, wherein the index comprises an index page that includes a slot array and a header comprising an update pointer;

locating one or more updates prepended to the index page by locating a most recently prepended update indicated by the update pointer;

generating a local offset table with entries in the slot array and the located one or more updates;

determining an isolation level that indicates whether the read query is precluded from accessing new prepended updates received after the read query;

providing latch-free access to the one or more records to the read query from the local offset table based on the isolation level, wherein an update query has concurrent access to the one or more records;

while performing the accessing, concurrently applying an update from an update query by prepending the update to the located one or more updates;

determining to regenerate the local offset table for the read query based on the isolation level and information of each prepended update; and

maintaining the generated local offset table when the isolation level precludes reading the prepended update or records requested by the read access are absent from the information.

13. The computer-readable device of claim 12, the operations further comprising:

changing the update pointer to a pointer of the applied update; and

receiving an attribute identifying an isolation level of the access request.