Software Bits Newsletter

Share this post
Column-oriented processing.
softwarebits.substack.com

Column-oriented processing.

Learning from DBMSs.

Taras Tsugrii
Apr 28, 2021
Comment
Share

It's tempting to believe that there is a single unifying theory of everything and while we haven't found it yet, there are numerous principles shared between different disciplines responsible for significant performance wins. With this post I'd like to start a series covering such principles.

Columnar database management systems (DBMS) store data tables by column rather than by row.

This way of storing data has many advantages for online analytical processing, including:

  • reduced IO. Since data is read in pages, in case of row-based storage, in addition to requested column, OS would also fetch other columns that are part of rows;

  • cache-friendly. Cache space is not wasted on storing unnecessary columns;

  • encoding-friendly. Delta-encoding, run-length encoding, delta-of-delta and ZigZag encodings are just a few schemes that are used to significantly reduce storage requirements.

Turns out that a very similar approach is known in game development under the name of parallel arrays, where instead of array of structs, a struct of arrays is used. In Go array of structs Users

can be represented using parallel arrays as in ParallelUsers

The benefits of such organization while doing linear scans of age values like in the function below

are very similar to those of columnar storage in DBMS:

  • reduced IO. While doing a linear scan over ages only relevant data will be fetched from memory;

  • cache-friendly. Only age values are stored in cache, they are also loaded in blocks and cache prefetcher is effective at speculative loading of age values that are going to be used soon;

  • vectorization. Compilers are able to leverage SIMD instructions to perform additions on of multiple age values.

To be continued...

CommentComment
ShareShare

Create your profile

0 subscriptions will be displayed on your profile (edit)

Skip for now

Only paid subscribers can comment on this post

Already a paid subscriber? Sign in

Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to sign in.

TopNewCommunity

No posts

Ready for more?

© 2022 Taras Tsugrii
Privacy ∙ Terms ∙ Collection notice
Publish on Substack Get the app
Substack is the home for great writing