Consider, I have the following documents that represent a tree structures:
[
{
"_id": 1,
"parentId": null,
},
{
"_id": 2,
"parentId": null,
},
{
"_id": 3,
"parentId": 1,
},
{
"_id": 4,
"parentId": 1,
},
{
"_id": 5,
"parentId": 2,
},
{
"_id": 6,
"parentId": 5,
},
]
What would be the most performant way to calculate a depth distribution for these trees using MongoDB aggregations?
I want to receive the following or similar result:
[
{
"depth": 0,
"count": 2,
},
{
"depth": 1,
"count": 3,
},
{
"depth": 2,
"count": 1,
}
]
The total sum of all the count's should be equal to the number of documents in the collection.
I've tried to use a combination of various aggregation functions, but only have managed to calculate the data without taking root nodes into account:
db.collection.aggregate([
{
// Skipping the root nodes,
// otherwise it will calculate results
// for all the nodes and count them multiple times
$match: {
parentId: null
}
},
{
$graphLookup: {
from: "collection",
startWith: "$_id",
connectFromField: "_id",
connectToField: "parentId",
as: "descendants",
depthField: "depth",
},
},
{
$unwind: "$descendants",
},
{
$group: {
_id: "$descendants.depth",
count: {
$sum: 1,
},
},
},
{
$project: {
_id: 0,
depth: "$_id",
count: "$count",
},
},
{
$sort: {
depth: 1,
},
},
]);
Here's the Mongo Playground with the example data.
In that structure, there is theoretically an unlisted root node with the id of null. A single graph lookup starting from that node would find all of the nodes whose parentage leads back to null. i.e. it would not include non-root loops in the tree.
To accomplish that you first need to retrieve a single document, then begin the graph lookup from null, perhaps:
[
{ $limit: 1 },
{
$graphLookup: {
from: "collection",
startWith: null,
connectFromField: "_id",
connectToField: "parentId",
as: "descendants",
depthField: "depth",
}
}
},
The rest of the unwind, group, project, sort stages would then transform that result into the format you are looking for.
As for performance, the graphLookup stage is implicitly reading every document in the collection. This means that no amount of indexing will improve the performance. If the entire collection fits in the cache, you might get reasonable performance. As the collection grows the amount of disk reading required to perform this query will also grow.
The long term performance may be acceptable if this is an infrequently run operation that can be segregated to a dedicated analytics node that does not serve application load.