{"action":"created","issue":{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/6094","repository_url":"https://api.github.com/repos/rethinkdb/rethinkdb","labels_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/6094/labels{/name}","comments_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/6094/comments","events_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/6094/events","html_url":"https://github.com/rethinkdb/rethinkdb/issues/6094","id":175629216,"number":6094,"title":"Consider making non-indexed `.orderBy(...)` stable","user":{"login":"marshall007","id":877936,"avatar_url":"https://avatars.githubusercontent.com/u/877936?v=3","gravatar_id":"","url":"https://api.github.com/users/marshall007","html_url":"https://github.com/marshall007","followers_url":"https://api.github.com/users/marshall007/followers","following_url":"https://api.github.com/users/marshall007/following{/other_user}","gists_url":"https://api.github.com/users/marshall007/gists{/gist_id}","starred_url":"https://api.github.com/users/marshall007/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/marshall007/subscriptions","organizations_url":"https://api.github.com/users/marshall007/orgs","repos_url":"https://api.github.com/users/marshall007/repos","events_url":"https://api.github.com/users/marshall007/events{/privacy}","received_events_url":"https://api.github.com/users/marshall007/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2016-09-07T23:18:24Z","updated_at":"2016-09-07T23:24:06Z","closed_at":null,"body":"Prior to some discussion with @danielmewes on Slack today, I had assumed all sorting operations in RethinkDB were stable. In particular, when comparing the field value of two documents, I assumed if the values were equal, we would fall back to comparing the documents in some deterministic fashion. Instead, it appears that document order is simply preserved from the input stream in this case.\r\n\r\nIt's worth noting that indexed `orderBy` is in fact stable since, internally, the secondary index is suffixed with the document's primary key. The discrepancy between an indexed and non-indexed sort is what caused confusion for me and it seems kinda bad as default behavior.\r\n\r\nI think we should consider making `orderBy` stable by default. In other words I think the following should produce the same (stable) result when multiple documents contain the same value for `foo`:\r\n\r\n- `.orderBy(index: 'foo')`\r\n- `.orderBy('foo')`\r\n- `.orderBy('foo', r.row)`\r\n\r\nDoesn't seem like there would be huge perf costs associated with this change, but even if there were I think I'd prefer a stable sort by default with an optarg to disable over the existing behavior."},"comment":{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/comments/245449649","html_url":"https://github.com/rethinkdb/rethinkdb/issues/6094#issuecomment-245449649","issue_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/6094","id":245449649,"user":{"login":"danielmewes","id":505365,"avatar_url":"https://avatars.githubusercontent.com/u/505365?v=3","gravatar_id":"","url":"https://api.github.com/users/danielmewes","html_url":"https://github.com/danielmewes","followers_url":"https://api.github.com/users/danielmewes/followers","following_url":"https://api.github.com/users/danielmewes/following{/other_user}","gists_url":"https://api.github.com/users/danielmewes/gists{/gist_id}","starred_url":"https://api.github.com/users/danielmewes/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danielmewes/subscriptions","organizations_url":"https://api.github.com/users/danielmewes/orgs","repos_url":"https://api.github.com/users/danielmewes/repos","events_url":"https://api.github.com/users/danielmewes/events{/privacy}","received_events_url":"https://api.github.com/users/danielmewes/received_events","type":"User","site_admin":false},"created_at":"2016-09-07T23:24:06Z","updated_at":"2016-09-07T23:24:06Z","body":"Three additional notes from our conversation:\r\n* The property `stable` of a sorting algorithm usually refers to our current behavior, that is maintaining the input order for elements with equal sorting keys. The proposed change would make the sorting unstable in that sense, but in a deterministic way.\r\n* The main case where this comes up is if someone does `r.table(...).orderBy('foo')` (possibly with a `getAll` or `between` before the `orderBy`). The result if this is not deterministic if there are duplicate values for a given `foo`, since `r.table(...)` does not return results in a deterministic order.\r\n* For this case, there is usually an easy work-around by adding an index-based `orderBy` in front of the final `orderBy`: `r.table(...).orderBy({index: \"id\"}).orderBy('foo')`. This makes the order of the input to `orderBy('foo')` deterministic, and hence the overall result is deterministic since `orderBy` is \"stable\"."}}
{"actor":{"display_login":"danielmewes"}}