Index-only tables with nested group keys

Abstract

A method and apparatus for building, maintaining, and using a multi-level index is provided. The multi-level index is accessed using a key. The key is divided into multiple portions referred to as sub-keys. The first level of the multi-level index is built on a first-level sub-key. Each index entry at the first-level is for a particular first-level sub-key value, and either includes sub-entries associated with second-level sub-key values or a reference to a second-level data retrieval structure. All second-level data retrieval structures are built on the portion of the key that has been designated as the second-level sub-key. As the vocabulary of the first-level sub-key becomes exhausted, fewer maintenance operations will have to be performed to maintain the first-level data retrieval structure. This decreases the overhead and increases the concurrency in a database system that uses the multiple-level index. The multi-level index structure is especially suited for queries that retrieve all values for a given first-level sub-key. The structure also has reduced storage costs compared to a single-level index structure, since first-level sub-key values are stored only once for each nested group.

Claims

What is claimed is:

1. A method for building a multiple-level index on a key, the method comprising the steps of:

dividing said key into a plurality of sub-keys;

building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and

building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and

establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.

2. The method of claim 1 wherein:

if the size of a group of second-level sub-key values associated with a first-level sub-key value is less than a predetermined threshold, then storing in said first-level data retrieval structure sub-entries that identify said second-level sub-key values that are associated with said first-level sub-key value; and

if the size of the group of second-level sub-key values associated with said first-level sub-key value exceeds said predetermined threshold, then creating a second-level data retrieval structure for said first-level sub-key value based on said second-level sub-key values.

3. The method of claim 1 wherein:

the step of building a first-level data retrieval structure includes building one of a B-tree or hash table based on said first-level sub-key; and

the step of building a second-level data retrieval structure includes building one of a B-tree or hash table based on said second-level sub-key.

4. The method of claim 3 wherein:

the step of building a second-level data retrieval structure includes building a second-level B-tree based on said second-level sub-key, said second-level B-tree having a plurality of leaf nodes;

the method further comprises the steps of:

linking said plurality of leaf nodes to form a leaf node chain; and

establishing a link between said index entry associated with said particular first-level sub-key value and a first leaf node in said leaf node chain.

5. The method of claim 4 further comprising the steps of:

receiving a query that requests information from all index entries associated with said particular first-level sub-key value;

traversing said first-level B-tree to locate said index entry associated with said particular first-level sub-key value;

following said link from said index entry to said first leaf node in said leaf node chain; and

following said leaf node chain to retrieve information from said plurality of leaf nodes.

6. The method of claim 1 wherein:

the key is a combination of a word value and a document identifier; and

the step of dividing the key into a plurality of sub-keys includes establishing the word value as the first-level sub-key and the document identifier as the second level sub-key;

the step of building a first-level data retrieval structure includes building a first-level data retrieval structure based on word values contained in said key; and

the step of building a second-level data retrieval structure includes building a second-level data retrieval structure based on document identifiers associated with a particular word value.

7. A method for indexing data based on a key, the method comprising the steps of:

dividing said key into a plurality of sub-keys;

building a B-tree based on a first-level sub-key of said plurality of sub-keys;

inserting an index entry into said B-tree by performing the steps of

receiving a request to insert a row of data;

reading a key value from said row of data;

dividing said key value into a plurality of sub-key values, said plurality of sub-key values including a first-level sub-key value;

traversing said B-tree to locate a leaf node of said B-tree that is associated with a range that includes said first-level sub-key value;

determining whether said leaf node already contains an entry for said first-level sub-key value;

if said leaf node does not already contain an entry for said first-level sub-key value, then inserting an entry for said first-level sub-key value into said leaf node;

creating a sub-entry that contains all sub-key values other than said first-level sub-key value and all non-key column values of said row of data; and

storing said sub-entry in said entry for said first-level sub-key value.

8. The method of claim 7 further comprising the steps of:

determining whether the size of sub-entries associated with said entry for said first-level sub-key value exceeds a predetermined threshold; and

if the size of sub-entries associated with said entry for said first-level sub-key value exceeds a predetermined threshold, then

building a second-level data retrieval structure based on a second-level sub-key of said plurality of sub-keys;

storing said sub-entries that reside in said entry for said first-level sub-key value in said second-level data retrieval structure;

removing said sub-entries from said entry for said first-level sub-key value; and

storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure.

9. The method of claim 8 wherein:

the step of building a second-level data retrieval structure includes the step of building a second-level B-tree; and

the step of storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure includes the step of storing in said entry for said first-level sub-key value a pointer to a root node of said second-level B-tree.

