Performance With An _rperm Index

Parse Server 📡
#1

I was fiddling with Parse server with MongoDB to understand its performance characteristics.
I created a collection of 87000 items, all readable only with the master key.
I used Postman to execute empty queries on the collection, without the master key or a session token. Of course, the query returns an empty result. What I am interested in is how long it takes to notice that an anonymous user is not allowed to read any of the objects.
Using a commit more recent than the latest release as of today, 4.5.0, the query takes about 47ms.
So I tried creating a MongoDB index on the _rperm field, which is what the Parse server filters on to enforce ACLs:

db.tmp.createIndex({_rperm: 1})

And the execution time jumps to 120ms, again, measured by Postman.
So that’s quite strange. Adding an index makes the query substantially slower, even with such a sizable collection.
I ran some queries on the Mongo shell directly. I filtered on the _rperm field, similar to what the Parse server does. And the query ran in less than a millisecond, as measure by the Mongo shell. That’s also perplexing. Digging into the Parse source, I see this line that adds ACL restrictions to user queries, in DatabaseController.js:

newQuery._rperm = { $in: [null, ‘*’, …acl] };

Adding the null to the query I ran using the Mongo shell, the execution time indeed jumps to ~100ms. Mind you, it was less than a ms without the null.
I am not sure what is causing that. I read the Mongo documentation on $in and couldn’t find a special meaning to null that would cause such behavior. As expected, removing the null from the Parse source makes the query significantly faster (~8ms), but it also breaks it as a non-existent _rperm field denotes public read access.
I have made all the necessary modifications to avoid using null in $in, and the code is at https://github.com/Ocell-io/parse-server/tree/query_acl_index_perf. It works and passes all tests (using Mongo, that is), however has a ~45% overhead in the non-indexed case.

Overall, this is how long the query takes, measured by Postman:

upstream, no index : 47ms
upstream, _rperm index: 120ms
patch, no index : 69ms
patch, _rperm index : 8ms

I initially considered creating a pull request, but given that it only seems to work with Mongo (likely because it uses $and) and has a relatively large overhead for non-indexed collections, I am hesitant.

Any ideas?

#2

Have you tried to run the query with upstream (in both scenarios of index and no index) using explain?

#3

Here is the query:

GET http://localhost:1337/parse/classes/tmp?explain=true

Without an index, this is the response:

{
    "results": {
        "queryPlanner": {
            "plannerVersion": 1,
            "namespace": "dev.tmp",
            "indexFilterSet": false,
            "parsedQuery": {
                "_rperm": {
                    "$in": [
                        null,
                        "*"
                    ]
                }
            },
            "winningPlan": {
                "stage": "LIMIT",
                "limitAmount": 100,
                "inputStage": {
                    "stage": "COLLSCAN",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "direction": "forward"
                }
            },
            "rejectedPlans": []
        },
        "executionStats": {
            "executionSuccess": true,
            "nReturned": 0,
            "executionTimeMillis": 45,
            "totalKeysExamined": 0,
            "totalDocsExamined": 87028,
            "executionStages": {
                "stage": "LIMIT",
                "nReturned": 0,
                "executionTimeMillisEstimate": 3,
                "works": 87030,
                "advanced": 0,
                "needTime": 87029,
                "needYield": 0,
                "saveState": 87,
                "restoreState": 87,
                "isEOF": 1,
                "limitAmount": 100,
                "inputStage": {
                    "stage": "COLLSCAN",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "nReturned": 0,
                    "executionTimeMillisEstimate": 3,
                    "works": 87030,
                    "advanced": 0,
                    "needTime": 87029,
                    "needYield": 0,
                    "saveState": 87,
                    "restoreState": 87,
                    "isEOF": 1,
                    "direction": "forward",
                    "docsExamined": 87028
                }
            },
            "allPlansExecution": []
        },
        "serverInfo": {
            "host": "kartal-flash",
            "port": 27017,
            "version": "4.4.6",
            "gitVersion": "72e66213c2c3eab37d9358d5e78ad7f5c1d0d0d7"
        },
        "ok": 1
    }
}

So it is a simple COLLSCAN.
And this is the result with an index on the _rperm field:

