> 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?
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 also TiDB which has decent adoption. It allows for columnar replicas of transactional data and exposes both over the same MySQL-compatible interface.
"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.
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)
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
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.
> 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?
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 also TiDB which has decent adoption. It allows for columnar replicas of transactional data and exposes both over the same MySQL-compatible interface.
"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.
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)
Well, yes. One of the things an index can do is column-oriented storage.
Am I missing something or is this nothing more but AOS vs SOA ?
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.
Thank you!
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
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.
I call that a pretty positive tradeoff :)
Please introduce your acronyms!
Array of Structures vs Structure of Arrays.
Great read! I do enjoy exploring both row and column data stores every now and then. Love the way I get my head bent.
I enjoyed reading this post