SingleStore’s Skiplist Indexes (2014)
singlestore.com
SingleStore’s Skiplist Indexes (2014)
1–5 of 5 posts
Re: SingleStore’s Skiplist Indexes (2014)
#2For 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.
Re: SingleStore’s Skiplist Indexes (2014)
#3For 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.
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)
Re: SingleStore’s Skiplist Indexes (2014)
#4For 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.
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.
Re: SingleStore’s Skiplist Indexes (2014)
#5Cyrus 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.