Database Backup and Restore with Integrated Index Reorganization

• US 20120221523A1
• Filed: 05/07/2012
• Published: 08/30/2012
• Est. Priority Date: 08/07/2009
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Bendakovsky, Amit, Hrle, Namik, Ritter, Thomas
• Granted Patent: US 8,626,717 B2
• Time in Patent Office: Days
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2201/80 Database-specific techniques

Abstract

According to an embodiment of the present invention, a method for reorganizing a source index tree of a database table resulting in a target index tree of the database table is provided. A backup process reads source leaf pages of the source index tree in a logical order defined by a sequence of index keys. The logical order can be different from a physical order of the source leaf pages defined by a sequence of respective storage locations. The backup process constructs target leaf pages of the target index tree maintaining the logical order. A restore process constructs target non-leaf pages of the target index tree based on the distribution of the index keys among the constructed leaf pages and stores the target leaf and non-leaf pages.

Claims

1. A method for reorganizing a source index tree of a database table resulting in a target index tree of the database table, the method comprising:

performing a backup of the source index tree from respective source storage locations, wherein the source index tree comprises source leaf pages and source non-leaf pages, wherein the source leaf pages comprise index records specifying respective index keys and respective table row identifiers of the database table, a source logical order defined by a sequence of the respective index keys of the index records, and a source physical order defined by a sequence of the respective source storage locations, wherein the source physical order of the source leaf pages being possibly different from the source logical order of the source leaf pages, and wherein performing the backup of the source index tree from the source storage locations comprises;

determining a sequence of the source storage locations according to the source logical order of the source leaf pages,

reading the source leaf pages from the source storage locations according to the determined sequence of the source storage locations, and

constructing target leaf pages of the target index tree, the target leaf pages having copies of the index records and a target logical order defined by the sequence of the index keys of the copies of the index records; and

performing a restore of the target index tree at target storage locations, wherein performing the restore of the target index tree at target storage locations comprises;

writing the constructed target leaf pages to the respective target storage locations defining a target physical order of the target leaf pages, the target physical order corresponding to the target logical order of the target leaf pages,

constructing target non-leaf pages of the target index tree based on the distribution of the index keys among the constructed leaf pages, and

writing the constructed target non-leaf pages to the respective target storage locations.

2. The method of claim 1, wherein a source database management component performs the backup step and a target database management component performs the restore step, and wherein the method further comprises:

writing the constructed target leaf pages to respective copy storage locations by the source database management component; and

reading the constructed target leaf pages from the respective copy storage locations by the target database management component.

3. The method of claim 1, wherein a database management component performs the backup step and the restore step.

4. The method of claim 1, wherein constructing the target leaf pages further comprises:

reading the index records from the read source leaf pages;

distributing the read index records among multiple sets of sorted index records, the sets having pre-defined maximum numbers of index records, and thereby maintaining the sequence of the respective index keys of the distributed index records;

constructing target leaf pages having a pre-defined size; and

inserting the sets of sorted index records into the respective constructed target leaf pages.

5. The method of claim 1, wherein constructing the target leaf pages further comprises:

copying the source leaf pages to the respective target leaf pages, and thereby maintaining a distribution of the index records.

7. The method of claim 1, wherein each leaf page comprises at least one of the following:

a reference to a respective predecessor leaf page and a reference to a respective successor leaf page, and wherein the predecessor leaf page, the leaf page, and the successor leaf page are defined by the logical order of the leaf pages, and the references to predecessor and successor leaf pages are associated with respective storage locations.

8. The method of claim 1, wherein, while a first operating system process is writing the constructed target leaf pages, a second operating system process is constructing and writing the target non-leaf pages according to the distribution of the index records among the written leaf pages.

9. The method of claim 1, wherein reading the source leaf pages further comprises:

receiving a read request for reading a specific source leaf page from a specific source storage location;

reading a chunk of source leaf pages from the respective source storage locations in response to the read request, the specific source leaf page being a member of the chunk of source leaf pages;

writing the read chunk of source leaf pages to cache storage locations according to the source physical order of the read source leaf pages;

determining a sequence of the cache storage locations according to the source logical order of the source leaf pages; and

reading the source leaf pages from the cache storage locations according to the determined sequence of the cache storage locations.

6. (canceled)

10-14. -14. (canceled)

15. A computer program product for reorganizing a source index tree of a database table resulting in a target index tree of the database table, the computer program product comprising a computer readable storage medium having computer readable program code embodied thereon, wherein the computer readable program code, when executed on a computing device, causes the computing device to:

perform a backup of the source index tree from respective source storage locations, wherein the source index tree comprises source leaf pages and source non-leaf pages, wherein the source leaf pages comprise index records specifying respective index keys and respective table row identifiers of the database table, a source logical order defined by a sequence of the respective index keys of the index records, and a source physical order defined by a sequence respective source storage locations, wherein the source physical order of the source leaf pages being possibly different from the source logical order of the source leaf pages, and wherein the computer readable program code to perform the backup of the source index tree from the source storage locations further causes the computing device to;

determine a sequence of the source storage locations according to the source logical order of the source leaf pages,

read the source leaf pages from the source storage locations according to the determined sequence of the source storage locations, and

construct target leaf pages of the target index tree, the target leaf pages having copies of the index records and a target logical order defined by the sequence of the index keys of the copies of the index records; and

