N-bit Compressed Versioned Column Data Array for In-Memory Columnar Stores

Patent metadata

Field	Value
Publication number	US-2016147447-A1
Application number	US-201414553435-A
Country	US
Kind code	A1
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	May 26, 2016
Grant date	—

Abstract

As part of a columnar in-memory database, value identifiers are inserted into a backing array in-memory until such time that it is determined that such backing array does not have sufficient capacity. A new backing array is then generated that includes the value identifiers in the old backing array and which has sufficient capacity. The old backing array can be flushed from memory when there are no active operations using such backing array. Such an arrangement allows for readers and non-structural writers to operate concurrently. Related apparatus, systems, techniques and articles are also described.

First claim

What is claimed is:

1 . A method comprising:
mapping, in an in-memory database, each distinct value in a column to a different value identifier; populating a first backing array of an index vector by inserting at each position p in the first backing array, the value identifier corresponding to the value row n has for the column, the first backing array having a predefined chunk of allocated memory, each position in the index vector being logically n-bits wide; determining that the first backing array does not have capacity in the predefined chunk of allocated memory for a subsequent value identifier to be inserted therein; generating, based on the determining, a second backing array in a different chunk of allocated memory including the first set of value identifiers and having capacity for the subsequent value identifier to be inserted therein; and inserting the subsequent value identifier in the second backing array.

2 . The method of claim 1 , wherein the determining is based on there being no empty row positions for the subsequent value identifier.

3 . The method of claim 1 , wherein the determining is based on the subsequent value identifier having a width that exceeds n bits.

4 . The method of claim 1 , wherein at least one writer and at least one reader to concurrently accesses the index vector.

5 . The method of claim 1 further comprising:
flushing the first backing array from memory after the subsequent value identifier is inserted into the second backing array.

6 . The method of claim 5 , wherein the first backing array is flushed when there are no outstanding readers that registered prior to the establishment of the second backing array.

7 . The method of claim 6 , wherein the readers register with a garbage collector.

8 . The method of claim 1 , wherein the database is a columnar in-memory database.

9 . The method of claim 1 , wherein there are a plurality of instances of vector indexes and the second backing array is generated on an instance-by-instance basis.

10 . The method of claim 1 further comprising:
associating a semaphore with each index vector; and
assigning the semaphore to a first writer seeking to generate the second backing array.

11 . The method of claim 10 further comprising:
releasing the semaphore after copying the value identifiers from the first backing array into the second backing array.

12 . The method of claim 10 further comprising:
waiting, by a second writer, the semaphore assigned to the first writer to be released;
obtaining, by the second writer, the semaphore; and
executing a write functor by the second writer on the second backing array.

13 . The method of claim 1 , wherein only one writer is allowed to perform structural changes to the first backing array at a given time.

14 . The method of claim 13 , wherein the writer allowed to perform structural changes to the first backing array at the given time is provided ownership of an exclusion mechanism that prevents other writers from performing structural changes.

15 . The method of claim 14 , wherein there are two or more writers concurrently seeking to perform structural changes to the first backing array, and the writer or writers without the exclusion mechanism wait for the release and subsequent provision of ownership of the exclusion mechanism before structural changes are made to the second backing array.

16 . The method of claim 15 , wherein there is at least one writer concurrently seeking to perform non-structural changes to the first backing array while another writer owns the exclusion mechanism, and the writer without the exclusion mechanism waits for the release of the exclusion mechanism before non-structural changes are made to the second backing array.

17 . The method of claim 14 further comprising: querying, by a writer, the exclusion mechanism to either obtain ownership of the exclusion mechanism or to put the writer to sleep until the exclusion mechanism is available to such writer.

18 . The method of claim 14 , wherein the exclusion mechanism is selected from a group consisting of: semaphores, mutexes, and spinlocks.

19 . A non-transitory computer program product storing instructions which, when executed by at least one data processor forming part of at least one computing system, result in operations comprising:
mapping, in a columnar in-memory database, each distinct value in a column to a different value identifier; populating a first backing array of an index vector by inserting at each position n in the first backing array, the value identifier corresponding to the value row n has for the column, the first backing array having a predefined chunk of allocated memory; determining that the first backing array does not have capacity in the predefined chunk of allocated memory for a subsequent value identifier to be inserted therein; generating, based on the determining, a second backing array in a different chunk of allocated memory including the first set of value identifiers and having capacity for the subsequent value identifier to be inserted therein; and inserting the subsequent value identifier in the second backing array.

20 . A system comprising:
at least one data processor; and memory storing instructions which, when executed by the at least one data processor, result in operations comprising: mapping, in a columnar in-memory database, each distinct value in a column to a different value identifier; populating a first backing array of an index vector by inserting at each position n in the first backing array, the value identifier corresponding to the value row n has for the column, the first backing array having a predefined chunk of allocated memory; determining that the first backing array does not have capacity in the predefined chunk of allocated memory for a subsequent value identifier to be inserted therein; generating, based on the determining, a second backing array in a different chunk of allocated memory including the first set of value identifiers and having capacity for the subsequent value identifier to be inserted therein; and inserting the subsequent value identifier in the second backing array.

Assignees

• Blanco Rolando
• Schreter Ivan
• Gottipati Chaitanya
• Andrei Mihnea
• Sherkat Reza

Inventors

• Blanco Rolando
• Schreter Ivan
• Gottipati Chaitanya
• Andrei Mihnea
• Sherkat Reza

Classifications

• G06F16/28

  Databases characterised by their database models, e.g. relational or object models · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F3/0604 Primary

  Improving or facilitating administration, e.g. storage management · CPC title