INSERT performance in column stores

The most common question I am asked about column stores is, "Isn't INSERT performance poor?" The rationale for this question stems from the fact that in a column store a new tuple must be 1) split into its component column values, and 2) each such value must then be written to a different place (file). This would seemingly result in writing a large number of different disk blocks for every insertion. Furthermore, if the physical representation of the column is sorted and compressed, preserving this will only add to the overhead of an INSERT. While there is some truth to this line of reasoning, the problem can be overcome with the proper implementation.


Overcoming the INSERT performance penalty

One approach to significantly mitigating the performance problem is to batch INSERTs and to perform the sorts, compression, and disk writes in large groups. By doing this, existing data is kept on disk in its sorted and compressed form and new tuples are batched in a separate memory space or cache. This cache is maintained as columns in insertion order. Periodically, an asynchronous process runs and writes a batch of tuples, merging them into the disk-based storage system. In this way, the performance cost of sorting and compression is shared and amortized across many tuples. The expected number of disk writes per INSERT will also decrease as the batch size grows. Further, if the insertion-order cache is stored in main memory, this structure can be quickly scanned.

A fair question to ask is whether this approach would mean that the answers to queries would be stale. The answer is no ... if the query evaluator looks in both places (the disk and the cache). To do so would require the query optimizer to generate two plans since the data is structured differently in each location, but the extra query planning work is worth the trouble because of the boost in INSERT performance.

It should also be pointed out that column stores can partition tables across a collection of shared-nothing nodes in a cluster. If INSERTs are randomly distributed on the partitioning key, then the load introduced by high INSERT rates is distributed evenly across the cluster. If the INSERT rate grows, more nodes can be added to cope with the increase.


A note about ACID

Of course, in order to support ACID transactions in this setting, there must be a safe way to allow committed data to reside in main memory. This can be accomplished by keeping redundant copies in multiple distributed main memories. In general, one can achieve k-safety, where k is the number of nodes that can fail without losing any work, by keeping data copies on k+1 different machines. All INSERTs will be sent to all k+1 relevant sites and stored in their main memory caches. Once all these copies are installed, the tuple is stable (subject to the k-safety constraints).


INSERT Performance Benchmarks

By implementing all these strategies, it is possible to have a column store with INSERT performance that is at least competitive in performance with that of the major row stores. In fact, in many cases, benchmarks have shown that load performance for a column store is typically better than that of a row store.