Arbitrary document ordering in CouchDB/PouchDB
<p>I’m building what can be treated as a slideshow app with CouchDB/PouchDB: each “slide” is its own Couch document, and slides can be reordered or deleted, and new slides can be added in between existing slides or at the beginning or end of the slideshow. A slideshow could grow from one to ≲10,000 slides, so I am sensitive to space- and time-efficiency.</p>

<p>I made the slide creation/editing functionality first, completely underestimating how tricky it is to keep track of slide ordering. This is hard because the order of each slide-document is completely independent of the slide-doc itself, i.e., it’s not something I can sort by time or some number contained in the document. I see numerous questions on StackOverflow about how to keep track of ordering in relational databases:</p>

<ul>
<li><a href="https://stackoverflow.com/questions/15118168/efficient-way-to-store-reorderable-items-in-a-database">Efficient way to store reorderable items in a database</a></li>
<li><a href="https://stackoverflow.com/questions/3813704/what-would-be-the-best-way-to-store-records-order-in-sql">What would be the best way to store records order in SQL</a></li>
<li><a href="https://stackoverflow.com/questions/812630/how-can-i-reorder-rows-in-sql-database">How can I reorder rows in sql database</a></li>
<li><a href="https://stackoverflow.com/questions/11094338/storing-item-positions-for-ordering-in-a-database-efficiently">Storing item positions (for ordering) in a database efficiently</a></li>
<li><a href="https://stackoverflow.com/questions/4115053/how-to-keep-ordering-of-records-in-a-database-table">How to keep ordering of records in a database table</a></li>
<li><a href="https://stackoverflow.com/questions/65205/linked-list-in-sql">Linked List in SQL</a></li>
</ul>

<p>but all these involve either</p>

<ol>
<li>using a floating-point secondary key for reordering/creation/deletion, with periodic normalization of indexes (i.e., imagine two documents are order-index 1.0 and 2.0, then a third document in between gets key 1.5, then a fourth gets 1.25, …, until ~31 docs are inserted in between and you get floating-point accuracy problems);</li>
<li>a linked list approach where a slide-document has a <code>previous</code> and <code>next</code> field containing the primary key of the documents on either side of it;</li>
<li>a very straightforward approach of updating all documents for each document reordering/insertion/deletion.</li>
</ol>

<p>None of these are appropriate for CouchDB: #1 incurs a huge amount of incidental complexity in SQL or CouchDB. #2 is unreliable due to lack of atomic transactions (CouchDB might update the previous document with its new <code>next</code> but another client might have updated the new next document meanwhile, so updating the new next document will fail with 409, and your linked list is left in an inconsistent state). For the same reason, #3 is completely unworkable.</p>

<hr>

<p>One CouchDB-oriented approach I’m evaluating would create a document that just contains the ordering of the slides: it might contain a primary-key-to-order-number hash object as well as an array that converts order-number-to-primary-key, and just update this object when slides are reordered/inserted/deleted. The downside to this is that Couch will keep a copy of this potentially large document for every order change (reorder/insert/delete)—CouchDB doesn’t support compacting just a single document, and I don’t want to run compaction on my entire database since I love preserving the history of each slide-document. Another downside is that after thousands of slides, each change to ordering involves transmitting the entire object (hundreds of kilobytes) from PouchDB/client to Couch.</p>

<p>A tweak to this approach would be to make a second database just to hold this ordering document and turn on auto-compaction on it. It’ll be more work to keep track of two database connections, and I’ll eventually have to put a lot of data down the wire, but I’ll have a robust way to order documents in CouchDB.</p>

<hr>

<p>So my questions are: how do CouchDB people usually store the order of documents? And can more experienced CouchDB people see any flaws in my approach outlined above?</p>