Indexing to efficiently manage versioned data in a database system

• US 7,047,250 B1
• Filed: 09/27/2002
• Issued: 05/16/2006
• Est. Priority Date: 09/28/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Murthy, Ravi, Agarwal, Nipun
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US10/260,161
• Time in Patent Office: 1,327 Days
• Field of Search: 707 1- 5, 707100-1041, 707201-206, 707/7, 707/8, 709/201, 709/203, 709/206, 709/207, 709/221, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method and apparatus for accessing information using indexes on versioned tables is described that exploits the power of partitioned indexing to index versioned data. In partitioned indexing, an index is divided in sub-indexes, referred to as index partitions. An index may be, for example, partitioned according to a particular version identified by a version id, that is, each index partition indexes the rows in a versioned table that belong to the version identified by a particular version id. Partitioned indexes can be more efficient to use to access versioned data. The utility of partitioned indexes extends beyond indexing versioned data.

Claims

1. A method of indexing a table, the method comprising the steps of:

storing, in a first index partition of a partitioned index, entries that index a first set of rows, wherein the first set of rows belongs to said table and contains a first value in a partition key of said table, wherein said partitioned index includes said first index partition and a second index partition,

wherein said table is not partitioned on the partition key; and

storing, in said second index partition, entries that index a second set of rows, wherein the second set of rows belongs to said table and contains a second value in the partition key.

2. The method of claim 1, wherein:

said partitioned index includes a plurality of partitions that include said first index partition;

the steps further include;

receiving a database statement;

detecting that the database statement requires rows from said table that have said first value in said partition key; and

in response to detecting that the database statement requires rows from said table that have said first value in said partition key, of said plurality of partitions, accessing only said first index partition to execute said database statement.

3. The method of claim 2, wherein:

a database server stores an attribute value associated with a user; and

said database server causes the step of accessing only said first index partition based on said attribute value.

4. The method of claim 3, wherein said database server causes the step of accessing only said first index partition by performing one or more steps that include adding a predicate to said database statement to create a transformed database statement, wherein said predicate is based on said partition key and said attribute value.

5. The method of claim 1, wherein:

storing in a first index partition of a partitioned index includes storing in said first index partition an entry that indexes a row that has said first value and said second value in said partition key; and

storing in said second index partition includes storing in said second index partition another entry that indexes said row.

6. The method of claim 1, wherein said table is a partitioned table that includes a plurality of table partitions.

7. The method of claim 1, wherein said partition key contains values that identify row versions.

8. The method of claim 1, wherein:

said first set of rows and said second set of rows hold versioned data; and

the steps further include storing in a third set of rows data that is not versioned.

9. The method of claim 8, further including storing, in a third index partition of said partitioned index, entries that only index said third set of rows.

10. The method of claim 1, wherein:

said table is a non-partitioned table.

11. The method of claim 1, wherein:

said table is a partitioned table.

12. The method of claim 11, wherein:

said partitioned table is partitioned by values in a different column than the partition key.

13. A computer-readable medium carrying one or more sequences of instructions for indexing a table, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

storing, in a first index partition of a partitioned index, entries that index a first set of rows, wherein the first set of rows belongs to said table and contains a first value in a partition key of said table, wherein said partitioned index includes said first index partition and a second index partition,

wherein said table is not partitioned on the partition key; and

storing, in said second index partition, entries that index a second set of rows, wherein the second set of rows belongs to said table and contains a second value in the partition key.

14. The computer-readable medium of claim 13, wherein:

said partitioned index includes a plurality of partitions that include said first index partition;

the steps further include;

receiving a database statement;

detecting that the database statement requires rows from said table that have said first value in said partition key; and

in response to detecting that the database statement requires rows from said table that have said first value in said partition key, of said plurality of partitions, accessing only said first index partition to execute said database statement.

15. The computer-readable medium of claim 14, wherein:

a database server stores an attribute value associated with a user; and

said database server causes the step of accessing only said first index partition based on said attribute value.

16. The computer-readable medium of claim 15, wherein said database server causes the step of accessing only said first index partition by performing one or more steps that include adding a predicate to said database statement to create a transformed database statement, wherein said predicate is based on said partition key and said attribute value.

17. The computer-readable medium of claim 13, wherein:

storing in a first index partition of a partitioned index includes storing in said first index partition an entry that indexes a row that has said first value and said second value in said partition key; and

storing in said second index partition includes storing in said second index partition another entry that indexes said row.

18. The computer-readable medium of claim 13, wherein said table is a partitioned table that includes a plurality of table partitions.

19. The computer-readable medium of claim 13, wherein said partition key contains values that identify row versions.

20. The computer-readable medium of claim 13, wherein:

said first set of rows and said second set of rows hold versioned data; and

the steps further include storing in a third set of rows data that is not versioned.

21. The computer-readable medium of claim 20, further including storing, in a third index partition of said partitioned index, entries that only index said third set of rows.

22. The computer-readable medium of claim 13, wherein:

said table is a non-partitioned table.

23. The computer-readable medium of claim 13, wherein:

said table is a partitioned table.

24. The computer-readable medium of claim 23, wherein:

said partitioned table is partitioned by values in a different column than the partition key.

25. A database system configured for indexing a table, said database system comprising:

means for storing, in a first index partition of a partitioned index, entries that index a first set of rows, wherein the first set of rows belongs to said table and contains a first value in a partition key of said table, wherein said partitioned index includes said first index partition and a second index partition,

wherein said table is not partitioned on the partition key; and

means for storing, in said second index partition, entries that index a second set of rows, wherein the second set of rows belongs to said table and contains a second value in the partition key.

26. The database system of claim 25, wherein:

said partitioned index includes a plurality of partitions that include said first index partition;

said database system further comprising;

means for receiving a database statement;

means for detecting that the database statement requires rows from said table that have said first value in said partition key; and

means for, in response to detecting that the database statement requires rows from said table that have said first value in said partition key, of said plurality of partitions, accessing only said first index partition to execute said database statement.