mongodb: modelling user defined sort order

Question

I am looking for a good way to implement a sort key, that is completely user definable. E.g. The user is presented with a list and may sort the elements by dragging them around. This order should be persisted.

One commonly used way is to just create an ascending integer type sort field within each element:

{
    "_id": "xxx1",
    "sort": 2
},
{
    "_id": "xxx2",
    "sort": 3
},
{
    "_id": "xxx3",
    "sort": 1
}

While this will surely work, it might not be ideal: In case the user moves an element from the very bottom to the very top, all the indexes in-between need to be updated. We are not talking about embedded documents here, so this will cause a lot of individual documents to be updated. This might be optimised by creating initial sort values with gaps in-between (e.g. 100, 200, 300, 400). However, this will create the need for additional logic an re-sorting in case the space between two elements is exhausted.

Another approach comes to mind: Have the parent document contain a sorted array, which defines the order of the children.

{
  "_id": "parent01",
  "children": ["xxx3","xxx1","xxx2"]
}

This approach would certainly make it easier to change the order, but will have it's own caveats: The parent documents must always keep track of a valid list of its children. As adding children will update multiple documents, this still might not be ideal. And there needs to be complex validation of the input received from the client, as the length of this list and the elements contained, may never be changed by the client.

Is there a better way to implement such a use case?

Answer 1

Hard to say which option is better without knowing:

1. How often the sort order is usually updated
2. Which queries you gonna run against the documents and how often
3. How many documents can be sorted at a time

I'm sure you gonna do much more queries than updates so personally I would go with the first option. It's easy to implement and it's simple which means it's gonna be rebust. I understand your concerns about updating multiple documents but the updates will be done in place, I mean no documents shifting will occur as you don't actually change the documents size. Just create a simple test. Generate 1k of documents, then just update each of them in a loop like that

db.test.update({ '_id': arrIds[i] }, { $set: { 'sort' : i } })

You will see it will be a pretty instant operation.

I like the second option as well, from programming perspective it looks more elegant but when it comes to practice you don't usually care much if your update takes 10 milleseconds instead of 5 if you don't do it often and I'm sure you don't, most applications are query oriented.

EDIT: When you update multiple documents, even if it's an instant operation, one may come up with an inconsistency issue when some documents are updated and some not. In my case it wasn't really an issue in fact. Let's consider an example, assume there's a list:

{ "_id" : 1, "sort" : 1 },{ "_id" : 2, "sort" : 4 },{ "_id" : 3, "sort" : 2 },{ "_id" : 4, "sort" : 3 }

so the ordered ids should look like that 1,3,4,2 according to sort fields. Let's say we have a failure when we want to move id=2 to the top. The failure occurs when we only updated two documents, so we will come up with the following state as we only managed to update ids 2 and 1:

{ "_id" : 1, "sort" : 2 },{ "_id" : 2, "sort" : 1 },{ "_id" : 3, "sort" : 2 },{ "_id" : 4, "sort" : 3 }

the data is in inconsistent state but still we can display the list to fix the problem, the ids order will be 2,1,3,4 if we just order it by sort field. why is it not a problem in my case? because when a failure occurs a user is redirected to an error page or provided with an error message, it is obvious for him that something got wrong and he should try again, so he just goes to the page and fix the order which is only partially valid for him.

Just to sum it up. Taking into account that it's a really rare case and other benefits of the approach I would go with it. Otherwise you will have to place everything in one document both the elements and the array with their indexes. This might be a much bigger issue, especially when it come to querying.

Hope it helps!