The culprit:
```
Tuple counts for PointsTo::InterProceduralPointsTo::scope_entry_value_transfer_from_earlier#741b54e2#ffff#join_rhs/5@eb1340iv after 12.6s:
72973 ~3% {2} r1 = JOIN PointsToContext::TImportContext#cf3039a0#f WITH Definitions::NonEscapingGlobalVariable#class#486534ab#f CARTESIAN PRODUCT OUTPUT Rhs.0, Lhs.0 'arg1'
537932 ~0% {3} r2 = JOIN r1 WITH Essa::EssaDefinition::getSourceVariable#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'arg2', Lhs.1 'arg1', Lhs.0
982333 ~0% {4} r3 = JOIN r2 WITH Essa::EssaVariable::getAUse#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.2, Lhs.1 'arg1', Lhs.0 'arg2', Rhs.1 'arg0'
37029774 ~0% {4} r4 = JOIN r3 WITH Essa::TEssaNodeDefinition#24e22a14#ffff ON FIRST 1 OUTPUT Rhs.3 'arg3', Lhs.1 'arg1', Lhs.2 'arg2', Lhs.3 'arg0'
35956211 ~0% {5} r5 = JOIN r4 WITH Essa::ScopeEntryDefinition::getScope#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.3 'arg0', Lhs.1 'arg1', Lhs.2 'arg2', Lhs.0 'arg3', Rhs.1 'arg4'
return r5
```
You may notice that this is a predicate that's _materialised_, but it's
never actually used anywhere. It's the old "standard order" bringing
much sadness.
The problem here is that in the standard order (which we never actually
use here), we end up with a join between the bits above, `getRootCall`,
and `appliesToScope`. The `join_rhs` bit is joined twice, once with
`getRootCall#prev` and `appliesToScope#prev_delta` (in that order), and
once with `prev` and `prev_delta` swapped.
So to fix this, I used the unbinding pragma to force `appliesToScope` to
appear first in the join order. This was enough to make the compiler
_not_ push the common context into its own `join_rhs` predicate (and
the join-order is still decent.)
Much sadness:
```
Tuple counts for ImportTime::ImportTimeScope::getOuterVariable#dispred#f0820431#fff/3@64d04d33 after 7.6s:
19624 ~1% {1} r1 = SCAN py_Classes OUTPUT In.0 'this'
19531 ~1% {1} r2 = JOIN r1 WITH ImportTime::ImportTimeScope#class#7851b601#f ON FIRST 1 OUTPUT Lhs.0 'this'
19531 ~0% {2} r3 = JOIN r2 WITH Scope::Scope::getEnclosingModule#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.0 'this', Rhs.1
296389 ~0% {3} r4 = JOIN r3 WITH Variables::Variable::getScope#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'var', Lhs.0 'this', Lhs.1
296389 ~0% {3} r5 = JOIN r4 WITH Variables::LocalVariable#3aa06bbf#f ON FIRST 1 OUTPUT Lhs.0 'var', Lhs.1 'this', Lhs.2
296389 ~1% {4} r6 = JOIN r5 WITH Variables::Variable::getId#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.2, Lhs.1 'this', Lhs.0 'var', Rhs.1
62294919 ~0% {4} r7 = JOIN r6 WITH Variables::Variable::getScope#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'var', Lhs.1 'this', Lhs.2 'var', Lhs.3
62294919 ~0% {4} r8 = JOIN r7 WITH Variables::GlobalVariable#class#3aa06bbf#f ON FIRST 1 OUTPUT Lhs.0 'result', Lhs.3, Lhs.1 'this', Lhs.2 'var'
639 ~0% {3} r9 = JOIN r8 WITH Variables::Variable::getId#dispred#f0820431#ff ON FIRST 2 OUTPUT Lhs.2 'this', Lhs.3 'var', Lhs.0 'result'
return r9
```
Clearly we _shouldn't_ be joining on `getId` as the last thing, as this
means we're building tuples of completely unrelated variables (not even
with the same name!) which obviously blows up.
A standard way of fixing this is to correlate as much information about
these variables as possible in a `nomagic`ked helper predicate. This is
what we do here, grouping together the variable with its scope and name
(both of which are uniquely determined by the variable). This results
in a much nicer join order:
```
Tuple counts for ImportTime::ImportTimeScope::getOuterVariable#dispred#f0820431#fff/3@82866b6p after 42ms:
23867 ~4% {2} r1 = JOIN Scope::Scope::getEnclosingModule#dispred#f0820431#ff WITH ImportTime::ImportTimeScope#class#7851b601#f ON FIRST 1 OUTPUT Lhs.0 'this', Lhs.1
296389 ~0% {4} r2 = JOIN r1 WITH ImportTime::class_var_scope#7851b601#fff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0 'this', Rhs.2 'var'
639 ~0% {3} r3 = JOIN r2 WITH ImportTime::global_var_scope#7851b601#fff ON FIRST 2 OUTPUT Lhs.2 'this', Lhs.3 'var', Rhs.2 'result'
return r3
```
```
Tuple counts for ImportTime::class_var_scope#7851b601#fff/3@366258vr after 47ms:
19624 ~1% {1} r1 = SCAN py_Classes OUTPUT In.0 'scope'
296743 ~0% {2} r2 = JOIN r1 WITH Variables::Variable::getScope#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'var', Lhs.0 'scope'
296743 ~0% {2} r3 = JOIN r2 WITH Variables::LocalVariable#3aa06bbf#f ON FIRST 1 OUTPUT Lhs.0 'var', Lhs.1 'scope'
296743 ~2% {3} r4 = JOIN r3 WITH Variables::Variable::getId#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.1 'scope', Rhs.1 'name', Lhs.0 'var'
return r4
```
```
Tuple counts for ImportTime::global_var_scope#7851b601#fff/3@718e4bpm after 18ms:
108173 ~0% {2} r1 = JOIN Variables::GlobalVariable#class#3aa06bbf#f WITH Variables::Variable::getId#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.0 'var', Rhs.1 'name'
108173 ~0% {3} r2 = JOIN r1 WITH Variables::Variable::getScope#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.1 'name', Rhs.1 'scope', Lhs.0 'var'
return r2
```
(You may be wondering what's up with the order of arguments for the two
helper predicates. By ordering the arguments this way, there's no need
to reorder the resulting relations when used in `getOuterVariable.)
Before:
```
Tuple counts for Essa::ScopeEntryDefinition#class#24e22a14#f/1@45e0d8dh after 10.5s:
2133368 ~1% {2} r1 = Essa::TEssaNodeDefinition#24e22a14#ffff_03#join_rhs AND NOT Essa::ImplicitSubModuleDefinition#class#24e22a14#f(Lhs.1 'this')
534478950 ~0% {2} r2 = JOIN r1 WITH Definitions::SsaSourceVariable::getScopeEntryDefinition#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.1 'this', Rhs.1
581249 ~4% {1} r3 = JOIN r2 WITH Essa::EssaNodeDefinition::getDefiningNode#dispred#f0820431#ff ON FIRST 2 OUTPUT Lhs.0 'this'
return r3
```
Let's see if pushing the `getDefiningNode` join further up improves the
number of intermediary tuples. (Intuitively it should, since there
should only be one defining node for any given `EssaNodeDefinition`.)
To do this, we unbind the `this.getSourceVariable()` part, which
encourages the compiler to put this join later.
After:
```
Tuple counts for Essa::ScopeEntryDefinition#class#24e22a14#f/1@30758cv4 after 300ms:
2133569 ~1% {2} r1 = SCAN Essa::TEssaNodeDefinition#24e22a14#ffff OUTPUT In.0, In.3 'this'
2133368 ~1% {2} r2 = r1 AND NOT Essa::ImplicitSubModuleDefinition#class#24e22a14#f(Lhs.1 'this')
2133368 ~0% {2} r3 = JOIN r2 WITH Definitions::SsaSourceVariable#class#486534ab#f ON FIRST 1 OUTPUT Lhs.1 'this', Lhs.0
2133368 ~0% {3} r4 = JOIN r3 WITH Essa::EssaNodeDefinition::getDefiningNode#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.0 'this'
581249 ~4% {1} r5 = JOIN r4 WITH Definitions::SsaSourceVariable::getScopeEntryDefinition#dispred#f0820431#ff ON FIRST 2 OUTPUT Lhs.2 'this'
return r5
```
Much better (and our intuition is confirmed -- joining with
`getDefiningNode` did not increase the number of tuples).
Before:
```
Tuple counts for Essa::EssaEdgeRefinement::getInput#dispred#f0820431#ff/2@b84afc77 after 20.3s:
873421 ~0% {3} r1 = JOIN Essa::TEssaEdgeDefinition#24e22a14#ffff_31#join_rhs WITH Essa::TEssaEdgeDefinition#24e22a14#ffff_30#join_rhs ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0 'this'
181627951 ~0% {3} r2 = JOIN r1 WITH Essa::EssaDefinition::getSourceVariable#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'result', Lhs.1, Lhs.2 'this'
873418 ~0% {2} r3 = JOIN r2 WITH Essa::EssaDefinition::reachesEndOfBlock#dispred#f0820431#ff ON FIRST 2 OUTPUT Lhs.2 'this', Lhs.0 'result'
return r3
```
It's perhaps not immediately obvious what's going on here (because of
the `...join_rhs` indirection), but basically we're joining together
`this` and `def` and their `getSourceVariable`, and only then actually
relating `this` and `def` through `reachesEndOfBlock`.
By unbinding `var`, we prevent this early join, which now encourages the
`reachesEndOfBlock` join to happen earlier:
```
Tuple counts for Essa::EssaEdgeRefinement::getInput#dispred#f0820431#ff/2@2d63e5lb after 2s
873421 ~0% {2} r1 = SCAN Essa::TEssaEdgeDefinition#24e22a14#ffff OUTPUT In.3 'this', In.1
873421 ~0% {3} r2 = JOIN r1 WITH Essa::TEssaEdgeDefinition#24e22a14#ffff_30#join_rhs ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0 'this'
873421 ~0% {3} r3 = JOIN r2 WITH Definitions::SsaSourceVariable#class#486534ab#f ON FIRST 1 OUTPUT Lhs.1, Lhs.2 'this', Lhs.0
8758877 ~0% {3} r4 = JOIN r3 WITH Essa::EssaDefinition::reachesEndOfBlock#dispred#f0820431#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1 'result', Lhs.2, Lhs.1 'this'
873418 ~0% {2} r5 = JOIN r4 WITH Essa::EssaDefinition::getSourceVariable#dispred#f0820431#ff ON FIRST 2 OUTPUT Lhs.2 'this', Lhs.0 'result'
return r5
```
On certain databases, the evaluation of this predicate was running out
of memory due to the way the `count` aggregate was being used. Here's
an example of the tuple counts involved:
```
Tuple counts for PointsToContext::syntactic_call_count#cf3039a0#ff#antijoin_rhs/1@d2199bb8 after 1m27s:
595518502 ~521250% {1} r1 = JOIN PointsToContext::syntactic_call_count#cf3039a0#ff#shared#3 WITH Flow::CallNode::getFunction#dispred#f0820431#ff_1#join_rhs ON FIRST 1 OUTPUT Lhs.1 'arg0'
26518709 ~111513% {1} r2 = JOIN PointsToContext::syntactic_call_count#cf3039a0#ff#shared#2 WITH Flow::CallNode::getFunction#dispred#f0820431#ff_1#join_rhs ON FIRST 1 OUTPUT Lhs.1 'arg0'
622037211 ~498045% {1} r3 = r1 UNION r2
return r3
```
and a timing report that looked like this:
```
time | evals | max @ iter | predicate
------|-------|--------------|----------
5m8s | | | PointsToContext::syntactic_call_count#cf3039a0#ff#shared#2@6d98d1nd
4m38s | | | PointsToContext::syntactic_call_count#cf3039a0#ff#count_range@f5df1do4
3m51s | | | PointsToContext::syntactic_call_count#cf3039a0#ff#shared#3@da3b4abf
1m58s | 7613 | 37ms @ 4609 | MRO::ClassListList::removedClassParts#f0820431#fffff#reorder_2_3_4_0_1@8155axyi
1m37s | 7613 | 33ms @ 3904 | MRO::ClassListList::bestMergeCandidate#f0820431#2#fff@8155a83w
1m27s | | | PointsToContext::syntactic_call_count#cf3039a0#ff#antijoin_rhs@d2199bb8
1m8s | 1825 | 63ms @ 404 | PointsTo::Expressions::equalityEvaluatesTo#741b54e2#fffff@8155aw7w
37.6s | | | PointsToContext::syntactic_call_count#cf3039a0#ff#join_rhs@e348fc1p
...
```
To make optimising this easier for the compiler, I moved the bodies of
the `count` aggregate into their own helper predicates (with size
linear in the number of `CallNode`s), and also factored out the many
calls to `f.getName()`.
The astute reader will notice that in writing this as a sum of `count`s
rather than a count of a disjunction, the intersection (if it exists)
will be counted twice, and so the semantics may be different. However,
since `method_call` and `function_call` require `AttrNode` and
`NameNode` functions respectively, and as these two types are disjoint,
there is no intersection, and so the semantics should be preserved.
After the change, the evaluation of `syntactic_call_count` now looks as
follows:
```
Tuple counts for PointsToContext::syntactic_call_count#cf3039a0#ff/2@662dd8s0 after 216ms:
23960 ~0% {1} r1 = @py_scope#f AND NOT py_Functions_0#antijoin_rhs(Lhs.0 's')
23960 ~0% {2} r2 = SCAN r1 OUTPUT In.0 's', 0
276309 ~7% {2} r3 = SCAN @py_scope#f OUTPUT In.0 's', "__init__"
11763 ~0% {2} r4 = JOIN r3 WITH Scope::Scope::getName#dispred#f0820431#fb ON FIRST 2 OUTPUT Lhs.0 's', 1
35723 ~0% {2} r5 = r2 UNION r4
252349 ~0% {2} r6 = JOIN @py_scope#f WITH Function::Function::getName#dispred#f0820431#ff ON FIRST 1 OUTPUT Lhs.0 's', Rhs.1
240586 ~0% {2} r7 = SELECT r6 ON In.1 != "__init__"
131727 ~4% {2} r8 = r7 AND NOT project#PointsToContext::method_call#cf3039a0#ff(Lhs.1)
131727 ~0% {3} r9 = SCAN r8 OUTPUT In.1, In.0 's', 0
240586 ~0% {2} r10 = SCAN r7 OUTPUT In.1, In.0 's'
108859 ~0% {3} r11 = JOIN r10 WITH PointsToContext::syntactic_call_count#cf3039a0#ff#join_rhs ON FIRST 1 OUTPUT Lhs.0, Lhs.1 's', Rhs.1
240586 ~0% {3} r12 = r9 UNION r11
24100 ~0% {2} r13 = JOIN r12 WITH PointsToContext::syntactic_call_count#cf3039a0#ff#join_rhs#1 ON FIRST 1 OUTPUT Lhs.1 's', (Rhs.1 + Lhs.2)
240586 ~0% {2} r14 = SELECT r6 ON In.1 != "__init__"
131727 ~4% {2} r15 = r14 AND NOT project#PointsToContext::method_call#cf3039a0#ff(Lhs.1)
131727 ~0% {3} r16 = SCAN r15 OUTPUT In.0 's', In.1, 0
108859 ~4% {3} r17 = JOIN r10 WITH PointsToContext::syntactic_call_count#cf3039a0#ff#join_rhs ON FIRST 1 OUTPUT Lhs.1 's', Lhs.0, Rhs.1
240586 ~4% {3} r18 = r16 UNION r17
216486 ~2% {3} r19 = r18 AND NOT project#PointsToContext::function_call#cf3039a0#ff(Lhs.1)
216486 ~0% {2} r20 = SCAN r19 OUTPUT In.0 's', (0 + In.2)
240586 ~0% {2} r21 = r13 UNION r20
276309 ~0% {2} r22 = r5 UNION r21
return r22
```
- "Normal" instead of "NonSpecial"
- "NonLibrary" instead of "2"
I could not find a good replacement for "NonLibrary", nor for "Source",
but I added QLDocs in a few places to help the reading.
