9 ms·
The design and implementation of modern column-oriented database systems
- walterbell 8y agohttp://www.timestored.com/time-series-data/column-oriented-databases http://www.timestored.com/time-series-data/column-oriented-d... > Open Source Column-Oriented Databases: There are three available open source column databases, all were based on works of research groups that later saw commercial spinoffs. C-Store produced vertica, MonetDB spawned Vectorwise and LucidDB was DynamoBI. Each project has stagnated as the team around them moved on to commercial endeavours. Only MonetDB appears to be still actively developed, it's also the one that seems most feature complete as we'll see later. Is the above an accurate characterization of OSS column-oriented databases? There is also MapD which uses GPUs, https://github.com/mapd/mapd-core https://github.com/mapd/mapd-core > MapD Core is an in-memory, column store, SQL relational database that was designed from the ground up to run on GPUs.
- threeseed 8y agoCassandra also counts as a column orientated database.
- pedrosorio 8y agoNot of the kind being described here. Cassandra is a https://en.wikipedia.org/wiki/Wide_column_store https://en.wikipedia.org/wiki/Wide_column_store not column oriented: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes
- manigandham 8y agoIt's actually not. Cassandra is a (badly named) wide-column database, which is more accurately described as an advanced key/value store, specifically a sorted hash map with multiple levels of values, which can also be part of the primary and secondary keys.
- olooney 8y agoI'm curious about this comment: > The ultimate performance boost from compression comes when operators can act directly on compressed values without needing to decompress. Consider a sum operator and RLE encoded values. It suffices to multiply the value by the run length. It sounds very impressive and I can see in theory how it could benefit COUNT(), COUNT(DISTINCT ), SUM(), AVG(), MIN(), and MAX()... in other words, pretty much all of the common aggregation functions. For example, COUNT(DISTINCT *), MIN(), and MAX() can literally just ignore run length as those are known duplicates, while the others simply need to use the run length as a factor. Does anyone know if this specific optimization is actually implemented in any real-world database?
- ryanworl 8y agoMany analytics databases implement something even stronger than that. They keep what are called "zone maps", which are pre-computed statistics for groups of rows that contain those same aggregate functions. This allows for those types of analytics functions, but also for pruning of data to read at all during regular table scans further in the query execution.
- kwillets 8y agoFrom a Vertica query plan: explain select country, count(*) from tablename group by 1 ... +-GROUPBY PIPELINED (GLOBAL RESEGMENT GROUPS) [Cost: 79, Rows: 1] (PATH ID: 1) | Aggregates: count(*) | Group By: tablename.country | Execute on: All Nodes | +---> STORAGE ACCESS for tablename [Cost: 78, Rows: 14M (1 RLE)] (PATH ID: 2) ... Note the row count at the top level. This type of thing only works when the group column is the first in the projection sort order (or for multiple columns, a prefix of it). Generally GROUPBY PIPELINED indicates that the sort order is being used (including RLE).
- manigandham 8y agoThis is used by all modern column-oriented databases. Combine the compression techniques with other metadata like max, min, avg, mean, null bloom filters, and more that is stored with each partition (group of X number of rows per column compressed together) and you can actually skip reading any data at all for many aggregation queries.
- neonate 8y agoDoes anyone know how much of this analysis does or doesn't apply to kdb? I wish it had been included.
- manigandham 8y agoAll of it applies. kdb+ is one of the most advanced and has unique features like special "as of" joins and complex math expressions because it's designed for heavy fintech uses.
- manigandham 8y agoModern column-oriented databases are rather incredible at what they do, and I'm surprised by how little they are used or known about. Redshift, BigQuery, Snowflake, Azure SQL DW, SQL Server, MonetDB, Vertica, Greenplum, MemSQL, kdb+, Clickhouse, even Druid are all column-stores that can do sub-second queries on massive amounts of data. I also want to note that time-series databases are basically obsolete at this point because time-series data is very well handled by these OLAP column-stores. Create a table with time as a primary or sort key and you'll get fast queries with full SQL and joins.
- beagle3 8y agoKdb+ is a time series database; and in my experience, for this work it is much, much faster than vertica, sql server and Monet.
- amelius 8y agoSo what kind of operations does a column store typically allow? Which of these operations are optimized for: - Appending cells to a column - Removing a range of cells from a column - Searching for data in a column (exact search or complicated text search). - Performing a map over a column (applies user defined function to each cell, producing a new column or makes changes in-place) - Filtering a column using a user-defined function. - Combining two or more columns through some user-defined function - Sorting - more ?
- nwatson 8y agoI'm no expert, but here's my take ... + "Appending cells to a column" ... when writing data to a "table" the columnar database goes through a lot of effort to compress each column of data into separate files on disk -- the benefits of compression come from regarding many "rows" of data, per column, at once, so appends probably go to transient areas, and then in the background recent appends are merged-and-compressed into files on disk ... data in all columns in the columnar DBs usually are stored sorted per some timestamp key, and that data doesn't always come in perfect order (e.g., there are different latencies for log records from the same timestamp arriving from different hosts / devices / applications in an SIEM system) -- so appends will be fast to keep up with the huge ingestion flow, but a lot of painstaking expensive compression is done while merging, and re-merging data -- most columnar DBs systems will segment data based on buckets of the timestamp range (and perhaps the more dense the table time-wise, the narrower are the buckets) + "Removing a range of cells from a column" ... removing a range of timestamp-ordered or even worse a filtered set of cells will be very expensive -- for all columns in the range to be removed, all deleted items will eventually need to be removed (e.g., 100 and 200 rows in two different timestamp buckets, per column, of 1,000,000 rows of data per bucket) -- reading, uncompressing, and filtering out removed columns will be fast -- recompression and re-writes will be slow ... there may be ways these DBs use side-data to instead, for a period before "vacuum" or in perpetuity, mark rows as deleted rather actually removing and recompressing the data -- these DBs are usually meant for write-once-and-never-delete, read-many-times situations + "Searching for data in a column" -- the main benefit from columnar DBs is that, once the data is available in compressed form on disk ... a query needs to read from disk only the specific columns involved in the search filter/terms, plus those needed to generate the output payload -- a typical query might surface just 5 of 80 columns, so compared to a traditional DB that reads all the data for each row (if data strays outside indexed columns), a columnar search will quickly fetch only the already-compressed data for a small number of columns off disk. queries usually involve scanning a huge number of rows in a timerange often expanding multiple timestamp buckets -- for each column, if the columns were stored uncompressed, the disk latency and bandwidth for reading the huge number of row values per column would dwarf the time taken in CPU/memory for processing the data -- with a columnar-DB with compressed columns, each disk read (the slow part) yields a huge number of easily-and-quickly-decompressed row values from that column. the compression is slow, but decompression is very fast ... so many rows of data, per column, can be pumped out to filtering/aggregation portions of the engine, much faster than in a traditional DB (I worked at a place that got 40x compression over traditional DBs) + "Performing a map over a column" -- the DB engine can process many rows across the columns of data involved quickly enough -- filters based on value are easy, functions can be applied to columns of data, or data from multiple columns can be joined -- as long as computations involve only data per-row, is usually fast -- it's additional aggregation, and multi-level query processing (results of one query, perhaps aggregated, feed into another), that involve careful planning of a query, especially in a distributed cluster where aggregation "keys" may require retrieval of rows from shards on different hosts + "Filtering a column using a user-defined function" ... fast, just like prior point + "Combining two or more columns through some user-defined function" ... fairly fast + "Sorting" ... here it would get tricky, because to sort a bunch of raw records without filtering takes a huge number of resources ... unless your sort is already on the timestamp field that's the organizing sort field for the columnar DB ... most queries won't involve retrieving 5 hours of data, sorting the raw data by some field other than "main timestamp", and returning results ... usually data is fetched, some aggregation is done in the query (perhaps multiple levels), and sorting is done on the vastly reduced (several orders of magnitude) data -- this kind of sorting is much easier + ... + "Joins" ... joins between two huge datasets on the raw contents of each table will be real expensive ... so expensive that the columnar DB vendor I worked at (starting in 2000) chose to not implement joins other than joining massive-DB-table-data with vastly smaller lookup-tables -- the value proposition for us was not in doing the joins, it was vastly reduced, reliable storage of huge numbers of log records, resulting in cheaper compression and very fast querying in a distributed cluster
- toolslive 8y agoSlightly different topic, but there is value in using a column based ORM strategy where each attribute has it's own table, and objects are dispersed over the tables. It's very flexible and most of the time you just want a few objects with a certain attribute having a certain value anyway.
- phaedrus 8y agoSounds a lot like the array-of-structs vs struct-of-arrays design decision for game engines. One of the features Jonathan Blow put into the programming language he has been working on (JAI) is better support for this dichotomy. IMO most programming languages have optimized the language only for array of structs and historically all but ignored the struct of arrays case.
- toolslive 8y agoyes, and it has the same performance implications (struct-of-arrays performs better as it yields better locality when iterating over the fields)
- amelius 8y agoWhat is the difference between a column-oriented database, and storing your data in a regular database where all tables have only a single column?
- phaedrus 8y agoIf I understood what I just read in this article and on the MonetDB website, I believe if you were to implement the same logical design it would actually be all tables having two columns: one for the object id (OID, or row ID) and one for the particular data attribute. Then to build a tuple it would be a join on OID for the attributes you need. The physical design of the column oriented DB can omit the explicit OID because it is just the array position.
- wenc 8y agoColumnar databases have optimizations for columns, like RLE compression, Bloom filters, etc. that speed up filtering, lookups and aggregations. Row-stores don't typically implement these optimizations. That said, some traditional row-store databases like SQL Server support columnar indices, which give row-oriented databases similar performance characteristics to columnar. The downside is lower write speed (the columnar indices have to be maintained, and the writes are still done row-wise).
- manigandham 8y agoSQL Server actually does have full column-oriented storage. They just call it a columnstore index but it's not a true index and it will turn the whole table into column-oriented compressed data files. It originally didn't support any updates in v2012 because of this, but now has evolved and can even combine it with in-memory option to support in-memory columnstores that support constant real-time updates.
- wenc 8y agoRight, but I would argue that it is a form of an index. An index is simply an internal derived data structure that has to be kept in sync with the source dataset. All indices are derived views of the original dataset that are optimized with certain characteristics.