5 ms·

SingleStore’s Skiplist Indexes (2014)

43 points by federicoponzi 4y ago

brd529 4y 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 4y 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 https://dl.acm.org/doi/abs/10.1145/3514221.3526055 (disclosure: SingleStore/MemSQL CTO)
- rbetts 4y ago
  You might enjoy this paper - https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/modde734-levandoski.pdf 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.
jph00 4y ago
Cyrus IMAP has been using skiplists for its storage for around 20 years IIRC. https://www.cyrusimap.org/imap/concepts/deployment/databases.html#skiplist 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/ https://fastmail.blog/open-technologies/why-we-contribute/

43 points by federicoponzi 4y 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 4y 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 https://dl.acm.org/doi/abs/10.1145/3514221.3526055 (disclosure: SingleStore/MemSQL CTO)
rbetts 4y ago
You might enjoy this paper - https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/modde734-levandoski.pdf 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.

jph00 4y ago

Cyrus IMAP has been using skiplists for its storage for around 20 years IIRC. https://www.cyrusimap.org/imap/concepts/deployment/databases.html#skiplist 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/ https://fastmail.blog/open-technologies/why-we-contribute/