10. The method of claim 9 wherein:

the method further includes the step of linking leaf nodes of said second-level B-tree to form a leaf node chain; and

the step of storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure further includes the step of storing in said entry for said first-level sub-key value a pointer to a first leaf node in said leaf node chain.

11. The method of claim 8 wherein the step of building a second-level data retrieval structure includes the step of building a second-level hash table.

12. The method of claim 8 further comprising the steps of:

receiving a query that specifies said key value;

reading said first-level sub-key value from said key value contained in said query;

traversing said B-tree based on said first-level sub-key value to locate said leaf node associated with said range that includes said first-level sub-key value;

locating said entry for said first-level sub-key value within said leaf node;

using said reference to said second-level data retrieval structure to locate said second-level data retrieval structure;

reading a second-level sub-key value from said key value contained in said query;

using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure; and

reading said non-key column values from said sub-entry.

13. The method of claim 12 wherein:

said second-level data retrieval structure is a second-level B-tree; and

the step of using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure includes traversing said second-level B-tree based on said second-level sub-key value.

14. The method of claim 12 wherein:

said second-level data retrieval structure is a hash table; and

the step of using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure includes performing a hash function on said second-level sub-key value.

15. A computer-readable medium having stored thereon sequences of instructions for building a multiple-level index on a key, the sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of:

dividing said key into a plurality of sub-keys;

building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and

building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and

establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.

16. The computer-readable medium of claim 15 further including instructions for:

if a first-level sub-key value is associated with a group of second-level sub-key values whose total size is less than a predetermined threshold, then storing in said first-level data retrieval structure sub-entries that identify said second-level sub-key values that are associated with said first-level sub-key value; and

if said first-level sub-key value is associated with a group of second-level sub-key values whose total size exceeds said predetermined threshold, then creating a second-level data retrieval structure for said first-level sub-key value based on said second-level sub-key values.

17. The computer-readable medium of claim 15 wherein:

the step of building a first-level data retrieval structure includes building a first-level B-tree based on said first-level sub-key; and

the step of building a second-level data retrieval structure includes building one of a B-tree or a hash table based on said second-level sub-key.

18. The computer-readable medium of claim 17 wherein:

the step of building a second-level data retrieval structure includes building a second-level B-tree based on said second-level sub-key, said second-level B-tree having a plurality of leaf nodes;

the computer-readable medium further comprises instructions for performing the steps of:

linking said plurality of leaf nodes to form a leaf node chain; and

establishing a link between said index entry associated with said particular first-level sub-key value and a first leaf node in said leaf node chain.

19. The computer-readable of claim 18 further comprising instructions for performing the steps of:

receiving a query that requests information from all index entries associated with said particular first-level sub-key value;

traversing said first-level B-tree to locate said index entry associated with said particular first-level sub-key value;

following said link from said index entry to said first leaf node in said leaf node chain; and

following said leaf node chain to retrieve information from said plurality of leaf nodes.

20. The computer-readable medium of claim 15 wherein:

the key is a combination of a word value and a document identifier; and

the step of dividing the key into a plurality of sub-keys includes establishing the word value as the first-level sub-key and the document identifier as the second level sub-key;

the step of building a first-level data retrieval structure includes building a first-level data retrieval structure based on word values contained in said key; and

the step of building a second-level data retrieval structure includes building a second-level data retrieval structure based on document identifiers associated with a particular word value.

Description

FIELD OF THE INVENTION

The present invention relates to database systems, and more particularly, to index structures used for accessing data stored in database systems.

BACKGROUND OF THE INVENTION

Many information retrieval applications make use of inverted indexes when performing content-based searches on text document collections. Typically, such inverted indexes are implemented using a table and a B-tree index.

Each row in the table has the form <word, doc.sub.-- oid, occurrence-data>, where "doc.sub.-- oid" is an identifier for a document in the document collection, "word" is a word that exists in the document identified by the doc.sub.-- oid, and "occurrence-data" is data that indicates the number of times the word appears in the specified document and the locations of the word within the specified document. For example, the row <happy, X, 3, "5 8 21"> indicates that the word "happy" appears three times in document X, at locations 5, 8 and 21.

To speed up retrieval of data from a table used to implement the inverted index, a B-tree index is typically built on the <word, doc.sub.-- oid> columns of the table. Thus, each index entry in the B-tree has the form <›word, doc.sub.-- oid!, rowid>, where rowid uniquely identifies the row within the table that corresponds to the index entry. For example, assuming that the row given above is row 10 of the table, the index entry for the row would be <›happy, X!, 10>.

