Method and apparatus for using incompatible types of indexes to process a single query

• US 5,903,888 A
• Filed: 02/28/1997
• Issued: 05/11/1999
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Cohen, Jeffrey Ira, Ozbutun, Cetin, Jakobsson, Hakan, Depledge, Michael
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Alam, Shahid
• Application Number:
  US08/808,096
• Time in Patent Office: 802 Days
• Field of Search: 707/2, 707/3, 707/4, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A method and apparatus for processing a query combines the use of different index types to minimize the rows of data that need to be retrieved from a table. A first index is accessed based on a query to produce a first result having a first format, for example a bitmap index outputting a bitmap. A second index, for example a B-tree index, is also accessed based on the query to produce a second result having a second format, for example a sequence of rowids. The first result is converted to a converted result having the second format, and the converted result and the second result are combined to obtain an end result. The end result can then be used to locate data that satisfies the query while minimizing the rows of data that need to be retrieved from a table during the query processing.

Claims

1. A method of processing a query that specifies data stored in a computer system, the method comprising the steps of:

accessing a first index based on the query to produce a first result having a first format;

accessing a second index based on the query to produce a second result having a second format;

converting the first result into a converted result having the second format;

combining the converted result and the second result into an end result; and

using the end result to locate data that satisfies the query.

2. The method of claim 1, wherein:

the step of accessing a first index includes the step of accessing a B-tree index; and

the step of accessing a second index includes the step of accessing a bitmap index.

3. The method of claim 2, wherein the first result is a sequence of row identifiers that identify rows in a table and the step of converting the first result into a converted result includes the step of converting the sequence of row identifiers into a series of bits corresponding to rows of the table.

4. The method of claim 3, wherein the step of combining the converted result and the second result comprises performing a logical AND operation between the converted result and the second result to obtain the end result.

5. The method of claim 3, wherein the step of combining the converted result and the second result comprises performing a logical OR operation between the converted result and the second result to obtain the end result.

6. The method of claim 1, wherein;

the step of accessing a first index includes the step of accessing a bitmap index; and

the step of accessing a second index includes the step of accessing a B-tree index.

7. A method of processing a query that specifies data stored in a computer system, the method comprising the steps of:

A) determining a first cost of a first execution path that includes the steps of;

A1) accessing a first index based on the query to produce a first result having a first format,

A2) accessing a second index based on the query to produce a second result having a second format,

A3) converting the first result into a converted result having the second format,

A4) combining the converted result and the second result into an end result, and

A5) using the end result to locate data that satisfies the query.

B) determining a second cost of a second execution path that includes the steps of;

B1) accessing the first index based on the query to produce a first result having a first format,

B2) using the first result to locate data that satisfies the query without accessing the second index,

C) selecting a selected execution path from among a set of execution paths that include the first execution path and the second execution path, and

D) executing the selected execution path.

8. The method of claim 7, wherein:

the step of accessing a first index includes the step of accessing a B-tree index; and

the step of accessing a second index includes the step of accessing a bitmap index.

9. A database system comprising:

a database storing stored data, a first index of the stored data and a second index of the stored data; and

a database server for processing a query by;

accessing the first index based on the query to produce a first result having a first format;

accessing the second index based on the query to produce a second result having a second format;

converting the first result into a converted result having the second format;

combining the converted result and the second result into an end result; and

using the end result to locate data from said database that satisfies the query.

10. The system of claim 9, wherein:

the first index is a B-tree index; and

the second index is a bitmap index.