Count Indexing for Fast Updates in Column Store Databases

Researchers in Prof. Michael Genesereth's laboratory have developed "count indexes", a unique indexing scheme to efficiently update run-length encoded columns in column stores. This method significantly lowers the update complexity to be logarithmic in the number of the tuples as compared to current methods that update a relation in time that is linear in the number of the tuples. The proposed indexing scheme can be generalized to other compression schemes and supports in-place updates of tuples (both inserts as well as deletes). Count indexing enables the "best of both worlds" scenario in column stores by supporting fast in-place updates while allowing efficient look-ups.