Cloud-Native Transactions and Analytics in SingleStore

(I used to work at SingleStore, and now work at Antithesis) SingleStore (f.k.a. MemSQL) used lock-free skiplists extensively as the backing storage of their rowstore tables and indexes. Adam Prout (ex CTO) wrote about it here: https://www.singlestore.com/blog/what-is-skiplist-why-skipli... When SingleStore added a Columnar storage option (LSM tree), L0 was simply a rowstore table. Since rowstore was already a highly optimized, durable, and large-scale storage engine, it allowed L0 to absorb a highly concurrent transactional write workload. This capability was a key part of SingleStore's ability to handle HTAP workloads. If you want to learn more, take a look at this paper which documents the entire system end-to-end: https://dl.acm.org/doi/10.1145/3514221.3526055

Its a popular design for SQL Data warehouses. I think almost all of them (snowflake, redshift, etc.) store cold data in S3 and hot data on local disk[1][2]. It works well if the data is stored as immutable files (i.e., A log structure merge tree) or is not index at all (classical columnstores). S3 doesn't provide an efficient way to update a file. [1] https://dl.acm.org/doi/10.1145/2882903.2903741 (snowflake SIGMOD paper) [2] https://dl.acm.org/doi/10.1145/3514221.3526055 (singlestore SIGMOD paper)

Disclaimer: I work at SingleStoreDB. Building a database that can handle both analytics and operations is what we've been working on for the past 10+ years. Our customers use us to build applications with a strong analytical component to them (all of the use cases you mentioned and many more). How's it going? It's going really well! And we're working on some really cool things that will expand our offering from being a pure data storage solution to much more of a platform[1]. If you want to learn more about our architecture, we published this paper at SIGMOD in late 2022 about it[2]. [1]: https://davidgomes.com/databases-cant-be-just-databases-anym... [2]: https://dl.acm.org/doi/pdf/10.1145/3514221.3526055

Columnstores can do row level access by trading off a bit in terms of compression. If you organize the columnstore files as an LSM tree and use incremental compression schemes (so you don't have to compress too many more rows then the one your after) it can get close to the performance of a B-Tree for point reads - it depends on the specific table schema. [1] https://dl.acm.org/doi/abs/10.1145/3514221.3526055

We do still use skiplists for in-memory rowstore indexes. They're great for very high throughput writes (less good for scans). In the years since this blog post most of our engineering effort went towards building a columnstore that supports efficient point (few row) read and write queries without giving up the traditional very fast scan performance of a regular columnstore. This is now our default table storage. Much details in our SIGMOD 2022 paper from June: https://dl.acm.org/doi/abs/10.1145/3514221.3526055 (disclosure: SingleStore/MemSQL CTO)