Versioned insert only hash table for in-memory columnar stores

Patent metadata

Field	Value
Publication number	US-10255309-B2
Application number	US-201414553654-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	Apr 9, 2019
Grant date	Apr 9, 2019

Abstract

At least one read operation is concurrently performed with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database. The backing array maps a plurality of pointers each to a respective bucket. Each bucket includes at least one state bit and a hashed value of a corresponding key. Thereafter, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted is iteratively determined (such that each first available position has no corresponding pre-existing pointer). Subsequently, for each write operation, the pointer to the new bucket containing the key/value pair is inserted at the corresponding first determined position in the backing array. Related apparatus, systems, techniques and articles are also described.

First claim

What is claimed is:

1. A method comprising:
concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key;
iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising:
identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,
iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and
creating a new bucket for the candidate position that does not have a pre-existing pointer, the new bucket encapsulating at least one state bit indicating that the bucket is not overflown, and the key/value pair; and

inserting, for each write operation, the pointer to the new bucket containing the key/value pair at the corresponding first determined position in the backing array.

2. The method of claim 1 , wherein the identifying the next candidate position in the backing array uses a compare-and-swap (CAS) technique to attempt to establish the pointer in the different position.

3. The method of claim 1 further comprising:
checking if there is already a pointer at the next candidate position;
creating a new bucket if there is not already a pointer at the next candidate position, the new bucket encapsulating (i) at least one state bit indicating that the bucket is not overflown, and (ii) the key/value pair.

4. The method of claim 1 , wherein the iteratively identifying and marking continues for a pre-determined number of times.

5. The method of claim 1 , wherein a size of the backing array is increased at such time that the pre-determined number of times is exceeded.

6. The method of claim 1 further comprising:
determining, for at least one write operation, that the value is already in the hash table; and
notifying a caller of the write operation that the value is already in the hash table.

7. The method of claim 1 , wherein the at least one write operation comprises executing a write functor.

8. The method of claim 7 further comprising:
associating a semaphore with each hash table; and
assigning the semaphore to a single write operation.

9. The method of claim 8 further comprising:
releasing the semaphore after execution of the write functor.

10. The method of claim 9 further comprising:
waiting, by a subsequent write operation, the semaphore assigned to the write operation to be released; and
executing a write functor by the subsequent write operation on the backing array.

11. The method of claim 1 further comprising:
accessing, by a reader operation, a backing hash table, wherein the backing hash table is not deallocated while the reader operation accesses the backing hash table.

12. The method of claim 11 , wherein the backing hash table is not deallocated if the reader operation continues to access the backing hash table and a new backing hash table is established by a writer operation.

13. A non-transitory computer program product storing instructions which, when executed by at least one data processor forming part of at least one computing device, result in operations comprising:
concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key; and
iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising:
identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,
iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and
creating a new bucket for the candidate position that does not have a pre-existing pointer, the new bucket encapsulating at least one state bit indicating that the bucket is not overflown, and the key/value pair; and

inserting, for each write operation, the pointer to the new bucket containing the key/value pair at the corresponding first determined position in the backing array.

14. The computer program product of claim 13 , wherein the at least one write operation comprises executing a write functor.

15. The computer program product of claim 14 , wherein the operations further comprise:
associating a semaphore with each hash table; and
assigning the semaphore to a single write operation.

16. The computer program product of claim 15 , wherein the operations further comprise:
releasing the semaphore after execution of the write functor.

17. The computer program product of claim 16 , wherein the operations further comprise:
waiting, by a subsequent write operation, the semaphore assigned to the write operation to be released; and
executing a write functor by the subsequent write operation on the backing array.

18. A system comprising:
an in-memory database comprising:
at least one processor; and
memory storing instructions which, when executed by the at least one data processor, result in operations comprising:
concurrently performing at least one read operation with at least one write operation that each insert a key/value pair into a backing array of a backing hash table of a hash table forming part of a columnar in-memory database, the backing array mapping a plurality of pointers each to a respective bucket, each bucket comprising at least one state bit and a hashed value of a corresponding key;
iteratively determining, for each write operation, a first available position in the backing array at which a pointer to a new bucket containing the key/value pair can be inserted, each first available position having no corresponding pre-existing pointer, the iteratively determining comprising:
identifying a candidate position in the backing array for the bucket containing the key/value pair by applying a modulo operation of the size of the backing array to a hash of the key determined using the hash table,
iteratively, until the candidate position does not have a pre-existing pointer, (i) marking the at least one state bit for the bucket corresponding to the candidate pointer as overflown and (ii) identifying a next candidate position in the backing array, and
creating a new bucket for

Assignees

• Blanco Rolando
• Schreter Ivan
• Legler Thomas
• Sap Se

Inventors

• Blanco Rolando
• Schreter Ivan
• Legler Thomas

Classifications

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F17/30324

  Physics · mapped topic

• G06F17/30315 Primary

  Physics · mapped topic