4 ms·

@OP: A really good read and performance find. I wouldn't have expected those kinds of gains, but I wouldn't have considered the impact on CPU optimization. Th

by Rapzid 12y ago

@OP: A really good read and performance find. I wouldn't have expected those kinds of gains, but I wouldn't have considered the impact on CPU optimization. The improvements are fantastic! Could you speak a bit about how the vectorized approach benefits more from CPU features? Does it work better with the cache? Aside: This is a good concept to keep in mind when using channels in Go as well. When you have an overhead to moving a single unit of work through a process, and you're doing MANY of these shipments, there are savings to be had from ensuring your unit of work is large(vector/slice of items vs a single item).

jandrewrogers 12y ago
Vectorization shifts the performance tradeoffs in the storage model. As a practical matter, users design their applications around the performance tradeoffs of database engines, so you really can't change your storage model without alienating users. There are roughly four different storage models in databases, with their own acronyms: NSM (pure row structured storage), DSM (sorted columnar structured storage), PAX (like DSM but where a row is stored within a single page), VSM (array structured individual columns where every element in a row has the same index). PAX and VSM are hybrid storage models. All four are used in real commercial systems. Vector storage models (VSM) are extremely good for real-time workloads; they sacrifice a little bit of insert performance for a major improvement in query performance relative to NSM, but their insert/append performance is much better than DSM or (to a lesser extent) PAX. The reason vector models are extremely efficient in terms of query processing boil down to a few facts. First, a column can be streamed into the CPU as a sequential memory scan, which is very efficient. Second, constraints on multiple columns can be trivially parallelized. Third, searches across multiple columns/attributes can usually be constructed as a bitmap per column, and then composed as simple AND/OR operations over those bitmaps, which is extremely fast. Fourth, individual columns in this model are amenable to the use of vector instructions for evaluation in the CPU, saving even more clock cycles. There is no ideal storage model, it really depends on the workload. Some sophisticated databases will change the storage model to adapt to the likely access patterns, such as NSM (great for a page with a lot of inserts) to PAX or VSM (great for queries when a page is unlikely to change much).
- ntoshev 12y ago
  The cstore_fdw extension uses the Optimized Row Columnar (ORC) format, which seems to be PAX in your nomenclature. The improvements he accomplished seems to be related just to the first "fact" that you listed, which applies to all column stores.
  - jandrewrogers 12y ago
    I am not familiar with that particular implementation. PAX is not my nomenclature, it is what sorted in-page columnar formats are called in the literature. (It is what the first paper describing them called them.) Not all columnar formats have great CPU streaming performance and even then it is data type dependent. Many columnar formats have significantly worse streaming performance than vector formats because only the latter is primarily optimized for it and column stores will trade that for other things (like format compressibility). And for data types that have no mathematical order of any kind e.g. interval data types, columnar formats effectively degenerate into very inefficient vector formats. It is still an open academic discussion.
yangyang 12y ago
Take a look at MonetDB, an open source column store database [1]. There was a commercialised extension to that called X100 targeting cache efficiency [2]. That became VectorWise [3]. [1] http://www.monetdb.org http://www.monetdb.org [2] http://www.cidrdb.org/cidr2005/papers/P19.pdf http://www.cidrdb.org/cidr2005/papers/P19.pdf [3] http://en.wikipedia.org/wiki/Vectorwise http://en.wikipedia.org/wiki/Vectorwise

by Rapzid 12y ago

jandrewrogers 12y ago

Vectorization shifts the performance tradeoffs in the storage model. As a practical matter, users design their applications around the performance tradeoffs of database engines, so you really can't change your storage model without alienating users. There are roughly four different storage models in databases, with their own acronyms: NSM (pure row structured storage), DSM (sorted columnar structured storage), PAX (like DSM but where a row is stored within a single page), VSM (array structured individual columns where every element in a row has the same index). PAX and VSM are hybrid storage models. All four are used in real commercial systems. Vector storage models (VSM) are extremely good for real-time workloads; they sacrifice a little bit of insert performance for a major improvement in query performance relative to NSM, but their insert/append performance is much better than DSM or (to a lesser extent) PAX. The reason vector models are extremely efficient in terms of query processing boil down to a few facts. First, a column can be streamed into the CPU as a sequential memory scan, which is very efficient. Second, constraints on multiple columns can be trivially parallelized. Third, searches across multiple columns/attributes can usually be constructed as a bitmap per column, and then composed as simple AND/OR operations over those bitmaps, which is extremely fast. Fourth, individual columns in this model are amenable to the use of vector instructions for evaluation in the CPU, saving even more clock cycles. There is no ideal storage model, it really depends on the workload. Some sophisticated databases will change the storage model to adapt to the likely access patterns, such as NSM (great for a page with a lot of inserts) to PAX or VSM (great for queries when a page is unlikely to change much).

ntoshev 12y ago
The cstore_fdw extension uses the Optimized Row Columnar (ORC) format, which seems to be PAX in your nomenclature. The improvements he accomplished seems to be related just to the first "fact" that you listed, which applies to all column stores.
- jandrewrogers 12y ago
  I am not familiar with that particular implementation. PAX is not my nomenclature, it is what sorted in-page columnar formats are called in the literature. (It is what the first paper describing them called them.) Not all columnar formats have great CPU streaming performance and even then it is data type dependent. Many columnar formats have significantly worse streaming performance than vector formats because only the latter is primarily optimized for it and column stores will trade that for other things (like format compressibility). And for data types that have no mathematical order of any kind e.g. interval data types, columnar formats effectively degenerate into very inefficient vector formats. It is still an open academic discussion.

yangyang 12y ago

Take a look at MonetDB, an open source column store database [1]. There was a commercialised extension to that called X100 targeting cache efficiency [2]. That became VectorWise [3]. [1] http://www.monetdb.org http://www.monetdb.org [2] http://www.cidrdb.org/cidr2005/papers/P19.pdf http://www.cidrdb.org/cidr2005/papers/P19.pdf [3] http://en.wikipedia.org/wiki/Vectorwise http://en.wikipedia.org/wiki/Vectorwise