The design and implementation of modern column-oriented database systems

Kdb+ is a time series database; and in my experience, for this work it is much, much faster than vertica, sql server and Monet.

> Create a table with time as a primary or sort key and you'll get fast queries with full SQL and joins.

Be careful with this. You can easily end up with pathologically bad performance, resource usage, contention etc. if most of your requests end up being directed to the same workers or shards in a distributed system. Partitioning by time can cause this because most queries tend to be for recent time windows.

Time can be a decent primary key withing a shard, but is normally a really bad choice for any key that's used to partition data between shards. Make sure you understand how your system partitions data so you don't fall into this.

Apologies if that came across as pedantic - you probably already know this, but hopefully some other readers can be saved from learning this through painful experience.

Most column-oriented database architectures have a giant weakness that limits their utility, which was briefly mentioned at the end of the article: they offer poor performance for high-throughput mixed workloads, especially if there is a real-time component to it. Getting data into the system fast enough is a real problem. As more analytics become operational in nature, being able to scale online mixed workloads becomes the key feature. In practice, these still use vector-ish internal organization but the techniques differ considerably from many of the ones in the article, since online write performance is critical. Scalable online ingestion performance is a killer feature for many analytics systems but few database kernels are designed for it (I specialize in high-throughput mixed workload kernel design).

Also, time-series database implemented as you suggest will work in some cases, and better than some might expect if you are clever, with the caveat that it has significant weaknesses and scalability limitations. Many real-world time-series data models and workloads would run poorly on a database organized this way. Sorting or sharding on time in the data organization is usually a mistake in my opinion. Some high-performance time-series databases don't use time as a sort/shard key at all, instead leveraging the approximate partial order of the underlying data sources directly. This often offers orders of magnitude better write performance with little or no loss of query performance in practice and it generalizes better.

This is all a very complex but fantastically interesting technical design area. I firmly believe that scalable high-throughput mixed-workload analytical databases are possible, but they largely don't exist. Yet.

Cassandra also counts as a column orientated database.

I'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

He didn't clarify it in the article, but deletes are basically flagged by a "deleted" column, and updates are implemented as delete/insert. The overriding idea is that a row is never overwritten; storage is write-only. Containers are periodically merged into larger containers (an LSM tree), and deletes are purged at that time.

Sounds 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.

All 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.

Many 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.

From 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).

This 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.

If 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.

Columnar 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).