Versioned insert only hash table for in-memory columnar stores

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.

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 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.