Method and apparatus for indexing database columns with bit vectors

Claim 3

The method of claim 1 further comprising the steps of: receiving a search value and a search function from an application program; comparing the search value to the index of bit vectors for the values by manipulation of the bit vectors based on the search value and the search function; and producing a resultant bit vector having a bit pattern indicating the identifier of each value satisfying the search function.

Claim 4

The method of claim 2 further comprising the steps of: retrieving from the data base each value associated with each identifier indicated in the bit pattern of the resultant vector; and providing each retrieved value to the application program.

Claim 5

The method of claim 2 further comprising the step of reconstructing each data value associated with each identifier indicated in the bit pattern of the resultant bit vector by selecting each bit, in each successive bit vector of the index, having a unique position corresponding to said identifier.

Claim 6

The method of claim 2 wherein the manipulation of the bit vectors comprises performing Boolean functions on selected bit vectors based on the search value and the search function.

Claim 7

The method of claim 1 wherein the compression step further comprises discarding the ordered set of values from the database and any bit vectors having bit values all equal to zero.

Claim 8

The method of claim 1 wherein the data records comprise medium or high cardinality data.

Claim 9

The method of claim 1 further comprising the steps of: providing another ordered set of values stored in the data base; accessing the other ordered set of values; and forming a B-tree index for the other ordered set of values.

Claim 10

The method of claim 8 wherein the other ordered set of values corresponds to low cardinality data.

Claim 11

The method of claim 8 further comprising the steps of: performing, for each ordered set of values corresponding to medium or high cardinality data, the processing steps necessary to form an index of bit vectors; and performing, for an ordered set of values corresponding to low cardinality data, the processing steps necessary to form a B-tree index.

Claim 12

The method of claim 8 further comprising the step of performing, based on the cardinality of a particular ordered set of values, either the processing steps necessary to form an index of bit vectors or the processing steps necessary to form a B-tree index.

Claim 13

An index method of data management in a data processing system, the method comprising: providing an application program, a database management system and a server; forming an index of bit vectors in the server, the index being formed from an ordered set of data values disposed in a database of the database management system as a plurality of data records arranged in row and column format, each data value disposed in the database having a bit pattern of arbitrary length and an identifier for a particular column associated therewith, the index being formed by: (i) creating a number of bit vectors, wherein the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values; (ii) assigning to a unique position in successive bit vectors each bit of the bit pattern for each data value, wherein each bit of the bit pattern for each data value is assigned to identical unique position in each of the successive bit vectors; so that each bit vector comprises an array storing a transposed sequence of bit values derived by taking a single bit value for each record of said database table, each bit vector comprising bit values taken from a single bit position for said particular column of said database table; receiving a search value and a search function from the application program; comparing the search value to the data values assigned into the bit vectors by manipulation of the bit vectors based on the search value and the search function; producing a resultant bit vector having a bit pattern indicating the identifier of one or more data values, thereby indicating that said one or more data values satisfy the search function; and compressing the ordered set of data values disposed in the database by deleting all data values which can be derived from said index of bit vectors.

Claim 14

An index method of data management in a data processing system, the method comprising: providing an application program, a database management system and a server; forming an index of bit vectors in the server, the index being formed from an ordered set of data values disposed in a database of the database management system as a plurality of data records arranged in row and column format, each data value disposed in the database having a bit pattern of arbitrary length and an identifier for a particular column associated therewith, the index being formed by: (i) creating a number of bit vectors, wherein the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values; (ii) assigning to a unique position in successive bit vectors each bit of the bit pattern for each data value, wherein each bit of the bit pattern for each data value is assigned to identical unique position in each of the successive bit vectors; so that each bit vector comprises an array storing a transposed sequence of bit values derived by taking a single bit value for each record of said database table, each bit vector comprising bit values taken from a single bit position for said particular column of said database table; receiving a search value and a search function from the application program; comparing the search value to the data values assigned into the bit vectors by manipulation of the bit vectors based on the search value and the search function; producing a resultant bit vector having a bit pattern indicating the identifier of one or more data values, thereby indicating that said one or more data values satisfy the search function; and compressing the ordered set of data values disposed in the database by deleting all data values which can be derived from said index of bit vectors.

Claim 15

The method of claim 12 further comprising the additional steps of: retrieving from the data base each value associated with each identifier indicated in the bit pattern of the resultant vector; and providing each retrieved value to the application program.

Claim 16

The method of claim 12 further comprising the additional steps of: reconstructing each data value associated with each identifier indicated in the bit pattern of the resultant bit vector by selecting each bit, in each successive bit vector of the index, having a unique position corresponding to said identifier; and providing each reconstructed data value to the application program.

Claim 17

The method of claim 12 wherein the manipulation of the bit vectors comprises performing Boolean functions on selected bit vectors based on the search value and the search function.

Claim 18

