SingleStore’s Skiplist Indexes (2014)

SingleStore’s Skiplist Indexes (2014)(singlestore.com)

43 points by federicoponzi 3 years ago | 4 comments

jph00 3 years ago |

Cyrus IMAP has been using skiplists for its storage for around 20 years IIRC.

https://www.cyrusimap.org/imap/concepts/deployment/databases...

I was very excited to come across this when I was working at fastmail. We used Cyrus from the start, and I loved seeing such a cool data structure getting utilised in practice.

https://fastmail.blog/open-technologies/why-we-contribute/

brd529 3 years ago |

For those of you that think you've seen this before, MemSQL was rebranded to SingleStore, and this was the first blog post MemSQL made - skip list indexes were always a fundamental performance innovation of MemSQL. I am not sure if MemSQL/Singlestore is still the only commercially available db using skiplist indexes but I do think it was the first when they debuted in 2014.

AdamProut 3 years ago | |

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)

rbetts 3 years ago | |

You might enjoy this paper - https://www.microsoft.com/en-us/research/wp-content/uploads/...

Other vendors evaluated skip lists ahead of memsql’s use and chose other implementations for their purposes. Which is not to detract from singlestore’s achievements or selected tradeoffs.