Faster main memory scans in unsorted dictionary-encoded vectors

Abstract

A ValueID corresponding to a value to be searched for in a database column can be determined by finding a match in a dictionary for the database column. A row of an index vector for the database column at which to begin a scan for the ValueID can be identified by reading a ValueID lookup table that maps each unique ValueID to a starting position in the index vector for the database column. The ValueID can not occur in the index vector prior to the starting position. The index vector can be scanned beginning at the starting position to find at least one occurrence of the ValueID corresponding to the value being searched, and a result that includes one or more row locations in the database column corresponding to the at least one occurrence in the index vector of the ValueID corresponding to the value being searched can be returned.

What is claimed is: 
     
       1. 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:
 determining a ValueID corresponding to a value to be searched for in a database column, the determining comprising finding a match in a dictionary for the database column, the dictionary comprising a listing of unique values in the column with corresponding unique ValueIDs; 
 identifying a row of an index vector for the database column at which to begin a scan for the ValueID, the identifying comprising reading a ValueID lookup table that maps group ranges of unique ValueIDs to a first occurrence in the index vector of any ValueID in the corresponding group range, the first occurrence corresponding to a starting position in the index vector for the database column to begin the scan for the ValueID corresponding to the value to be searched, the index vector comprising an insert-only data structure, wherein the rows of the index vector for the database column are ordered in an order of insertion, and not reordered by group ranges of ValueIDs; 
 scanning the index vector beginning at the starting position to find at least one occurrence of the ValueID corresponding to the value being searched; and 
 returning a result comprising one or more row locations in the database column corresponding to the at least one occurrence in the index vector of the ValueID corresponding to the value being searched. 
 
     
     
       2. The computer program product as in  claim 1 , wherein the group ranges are of a same size. 
     
     
       3. The computer program product as in  claim 1 , wherein the group ranges have variable sizes. 
     
     
       4. The computer program product as in  claim 3 , wherein the variable sizes increase exponentially from a first group range along a series of group ranges. 
     
     
       5. The computer program product as in  claim 1 , wherein the operations further comprise:
 upon determining that a new value for adding to the database column is a new unique value, appending a new dictionary row to the dictionary for the database column, the new dictionary row comprising the new unique value and a new ValueID that corresponds to the new unique value; 
 appending an index vector entry that includes the new ValueID corresponding to the new unique value to an end of the index vector; 
 updating the ValueID lookup table to indicate a first position in the index vector where the ValueID occurs; and 
 initiating adding of a new value to a database column, the initiating comprising determining that the new value is a new unique value. 
 
     
     
       6. A method for implementation by one or more data processors forming part of at least one computing system, the method comprising:
 determining a ValueID corresponding to a value to be searched for in a database column, the determining comprising finding a match in a dictionary for the database column, the dictionary comprising a listing of unique values in the column with corresponding unique ValueIDs; 
 identifying a row of an index vector for the database column at which to begin a scan for the ValueID, the identifying comprising reading a ValueID lookup table that maps group ranges of unique ValueIDs to a first occurrence in the index vector of any ValueID in the corresponding group range, the first occurrence corresponding to a starting position in the index vector for the database column to begin the scan for the ValueID corresponding to the value to be searched, the index vector comprising an insert-only data structure, wherein the rows of the index vector for the database column are ordered in an order of insertion, and not reordered by group ranges of ValueIDs; 
 scanning the index vector beginning at the starting position to find at least one occurrence of the ValueID corresponding to the value being searched; and 
 returning a result comprising one or more row locations in the database column corresponding to the at least one occurrence in the index vector of the ValueID corresponding to the value being searched. 
 
     
     
       7. The method as in  claim 6 , wherein the group ranges are of a same size. 
     
     
       8. The method as in  claim 6 , wherein the group ranges have variable sizes. 
     
     
       9. The method as in  claim 8 , wherein the variable sizes increase exponentially from a first group range along a series of group ranges. 
     
     
       10. The method as in  claim 6 , further comprising:
 upon determining that a new value for adding to the database column is a new unique value, appending a new dictionary row to the dictionary for the database column, the new dictionary row comprising the new unique value and a new ValueID that corresponds to the new unique value; 
 appending an index vector entry that includes the new ValueID corresponding to the new unique value to an end of the index vector; 
 updating the ValueID lookup table to indicate a first position in the index vector where the ValueID occurs; and 
 initiating adding of a new value to a database column, the initiating comprising determining that the new value is a new unique value. 
 
     
     
       11. A system comprising:
 computer hardware comprising at least one programmable processor configured to perform operations comprising:
 determining a ValueID corresponding to a value to be searched for in a database column, the determining comprising finding a match in a dictionary for the database column, the dictionary comprising a listing of unique values in the column with corresponding unique ValueIDs; 
 identifying a row of an index vector for the database column at which to begin a scan for the ValueID, the identifying comprising reading a ValueID lookup table that maps group ranges of unique ValueIDs to a first occurrence in the index vector of any ValueID in the corresponding group range, the first occurrence corresponding to a starting position in the index vector for the database column to begin the scan for the ValueID corresponding to the value to be searched, the index vector comprising an insert-only data structure, wherein the rows of the index vector for the database column are ordered in an order of insertion, and not reordered by group ranges of ValueIDs; 
 scanning the index vector beginning at the starting position to find at least one occurrence of the ValueID corresponding to the value being searched; and 
 returning a result comprising one or more row locations in the database column corresponding to the at least one occurrence in the index vector of the ValueID corresponding to the value being searched. 
 
 
     
     
       12. The system as in  claim 11 , wherein the group ranges are of a same size. 
     
     
       13. The system as in  claim 11 , wherein the group ranges have variable sizes. 
     
     
       14. The system as in  claim 13 , wherein the variable sizes increase exponentially from a first group range along a series of group ranges. 
     
     
       15. The system as in  claim 11 , wherein the operations further comprise:
 upon determining that a new value for adding to the database column is a new unique value, appending a new dictionary row to the dictionary for the database column, the new dictionary row comprising the new unique value and a new ValueID that corresponds to the new unique value; 
 appending an index vector entry that includes the new ValueID corresponding to the new unique value to an end of the index vector; 
 updating the ValueID lookup table to indicate a first position in the index vector where the ValueID occurs; and 
 initiating adding of a new value to a database column, the initiating comprising determining that the new value is a new unique value.