The method of claim 12 wherein the compression step further comprises discarding any bit vectors having bit values all equal to zero.

Claim 19

The method of claim 12 wherein the ordered set of values corresponds to medium or high cardinality data.

Claim 20

The method of claim 12 further comprising the additional steps of: providing another ordered set of data values stored in the data base; accessing said other ordered set of values; and forming a B-tree index for the other ordered set of values.

Claim 21

The method of claim 18 wherein the other ordered set of values corresponds to low cardinality data.

Claim 22

A database management system comprising: a server having a database comprising an ordered set of data values stored as a plurality of data records arranged in row and column format, each data value having a bit pattern and an identifier associated therewith, the server comprising a memory, and a processor; means for creating a number of bit vectors in the memory, such that the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values; means for accessing one of the ordered set of data values stored in the database; means for assigning each successive bit of the bit pattern for the accessed data value to a unique position in successive bit vectors, the bits being assigned into an identical unique position in each of the successive bit vectors, so that each bit vector comprises an array storing a column of bit values created by taking a single bit value at a particular unique bit position of one column for each record of said database table; means for repeating the accessing and assigning steps for each remaining data value to form an index of bit vectors for the data values; and means for compressing the ordered set of data values disposed in the database by eliminating data values which can be derived from said bit vectors.

Claim 23

A database management system comprising: a server having a database comprising an ordered set of data values stored as a plurality of data records arranged in row and column format, each data value having a bit pattern and an identifier associated therewith, the server comprising a memory, and a processor; means for creating a number of bit vectors in the memory, such that the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values; means for accessing one of the ordered set of data values stored in the database; means for assigning each successive bit of the bit pattern for the accessed data value to a unique position in successive bit vectors, the bits being assigned into an identical unique position in each of the successive bit vectors, so that each bit vector comprises an array storing a column of bit values created by taking a single bit value at a particular unique bit position of one column for each record of said database table; means for repeating the accessing and assigning steps for each remaining data value to form an index of bit vectors for the data values; and means for compressing the ordered set of data values disposed in the database by eliminating data values which can be derived from said bit vectors.

Claim 24

The data base management system of claim 20 further comprising: means for receiving a search value and a search function from an application program; means for comparing the search value to the index of bit vectors for the values by manipulation of the bit vectors based on the search value and the search function; and means for producing a resultant bit vector having a bit pattern indicating the identifier of each value satisfying the search function.

Claim 25

The data base management system of claim 21 further comprising: means for retrieving from the data base each value associated with each identifier indicated in the bit pattern of the resultant vector; and means for providing each retrieved value to the application program.

Claim 26

The data base management system of claim 21 further comprising means for reconstructing each data value associated with each identifier indicated in the bit pattern of the resultant bit vector by selecting each bit, in each successive bit vector of the index, having a unique position corresponding to said identifier.

Claim 27

The database management system of claim 20 wherein the means for compressing discards all of the ordered set of data values from the database.

Claim 28

The data base management system of claim 21 wherein the manipulation of the bit vectors comprises performing Boolean functions on selected bit vectors based on the search value and the search function.

Claim 29

The data base management system of claim 20 wherein the ordered set of data values corresponds to high cardinality data.

Claim 30

The data base management system of claim 26 further comprising means for accessing another ordered set of data values stored in the data base, and means for forming a B-tree index for the other ordered set of data values.

Claim 31

The data base management system of claim 27 wherein the other ordered set of data values corresponds to low cardinality data.

Claim 34

The method of claim 29 further comprising the step of compressing the ordered set of data values disposed in the data base subsequent to the repeating step.

Claim 35

The method of claim 30 wherein the compressing step further comprises discarding those data values of the ordered set which can be derived from said bit vectors.

Claim 36

A database management system comprising: a server having a database storing an ordered set of data values as rows of data records, each data value having a bit pattern and an identifier for a particular database column associated therewith, the server comprising a memory and a processor; means for creating a number of bit vectors in the memory, such that the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values, said means for creating including: means for accessing one of the ordered set of data values stored in the database; means for assigning each bit of the bit pattern for the accessed data value to a unique position in successive bit vectors, the bits being assigned into an identical unique position in each of the successive bit vectors; and means for repeating the accessing and assigning steps for each remaining data value to form an index of bit vectors for the data values, so that each bit vector comprises an array storing a column of bit values created by taking a single bit value at a particular unique bit position of one column for each row of said database; means for receiving a search value and a search function from the application program; means for comparing the search value to the data values assigned into the bit vectors by manipulation of the bit vectors based on the search value and the search function; means for producing a resultant bit vector having a bit pattern indicating the identifier of one or more data values, thereby indicating that said one or more data values satisfy the search function; and means for reconstructing each data value associated with each identifier indicated in the bit pattern of the resultant bit vector by selecting each bit, in each successive bit vector of the index, having a unique position corresponding to said identifier.

Claim 37

