Remix.run Logo
▲ pdpi 2 hours ago

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.

▲j0shk0 2 hours ago | parent [-]

Thank you!

▲OskarS 2 hours ago | parent [-]

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.

▲ConnorTsui20 an hour ago | parent | next [-]

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

▲slfnflctd an hour ago | parent | prev | next [-]

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

▲pdpi an hour ago | parent | prev [-]

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 :)