System and method for continuously adaptive indexes
First Claim
Patent Images
1. A computer program product, stored on machine-readable medium, for maintaining a data set, comprising instructions operable to cause a programmable processor to:
- provide a hybrid index on a domain, the hybrid index including entries, each of which includes a value associated with a key, the value portion of each entry specifying a record or records in a data set that has the key for the entry, wherein the hybrid index uses two or more representations for the value portions of the entries, and wherein the representation of a value associated with a key depends on the selectivity of the key.
4 Assignments
0 Petitions
Accused Products
Abstract
Hybrid target indexes are employed for skewed data set domains. Such hybrid indexes contain multiple value representations within a given index. The representations can be optimized for particular keys in highly skewed data set domains. For example, a hybrid target index on customer states might employ a bitmap to represent the index value for a California key and also employ, in the same index, an uncompressed list of row-IDs to represent the index value for a Delaware key.
50 Citations
33 Claims
-
1. A computer program product, stored on machine-readable medium, for maintaining a data set, comprising instructions operable to cause a programmable processor to:
provide a hybrid index on a domain, the hybrid index including entries, each of which includes a value associated with a key, the value portion of each entry specifying a record or records in a data set that has the key for the entry, wherein the hybrid index uses two or more representations for the value portions of the entries, and wherein the representation of a value associated with a key depends on the selectivity of the key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
10. In a computer system comprising a data set and a hybrid index of entries, each of which includes a value associated with a key, the value portion of each entry specifying a record or records in the data set, wherein a first entry has a first representation for its value and a second entry has a second representation for its value,
a method of modifying the hybrid index when a record in the data set is inserted, deleted, or updated, the method comprising: -
(a) identifying the hybrid index key of the record that is being inserted, deleted, or updated;
(b) determining how to represent the value of the hybrid index entry for the key of the record that is being inserted, deleted, or updated; and
(c) representing, as determined in (b), the value of the hybrid index entry for the key of the record being inserted, deleted, or updated. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. In a computer system comprising a relational database table and configured to store a hybrid index of entries, each of which includes a value associated with a key, the value portion of an entry specifying a record or records in the data set, wherein a first entry has a first representation for its value and a second entry has a second representation for its value, a method of creating the hybrid index comprising:
-
(a) identifying the key of one or more records in the relational database table;
(b) determining how to represent the value of the hybrid index entry for the key of the record or records, depending on a selectivity of the key; and
(c) representing, as determined in (b), the value of the hybrid index entry for the key of the record or records. - View Dependent Claims (24, 25, 26, 27, 28)
-
-
29. A method for creating a hybrid index, the method comprising:
-
identifying one or more keys in a data set to be indexed;
for each key, selecting a representation to represent which records in the data set includes the key, the selection depending on the selectivity of the key; and
for each key, representing which records in the data set includes the key each in accordance with the selection. - View Dependent Claims (30)
-
-
31. A method for modifying a hybrid index in a data set, the method comprising:
-
calculating parameters of one or more keys in the hybrid index in response to an insertion, deletion, or update of the data set;
for each key whose corresponding parameters has changed in response to the insertion, deletion, or update of the data set, selecting a representation to represent which records in the data set includes the key, the selection depending on the changed parameters of the key; and
representing which records in the data set includes the key each in accordance with the selection. - View Dependent Claims (32, 33)
-
Specification