A database management system comprising: a server having a database storing an ordered set of data values as rows of data records, each data value having a bit pattern and an identifier for a particular database column associated therewith, the server comprising a memory and a processor; means for creating a number of bit vectors in the memory, such that the number of bit vectors is equal to the length of the longest of the bit patterns for the data values and the length of each bit vector is equal to the number of data values, said means for creating including: means for accessing one of the ordered set of data values stored in the database; means for assigning each bit of the bit pattern for the accessed data value to a unique position in successive bit vectors, the bits being assigned into an identical unique position in each of the successive bit vectors; and means for repeating the accessing and assigning steps for each remaining data value to form an index of bit vectors for the data values, so that each bit vector comprises an array storing a column of bit values created by taking a single bit value at a particular unique bit position of one column for each row of said database; means for receiving a search value and a search function from the application program; means for comparing the search value to the data values assigned into the bit vectors by manipulation of the bit vectors based on the search value and the search function; means for producing a resultant bit vector having a bit pattern indicating the identifier of one or more data values, thereby indicating that said one or more data values satisfy the search function; and means for reconstructing each data value associated with each identifier indicated in the bit pattern of the resultant bit vector by selecting each bit, in each successive bit vector of the index, having a unique position corresponding to said identifier.

Claim 38

The database management system of claim 32 further comprising means for compressing the ordered set of data values disposed in the database.

Claim 39

The database management system of claim 33 wherein the means for compressing discards any data values of the ordered set of values from the database which can be derived from said bit vectors.

Claim 40

In a database system comprising a database storing information in a database table as a sequence of data records arranged in row and column format, an improved method for indexing said database table, the method comprising: selecting a particular column of the database table to index, said particular column representing a particular category of information for which each data record stores a data value, each data value representing information in the database stored as a sequence of bit values, each bit value having a particular bit position in said sequence of bit values; and creating an index for said particular column comprising a plurality of bit vectors by performing substeps of: (i) determining a maximum number of bit positions employed in said sequence of bit values for storing information for said particular column, (ii) initializing a sequence of bit vectors based on said determined maximum number of bit positions, so that each bit vector is associated with a particular one of said bit positions employed, and (iii) copying data values stored for said particular column by said sequence of data records into said sequence of bit vectors, so that for each particular bit position at each particular data record any bit value stored thereat is copied into the bit vector associated with that bit position, the bit value being copied into a particular bit position of the bit vector which corresponds to position of the particular data record relative to other data records in said sequence of data records.

Claim 41

In a database system comprising a database storing information in a database table as a sequence of data records arranged in row and column format, an improved method for indexing said database table, the method comprising: selecting a particular column of the database table to index, said particular column representing a particular category of information for which each data record stores a data value, each data value representing information in the database stored as a sequence of bit values, each bit value having a particular bit position in said sequence of bit values; and creating an index for said particular column comprising a plurality of bit vectors by performing substeps of: (i) determining a maximum number of bit positions employed in said sequence of bit values for storing information for said particular column, (ii) initializing a sequence of bit vectors based on said determined maximum number of bit positions, so that each bit vector is associated with a particular one of said bit positions employed, and (iii) copying data values stored for said particular column by said sequence of data records into said sequence of bit vectors, so that for each particular bit position at each particular data record any bit value stored thereat is copied into the bit vector associated with that bit position, the bit value being copied into a particular bit position of the bit vector which corresponds to position of the particular data record relative to other data records in said sequence of data records.

Claim 42

The method of claim 35, further comprising: compressing the data values stored in said bit vectors by eliminating bit values which are unused by the data values.

Claim 43

The method of claim 36, wherein said compressing step comprises: compressing the data values stored in said bit vectors by eliminating any bit vector having its bit values all set equal to 0.

Claim 44

The method of claim 36, wherein said particular column stores integer data values, and wherein said unused bit values comprise at least some high-order bits of the integer data values.

Claim 45

The method of claim 35, further comprising: compressing the database table by eliminating data values of said particular column.

Claim 46

The method of claim 39, further comprising: reconstructing said particular column by copying data values stored in said sequence of bit vectors back into said sequence of data records.

Claim 47

The method of claim 35, further comprising: repeating said selecting and creating steps for another column of the database table.

Claim 48

The method of claim 35, wherein said category of information comprises medium or high cardinality data.

Claim 49

The method of claim 35, further comprising: receiving a search value and a search function from an application program; comparing the search value to the index of bit vectors of data values by manipulation of the vectors based on the search functions; and producing a resultant bit vector having a bit pattern indicating a record identifier for each data value satisfying the search function.

Claim 50

The method of claim 43, further comprising: retrieving from the database each data record associated with each record identifier indicated in the bit pattern of the resultant vector; and providing each retrieved data record to the application program.

Claim 51

The method of claim 35, wherein: each bit vector has a length equal to how many data values are present in the database table for said particular column.