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.
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.
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.
Comments
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.
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)
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.