IP Library › Granted Patent US 10,726,016

Granted Patent B2

US 10,726,016 · App. 15/294,460 · Granted Jul 28, 2020

In-memory column-level multi-versioned global dictionary for in-memory databases

Inventors: Shasank K. Chavan (Menlo Park, CA); Prashant Gaharwar (San Mateo, CA); Ajit Mylavarapu (Mountain View, CA); Dina Thomas (Palo Alto, CA); Dennis Lui (San Jose, CA); Sheldon A. K. Lewis (Jalisco, MX); Roger D. Macnicol (Hummelstown, PA)

Assignee: Oracle International Corporation

G06F16/24561 G06F16/221 G06F16/3347

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 10,726,016
App. No.: 15/294,460
Granted: Jul 28, 2020
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

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.

Claims (149)

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 a first volatile memory of a first node;

wherein the first node is a first computing device that comprises the first volatile memory;

building, in the first volatile memory of the first node, a first copy of a particular dictionary;

wherein building the first copy of the particular dictionary includes:

creating a first sorted list of values that includes:

values from the first portion of the particular column; and

values, received from a second node via inter-node communication, obtained by the second node from a second portion of the particular column;

storing entries in the first copy of the particular dictionary, for values in the first sorted list of values, in sort order of the first sorted list of values;

encoding, by the first node, the first column vector, using the first copy of the particular dictionary, to produce a first encoded column vector;

loading values from the second portion of the particular column into a second column vector in a second volatile memory of the second node;

wherein the second node is a second computing device that comprises the second volatile memory;

wherein the first node is a different computing device than the second node;

wherein both the first node and the second node have access to the table on persistent storage;

building, in the second volatile memory of the second node, a second copy of the particular dictionary;

wherein building the second copy of the particular dictionary includes:

creating a second sorted list of values that includes:

values from the second portion of the particular column; and

values, received from the first node via inter-node communication, obtained by the first node from the first portion of the particular column;

storing entries in the second copy of the particular dictionary, for values in the second sorted list of values, in sort order of the second sorted list of values;

wherein the first sorted list of values is identical to the second sorted list of values;

encoding, by the second node, the second column vector, using the second copy of the particular dictionary, to produce a second encoded column vector.

2. The method of claim 1 further comprising:

analyzing the particular column to determine whether a global dictionary should be used to encode column vectors for the particular column; and

wherein the step of encoding the second column vector using the particular dictionary is performed in response to determining that a global dictionary should be used to encode column vectors for the particular column.

3. 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 a first volatile memory of a first computing device;

building a particular dictionary based on values in the first column vector;

wherein building the particular dictionary includes:

obtaining, from the first column vector, a first set of values that are not already in the particular dictionary;

creating a second set of values by sorting the first set of values based on a particular sorting criterion and removing duplicates from the first set of values;

storing a first ordered set of entries in the particular dictionary;

wherein the first ordered set of entries includes a single entry for each distinct value in the second set of values;

wherein, within the particular dictionary, order of the first ordered set of entries reflects order of the second set of values;

encoding the first column vector, using the 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,

storing the second column vector in one of:

the first volatile memory of the first computing device; or

a second volatile memory of a second computing device;

adding entries to the particular dictionary based values in the second column vector;

wherein adding entries to the particular dictionary includes:

obtaining, from the second column vector, a third set of values that are not already in the particular dictionary;

creating a fourth set of values by sorting the third set of values based on the particular sorting criterion and removing duplicates from the third set of values;

storing a second ordered set of entries in the particular dictionary;

wherein the second ordered set of entries includes a single entry for each distinct value in the fourth set of values;

wherein, within the particular dictionary, order of the second ordered set of entries reflects order of the fourth set of values;

encoding the second column vector, using the particular dictionary, to produce a second encoded column vector;

wherein:

within the table, the first portion of the particular column and the second portion of the particular column have a particular value in common;

the particular dictionary maps the particular value to a single unique code;

