The ACM SIGMOD Programming Contest Implementation

The Task

The task was basically implementing a Main Memory Transactional Index for main memory data. The performance criteria is based on execution time on a given workload. Type of queries to be supported are range queries and exact match queries. Index should support updates, deletes and inserts. The index should be capable of handling multiple transactions concurrently. Data types are 32-bit and 64-bit integers and variable length strings. Payloads are also varchar strings with a given maximum length. Total amount of data to be stored is at maximum 4 GB. The benchmark is a combination of scans (%10), gets (%30) and updates (%60). More detailed information about the specifications can be found on the programming contest webpage.

My Approach and implementation

Our implementation uses T-Tree [1] as the main data structure and Two Phase Locking (2PL)[2] for the concurrency control. T-Tree is a kind of self-balancing data structure suggested for main memory resident database systems. It is very similar to AVL Tree, except it may contain more than one item at each node. In our implementation, node sizes vary for different key types. For reference one can see the source code. Locking is done at a relation level, basically each transaction needs to acquire the lock on the index (relation) to do some operation.

My T-Tree implementation is a little modified version of the original suggested T-Tree. Normally when searching in a T-Tree, you have to compare the key with the minimum and maximum key of the node. As a result, when your node size is more than the cache line this causes some penalty for the maximum key comparison. My implementation keeps the maximum key in the first cache line bytes of the node, and whenever the maximum key changes this maximum key is also updated. Consequently, during searches all the comparisons are done from the cache line. This was one of the improvements of my implementation. Also cache conscious layout of the T-Tree Nodes, such as keeping payloads in a separate location than the keys of the node and only keeping pointer offsets for payloads are some of the other optimizations. Also duplicate keys are handled with another auxilliary data structure which is a binary search tree. At the record of the duplicate key, we keep a pointer to the binary search tree of the payloads. In the Concurrency control, we keep lock information directly on the index data structure, so we are not keeping additional lock hash table and this enables us to efficiently acquire lock information about the indexes. For memory management we implemented a simple Buffer Manager. Buffer Manager takes care of memory allocation and re-use for most of the memory intensive operations. We do pre-allocation of memory where necessary and this speeds up our implementation during the runtime. During the runtime, when memory is not necessary it is usually given back to the Buffer Manager and it can be re-used in the life-time of the application. For more detailed information on the implementation feel free to contact the author. All the source code is written in ANSI C.

Source code

The source code as submitted to the SIGMOD contest. Download

References