Optimizing wide data-type storage and analysis of data in a column store database

A method of performing a database search, the method comprising:

• obtaining, with a computer system, a dictionary table that has a reference column that includes reference keys and a variable character column that includes text, wherein each reference key of a row of the dictionary table identifies a row in a database table having matching text, and wherein at least one row of the dictionary table has more than one reference key;
• receiving, with the computer system, a query including first text;
• determining, with the computer system, a first hash value, the first hash value being based on the first text;
• accessing, with the computer system, a hash table at a given position in the hash table specified by the first hash value to obtain a first array index value stored at the given position in the hash table, wherein:
• the hash table includes an ordered list of items,
• at least some of the items in the ordered list of the hash table associate a respective position in the ordered list with a respective row of the dictionary table, and
• the respective row of the dictionary table identifies a row in the database table having matching text that hashes to the respective position in the ordered list of the hash table;
• accessing, with the computer system, the dictionary table using the first array index value of the hash table to identify one or more first reference keys from the dictionary table;
• and
• using the one or more first reference keys of the dictionary table to access the database table, wherein the query includes an access pattern of “Greater Than,” wherein the rows of the dictionary table are ordered based on the text in the variable character column, and wherein accessing the dictionary table using the first array index value includes obtaining reference keys in rows that have an array index value greater than the first array index value.

A computer product comprising a computer readable medium storing a plurality of instructions for controlling a computer system to perform an operation of storing variable-width data in a database, the instructions comprising:

• receiving a first array of field values, wherein each field value is associated with one first array index value of M index values in a database table, M corresponding to a length of the first array of field values;
• identifying field values of the received first array of field values that have a unique field value from the database table, wherein the first array of field values has N unique field values, and wherein N is an integer greater than one and less than M;
• creating a dictionary table with at least N rows, each row associating one of the identified field values from the database table with one or more reference keys, wherein:
• for each of the identified field values of the received first array of field values, each of the one or more associated reference keys is an index value of the M index values in the database table corresponding to the identified field value, wherein at least one row of the dictionary table has more than one reference key, and
• each of the identified field values is further associated with a row index of the dictionary table;
• creating a reference store table including a second array of fixed-width values and associated second array index values, each of the fixed-width values being one of the row indices of the dictionary table and being associated with a second array index value that corresponds to one of the first array index values of the database table;
• receiving a query including first text;
• operating on the first text using a hash function to obtain a first hash value;
• accessing a hash table using the first hash value to obtain a corresponding row index of the dictionary table;
• accessing the dictionary table using the corresponding row index to identify one or more first reference keys;
• and
• using the one or more first reference keys to access the database table, wherein:
• at least one of the second array of fixed-width values is part of the hash table,
• the hash table has an ordered arrangement of the fixed-width values at respective positions in the ordered list, and
• the position of a given fixed-width value in the ordered arrangement corresponds to a hash function output based on a given unique field value in the first array of field values that is associated with reference keys in a given row of the dictionary table having the row index of the given fixed-width value.