Oracle International Corporation

Michael Charles Depledge

Cetin Ozbutun

Jeffrey Ira Cohen

Hakan Jakobsson

Quoc Tai Tran

Mark Kremer

Alexander C Ho

Julian Hyde

William H Waddington

Angela Amor

Santanu Mukhopadhyay

Behrouz Arbab-Dehkordi

William M Keese

A technique and mechanism for transforming a query is described. A given query is transformed into a transformed query that references a global temporary table. Specifically, the given query contains a join between a given table and one or more other tables referenced by constraints (e.g. predicates). References to one or more of the constrained tables are replaced by a reference to a global temporary table. Before executing the transformed query, data that satisfies the constraints placed on the constrained table is inserted into the global temporary table.

Using global temporary tables to transform queries

A method and apparatus for segmenting bitmaps in a bitmap index is provided. A segmented bitmap includes a plurality of bitmap segments that are used to indicate which records in a body of records that is associated with the segmented bitmap satisfy a particular criteria. Each bitmap segment contains a string of bits that correspond to a corresponding range of records in the body of records. There may be gaps between the ranges represented by the bitmap segments when, for example, the body of records does not contain records in a particular range. For the purposes of retrieval, compression, de-compression, locking and logging, the database system treats each bitmap segment as a distinct data item.

Bitmap segmentation

Bitmap index compression

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.

Method and apparatus for using incompatible types of indexes to process

A method for performing logical operations on bitmap streams from segmented bitmaps. The logical operations include the AND, OR, and Set Minus operations. One embodiment of the invention performs the logical AND operation on a plurality of bitmap streams by searching for a set of overlapping bitmap segments. The ranges corresponding to the overlap among the overlapping bitmap segments are scanned to generate non-gap results. One embodiment of the invention performs the logical OR operation on a plurality of bitmap streams. To generate a result for a given range, only the bitmap segments overlapping the given range are ORed together. One embodiment of the invention performs a Set Minus between bitmap streams. A set minus is the ANDing of a first condition with the negation of another condition. To generate a set minus result, the ranges corresponding to the gaps in the bitmap associated with the negated condition are ignored.

Query processing using compressed bitmaps

A method and apparatus for generating and using bitmaps in a database system that employs multi-level identifiers is provided. The generated bitmaps include bits that correspond to the identifiers that have been assigned to existing records, as well as bits that correspond to all intervening multi-level identifiers that have not yet been assigned. Therefore, when new rows are inserted into the table associated with the bitmap, new bits do not have to be inserted into the existing bitmap. When existing rows are deleted, the bits that correspond to the deleted rows are not themselves deleted, but are simply set to a value that indicates that the corresponding row does not satisfy the criteria associated with the bitmap.

Creating bitmaps from multi-level identifiers

Sort plus operations such as 'group by' and 'distinct' generally require sorting of the retrieved data before performing the sort plus operation. A method and apparatus is disclosed for executing a query specifying a sort plus operation without performing the sorting operation. To perform the sort plus operation, it is determined whether a sorted source exists that can be used to obtain the data specified in the query. If the sorted source does exist, it is then used to perform the sort plus operation.

Method and apparatus for executing a query that specifies a sort plus

A method for combining within memory a limit, a plurality of bitmap streams from bitmaps of indefinite size and number. The bitmap streams are merged into a resulting bitmap which can be used in subsequent logical operations. In order to perform a merge within a memory limit, the method relies on the data compression. When compression by itself may be ineffective, the method produces a resulting bitmap for a reduced range. The ensures the production of a resulting bitmap. When the range is reduced, the method may be repeated to produce a merge for a range beyond the reduced range.

Combining bitmaps within a memory limit

In processing a query, a database server parses a string describing a query into a query representation. The query string is parsed again to generate a replica of the query representation. Various transformations can be applied to the replica in order to reduce the amount of processing for the query. In addition, transformations are applied to the query string before parsing again to produce a transformed query representation. A transformed query representation is selected for processing a query according to an estimated cost of using the query representation.

Method and apparatus for transforming queries

A list of indexes, from which indexes are selected for an index access path, is sorted by number of columns upon which each index is built. From the sorted list of indexes, a set of index access methods is generated in a heuristically ordered set of passes from a given WHERE clause. The index access methods that comprise the index access path are selected from the set of index access methods according to a cost/benefit analysis.

Index selection for an index access path

A method and apparatus for compressing data is provided. The invention compresses an input bit stream into a compressed output bit stream. The input bit streams are byte aligned and classified. Bytes with all bits set to value zero are classified as gap bytes. Bytes with only one bit set to value one are classified as offset bytes. All other bytes are classified as map bytes. Groups of adjacent bytes are organized into two types of groups. The first type is a gap bit group. A gap map group contains gap bytes and one offset byte. The second type is the gap map group. It contains gap bytes and map bytes. The number of gap bytes in a group is called a gap size. The groups are compressed into four types of atoms. Each type of atom has one control byte, zero or more gap size bytes, and zero or map bytes. A control byte describes the atom. The map bytes in an atom are copies of the map bytes in the control group.

A method and apparatus provide bitmapped indexing with high granularity locking. Whenever a change is made to a data table upon which a bitmapped index is based, two differential entries are generated and stored as index entries in the bitmapped index. Each differential entry identifies a bit to be flipped in the corresponding bitmap index entry. When applied to corresponding bitmap index entry, the changes are reflected in the appropriate bitmaps. Whenever a bitmap is read from the bitmapped index, any corresponding differential entries are applied so that the resulting bitmap reflects the change made to the data table.

Growing community of inventors

San Jose, CA, United States of America

Michael Charles Depledge