Generating and implementing indexes based on criteria set forth in queries

Claim 3

The method of claim 1 wherein the Boolean expression that includes at least one operator that is not equality involves one or more relational operators from the set consisting of “greater than”, “less than”, “equal to”, “greater than or equal to”, “less than or equal to”.

Claim 4

The method of claim 1 wherein the search criterion further involves values from more than one column of each row.

Claim 5

The method of claim 1 further comprising the steps of: detecting updates to one or more columns of the table that are referenced in the search criterion; in response to the updates, updating the bits in the bitstring corresponding to the updated rows if the updates cause the updated rows to change status with respect to satisfying the search criterion; and in response to the updates, not updating the bits in the bitstring corresponding to the updated rows if the updates do not cause the updated rows to change status with respect to satisfying the search criterion.

Claim 6

The method of claim 1 wherein the step of storing the bitstring corresponding to the rows of the table further comprises the steps of: dividing the bitstring into segments; selecting a size for the segment such that the segment does not span more than a block of data, wherein the block of data is the smallest quantity of data that can be read from a persistent store; providing a mechanism for determining the segment to which a bit corresponding to a given row in the table maps; and providing a mechanism for determining the position, within the segment, of the bit corresponding to a given row in the table.

Claim 7

The method of claim 1 wherein: each bit of the bitstring is mapped to a unique key value which, in turn, maps to a row in the table; and the unique key value includes values from one or more columns of the table.

Claim 8

The method of claim 1 wherein: unique key values are associated with rows of the table; and the step of storing the bitstring corresponding to the rows of the table further comprises the step of not storing the segments of bitstring corresponding to gaps in a range of unique key values associated with the rows of the table.

Claim 9

The method of claim 1 wherein: unique key values are associated with rows of the table; and the step of storing the bitstring corresponding to the rows of the table further comprises the step of not storing segments of bitstring corresponding to a range of unique key values for which the status of the rows associated with the range of unique key values have a particular value.

Claim 10

The method of claim 1 further comprising the step of: dividing the bitstring into segments; and storing the segments in index entries within a B-tree index.

Claim 11

The method of claim 1 further comprising the steps of: dividing the bitstring into segments; and organizing the segments in a hash table.

Claim 12

The method of claim 1 further comprising the steps of: determining whether each row in the table satisfies one or more additional search criteria, wherein each of the one or more additional search criteria involves a Boolean expression; and the bitstring includes bits which indicate whether the rows that correspond to the bits satisfy the one or more additional search criteria.

Claim 13

A computer-readable medium carrying one or more sequences of instructions for generating one or more indexes for use in processing a query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: determining whether each row in a table satisfies a search criterion, wherein the search criterion involves a Boolean expression that includes at least one operator that is not equality; generating a bitstring corresponding to the rows of the table, wherein bits of the bitstring indicate whether their corresponding rows in the table satisfy the search criterion; and storing the bitstring as at least a portion of an index for use in processing subsequent queries that access the table.

Claim 14

A computer-readable medium carrying one or more sequences of instructions for generating one or more indexes for use in processing a query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: determining whether each row in a table satisfies a search criterion, wherein the search criterion involves a Boolean expression that includes at least one operator that is not equality; generating a bitstring corresponding to the rows of the table, wherein bits of the bitstring indicate whether their corresponding rows in the table satisfy the search criterion; and storing the bitstring as at least a portion of an index for use in processing subsequent queries that access the table.

Claim 15

The computer-readable medium of claim 12 wherein the Boolean expression that includes at least one operator that is not equality involves one or more relational operators from the set consisting of “greater than”, “less than”, “equal to”, “greater than or equal to”, “less than or equal to”.

Claim 16

The computer-readable medium of claim 12 wherein the search criterion further involves values from more than one column of each row.

Claim 17

The computer-readable medium of claim 12 further comprising the steps of: detecting updates to one or more columns of the table that are referenced in the search criterion; in response to the updates, updating the bits in the bitstring corresponding to the updated rows if the updates cause the updated rows to change status with respect to satisfying the search criterion; and in response to the updates, not updating the bits in the bitstring corresponding to the updated rows if the updates do not cause the updated rows to change status with respect to satisfying the search criterion.

Claim 18

The computer-readable medium of claim 12 wherein the step of storing the bitstring corresponding to the rows of the table further comprises the steps of: dividing the bitstring into segments; selecting a size for the segment such that the segment does not span more than a block of data, wherein the block of data is the smallest quantity of data that can be read from a persistent store; providing a mechanism for determining the segment to which a bit corresponding to a given row in the table maps; and providing a mechanism for determining the position, within the segment, of the bit corresponding to a given row in the table.

Claim 19

The computer-readable medium of claim 12 wherein: each bit of the bitstring is mapped to a unique key value which, in turn, maps to a row in the table; and the unique key value includes values from one or more columns of the table.

Claim 20

The computer-readable medium of claim 12 wherein: unique key values are associated with rows of the table; and the step of storing the bitstring corresponding to the rows of the table further comprises the step of not storing the segments of bitstring corresponding to gaps in a range of unique key values associated with the rows of the table.

Claim 21

The computer-readable medium of claim 12 wherein: unique key values are associated with rows of the table; and the step of storing the bitstring corresponding to the rows of the table further comprises the step of not storing segments of bitstring corresponding to a range of unique key values for which the status of the rows associated with the range of unique key values have a predetermined value.

Claim 22

The computer-readable medium of claim 12 further comprising the step of: dividing the bitstring into segments; and storing the segments in index entries within a B-tree index.

Claim 23

The computer-readable medium of claim 12 further comprising the steps of: dividing the bitstring into segments; and organizing the segments in a hash table.

Claim 24

The computer-readable medium of claim 12 further comprising the steps of: determining whether each row in the table satisfies one or more additional search criteria, wherein each of the one or more additional search criteria involves a Boolean expression; and the bitstring includes bits which indicate whether the rows that correspond to the bits satisfy the one or more additional search criteria.

Claim 27

The method of claim 23 wherein evaluation of the Boolean expression requires a join between said table and said one or more tables.

Claim 28

A computer-readable medium carrying one or more sequences of one or more instructions for generating one or more indexes for use in processing a query, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: determining whether each row in a table satisfies a search criterion, wherein the search criterion involves a Boolean expression, wherein evaluation of the Boolean expression requires data from one or more tables other than said table; generating a bitstring corresponding to the rows of the table, wherein bits of the bitstring indicate whether their corresponding rows in the table satisfy the search criterion; and storing the bitstring as at least a portion of an index for use in processing subsequent queries that access the table.

Claim 29

A computer-readable medium carrying one or more sequences of one or more instructions for generating one or more indexes for use in processing a query, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: determining whether each row in a table satisfies a search criterion, wherein the search criterion involves a Boolean expression, wherein evaluation of the Boolean expression requires data from one or more tables other than said table; generating a bitstring corresponding to the rows of the table, wherein bits of the bitstring indicate whether their corresponding rows in the table satisfy the search criterion; and storing the bitstring as at least a portion of an index for use in processing subsequent queries that access the table.

Claim 30

The computer-readable medium of claim 25 , wherein evaluation of the Boolean expression requires a join between said table and said one or more tables.