IN-MEMORY COLUMN-LEVEL MULTI-VERSIONED GLOBAL DICTIONARY FOR IN-MEMORY DATABASES

摘要

Techniques are described herein for sharing a dictionary across multiple in-memory compression units (IMCUs). After a dictionary is used to encode a first column vector in a first IMCU, the same dictionary is used to encode a second column vector in a second IMCU. The entries in the dictionary are in sort order to facilitate binary searching when performing value-to-code look-ups. If, during the encoding of the second column vector, values are encountered for which the dictionary does not already have codes, then a “sort-order-boundary” is established after the last entry in the dictionary, and entries for the newly encountered values are added to the dictionary, after the sort-order-boundary. To facilitate value-to-code look-ups, the new entries are also sorted relative to each other, creating a second “sort order set”. A new version of the dictionary may be created when the number of sort order sets in the first version of the dictionary reaches a configurable threshold.

主权项

1. A method comprising:
maintaining a table on persistent storage; wherein the table includes a particular column; loading values from a first portion of the particular column into a first column vector in volatile memory; encoding the first column vector, using a particular dictionary, to produce a first encoded column vector; and loading values from a second portion of the particular column into a second column vector in volatile memory; encoding the second column vector, using the particular dictionary, to produce a second encoded column vector; and wherein the method is performed by one or more computing devices.