The conventional "table plus B-tree" approach to implementing an inverted index has numerous drawbacks. For example, there is a large degree of duplication between the data stored in the index and the data stored in the table. Specifically, every <word, doc.sub.-- oid> value is stored in both the table and the index. In the example given above, the value ›happy, X! is stored in both the table and the B-tree index. This redundancy can be an expensive waste of storage since the inverted index for a large set of documents can be huge.

Another disadvantage with conventional inverted indexes is that an enormous amount of overhead may be required to support incremental updates to the inverted index. Specifically, when a document is dynamically added or deleted from the collection associated with the inverted index, a large number of entries must be added to or deleted from both the B-tree index and the table. The addition or deletion of index entries in the B-tree may result in splitting and merging of B-tree nodes. Such operations may be very expensive, since the splits or merges may go all the way to the root of a massive B-tree.

Yet another disadvantage of the conventional implementation of inverted indexes is amount of overhead required for the retrieval of all entries for a given word. This type of request is common in information retrieval environments. To handle a request for all entries for a given word, the B-tree index must be accessed to get each index entry for the specified word. The rowids within each such index entry is then used to retrieve the corresponding row from the table. It would be more efficient if the data is available in the B-tree index leaf nodes.

Based on the foregoing, it is clearly desirable to provide a structure for implementing an inverted index that does not involve as much duplication of data as conventional implementations. It is further desirable to provide an indexing mechanism where the balance can be maintained with less overhead than that required to maintain conventional inverted indexes. It is further desirable to provide a more efficient technique for extracting information from inverted indexes.

SUMMARY OF THE INVENTION

A method and apparatus for constructing and using a multiple-level index are provided. According to the method, the key to the index is divided into two or more sub-keys. A first-level data retrieval structure, such as a B-tree or hash table, is built on a first-level sub-key of the two or more sub-keys.

Each index entry in the first-level data retrieval structure is for a particular first-level sub-key value. According to one aspect of the invention, each index entry in the first-level data retrieval structure includes either a set of sub-entries, or a reference to a second-level data retrieval structure that is built on a second-level sub-key.

Specifically, sub-entries for a particular first-level sub-key value are stored in the index entry for that first-level sub-key value until the space occupied by the set of sub-entries exceeds a predetermined threshold. When the threshold is exceeded, the sub-entries are removed from the index entry in the first-level data retrieval structure and stored in a second-level data retrieval structure that is built on the second-level sub-key.

According to another aspect of the invention, each sub-entry for a given first-level sub-key value includes a second-level sub-key value and data from all of the non-key columns that correspond to the particular first-level sub-key/second-level sub-key combination. Because the actual data from the non-key columns is stored within the index structure itself, the index does not have to be used in combination with a table. Consequently, values that constitute the key to the index do not have to be stored redundantly, and use of the index does not require the additional step of retrieving information stored in a table associated with the index.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 is a block diagram of a computer system that may be used to implement embodiments of the present invention;

FIG. 2 is a block diagram of an index-only table with a row overflow area according to an embodiment of the invention;

FIG. 3 is a block diagram of a two-level data retrieval structure according to an embodiment of the invention;

FIG. 4A is a portion of a flow chart that illustrates steps performed to add an index entry to the two-level data retrieval structure shown in FIG. 3;

FIG. 4B is another portion of the flow chart that illustrates steps performed to add an index entry to the two-level data retrieval structure shown in FIG. 3;

FIG. 5 is a block diagram of a four-level data retrieval structure according to an embodiment of the invention; and

FIG. 6 is a block diagram of a two-level index plus table arrangement according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A method and apparatus for implementing inverted indexes using an index-only table with nested group keys is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

HARDWARE OVERVIEW

Referring to FIG. 1, it is a block diagram of a computer system 100 upon which an embodiment of the present invention can be implemented. Computer system 100 includes a bus 101 or other communication mechanism for communicating information, and a processor 102 coupled with bus 101 for processing information. Computer system 100 further comprises a random access memory (RAM) or other dynamic storage device 104 (referred to as main memory), coupled to bus 101 for storing information and instructions to be executed by processor 102. Main memory 104 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 102. Computer system 100 also comprises a read only memory (ROM) and/or other static storage device 106 coupled to bus 101 for storing static information and instructions for processor 102. Data storage device 107 is coupled to bus 101 for storing information and instructions.

