News for hackers. Stuff that matters.
Re:MySQL is bazillion times faster than MemSQL by dhruvbird on Tuesday June 26, 2012 @01:58PM (#4163249)
Even though skip-lists as described in literature are singly linked (horizontally), they can be augmented with a back pointer to make them doubly linked. This would allow one to re-use an index as either a forward or backward index, and the order of the index is no longer important. I am not sure how easy this is to do in a lock free fashion. However, if one were to adopt a strategy which combines functional data structures and RCU, I am guessing that it would be possible to implement it with relatively good readability.

Additionally, skip-lists can be used for performing range queries as well. This means that "SELECT * FROM table ORDER BY id DESC LIMIT 5;" can be executed very efficiently as long as there is a skip-list on "id". Additionally, even COUNT(), MAX(), MIN(), etc... queries can be optimized in a similar fashion. Again, however, doing it in a lock-free manner might not be the most fun thing to do.

Re:MySQL is bazillion times faster than MemSQL by tintor on Tuesday June 26, 2012 @03:59PM (#4163831)
Skip list is essentially a hierarchy of linked lists. It is very hard to make a doubly linked list work concurrently without using locks. One would have to update two pointers atomically in order to insert a new element in a doubly linked list.
Re:MySQL is bazillion times faster than MemSQL by Nitramp on Tuesday June 26, 2012 @05:15PM (#4164170)
You could probably pull that off if you implement it like full text search indices in e.g. Lucene. Have every modification create a "diff" skip list that takes precedence over older skip lists, and then have a merge operation that runs asynchronously (and will either have to lock, or copy the entire data structure and switch it in atomically). That's also essentially how Bigtable's disk format works.
Re:MySQL is bazillion times faster than MemSQL by dhruvbird on Tuesday June 26, 2012 @05:22PM (#4164211)
Actually, there are papers about it http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4... but I don't know much about the implementation complexity since I've never implemented one.
Re:MySQL is bazillion times faster than MemSQL by bcoates on Tuesday June 26, 2012 @08:30PM (#4164915)
That shouldn't be any harder than updating one pointer atomically, modern x64s have two-pointer sized atomic exchange operations.
Re:MySQL is bazillion times faster than MemSQL by tintor on Wednesday June 27, 2012 @12:02AM (#4165441)
Modern x64s have 128-bit CAS instruction, but the problem is that those two pointers can be far apart in memory, in two different elements of the list.