1

My understanding of how regular rowstore indexes are stored is in a type of b-tree data structure, but I was wondering because of the different nature of columnstore indexes, what type of underlying data structure is used?

  • 1
    Here's a research paper with some more formal tone. But I don't think that there's a common name for that "storage structure", in the way that we call row-indexes B-trees. So, in the end, we seems to be talking about terminology, and for col-store indexes we seem to have lack of formalism. FWIW, in the end, in SQL Server, the data is in blob-pages. microsoft.com/en-us/research/wp-content/uploads/2013/06/… – Tibor Karaszi Jun 10 at 8:59
  • The doc shows the organization of a columnstore index in terms of rowgroups, column segments, and deltastore. However, it doesn't call out the columnstore segments are physically stored as blobs. – Dan Guzman Jun 10 at 10:44
  • 1
    Does that linked duplicate answer your question? It seems to cover all of the bases of how columnstore indexes are structured, and links to even more detailed coverage. – Josh Darnell Jun 10 at 13:33
5

We usually think of an index as a way of rapidly finding all references to a given piece of information. In a textbook given a topic we can find all pages that mention that topic. In a database given a column value we can find all rows that have that value.

Calling a columnstore an "index" in this sense is a bit of a misnomer. It is not intended to provide fast lookup for a specific column value's rows. Rather it is intended to quickly provide results of aggregates over large datasets. As such it is a data format in itself. The columnar data store, sometimes called the decompositional storage model (DSM), is well-known and venerable. Many proprietary and open-source DBMS offer it.

The basic idea of a column store is that values for a column are stored contiguously on disk. Then an aggregate on that column can efficiently pull that column, and only that column, from disk reducing the number of disk blocks that must be read. Further, since all the data values in a block are from the same domain compression on that block is likely to be very efficient, further reducing the number of blocks required. Compression can be much better than a generic ZIP - dictionaries, run-length and delta encodings can be used.

For various reasons it is better to break up rows into large groups before compressing and storing them. SQL Server calls these groups "row groups", which are made up of "column segments". Each row group holds just over one million rows. When the segments are constructed the server extracts some metadata such as min, max and (perhaps) sum for that column. This metadata is sometimes called zonemaps. At run time these zonemaps can be compared to the query predicates and, if the predicate does not lie between the segment's min and max values, processing can entirely avoid reading those blocks from disk. This is called segment elimination and is analogous to partition elimination. Moreover some queries can be answered directly from the zonemaps e.g. "select min(column) from table" can be answered by comparing the "min" segment summary values from the zonemaps.

I would note that B-Trees are not the only structure for indexing rowstores, it's just it is the only one available to database developers using SQL Server.

| improve this answer | |
  • Thank you! This part of your answer really helped me conceptualize how the data is stored and that makes a lot of sense to me in regards to when one should use a column store index: "The basic idea of a column store is that values for a column are stored contiguously on disk. Then an aggregate on that column can efficiently pull that column". – J.D. Jun 10 at 20:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.