-
Notifications
You must be signed in to change notification settings - Fork 13
Performance: Query Planner
You should make sure that you've read and understand the basics of XPath Evaluation Query Performance before digging into the query planning structure, since most optimizations occur at that level.
For brevity in this document the reference header
instance('casedb')/casedb/
is abbreviated as
db()/
Basic XPath query optimization focuses on simplifying fairly straightforward optimizations like
db()/case[@case_type='patient'][@status='open']
based on reasonable and common assumptions of usage.
Those optimizations fail to significant improve performance, however, in situations in which nested or complex queries can result in hundreds or thousands of individual DB lookups.
A basic example is the situation is accessing a property from a case's "grandparent" in a case list to filter the list of child cases, which would follow the pattern
db()/case[@case_type = 'grandchild'][@status = 'open'][db()/case[@case_id = db()/case[@case_id = current()/index/parent]/index/parent]/grandparent_matches_filter = 'yes']
or broken down a bit more cleanly into a tree
db()/case
[@case_type = 'grandchild']
[@status = 'open']
[db()/case
[@case_id = db()/case
[@case_id = current()/index/parent]
/index/parent
]/grandparent_matches_filter = 'yes'
]
The 'grandchild'/'open' pairing is trivially optimized, but each set of internal reads will still be executed linearly. against each resulting record. The interior @case_id = current()/index/parent is fast, but it's still a single db read, and while 1 db read is fast, 2000 * 4 DB reads may not be.
To accommodate (and isolate) the ongoing improvements needed to fulfill more complex optimizations, CommCare implements a very, very basic planner for how to execute queries. Not all optimizations have been moved into that planner, but in the future the majority of non-native path evaluation should live in the planner.
The basic components of the planner are broken up by responsibility
The planner is currently a fairly naive passthrough object. It aggregates all of the known handlers for a model (like the <casedb> and coordinates dispatching queries to those handlers. It also (quite roughly) tries to pick 'faster' optimization for a given input but currently that is just ordering the handlers by efficiency when they are introduced for multiple sources (IE: CommCare's core engine + some platform specific code)
A handler gets PredicateProfiles (generated by the model) that it is capable of optimizing beyond the native processor and handles requests to do so. A handler would do something like "inform the planner that it can optimize @case_id = VALUE", and when asked, provide the resulting element that matches the profile.
If a handler can do much better than the default model implementations it provides an entirely different PredicateProfile which it can use to plan a complex query.
The Planner and Handlers should never store any state about an individual query, they are logical workflow objects, and not state management objects. More importantly, query evaluation can be very recursive over the same model, so the same handlers / planner can be triggered multiple times during a single "query" evaluation.
The other central component of the planner is the query context (distinct from the evaluation context)
The context for a query "begins" when the very first component of the query is being evaluated. so in a nested situation like
db()/case[index/parent = db()/case[index/parent = current()/@case_id]]/output
The context is opened at the root of the query. This is important for a couple of reasons, but one central one is that the context is a safe place to store references to large amounts of data, since it has a safe life-cycle.
The context keeps track of a 'scope' as a query is being evaluated. The scope of the query keeps track of the rough "magnitude" of the current processing. When a context is created it starts with a "Scope" of 1, meaning that something being performed in the current context should be expected to be performed O(1) times.
When the context detects that the magnitude of the query has grown, it expands the internal scope to reflect that shift.
As an example consider the recursive query in a context where the patient set is 5,000 cases large
db()/c[@case_type='patient][count( db()/c[ complex_predicate_filter ][ additional_filter ] )]
after the evaluation context processes
db()/c[@case_type='patient]
the next predicate (count( db()/c[ complex_predicate_filter ] [ additional_filter ])) is being evaluated 5000 times. complex_predicate_filter may have behavior that can be optimized differently depending on whether it expects to have to implement that filter once or thousands of times.
Generally speaking a new query context is created any time the previous query context is exceeded by 10. That means that if complex_predicate_filter produces a record set that is actually 50,000 elements large, that additional_filter receives a child context with that scope. The derivative scope will expire as soon as it has completed evaluating, making it safe for a handler to assume that data will be isolated appropriately.
The query context provides the planner and handlers with caches that they can use when evaluating queries, or can store any data that they think will be valuable to other handlers.
The caches are requested by class, and if no cache has been requested in the current context, a new one will be created. The caches will leave working memory when the context that spawned them has completed, so no cleanup needs to be managed by the handlers themselves.
Optimizes the loading of matches to index/* requests if the query scope is greater than some threshold. Major reduction to db transactions in bulk contexts.
Abstract entry point to allow a model to let the planner know when it is capable of handling some requests in memory based on cues from loading or parsing.
Keeps a very, small-N cache of models requested super frequently to improve performance of forms and contexts which are central to a workflow but can't be heuristically identified otherwise.
When handlers or models perform a lookup optimization that returns a large enough set of case ID's (IE: something like [@case_type = 'patient'] -> [0, 23, 43, 50]), that set of cases is provided to the CaseGroup cache. This cache can be retrieved again instead of performing the same lookup.
Additionally, when the case database child model receives a request to inflate a case which is in that group (IE: db_row: 23 -> <case> tree), and needs to load the requisite case object from storage, the platform (on Android, Web Apps, and other SQL backed platforms) will load all matching cases from that group (or some portion of it) at once in order to minimize db requests.
Example:
Query:
count(db()/case[@case_type = 'patient'][@case_type='open'][enrolled='true'])
-------------
Step 0:
Handled:
db()/
Current Working Set:
db()/
Next:
case[@case_type = 'patient'][@case_type='open']
Context:
Scope: 1
Cache:
-------------
Step 1:
Handled:
db()/case[@case_type = 'patient'][@case_type='open']
Result (200 matching cases):
[0, 10, 15, 20,...]
Current Working Set:
> db()/case[0]
db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => Empty
-------------
Step 2:
Linear scan through working set:
db()/case[0] -> [enrolled = 'yes']
Inflate case[0] ('Query' step in the virtual instance)
1. check CaseGroupCache.cached_cases
2. case_0 is not in CaseGroupCache.cases
3. check CaseGroupCache.groups for case 0
4. return case_patient_open set (0, 10, 15, 20...)
5. retrieve all records (case_0, case_10, case_15, case_20) from DB and store in cached cases
6. return case_0
7. inflate case[0]
8. db()/case[0]/enrolled = 'yes' => true
Current Working Set:
db()/case[0] => true
> db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => [0 -> case_0, 10 -> case_10, 15 -> case_15, 20 -> case_20...)]
Step 3:
Linear scan through working set:
db()/case[10] -> [enrolled = 'yes']
Inflate case[10] ('Query' step in the virtual instance)
1. check CaseGroupCache.cached_cases
2. case_10 is in CaseGroupCache.cases
6. return case_10
7. inflate case[10]
8. db()/case[10]/enrolled = 'yes' => false
Current Working Set:
db()/case[0] => true
[deleted] db()/case[10] => false
> db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => [0 -> case_0, 10 -> case_10, 15 -> case_15, 20 -> case_20...)]
... repeat for all members of working set
Another powerful, but complex, query handler provides the capacity to break down nested queries in ways that avoids retrieving intermediate data from storage. This implementation is currently only implemented with case queries.
The Model Query Lookup Handler scans over a predicate set when profiles are collected to see if it is possible to express the output of a predicate as a simple transform to model that was passed to it.
An example of such a transform would be
db()/c[@case_id = current()/index/parent]
Since the /index/parent step is indexed independently, and the @case_id match is indexed independently, there's no reason to evaluate the db lookups for either component.
Instead the expression is captured as a ModelQueryLookup profile, which is evaluated based on the transformation from one case (represented by current()) to another (the parent of that case).
For a more concrete example consider the process of filtering patient cases by a parent case property.
db()/case[@case_type = 'patient'][@case_type='open'][ db()/case[@case_id = current()/index/parent]/filter = 'yes']
After the initial evaluation [@case_type = 'patient'][@case_type='open'] (as seen in examples above), the engine will proceed with a linear scan of matching open patients.
The engine also provides a cue to the context about the current query set, which is to say, the working set of references which are being evaluated (IE: [0, 5, 10, 15, ...]). None of those case objects have been fetched from the database yet, but the context knows what their ids will be.
When evaluating the internal predicate
c/filter = 'yes'
the query set handler identifies that @case_id = current()/index/parent can be expressed as a transformation.
"@case_id =" <- Identity Lookup
current() <- Model Set [current]
/index/parent <- Index Transform [parent]
[Identity Lookup of (Model Set-> Index Transform)] = Model Set
So for the first reference evaluated, current() is db()/case[0], the transformation would simply evaluate
db()/case[Identity(Index Transform(Model Set[current[0]]->parent)]
By performing a parent index lookup at the db level for case record 0 to get the parent case (say, case 1), and letting the handler proceed with
db()/case[1]/filter
rather than
- retrieving the current case and inflate the
<case>reference - reading its
index/parentvalue - doing a db lookup to match the case by string id
- reading the
filterproperty from that inflated case reference
Model transforms like this let the queryset lookup handler avoid a significant amount of intermediate inflation and lookups.
Additionally, model transforms chain effectively. So if the example above was doubly nested as a grandparent reference, the query set matcher would be able to identify a two-part transform to the set.
Essentially the output of
db()/case[@case_id = current()/index/parent]
is itself the base of a model set lookup, so it is applicable to transform.
The general parse structure of a model set is
[@case_id = {model set}\{transform}]
where {model set} is either recursively defined by that structure or matches
current()
Eventually this work can/should be extended to include model sets which match the other key/value patterns, IE:
[index\* = {model set}\{transform}]
[selected({model set}\{transform}, index\*]
both of which could fairly easily be extended in the current code, but have not yet been included.
The other major improvement gained from query set lookups is similar to the case group cache optimization above.
When we are processing model set transforms, we still need to use a db lookup to transform a case reference (row 0) to its index case (row 1). While doing these lookups purely at the ID level is more efficient than loading and reading the instance elements, it's still an individual lookup.
Since the inputs to query sets are already primed, however, it's possible for us to perform the transform for every member of a query set to another in a single DB operation, which is a massive performance improvement in situations involving hundreds or thousands of referenced cases.
Returning to the earlier example, the structure of a query set lookup is quite similar to the structure of a case group cache lookup
Query:
`db()/case[@case_type = 'patient'][@case_type='open'][ db()/case[@case_id = current()/index/parent]/filter = 'yes']`
-------------
Step 0:
Handled:
db()/
Current Working Set:
db()/
Next:
[@case_type = 'patient'][@case_type='open'][ db()/case[@case_id = current()/index/parent]/filter = 'yes']
Context:
Scope: 1
Cache:
-------------
Step 1:
Handled:
[@case_type = 'patient'][@case_type='open']
Result (200 matching cases):
[0, 10, 15, 20,...]
Current Working Set:
db()/case[0]
db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: (0, 10, 15, 20....)]
-------------
Step 2:
Linear scan through working set:
db()/case[0] -> [ db()/case[@case_id = current()/index/parent]/filter = 'yes']
Evaluating:
db()/case[...inner query...]
Recursive Case Query Triggered to match interior of [] -> Step 2.0
Current Working Set:
>db()/case[0]
db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: (0, 10, 15, 20....)]
-------------
Step 2.0
Query:
case[@case_id = current()/index/parent]
Working Set:
db()/
Context:
Current: db()/case[0]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: (0, 10, 15, 20....)]
-------------
Step 2.1
Predicate Processed:
case[ModelSetQueryProfile]
ModelSetQueryProfile
Model Set Transform(current_i_parent)
ModelSet (current_case)
Working Set:
db()/
Context:
Current: db()/case[0]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: (0, 10, 15, 20....)]
-------------
Step 2.2
Predicate Evaluated:
case[ModelSetQueryProfile] => 1
Process
1. Model Set Transform input: 0
2. Model Set Transform checks for cache (current_i_parent), no cache exists.
3. Model Set Transform dispatches request to Model Set for set body.
4. Model Set checks for body (current_case) and returns: (0, 10, 15, 20....)
5. Model Set Transform queries DB against body (0, 10, 15, 20....), gets transform map (0->1, 10->11, 15->16, 20-21,...)
6. Model Set Transform caches map (0->1, 10->11, 15->16, 20-21,...) and model set body (1, 11, 16, 21,...)
6.1 Model Set Transform reports (1, 11, 16, 21,...) to Case Group Result Cache
7. Model Set Transform checks map for input 0
8. Model Set Transform returns transformed id 1
Recursive Step Ends.
Final Nodeset:
db()/case[1]
Context:
Current: db()/case[0]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
-------------
Step 3:
Evaluated:
db()/case[0] -> [ db()/case[1]/filter = 'yes'] -> true
db()/case[1] inflated from storage, triggering case group bulk fetch for case_patient_open_i_parent
Next:
db()/case[10]
Current Working Set:
db()/case[0] => true
> db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => [1 -> case_1, 11 -> case_11, 16 -> case_16, 21 -> case_21...)]
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
Step 4:
Linear scan through working set:
db()/case[10- -> [ db()/case[@case_id = current()/index/parent]/filter = 'yes']
Evaluating:
db()/case[...inner query...]
Recursive Case Query Triggered to match interior of [] -> Step 4.0
Current Working Set:
>db()/case[0]
> db()/case[10]
db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => [1 -> case_1, 11 -> case_11, 16 -> case_16, 21 -> case_21...)]
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
-------------
Step 4.0
Query:
case[@case_id = current()/index/parent]
Working Set:
db()/
Context:0
Current: db()/case[10]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => [0 -> case_1, 11 -> case_11, 16 -> case_16, 21 -> case_21...)]
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
-------------
Step 4.1
Predicate Processed:
case[ModelSetQueryProfile]
ModelSetQueryProfile
Model Set Transform(current_i_parent)
ModelSet (current_case)
Working Set:
db()/
Context:
Current: db()/case[10]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => [1 -> case_11, 11 -> case_11, 16 -> case_16, 21 -> case_21...)]
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
-------------
Step 4.2
Predicate Evaluated:
case[ModelSetQueryProfile] => 11
Process
1. Model Set Transform input: 10
2. Model Set Transform checks for cache (current_i_parent), cache exists.
3. Model Set Transform retrieves cached value (10->11)
8. Model Set Transform returns transformed id 11
Recursive Step Ends.
Final Nodeset:
db()/case[11]
Context:
Current: db()/case[10]
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => Empty
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
-------------
Step 5:
Evaluated:
db()/case[10] -> [ db()/case[11]/filter = 'yes'] -> false
db()/case[10] inflated from storage by retrieving case from cached_cases.
Next:
db()/case[15]
Current Working Set:
db()/case[0] => true
[removed[ db()/case[10] => false
> db()/case[15]
db()/case[20]
...
Context:
Scope: 200
Cache:
CaseGroupCache:
groups: [case_patient_open => (0, 10, 15, 20...),
case_patient_open_i_parent => (1, 11, 16, 21,...)]
cached_cases => [1 -> case_11, 11 -> case_11, 16 -> case_16, 21 -> case_21...)]
Model Sets Cache:
caches: [current_case: body(0, 10, 15, 20....),
current_i_parent: map(0->1, 10->11, 15->16, 20->21....), body(1, 11, 16, 21)]
... repeat for all members of working set
Currently the model set matcher won't provide a set transform/lookup for predicates which transform matches to index/*, which could be done with some more static analysis.
The model query set matcher also doesn't match across model boundaries (between cases and fixtures, say), and currently is only implemented for cases, although it would be easy to extend that pattern.
The QueryContext or Planner should be providing / tracking significantly more "tuning" information on the current platform. The limits for "bulk" execution were collected heuristically and could be improved on some platforms.
Currently the Predicate -> PredicateProfile sets are mostly provided by the models themselves, but should meaningfully be handled by the planner, dispatching through the handlers.
The process that builds Predicate Profiles also currently evaluates all necessary elements to do so when asked, which is quite limiting.
If, for instance, one handler could optimize [a = complex_expression] to make the a = section faster, and another could optimize complex_expression significantly faster (say, by detecting that it would always return blank), the first handler would defeat the purpose of the second when it evaluated complex_expression when generating its predicate profile.
Currently we work around this by only implementing custom PredicateProfile objects in a handler when that handler has no competition for being the fastest, but long-term the evaluation of a predicate profile should likely be lazy and/or decouple from its structural generation.