why/how mongodb keep alphabetic order for keys on docs ?

[Arthur Neves]

running this gist: 

https://gist.github.com/arthurnn/5706565 

You can see that, the last output returns the doc, which has alphabetic ordered keys. I have a few question around this.

1. Why? - something related to indexes or BSON implementation?

2 . When? - Is this something that happens all the time, or it is not guaranteed to be sorted?

3. How? - How is that implemented, I looked up at the source but couldnt find the right place, if someone could point me out the right file would be awesome. Wondering if they use RBtree for the keys on the doc, or something like that.

The main reason that I am asking this is because I am having some issues when mapping MongoDB docs to Ruby hashes, as since ruby 1.9, hashes are not ordered by keys anymore.

thanks.

[Brandon Black]

Actually, I think you have it reversed.

Hashes in Ruby 1.9 *are* ordered. It's hashes in Ruby versions *before* 1.9 (ex. 1.8.x) that don't guarantee the preservation of order. Ilya Grigorik wrote up a great blog that explains what changed for hashes and how the implementation differs in Ruby 1.9 which you should take a look at here.

If you're using using the MongoDB Ruby driver from 10gen, we have a class called OrderedHash which we use to represent documents when we detect that you're using Ruby 1.8. This class allows us to guarantee ordering even on older versions of Ruby. Other community Ruby drivers like Mongoid/Moped don't support Ruby pre-1.9.

[Arthur Neves]

I think you misunderstood me. I meant, hashes in ruby 1.9+ are not ordered by the KEY. Because they are ordered by the insertion order.

For instance:

2.0.0p0 :001 > a = {}

 => {}

2.0.0p0 :002 > a['a'] = 1

 => 1

2.0.0p0 :003 > a['c'] = 1

 => 1

2.0.0p0 :004 > a['b'] = 1

 => 1

2.0.0p0 :005 > a

 => {"a"=>1, "c"=>1, "b"=>1}

2.0.0p0 :006 > a.keys

 => ["a", "c", "b"]

The problem here, is mongodb always re-sort the items in the docs to have them ordered by KEY(as I showed on my gist). Therefor if I am adding a new field on mongodb and also add this field to a local hash, that hash would not be the same as the mongodb doc. I would have to reload it.

This is a problem specially when your trying to $pull an element from an array, as they have to match 100%. Just to give a more concrete example, this is the error, that I am solving, and after debugging it, I realize the issue was in the key order. https://github.com/mongoid/mongoid/issues/3085

[Brandon Black]

MongoDB does not guarantee ordering of documents or its fields within a given document. 

The ordering you're observing the shell is actually just coincidental and it's not guaranteed that MongoDB will continue to order those document fields that way every time. The database is actually just ordering those fields in an fashion that best suits its own needs and this ordering has the potential to change with every update that causes that document to grow.

From the MongoDB docs:

When performing update operations that increase the document size beyond the allocated space for that document, the update operation relocates the document on disk and may reorder the document fields depending on the type of update

All that said, while you shouldn't rely on field order within the document, there are certain types of fields that do perserve order for their respective values. Fields that contain array values are guaranteed to perserve ordering. 

For example, given this document:

{

  _id: foo,  

  a: 1,

  b: 2,

  c: [1,2,3]

}

There is no guarantee about the order of a, b, and c within the document. However, the value of c (eg. [1,2,3]) is guaranteed to perserve its order. As a result, operations like the following will perserve the array's order.

db.test_coll.update({_id: foo}, { $push: {c: 5} })

{  

  _id: foo,

  a: 1,

  b: 2,

  c: [1,2,3,5]

}

db.test_coll.update({_id: foo}, { $pop: {c: -1} })

{

  _id: foo,  

  a: 1,

  b: 2,

  c: [2,3,5]

}

db.test_coll.update({_id: foo}, { $pop: {c: 1} })

{

  _id: foo,  

  a: 1,

  b: 2,

  c: [2,3]

}