the first ordered set of entries constitute a first sort order set, wherein the first order set includes a single entry for each distinct value from the first portion of the particular column;

after the first sort order set and before a second order set, the particular dictionary includes a sort order boundary;

wherein the second ordered set of entries constitute the second order set, which includes a single entry for each distinct value that:

is in the second portion of the particular column; and

is not in the first portion of the particular column;

wherein the only entry, within the particular dictionary, for the particular value is within the first order set.

4. The method of claim 3 further comprising performing a value-to-code look-up by performing a first binary search on the first sort order set and a second binary search on the second sort order set.

5. The method of claim 3 wherein:

a first version of the particular dictionary is used to encode the first and second encoded column vectors; and

the method further comprises:

in response to detecting that the first version of the particular dictionary includes a maximum number of sort order sets, creating a second version of the particular dictionary that includes entries for all values from the first version of the particular dictionary;

loading values from a third portion of the particular column into a third column vector in volatile memory; and

encoding the third column vector, using the second version of the particular dictionary, to produce a third encoded column vector.

6. The method of claim 5 further comprising, after producing the first encoded column vector, rebuilding the first encoded column vector by:

loading values from the first portion of the particular column into a new first column vector in volatile memory; and

encoding the new first column vector, using the second version of the particular dictionary, to produce a new first encoded column vector.

7. The method of claim 5 further comprising:

maintaining a first usage-count for the first version of the particular dictionary;

incrementing the first usage-count in response to encoding the first column vector using the first version of the particular dictionary;

incrementing the first usage-count in response to encoding the second column vector using the first version of the particular dictionary; and

decrementing the first usage-count when any encoded column vector that was encoded using the first version of the particular dictionary is discarded or rebuilt.

8. The method of claim 7 further comprising discarding the first version of the particular dictionary when the first usage-count reaches zero.

9. One or more non-transitory computer-readable media, storing instructions which, when executed by one or more processors, cause:

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 a first volatile memory of a first node;

wherein the first node is a first computing device that comprises the first volatile memory;

building, in the first volatile memory of the first node, a first copy of a particular dictionary;

wherein building the first copy of the particular dictionary includes:

creating a first sorted list of values that includes:

values from the first portion of the particular column; and

values, received from a second node via inter-node communication, obtained by the second node from a second portion of the particular column;

storing entries in the first copy of the particular dictionary, for values in the first sorted list of values, in sort order of the first sorted list of values;

encoding, by the first node, the first column vector, using the first copy of the particular dictionary, to produce a first encoded column vector;

loading values from the second portion of the particular column into a second column vector in a second volatile memory of the second node;

wherein the second node is a second computing device that comprises the second volatile memory;

wherein the first node is a different computing device than the second node;

wherein both the first node and the second node have access to the table on persistent storage;

building, in the second volatile memory of the second node, a second copy of the Particular dictionary;

wherein building the second copy of the particular dictionary includes:

creating a second sorted list of values that includes:

values from the second portion of the particular column; and

values, received from the first node via inter-node communication, obtained by the first node from the first portion of the particular column;

storing entries in the second copy of the particular dictionary, for values in the second sorted list of values, in sort order of the second sorted list of values;

wherein the first sorted list of values is identical to the second sorted list of values;

encoding, by the second node, the second column vector, using the second copy of the particular dictionary, to produce a second encoded column vector.

10. The one or more non-transitory computer-readable media, storing instructions which, when executed by one or more processors, cause:

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 a first volatile memory of a first computing device;

building a particular dictionary based on values in the first column vector;

wherein building the particular dictionary includes:

obtaining, from the first column vector, a first set of values that are not already in the particular dictionary;

creating a second set of values by sorting the first set of values based on a particular sorting criterion and removing duplicates from the first set of values;

storing a first ordered set of entries in the particular dictionary;

wherein the first ordered set of entries includes a single entry for each distinct value in the second set of values;

wherein, within the particular dictionary, order of the first ordered set of entries reflects order of the second set of values;

encoding the first column vector, using the 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;