In-place index repair

Patent metadata

Field	Value
Publication number	US-9400817-B2
Application number	US-201314145618-A
Country	US
Kind code	B2
Filing date	Dec 31, 2013
Priority date	Dec 31, 2013
Publication date	Jul 26, 2016
Grant date	Jul 26, 2016

Abstract

Disclosed herein are system, method, and computer program product embodiments for sorting a disarranged index keys in an index. First an operation is performed on a table that includes an index set on at least one column, where the operation causes the index keys in the index to become disarranged. The disarranged index keys are rearranged into a proper order using an in-place index sort. To rearrange the index keys in the index, a determination is made whether the index is a tail-end index and whether the index is a fixed-size index. Based on the determination, the in-place index sort is performed on the index, where the in-place index sort arranges the index keys in the index into the proper order.

First claim

What is claimed is:

1. A method, comprising:
performing an operation on a database table comprising an index, wherein the index is set on at least one column having duplicate values, and wherein the operation scrambles index keys of the index that are set on the duplicate values of the at least one column out of order; and
reordering, using an in-place index sort, the index set on the at least one column in the database table, wherein reordering the index in-place unscrambles the index keys.

2. The method of claim 1 , further comprising:
determining the index as a tail-end index, wherein the index is the tail-end index when the index is set in order on a first column and a second column of the at least one columns; and
wherein the reordering is based on the determining.

3. The method of claim 2 , wherein performing the in-place index sort on the index further comprises:
performing the in-place index sort on the index wherein the first column and the second column are sorted in the order the index is set on the first column and the second column.

4. The method of claim 1 , further comprising:
determining the index as a fixed-size index,
wherein the index is the fixed-size index when the at least one column includes rows of a fixed width; and
wherein the reordering is based on the determining.

5. The method of claim 1 , further comprising:
determining a key group including a first column and a second column of the at least one column, wherein the first column is to the left of the second column, and wherein values in the first column in the key group are duplicates of each other; and
sorting, using the in-place index sort, index keys of the second column, wherein the index keys of the second column are associated with values that are duplicates of each other.

6. The method of claim 1 , wherein performing the operation further comprises copying the database table from a first location to a second location as part of a database compaction operation that reorganizes physical memory space in a database system.

7. The method of claim 1 , wherein performing the operation further comprises changing a sorting order of a fixed-length data in the database table.

8. The method of claim 1 , wherein an index key of the index keys includes mapping of a logical memory location of a row in the at least one column to a physical memory location of the row in the at least one column.

9. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
perform an operation on a database table comprising an index, wherein the index is set on at least one column having duplicate values, and wherein the operation scrambles index keys of the index that are set on the duplicate values out of order; and
reorder, using an in-place index sort, the index set on the at least one column in the database table, wherein reordering the index in-place unscrambles the index keys.

10. The system of claim 9 , further comprising:
determining the index as a tail-end index, wherein the index is the tail-end index when the index is set in order on a first column and a second column of the at least one columns; and
wherein the reordering is based on the determining.

11. The system of claim 10 , wherein to perform the in-place index sort on the index the at least one processor is further configured to:
perform the in-place index sort on the index where the first column and the second column are sorted in the order the index is set on the first column and the second column.

12. The system of claim 9 , further comprising:
determining the index as a fixed-size index wherein the index is the fixed-size index when the at least one column includes rows of a fixed width; and
wherein the reordering is based on the determining.

13. The system of claim 9 , wherein the at least one processor is
further configured to:
determine a key group including a first column and a second column of the at least one column, wherein the first column is to the left of the second column, and wherein values in the first column in the key group are duplicates of each other; and
sort, using the in-place index sort, index keys of the second column, wherein the index keys of the second column are associated with values that are duplicates of each other.

14. The system of claim 9 , wherein to perform the operation, the at least one processor is further configured to copy the database table from a first location to a second location as part of a database compaction operation that reorganizes physical memory space in a database system.

15. The system of claim 9 , wherein an index key of the index keys includes mapping of a logical memory location of a row in the at least one column to a physical memory location of the row in the at least one column.

16. The system of claim 9 , wherein to perform the operation the at least one processor is further configured to change the sorting order of fixed-length data.

17. A 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:
performing an operation on a database table comprising an index, wherein the index is set on at least one column having duplicate values, and wherein the operation scrambles index keys of the index that are set on the duplicate values out of order; and
reordering, using an in-place index sort, the index set on the at least one column in the database table, wherein reordering the index in place unscrambles the index keys.

18. The computer-readable device of claim 17 , the operations further comprising:
determining the index as a tail-end index, wherein index is the tail-end index when the index is set in order on a first column and a second column of the at least one columns; and
wherein the reordering is based on the determining.

19. The computer-readable device of claim 18 , wherein to perform the in-place index sort on the index, the operations further comprise:
performing the in-place index sort on the index where the first column and the second column are sorted in the order the index is set on the first column and the second column.

20. The computer-readable device of claim 17 , wherein the operations further comprise:
determining the index as a fixed-size index, wherein the index is the fixed-size index when the at least one column includes rows of a fixed width; and
wherein the reordering is based on the determining.

Assignees

• Wildermuth Elton
• Sybase Inc

Inventors

• Wildermuth Elton

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F17/30336 Primary

  Physics · mapped topic

• G06F17/30321

  Physics · mapped topic