Cursors returned by minimongo find with a sort order are unstable

[mizzao]

Suppose one is rendering a template with a sorted cursor, like the following:

<template name="foo">
  {{#each items}}
  {{this}}
  {{/each}}
</template>

Template.foo.items = ->
  Bar.find {}.
    sort: { someKey: 1 }

In particular, imagine that there are multiple identical values for someKey. When the page renders, the items are sorted in some particular order.

Now - imagine that we change one of the items in Bar, but without changing someKey. This could be anything - adding a field, setting a field, removing a field. The item will now jump to the end of all items with the same someKey when it is re-rendered. Basically, the sort order is unstable.

When there are identical keys, and items can be interacted with, this is a particularly annoying problem. In my app, users can choose the sort order and do stuff to items. However, as soon as they touch an item, it jumps to the end of all items with the same sort key. This is very unintuitive behavior because the order shouldn't change unless the value of the sorted key is changed.

To see what I mean, go to http://crowdmapper.meteor.com/. Click Events at the top. Click one of the headers to sort a column by that header. Now, click the yellow edit button to edit any row that has the same key. You'll see it instantly jump out from under you.

[digilord]

+1 - I have this same issue with a sortable drag-n-drop. As soon as I drop an item into the middle of the list the newly dropped item moves to the top of the list.

[timhaines]

I noticed something similar this problem and worked around it by adding the id as a second field in the sort order. I'm not saying it's the full solution to the issue, but it may help you with the problem you're trying to solve.

[Slava]

Oops, closed/opened by accident.

I was going to comment :). Does anyone know if such behavior is encountered in MongoDB? Is their sorting stable?

[mizzao]

@timhaines Thanks, that's a great solution for now.

@imslavko The issue title is a misnomer. There's not really any sorting going on - just editing any field of any object in a sorted collection will cause it to jump around among other objects of equal sort keys. This is probably because it's being unnecessary re-inserted in whatever data structure is tracking the sort order or something.

[awwx]

Does anyone know if such behavior is encountered in MongoDB? Is their sorting stable?

There's a bit of confusion here in terminology, I think. For a sort to be "stable" presupposes that the list being sorted started in some particular order. The original poster is requesting that Minimongo act as if collections are kept internally in some particular but unspecified order, and then have a stable sort applied to it.

MongoDB is in a bit of a different situation. Database query results are returned unordered, unless put in a particular order by a sort specifier. Without a particular ordering determined by a sort specification, running a query a second time may return results in a different order. This doesn't mean that MongoDB sorting isn't "stable", it just means that results start off unordered.

But MongoDB doesn't do reactive updates. The minimongo behavior is technically correct (if your sort specification doesn't determine a particular order, you may get a different order at different times) but in a reactive facility that turns out to be unpleasant... people don't actually expect a displayed list to jump around randomly, while they aren't surprised by two separate queries returning results in different orders.

[timhaines]

It seems that Mongo's terrible at handling a secondary field in the sort parameter like this. It causes it to scan way more docs, ignoring the index for sort. I posted a question on the mongo user list here: https://groups.google.com/forum/#!topic/mongodb-user/Bch6lj5Q8SM

[Slava]

@mizzao @awwx Thanks! I clearly misunderstood the issue.

[mizzao]

@awwx I'm not sure if you're for or against fixing this, but I just want to point out that editing fields of objects from an unsorted cursor does not cause the objects to jump around. It would make sense for them to not jump when there is a sort option applied, either.

As @timhaines suggested, adding the _id to the end of the sort cursor is a reasonable way to fix this. This should be either applied automatically, or whatever data structure that is keeping track of the order of objects from a cursor should be modified to behave in a stable way.

[awwx]

@awwx I'm not sure if you're for or against fixing this

Oh, definitely fix it.

[glasser]

There are a lot of different code paths depending on exactly what cursor is used, etc, that end up leading to these calculations. Can you provide a cloneable reproduction? http://filing-bug-reports.meteor.com/

[mizzao]

Hi @glasser I'm currently out of the country at the moment and don't have the bandwidth to do this right now. I'd be happy to do so when I get back in 2 weeks or maybe one of these other guys can pitch in (seems like everyone knows what's going on.)

[mizzao]

Does the new rendering engine in blaze/shark make it easier to do this? i.e., when a field in a document is updated, are moved events generated in the cursor?

I actually don't know if this is still a problem, because I added a secondary sort argument by _id to places where I experienced it before - so there's no strong incentive to fix it. But just checking back in...

[glasser]

This bug does not have a reproduction, so I'm closing it. If anyone is able to come up a way to consistently reproduce it, we can reopen it.

[mizzao]

I'm guessing the lack of reproduction is due to the easy workaround (secondary sort on _id). However, I'd venture a guess that this won't happen on Blaze anyway.