> Those consequences are the reason that most database systems are built for either transactions or analytics, and not both. [24]
> [...]
> [24] People have tried to build one system that does both in the past (HTAP, or hybrid transactional/analytical processing), but those attempts generally didn't work out. Some newer systems seem to be bridging the gap, however. CedarDB, the commercial version of Umbra (a research system from TU Munich), runs transactions and analytics on just one engine and one copy of the data. Databricks' Lakebase keeps Postgres (a row store) as the engine for transactional queries, but its storage layer rewrites the same data into columnar formats in the background, allowing an analytical engine to query it.
The footnote says "those attempts generally didn't work out" but then mentions Lakebase and CedarDB as newer efforts. Can anyone speak to whether or not CedarDB, Lakebase (and any others?) are achieving the fabled transactions + analytics in one database? Should we expect, at some point in the near future, for transactions + analytics to be standard in all databases, or is combining them a niche / esoteric thing with many tradeoffs?
It is certainly possible. I built a highly optimized KV store, originally designed to add tags (key-value pairs) for the object store I invented a few years ago. This tagging system turned out to resemble a columnar store database, so I started using it to create relational tables.
As predicted, it was very good at performing analytic operations; but it also was very fast at traditional OLTP operations too. I benchmarked a large number of queries against other databases and in the majority of cases, it was actually faster. In some cases it was much faster. It was able to do all this using just one copy of the data without needing to create and maintain separate indexes.
There are several short demo videos on my YouTube channel (listed in my profile).
There are always tradeoffs. Databases are fundamentally about managing optimizations, and the question is whether those tradeoffs make sense for your workload.
HTAP has historically been niche because the cost of analytics on fresh data wasn't worth the squeeze (sooner or later the MBAs step in). Separating the OLTP and OLAP layers gives you better workload isolation and the ability to optimize each independently.
Databricks Lakebase/LTAP uses Postgres for transactions and lakehouse engines for analytics, with a shared storage layer. They also use Spark to build Postgres pages in parallel and write them directly to storage, avoiding the single-writer bottleneck when loading large volumes of data.
SingleStore takes a different approach: a distributed database based on MySQL with an in memory rowstore for transactions tightly coupled with a merger to columnstore for analytics.
I don't think HTAP DBs will become the default for every use case. But I do think the space will grow as we move towards agents and automated decision making and optimizations.
Agree with everything here. Workload isolation and independent scaling in particular are the reasons I never see HTAP work out in practice, even beyond expected loss from not using the more specialized solution. A very low latency storage handoff between two engines always seems like 80% of value with 20% of operational headache.
> HTAP has historically been niche because the cost of analytics on fresh data wasn't worth the squeeze (sooner or later the MBAs step in). Separating the OLTP and OLAP layers gives you better workload isolation and the ability to optimize each independently.
That feels like something HTAP databases could offer as a choice!
- Things you can always do
- Things you can do when optimizing for fresh data
- Things you can do when optimizing for analytics on old data
- Things you can do, but with poor performance
This feels like one of those cases where people choose to make software simple instead of, and at the cost of (not) making operations simple.
You are correct! And sadly the vast majority of people don't want to make choices or think about that tradeoff.
If it can't outperform pure OLTP and it can't outperform pure OLAP then there is no pit of success for such an HTAP system.
The unfortunate part is that the vast majority of software out there in the world would be served perfectly with an HTAP solution.
The fortunate part is that for a lot of problems you can just run Postgres and then when you need analytics you can still use Postgres, until you hit scaling issues (if ever).
I've never seen a project choose to solve OLAP and OLTP upfront and succeed.
I think there's never going to be a point where you can have the kind of performance you can get by optimising a datastructure for a 'fixed' dataset. Nor can you get the maximal performance updating data if you need to maintain a useful datastructure.
A simple case is a sorted list, you can sort it after every update, you can ignore the ordering and sort it as needed, or you can use a datastructure that is typically O(log(N)) at both updates and retrieval. Better datastructurs help, but they cannot remove the tradeoff entirely (in fact O(log(N)) inserts are kind of theoretically minimal, though a trie can do it in O(1) for fixed length datatypes).
There's a general trick which combines the time complexities.
In the case of a sorted list, it's keeping a sorted list, along with a growing small unsorted list that you will query or sort when needed.
This works for kernel timer trees, database storage, and indexes.
Keep your "fixed" data up to some checkpoint in an efficient form, and your "new" data since the checkpoint in a faster-updating, slower-querying form. When doing queries, read both and merge, and maybe sort parts of the new data on demand. The new data will be slower to query, but it should also be smaller.
At carefully chosen times, transfer data from the new form to the "fixed" form, either with an incremental update if you can, or by rewriting the fixed form entirely. It doesn't have to stop at two layers, and shouldn't if the fixed form is large, or if you want unlimited scale.
Choosing the right times and how much to update (the whole key range, intervals, predicate subsets, ertc) is an interesting algorithm design problem. When you get it just right, you can get excellent performance in fast-queryable compression and continuous fast-updates at the same time. (I'm building a database engine that does this in my spare time.)
There's also TiDB which has decent adoption. It allows for columnar replicas of transactional data and exposes both over the same MySQL-compatible interface.
So just putting it out there. Compressed inverted indexes for "documents" does columns. For each word you might want to search on, keep a list of the documents that contain it. For words that occur in all documents the compressed index is zero long; for those words occuring in jut one document, the index is 1 London. The words in half the documents take the most space, but are also the best discriminators.
The simple example of computing an average over a single column makes it seem like each columns data is stored by itself, but as soon as you want to do something with the correlation of two columns (such as a simple single column group by) doesnt that mean that each column would have to store both the column's value and some kind of row identifier that lets you join with the other columns in the same record? I've never looked into columnar stores so this is an honest question, I just always assumed thats how it would have to be structured
You correlate positionally, within a block/rowgroup.
If you run e.g. a `SELECT SUM(col1) WHERE col2 = x`, a columnar DB will typically produce produce a bitmap from of col2, use it to mask col1, then sum what's left—all very efficient operations.
> a columnar DB will typically produce produce a bitmap from of col2
Bitmaps fell out of fashion after the branch predictor became the slowest part of vectorized execution.
Most columnar dbs use compact selection vectors and loop over the values within them, rather than an if() over each row.
Imagine you had 1024 rows in the col1 column and only 1 row is selected, then this optimization has to only do 3-4 branches before the vector is done vs a bit-map which has to always do 1024 checks.
This became relevant somewhere in the mid 2010s and is called out in the Hive design[1] docs from that era.
"a database that keeps each record's details together can't take advantage of that: to read two columns, it has to read all five."
My understanding is that modern databases will take advantage of that if you create an index of those fields - ie it'll read from the index, not the records.
We generally refer to an index that holds the data it indexes at its leaves a "clustered index". But this only means that the tuples are organized according to the ordering of the index: you still generally store the entire record (all columns/attributes) together.
For example, if I cluster on my sorted primary key, that just means that the index can jump to the tuple with the correct primary key quickly (log time), but you will still end up reading* the entire tuple in the same way I explain in the blog. And if you only store a record ID that points to the other fields instead of the entire tuple at the leaves of the index, then that wouldn't be considered a clustered index.
I will note, however, that DBMSs should be smart enough to know that an aggregation on only an indexed column does not need to fetch the rest of the columns, only the data at the leaves of the index.
One can argue each view of a database is merely a derivate of the WAL, and therefore every view is an index. The major benefit of columnar databases is the data stored being continuous in memory. Avoid all serialize/deserialize and control flow logic. Most core index data structures in relational DBs do not support this kind of tight vector view, Arrow[1]is a format that does.
Theoretically one can have a custom index extension which stores the data in a column-oriented manner, yet then one has major duplication, which is a problem for petabyte-scale databases, and is an even bigger problem in the Cloud.
KDB+ is the best implementation of a columnar DB in my opinion. Simple C, and one can understand how the data is stored down to the DRAM cells. Durability is just MMAP, which is fine as OLAP DBMSs tend not to be ACID.
In my personal opinion one shall learn from the best. The best in the world in massively parallel vectorized computation are the people at OpenAI and Anthropic, and the people who built PyTorch. Much of their work can be applied to analytical DBMSs.
Index-only scans are possible when the index covers all involved columns and the query condition favors using the index. If you have an index on (col_a, col_b) but you run SELECT col_a WHERE col_b, you typically will not get an index-only scan because the query planner will decide against using the index in the first place, since it is ordered on col_a before col_b.
Not really modern either.. Oracle/Sybase/SQL Server have been doing that already in the 90s.. including indexed views for aggregation
What they recently (and some of these were added in late 2000s) added is columnstore indexes... with compression and also in memory (Sybase Hana, SQL Server In Memory aka Hekaton, Oracle IM column store)
> Most formats split the table into large groups of rows and store the columns separately inside of each group (this is known as a "row group"). This idea goes back to PAX, from Weaving Relations for Cache Performance (VLDB 2001), and it's how Apache Parquet files work today.
PAX’s “row group” has the same size as a disk page, whereas Parquet row groups are much larger so a page stores only data from the same column. I’ve been trying to track down the origin of this change in design but haven’t been able to find the right paper
Related US Patent US7024414B2 [0] from Addamark (later Sensage) filed 2001 August, "Storage of row-column data". The patent outlines columnar compressed storage similar in many respects to parquet.
It's the same basic concept, yes. The details matter, though, and the fact that AoS/SoA is mostly about in-memory layout, whereas row/column store is about on-disk layout means that the performance compromises are very different. E.g. column store databases frequently use RLE for compression, but that's probably _way_ too expensive for SoA.
One thing to add is that databases tend to take it further using compression. For instance, if you have a column that is all either A or B, you can use run-length encoding ("the next thousand entries are B"). Or you can do delta encoding: if you have some very large number that takes a lot of bits to store, but the deltas between them are quite small, you can save a lot of disk space and I/O by just storing the deltas.
You can also combine these two: if you have a numeric id that increases by 1 every row, you can delta-encode that to just get a massive list of 1's, which you can then run-length encode to just be "the delta for the next million rows is 1", saving huge amounts of space.
You generally don't do this with AOS/SOA, because you do want to be able to random-access your entries ("index" them, in database terms) and I/O performance is much less important. Databases have this issue too, which is why indexes tend to either not be available or much slower in column-oriented DBs.
EDIT: ah, read the original commenter a bit too quickly, missed that they mentioned run-length encoding. Apologies.
One of the cool things about Vortex (which is a file format, but in this context can be better thought of as the storage layer of a DBMS) is that we have implemented compression encodings that _do_ support fast random access. For example, FastLanes allows us to bit-pack values extremely effectively while retaining random access, and this can be combined with other encodings such as ALP and FSST.
I believe Vortex is unique in its ability to retain random access while recursively compressing data. And turns out that this is helpful for both in-memory _and_ on-disk (we might write about that in the future)!
I unfortunately didn't have much space to write about that in this blog, but in the compression section I did link to other blogs that we have written that go into much more detail, if you are interested :D
Fun fact, the original Pokemon used both DE and RLE to compress the sprites. It's one of the things that makes missingno screw up sprites (it tries to decode game data as if it's a sprite encoded this way and sometimes causes buffer overruns)
Appreciate you going into more detail about how run-length encoding works in any case. I had an abstract idea it was something like that, but didn't realize it could actually be implemented so 'simply'.
On the one hand, you missed me mentioning RLE. Oh no how dare you.
On the other hand, you added a bunch of extra detail, including stuff I didn't know about.
It's a technical forum. That's like asking to "please introduce the definition of a linker" the first time it crops up. If somebody really doesn't know, searching "aos vs soa" in Google yields a largely correct AI summary followed by a Wikipedia article on the topic followed by a StackOverflow discussion on pros/cons followed by a similar Reddit discussion. Aside from maybe the image/video results, literally everything on the first page looks like it would explain the concept well.
Expanding acronyms helps bring people into your field of interest.
People who might be technical and might even intuitively understand what is meant by "Array of Structures vs Structures of Arrays" might not be familiar with the acronym AOS vs SOA, especially given SOA is already a technical acronym their brain might shortcut to, "Service Oriented Architecture", even if instantly dismissed as clearly incorrect.
By expanding the algorithm you also help let people better decide if they want to spend the time reading up more about it.
It's the same problem you see with variable names though -- longer names add local clarity but give disproportionate weight to those local concepts rather than the global structure. There's value in selectively using less precise identifiers.
Maybe you agree with that and just disagree with where the line should be drawn?
My line on acronyms is fairly clear, I think that introducing acronyms by expanding them on first-use is a useful guideline and principle to try to stick by.
I'd also err on the side of generally assuming that most people, even in a technical forum, don't know all acronyms unless they're very widely known outside of the topic at hand. I don't think AOS vs SOA comes anywhere close to that line.
Some acronyms are of course better understood by their acronym, I wouldn't introduce a Local Area Network (LAN), or Domain Name Resolution (DNS), so like all guidelines there's judgement to be made.
Even then, if I were writing an intro to DNS, then I would call it an Introduction to Domain Name Resolution (DNS), because it is specifically targeted as an introduction. I wouldn't do the same for SQL, because no-one calls it Structured Query Language. Fairly often it would be more confusing if they did expand it, because quite often when people talk about SQL they're not really talking about the language at all, but using it as a short-hand for talking about SQL-compatible databases, or more specifically talking about relational database management systems (RDBMS), but "SQL" is a useful shorthand to contrast to "No-SQL" databases that were popularised a decade or two ago.
> [...]
> [24] People have tried to build one system that does both in the past (HTAP, or hybrid transactional/analytical processing), but those attempts generally didn't work out. Some newer systems seem to be bridging the gap, however. CedarDB, the commercial version of Umbra (a research system from TU Munich), runs transactions and analytics on just one engine and one copy of the data. Databricks' Lakebase keeps Postgres (a row store) as the engine for transactional queries, but its storage layer rewrites the same data into columnar formats in the background, allowing an analytical engine to query it.
The footnote says "those attempts generally didn't work out" but then mentions Lakebase and CedarDB as newer efforts. Can anyone speak to whether or not CedarDB, Lakebase (and any others?) are achieving the fabled transactions + analytics in one database? Should we expect, at some point in the near future, for transactions + analytics to be standard in all databases, or is combining them a niche / esoteric thing with many tradeoffs?
As predicted, it was very good at performing analytic operations; but it also was very fast at traditional OLTP operations too. I benchmarked a large number of queries against other databases and in the majority of cases, it was actually faster. In some cases it was much faster. It was able to do all this using just one copy of the data without needing to create and maintain separate indexes.
There are several short demo videos on my YouTube channel (listed in my profile).
HTAP has historically been niche because the cost of analytics on fresh data wasn't worth the squeeze (sooner or later the MBAs step in). Separating the OLTP and OLAP layers gives you better workload isolation and the ability to optimize each independently.
Databricks Lakebase/LTAP uses Postgres for transactions and lakehouse engines for analytics, with a shared storage layer. They also use Spark to build Postgres pages in parallel and write them directly to storage, avoiding the single-writer bottleneck when loading large volumes of data.
SingleStore takes a different approach: a distributed database based on MySQL with an in memory rowstore for transactions tightly coupled with a merger to columnstore for analytics.
I don't think HTAP DBs will become the default for every use case. But I do think the space will grow as we move towards agents and automated decision making and optimizations.
I'm working on one such solution right now,
That feels like something HTAP databases could offer as a choice!
- Things you can always do
- Things you can do when optimizing for fresh data
- Things you can do when optimizing for analytics on old data
- Things you can do, but with poor performance
This feels like one of those cases where people choose to make software simple instead of, and at the cost of (not) making operations simple.
If it can't outperform pure OLTP and it can't outperform pure OLAP then there is no pit of success for such an HTAP system.
The unfortunate part is that the vast majority of software out there in the world would be served perfectly with an HTAP solution.
The fortunate part is that for a lot of problems you can just run Postgres and then when you need analytics you can still use Postgres, until you hit scaling issues (if ever).
I've never seen a project choose to solve OLAP and OLTP upfront and succeed.
A simple case is a sorted list, you can sort it after every update, you can ignore the ordering and sort it as needed, or you can use a datastructure that is typically O(log(N)) at both updates and retrieval. Better datastructurs help, but they cannot remove the tradeoff entirely (in fact O(log(N)) inserts are kind of theoretically minimal, though a trie can do it in O(1) for fixed length datatypes).
In the case of a sorted list, it's keeping a sorted list, along with a growing small unsorted list that you will query or sort when needed.
This works for kernel timer trees, database storage, and indexes.
Keep your "fixed" data up to some checkpoint in an efficient form, and your "new" data since the checkpoint in a faster-updating, slower-querying form. When doing queries, read both and merge, and maybe sort parts of the new data on demand. The new data will be slower to query, but it should also be smaller.
At carefully chosen times, transfer data from the new form to the "fixed" form, either with an incremental update if you can, or by rewriting the fixed form entirely. It doesn't have to stop at two layers, and shouldn't if the fixed form is large, or if you want unlimited scale.
Choosing the right times and how much to update (the whole key range, intervals, predicate subsets, ertc) is an interesting algorithm design problem. When you get it just right, you can get excellent performance in fast-queryable compression and continuous fast-updates at the same time. (I'm building a database engine that does this in my spare time.)
That said, it works wonderfully and I love it.
If you run e.g. a `SELECT SUM(col1) WHERE col2 = x`, a columnar DB will typically produce produce a bitmap from of col2, use it to mask col1, then sum what's left—all very efficient operations.
Bitmaps fell out of fashion after the branch predictor became the slowest part of vectorized execution.
Most columnar dbs use compact selection vectors and loop over the values within them, rather than an if() over each row.
Imagine you had 1024 rows in the col1 column and only 1 row is selected, then this optimization has to only do 3-4 branches before the vector is done vs a bit-map which has to always do 1024 checks.
This became relevant somewhere in the mid 2010s and is called out in the Hive design[1] docs from that era.
[1] - https://issues.apache.org/jira/secure/attachment/12594231/Hi...
My understanding is that modern databases will take advantage of that if you create an index of those fields - ie it'll read from the index, not the records.
For example, if I cluster on my sorted primary key, that just means that the index can jump to the tuple with the correct primary key quickly (log time), but you will still end up reading* the entire tuple in the same way I explain in the blog. And if you only store a record ID that points to the other fields instead of the entire tuple at the leaves of the index, then that wouldn't be considered a clustered index.
I will note, however, that DBMSs should be smart enough to know that an aggregation on only an indexed column does not need to fetch the rest of the columns, only the data at the leaves of the index.
Theoretically one can have a custom index extension which stores the data in a column-oriented manner, yet then one has major duplication, which is a problem for petabyte-scale databases, and is an even bigger problem in the Cloud.
KDB+ is the best implementation of a columnar DB in my opinion. Simple C, and one can understand how the data is stored down to the DRAM cells. Durability is just MMAP, which is fine as OLAP DBMSs tend not to be ACID.
In my personal opinion one shall learn from the best. The best in the world in massively parallel vectorized computation are the people at OpenAI and Anthropic, and the people who built PyTorch. Much of their work can be applied to analytical DBMSs.
(Draft, of course the topic is much more nuanced)
[1] https://arrow.apache.org/
What they recently (and some of these were added in late 2000s) added is columnstore indexes... with compression and also in memory (Sybase Hana, SQL Server In Memory aka Hekaton, Oracle IM column store)
PAX’s “row group” has the same size as a disk page, whereas Parquet row groups are much larger so a page stores only data from the same column. I’ve been trying to track down the origin of this change in design but haven’t been able to find the right paper
[0] https://patents.justia.com/patent/20030028509
You can also combine these two: if you have a numeric id that increases by 1 every row, you can delta-encode that to just get a massive list of 1's, which you can then run-length encode to just be "the delta for the next million rows is 1", saving huge amounts of space.
You generally don't do this with AOS/SOA, because you do want to be able to random-access your entries ("index" them, in database terms) and I/O performance is much less important. Databases have this issue too, which is why indexes tend to either not be available or much slower in column-oriented DBs.
EDIT: ah, read the original commenter a bit too quickly, missed that they mentioned run-length encoding. Apologies.
I believe Vortex is unique in its ability to retain random access while recursively compressing data. And turns out that this is helpful for both in-memory _and_ on-disk (we might write about that in the future)!
I unfortunately didn't have much space to write about that in this blog, but in the compression section I did link to other blogs that we have written that go into much more detail, if you are interested :D
I call that a pretty positive tradeoff :)
Array of Structures vs Structure of Arrays.
People who might be technical and might even intuitively understand what is meant by "Array of Structures vs Structures of Arrays" might not be familiar with the acronym AOS vs SOA, especially given SOA is already a technical acronym their brain might shortcut to, "Service Oriented Architecture", even if instantly dismissed as clearly incorrect.
By expanding the algorithm you also help let people better decide if they want to spend the time reading up more about it.
Maybe you agree with that and just disagree with where the line should be drawn?
I'd also err on the side of generally assuming that most people, even in a technical forum, don't know all acronyms unless they're very widely known outside of the topic at hand. I don't think AOS vs SOA comes anywhere close to that line.
Some acronyms are of course better understood by their acronym, I wouldn't introduce a Local Area Network (LAN), or Domain Name Resolution (DNS), so like all guidelines there's judgement to be made.
Even then, if I were writing an intro to DNS, then I would call it an Introduction to Domain Name Resolution (DNS), because it is specifically targeted as an introduction. I wouldn't do the same for SQL, because no-one calls it Structured Query Language. Fairly often it would be more confusing if they did expand it, because quite often when people talk about SQL they're not really talking about the language at all, but using it as a short-hand for talking about SQL-compatible databases, or more specifically talking about relational database management systems (RDBMS), but "SQL" is a useful shorthand to contrast to "No-SQL" databases that were popularised a decade or two ago.
“Column-Stores vs. Row-Stores: How Different Are They Really?”, 2008
https://15721.courses.cs.cmu.edu/spring2016/papers/p967-abad...