Index with entries that store the key of a row and all non-key values of the row

• US 6,128,610 A
• Filed: 08/25/1998
• Issued: 10/03/2000
• Est. Priority Date: 07/09/1996
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Freiwald, Chuck, Fazio, Samuel De, Banerjee, Jayanta, Das, Souripriya, Srinivasan, Jagannathan, Nori, Anil
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US09/139,526
• Time in Patent Office: 770 Days
• Field of Search: 707/1-5, 707/100-103, 707/201-205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus for efficiently storing and retrieving data in a database using index-only tables is disclosed. Storing a row of data in a database using index-only tables involves storing in a leaf node an index entry that includes a key value along with all other values in the row of data. If the row of data exceeds a predetermined size, then a portion of the row of data is stored in a user specified overflow area. Retrieving a row of data from an index-only table for a user-supplied key involves identifying a leaf node for the key, and reading a row of data from the index entry and any remaining portion from the overflow area when the row exceeds the predetermined size.

Claims

1. A method for storing data in a database, the method comprising the steps of:

receiving a row of data from a client;

wherein said row includes a set of one or more key columns and a set of one or more non-key columns;

identifying a key value in said set of one or more key columns of said row of data;

locating an index in said database that is built on said set of one or more key columns;

wherein said index has a plurality of branch levels populated with branch nodes;

identifying a leaf node in said index by traversing each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and

storing in said leaf node an index entry that includes said key value and all other values in said row of data.

2. The method of claim 1, wherein the step of storing includes storing at least a portion of said other values in an overflow area.

3. The method of claim 2, wherein the step of storing at least a portion of said other values includes storing at least a portion of said other values in a user specified overflow area.

4. The method of claim 1, the method further comprising the steps of:

wherein the leaf node resides on a storage block that has space available to entirely store the row of data,

determining whether the row of data exceeds a threshold size, and

if the row of data exceeds said threshold size, then storing a portion of said row of data in an overflow area.

5. The method of claim 4, wherein the step of determining whether the row of data exceeds a predetermined size includes determining whether the row of data exceeds a user specified threshold size.

6. The method of claim 5, wherein the step of determining whether the row of data exceeds a user specified threshold includes determining whether the row of data exceeds a user specified percentage of a block size.

7. The method of claim 1 wherein said step of identifying a leaf node includes finding said leaf node in a B-tree index.

8. A method for retrieving data from a database for a user-supplied key, the method comprising the steps of:

identifying an index entry in a leaf node of an index based on said user-supplied key;

wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data;

determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount;

if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and

if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area.

9. The method of claim 8, wherein the step of reading a first portion and a second portion includes reading the second portion of the row of data from a user specified row overflow area.

10. A method for retrieving data from a database for a user-supplied key, the method comprising the steps of:

receiving one or more SQL statements requesting data from said database;

in response to receiving said one or more SQL statements, performing the steps of;

identifying an index entry in a leaf node of an index based on said user-supplied key;

wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data;

determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount;

if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and

if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area.

11. A computer-readable medium carrying one or more sequences of one or more instructions for storing data in a database, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of:

receiving a row of data from a client;

wherein said row includes a set of one or more key columns and a set of one or more non-key columns;

identifying a key value in said set of one or more key columns of said row of data;

locating an index in said database that is built on said set of one or more key columns;

wherein said index has a plurality of branch levels populated with branch nodes;

identifying a leaf node in said index by traversing each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and

storing in said leaf node an index entry that includes said key value and all other values in said row of data.

12. The computer-readable medium of claim 11, wherein the step of storing includes storing at least a portion of said other values in an overflow area.

13. The computer-readable medium of claim 12, wherein the step of storing at least a portion of said other values includes storing at least a portion of said other values in a user specified overflow area.

21. The computer-readable of claim 11, the method further comprising the steps of:

wherein the leaf node resides on a storage block that has space available to entirely store the row of data,

determining whether the row of data exceeds a threshold size, and

if the row of data exceeds said threshold size, then storing a portion of said row of data in an overflow area.

22. The computer-readable of claim 21, wherein the step of determining whether the row of data exceeds a predetermined size includes determining whether the row of data exceeds a user specified threshold size.

23. The computer-readable of claim 22, wherein the step of determining whether the row of data exceeds a user specified threshold includes determining whether the row of data exceeds a user specified percentage of a block size.

24. The computer-readable of claim 11, wherein said step of identifying a leaf node includes finding said leaf node in a B-tree index.

14. A computer-readable medium carrying one or more sequences of one or more instructions for retrieving data from a database for a user-supplied key, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of:

identifying an index entry in a leaf node of an index based on said user-supplied key;

wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data;

determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount;

if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and

if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area.

15. The computer-readable medium of claim 14, wherein the step of reading a first portion and a second portion includes reading the second portion of the row of data from a user specified row overflow area.

16. A database system, comprising:

a processor,

a memory coupled to said processor;

a database;

an index that has a plurality of branch levels populated with branch nodes,

said index is built on a set of one or more key columns of a row of data;

said processor being configured to identify a leaf node in an index based on a key value by traversing each branch level of said plurality of branch levels;

said processor being configured to traverse each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and

said processor being configured to store in said leaf node an index entry that includes said key value and all other values in said row of data.

17. The database system of claim 16, wherein said processor is configured to store said index entry in said leaf node by storing at least a portion of said other values in a user specified overflow area.

18. The database system of claim 16 wherein:

said processor is configured to store at least a portion of said index entry in a storage block that may be used to store up to a maximum amount of data;

said processor is configured to identify the index entry in said leaf node based on a user-supplied key;

said processor is configured to determine whether the index entry has a size that exceeds a row threshold that is less than the maximum amount of data;

said processor is configured to read a row of data from the index entry if the index entry has a size that exceeds the row threshold; and

said processor is configured to read a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area if the index entry has a size that exceeds the row threshold.

19. The database system of claim 18, wherein said processor is configured to read the second portion by reading a user specified row overflow area.

20. A database system that includes an index stored on a storage device, wherein:

the database system has no separately stored table that corresponds to the index;

the index is built on key values contained in rows that are stored in the index itself;

entries within the index include both a key value for a row and all other values for the row; and

the index has plurality of branch levels populated with branch nodes;

the database system is configured to identify a leaf node containing a particular row by traversing each branch level of said plurality of branch levels; and

the database system is configured to traverse each branch level by comparing said key value for the row to a key value associated with a branch node at said each branch level.