{
    "results": {
        "queryPlanner": {
            "plannerVersion": 1,
            "namespace": "dev.tmp",
            "indexFilterSet": false,
            "parsedQuery": {
                "_rperm": {
                    "$in": [
                        null,
                        "*"
                    ]
                }
            },
            "winningPlan": {
                "stage": "LIMIT",
                "limitAmount": 100,
                "inputStage": {
                    "stage": "FETCH",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "inputStage": {
                        "stage": "IXSCAN",
                        "keyPattern": {
                            "_rperm": 1
                        },
                        "indexName": "_rperm_1",
                        "isMultiKey": true,
                        "multiKeyPaths": {
                            "_rperm": [
                                "_rperm"
                            ]
                        },
                        "isUnique": false,
                        "isSparse": false,
                        "isPartial": false,
                        "indexVersion": 2,
                        "direction": "forward",
                        "indexBounds": {
                            "_rperm": [
                                "[undefined, undefined]",
                                "[null, null]",
                                "[\"*\", \"*\"]"
                            ]
                        }
                    }
                }
            },
            "rejectedPlans": []
        },
        "executionStats": {
            "executionSuccess": true,
            "nReturned": 0,
            "executionTimeMillis": 118,
            "totalKeysExamined": 87028,
            "totalDocsExamined": 87028,
            "executionStages": {
                "stage": "LIMIT",
                "nReturned": 0,
                "executionTimeMillisEstimate": 16,
                "works": 87029,
                "advanced": 0,
                "needTime": 87028,
                "needYield": 0,
                "saveState": 87,
                "restoreState": 87,
                "isEOF": 1,
                "limitAmount": 100,
                "inputStage": {
                    "stage": "FETCH",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "nReturned": 0,
                    "executionTimeMillisEstimate": 16,
                    "works": 87029,
                    "advanced": 0,
                    "needTime": 87028,
                    "needYield": 0,
                    "saveState": 87,
                    "restoreState": 87,
                    "isEOF": 1,
                    "docsExamined": 87028,
                    "alreadyHasObj": 0,
                    "inputStage": {
                        "stage": "IXSCAN",
                        "nReturned": 87028,
                        "executionTimeMillisEstimate": 7,
                        "works": 87029,
                        "advanced": 87028,
                        "needTime": 0,
                        "needYield": 0,
                        "saveState": 87,
                        "restoreState": 87,
                        "isEOF": 1,
                        "keyPattern": {
                            "_rperm": 1
                        },
                        "indexName": "_rperm_1",
                        "isMultiKey": true,
                        "multiKeyPaths": {
                            "_rperm": [
                                "_rperm"
                            ]
                        },
                        "isUnique": false,
                        "isSparse": false,
                        "isPartial": false,
                        "indexVersion": 2,
                        "direction": "forward",
                        "indexBounds": {
                            "_rperm": [
                                "[undefined, undefined]",
                                "[null, null]",
                                "[\"*\", \"*\"]"
                            ]
                        },
                        "keysExamined": 87028,
                        "seeks": 1,
                        "dupsTested": 87028,
                        "dupsDropped": 0
                    }
                }
            },
            "allPlansExecution": []
        },
        "serverInfo": {
            "host": "kartal-flash",
            "port": 27017,
            "version": "4.4.6",
            "gitVersion": "72e66213c2c3eab37d9358d5e78ad7f5c1d0d0d7"
        },
        "ok": 1
    }
}

This one is more interesting. It uses an IXSCAN, but also a filter (I don’t know what that means).

#4

You said that all objects have the same ACL (readable only with master key), right? Could you share one of the objects?

#5

Here’s one of the objects from the response of a query that used the master key:

{
    "objectId": "tpMaGNehny",
    "createdAt": "2021-06-04T16:12:39.996Z",
    "updatedAt": "2021-06-04T16:12:39.996Z",
    "ACL": {}
}

And this was the curl command used to create them:

curl -H "X-Parse-Master-Key: my-master-key" -X POST -H "X-Parse-Application-Id: my-app-id" -H "Content-Type: application/json" -d '{"ACL":{}}' -s http://localhost:1337/parse/classes/tmp

#6

Would you mind to share the MongoDB object?

#7

From the mongo shell:

> db.tmp.find()[0]
{
	"_id" : "tpMaGNehny",
	"_wperm" : [ ],
	"_rperm" : [ ],
	"_acl" : {
		
	},
	"_created_at" : ISODate("2021-06-04T16:12:39.996Z"),
	"_updated_at" : ISODate("2021-06-04T16:12:39.996Z")
}
#8

That’s really strange and looks like a MongoDB issue. I found this thread with some different ways of checking if the array is not empty. Maybe we can find some inspiration here. I saw in your fork that your current solution uses $exists. I am not super fan of $exists because it often causes performance issues as well.

I am also wondering if a sparse index could help in this case. Would you mind to test?

#9

I tested a sparse index on the _rperm field using a parse server instance without the modifications in the fork. It seems mongo ignores it altogether, at least for the query issued by Parse:

db.tmp.createIndex({"_rperm": 1}, {sparse: true})

And here is the explain output:

{
    "results": {
        "queryPlanner": {
            "plannerVersion": 1,
            "namespace": "dev.tmp",
            "indexFilterSet": false,
            "parsedQuery": {
                "_rperm": {
                    "$in": [
                        null,
                        "*"
                    ]
                }
            },
            "winningPlan": {
                "stage": "LIMIT",
                "limitAmount": 100,
                "inputStage": {
                    "stage": "COLLSCAN",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "direction": "forward"
                }
            },
            "rejectedPlans": []
        },
        "executionStats": {
            "executionSuccess": true,
            "nReturned": 0,
            "executionTimeMillis": 40,
            "totalKeysExamined": 0,
            "totalDocsExamined": 87169,
            "executionStages": {
                "stage": "LIMIT",
                "nReturned": 0,
                "executionTimeMillisEstimate": 2,
                "works": 87171,
                "advanced": 0,
                "needTime": 87170,
                "needYield": 0,
                "saveState": 87,
                "restoreState": 87,
                "isEOF": 1,
                "limitAmount": 100,
                "inputStage": {
                    "stage": "COLLSCAN",
                    "filter": {
                        "_rperm": {
                            "$in": [
                                null,
                                "*"
                            ]
                        }
                    },
                    "nReturned": 0,
                    "executionTimeMillisEstimate": 2,
                    "works": 87171,
                    "advanced": 0,
                    "needTime": 87170,
                    "needYield": 0,
                    "saveState": 87,
                    "restoreState": 87,
                    "isEOF": 1,
                    "direction": "forward",
                    "docsExamined": 87169
                }
            },
            "allPlansExecution": []
        },
        "serverInfo": {
            "host": "kartal-laptop",
            "port": 27017,
            "version": "4.4.6",
            "gitVersion": "72e66213c2c3eab37d9358d5e78ad7f5c1d0d0d7"
        },
        "ok": 1
    }
}

The query performance is also identical to the case without the index.

I double checked that the index is there using db.tmp.getIndices(). As expected, passing sparse: false produces the same results as having a regular index.

#10

Got it. What is the version of MongoDB that you are using? Have you tried also with a different version?