A data storage device 107 such as a magnetic disk or optical disk and its corresponding disk drive can be coupled to computer system 100. Computer system 100 can also be coupled via bus 101 to a display device 121, such as a cathode ray tube (CRT), for displaying information to a computer user. An alphanumeric input device 122, including alphanumeric and other keys, is typically coupled to bus 101 for communicating information and command selections to processor 102. Another type of user input device is cursor control 123, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 102 and for controlling cursor movement on display 121. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), which allows the device to specify positions in a plane.

Alternatively, other input devices such as a stylus or pen can be used to interact with the display. A displayed object on a computer screen can be selected by using a stylus or pen to touch the displayed object. The computer detects the selection by implementing a touch sensitive screen. Similarly, a light pen and a light sensitive screen can be used for selecting a displayed object. Such devices may thus detect selection position and the selection as a single operation instead of the "point and click," as in a system incorporating a mouse or trackball. Stylus and pen based input devices as well as touch and light sensitive screens are well known in the art. Such a system may also lack a keyboard such as 122 wherein all interface is provided via the stylus as a writing instrument (like a pen) and the written text is interpreted using optical character recognition (OCR) techniques.

The present invention is related to the use of computer system 100 to build, maintain and use index-only table with nested group keys. According to one embodiment, these operations are performed by computer system 100 in response to processor 102 executing sequences of instructions contained in memory 104. Such instructions may be read into memory 104 from another computer-readable medium, such as data storage device. Execution of the sequences of instructions contained in memory 104 causes processor 102 to perform the process steps that will be described hereafter. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the present invention. Thus, the present invention is not limited to any specific combination of hardware circuitry and software.

INDEX-ONLY TABLES

According to one embodiment of the invention, an inverted index is implemented using an index-only table. An index-only table is similar to a conventional table with an index on one or more of its columns. Users may access and manipulate index-only tables using the same operations that can be performed on conventional tables. However, an index-only table differs from a standard table in that instead of maintaining two separate data structures (i.e. a table and an index), the database server only maintains an index with no actual table.

Each entry in an index-only table contains both the encoded key value and the associated column values for the corresponding row. That is, rather than having row ROWID as the second element of the index entry, the actual data from the corresponding row is stored in the index. Thus, every index entry for an index-only table has the form <primary.sub.-- key.sub.-- value, non.sub.-- primary.sub.-- key.sub.-- column.sub.-- values>.

As mentioned above, conventional inverted index implementations store the values in the primary key columns in both an index and in a corresponding table. In contrast, values from the key columns are stored only in the index of an index-only table. There is no corresponding table. Consequently, the use of index-only tables to implement inverted indexes avoids the storage waste associated with the data duplication involved with conventional inverted index implementations.

In addition, the use of index-only tables reduces the number of steps required to use an inverted index. Specifically, an index-only table may be traversed to identify the index entries associated with a particular key value. However, rowids within the index entries are not used to retrieve rows from a table. Rather, the index entries themselves contain all of the information that conventionally would have been stored in the table. Therefore, the extra step of retrieving rows from a table is avoided.

USING INDEX-ONLY TABLES

As with conventional tables, clients manipulate index-only tables by submitting statements to the database server in the database language supported by the database server. However, all operations on the data in the table are performed by manipulating the corresponding index.

According to an embodiment of the invention, the same database commands used to build and access a conventional table and index are used to build and access index-only tables. For example, an index-only table can be created to model an inverted index for an information retrieval client in the following manner:

    ______________________________________
    CREATE TABLE docindex
    (   token char(20),
    doc.sub.-- oid integer,
    token.sub.-- frequency smallint,
    token.sub.-- occurrence.sub.-- data varchar(512),
    CONSTRAINT pk.sub.-- docindex PRIMARY KEY (token, doc.sub.-- oid))
    ORGANIZATION INDEX AREA text.sub.-- collection
    PCTTHRESHOLD 20
    OVERFLOW AREA text.sub.-- collection.sub.-- overflow;
    ______________________________________

• Inventors
  Srinivasan, Jagannathan; DeFazio, Samuel; Banerjee, Jayanta; Freiwald, Chuck; Das, Souripriya;
• Assignee
  Oracle Corporation (Redwood Shores, CA)
• Published
  Dec-22-1998
• Current US Classes:
  707/201
  707/3
  707/4
  707/6
• Application #
  764112
• International Classes
  G06F 017/00
• Field of Search
  707/1-10 707/201 707/522 707/532 707/526 382/230
• Examiner
  Black; Thomas G.
• Agent
  McDermott, Will & Emery
• US Patent References:
  5404514
  5551027
  5619709
  5623679
  5623681
  5706365