perform a restore of the target index tree at target storage locations, wherein the computer readable program code to perform the restore of the target index tree at target storage locations further causes the computing, device to;

write the constructed target leaf pages to the respective target storage locations defining a target physical order of the target leaf pages, the target physical order corresponding to the target logical order of the target leaf pages,

construct target non-leaf pages of the target index tree based on the distribution of the index keys among the constructed leaf pages, and

write the constructed target non-leaf pages to the respective target storage locations.

16. The computer program product of claim 15, wherein the computer readable program code further causes the computing device to:

write the constructed target leaf pages to respective copy storage locations by the source database management component; and

read the constructed target leaf pages from the respective copy storage locations by the target database management component.

17. The computer program product of claim 15, wherein the computer readable program code to construct the target leaf pages further causes the computing device to:

read the index records from the read source leaf pages;

distribute the read index records among multiple sets of sorted index records, the sets having pre-defined maximum numbers of index records, and thereby maintaining the sequence of the respective index keys of the distributed index records;

construct target leaf pages having a pre-defined size; and

insert the sets of sorted index records into the respective constructed target leaf pages.

18. The computer program product of claim 15, wherein the computer readable program code to construct the target leaf pages further causes the computing device to:

copy the source leaf pages to the respective target leaf pages, and thereby maintaining a distribution of the index records.

19. The computer program product of claim 15, wherein each leaf page comprises at least one of the following:

a reference to a respective predecessor leaf page and a reference to a respective successor leaf page, and wherein the predecessor leaf page, the leaf page, and the successor leaf page are defined by the logical order of the leaf pages, and the references to predecessor and successor leaf pages are associated with respective storage locations.

20. The computer program product of claim 15, wherein the computer readable program code to read the source leaf pages further causes the computing device to:

receive a read request for reading a specific source leaf page from a specific source storage location;

read a chunk of source leaf pages from the respective source storage locations in response to the read request, the specific source leaf page being a member of the chunk of source leaf pages;

write the read chunk of source leaf pages to cache storage locations according to the source physical order of the read source leaf pages;

determine a sequence of the cache storage locations according to the source logical order of the source leaf pages; and

read the source leaf pages from the cache storage locations according to the determined sequence of the cache storage locations.

21. An apparatus for reorganizing a source index tree of a database table resulting in a target index tree of the database table, the apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

perform a backup of the source index tree from respective source storage locations, wherein the source index tree comprises source leaf pages and source non-leaf pages, wherein the source leaf pages comprise index records specifying respective index keys and respective table row identifiers of the database table, a source logical order defined by a sequence of the respective index keys of the index records, and a source physical order defined by a sequence of the respective source storage locations, wherein the source physical order of the source leaf pages being possibly different from the source logical order of the source leaf pages, and wherein the computer readable program code to perform the backup of the source index tree from the source storage locations further causes the computing device to;

determine a sequence of the source storage locations according to the source logical order of the source leaf pages,

read the source leaf pages from the source storage locations according to the determined sequence of the source storage locations, and

construct target leaf pages of the target index tree, the target leaf pages having copies of the index records and a target logical order defined by the sequence of the index keys of the copies of the index records; and

perform a restore of the target index tree at target storage locations, wherein the computer readable program code to perform the restore of the target index tree at target storage locations further causes the computing device to;

write the constructed target leaf pages to the respective target storage locations defining a target physical order of the target leaf pages, the target physical order corresponding to the target logical order of the target leaf pages,

construct target non-leaf pages of the target index tree based on the distribution of the index keys among the constructed leaf pages, and

write the constructed target non-leaf pages to the respective target storage locations.

22. The apparatus of claim 21, wherein the instructions further cause the processor to:

write the constructed target leaf pages to respective copy storage locations by the source database management component; and

read the constructed target leaf pages from the respective copy storage locations by the target database management component.

23. The apparatus of claim 21, wherein the instructions to construct the target leaf pages further cause the processor to:

read the index records from the read source leaf pages;

distribute the read index records among multiple sets of sorted index records, the sets having pre-defined maximum numbers of index records, and thereby maintaining the sequence of the respective index keys of the distributed index records;

construct target leaf pages having a pre-defined size; and

insert the sets of sorted index records into the respective constructed target leaf pages.

24. The apparatus of claim 21, wherein the instructions to construct the target leaf pages further cause the processor to:

copy the source leaf pages to the respective target leaf pages, and thereby maintaining a distribution of the index records.

25. The apparatus of claim 21, wherein each leaf page comprises at least one of the following:

a reference to a respective predecessor leaf page and a reference to a respective successor leaf page, and wherein the predecessor leaf page, the leaf page, and the successor leaf page are defined by the logical order of the leaf pages, and the references to predecessor and successor leaf pages are associated with respective storage locations.

26. The apparatus of claim 21, wherein the instructions to read the source leaf pages further cause the processor to:

receive a read request for reading a specific source leaf page from a specific source storage location;

read a chunk of source leaf pages from the respective source storage locations in response to the read request, the specific source leaf page being a member of the chunk of source leaf pages;

write the read chunk of source leaf pages to cache storage locations according to the source physical order of the read source leaf pages;

determine a sequence of the cache storage locations according to the source logical order of the source leaf pages; and

read the source leaf pages from the cache storage locations according to the determined sequence of the cache storage locations.