Patent ID: 8892586

Claim:
A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising: accessing a column of compressed data in a table, wherein the accessing comprises seeking one or more specific values in the column without decompressing the column, wherein the compressed data comprises values from a dictionary, wherein the values comprise the one or more specific values, wherein each of the values is encoded with a corresponding bit value in an index vector; deleting all occurrences of a most-frequently occurring value from the column and storing positions for the deleted occurrences in a bit vector, wherein the bit vector comprises a bit set when a value of a corresponding row is not the most-frequently occurring value; initializing an additional data structure that comprises a prefix, wherein the prefix comprises storing, for each block of a plurality of blocks of values in the column, a total number of bits set in the bit vector for previous blocks of the plurality of blocks that are previous to that block; determining, in response to the accessing, a block number for a target block of the plurality of blocks, wherein the target block contains the one or more specific values, wherein the determining comprises checking whether or not a specified row number corresponding to the block number to be accessed is located in the prefix; and if the specified row number is located in the prefix, returning a prefix value of the prefix, and if the specified row number is not located in the prefix, querying the most frequently occurring value and returning the most frequently occurring value when a corresponding bit for the specified row number is not set in the bit vector, and calculating a position of the specified row number in the index vector for the column by counting bits in the bit vector and returning the position when the corresponding bit for the specified row number is set in the bit vector.