Aggregation $graphLookup retrieving results in different order every-time the query is executed?

Question

I have the following dataset (categories):

[{
  "_id": 1,
  "name": "Root",
  "parent": null
},
 {
   "_id": 2,
   "name": "Sub - Level 1",
   "parent": 1
 }, {
   "_id": 3,
   "name": "Sub - Level 2",
   "parent": 2
 }, {
   "_id": 4,
   "name": "Sub - Level 3",
   "parent": 3
 }
]

and I am running the following pipeline on this dataset to fetch the tree recursively:

[{
  '$match': {
    '_id': 1
  }
}, {
  '$graphLookup': {
    'from': 'categories', 
    'startWith': '$_id', 
    'connectFromField': '_id', 
    'connectToField': 'parent', 
    'as': 'menu'
  }
}, {
    '$sort': {
      'menu.parent': 1
    }
  }]

The aim is to fetch the tree recursively like this:

{
    "_id": 1,
    "name": "Root",
    "parent: "null",
    "menu": [
        {..sub},{..sub},{...sub}
    ]
}

It does the job, but each time the query is executed the order of the elements in the menu array is different. EVERYTIME!

"menu" : [{... Sub - Level 2},{... Sub - Level 3}, {... Sub - Level 1}]
"menu" : [{... Sub - Level 1},{... Sub - Level 3}, {... Sub - Level 2}]
"menu" : [{... Sub - Level 3},{... Sub - Level 1}, {... Sub - Level 2}]

Is this the normal behaviour of $graphLookup or am I missing out on something? How am I supposed to sort the menu array?

Answer 1

Documents returned in the as field are not guaranteed to be in any order.

https://docs.mongodb.com/manual/reference/operator/aggregation/graphLookup/#definition

If you need an order, consider specifying the 'depthField' argument, and sorting by that.

https://jira.mongodb.org/browse/SERVER-26153

Workaround:

db.categories.aggregate([
  {
    "$match": {
      "_id": 1
    }
  },
  {
    "$graphLookup": {
      "from": "categories",
      "startWith": "$_id",
      "connectFromField": "_id",
      "connectToField": "parent",
      "as": "menu",
      depthField: "order"
    }
  },
  {
    $unwind: "$menu"
  },
  {
    $sort: {
      _id: 1,
      "menu.order": 1
    }
  },
  {
    $group: {
      _id: "$_id",
      name: {
        $first: "$name"
      },
      parent: {
        $first: "$parent"
      },
      menu: {
        $push: "$menu"
      }
    }
  },
  {
    $unset: "menu.order" //Change to $project:{"menu.order":0} for MongoDB <v4.2
  }
])

MongoPlayground