Versioned insert only hash table for in-memory columnar stores

US10255309B2 · kind B2 · utility

Assignee

• SAP SE · DE

Inventors

• Rolando Blanco · Schreiber, CA
• Ivan Schreter · Malsch, DE
• Thomas Legler · Walldorf, DE

Key dates

• Filing date: Nov 25, 2014
• Grant date: Apr 9, 2019
• Expiry date: Sep 16, 2037

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/2237
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

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.