Query inefficiency with a single-statement query with nested queries

[CatherineGasnier]

Copying a user report, which I could repro:

I want to run the following query to get some cxx variable declarations with empty string name

codemarkup.FileEntityLocations {file="fbcode/dead_code_removal/invariant_thrift/test/DataCollectorThriftInterceptorTest.cpp", entity={cxx={decl=DECL}}};

DECL = {variable={name={name=""}}};
DECL

This query takes forever and times out.

Changing the filtering to {variable={name={name=_}}} the 15 variables on that file immediately.

Trying a different string filter like {variable={name={name="test_info_"}}} also hangs.

But a more "normal" string like {variable={name={name="invariantFields"}}} finishes fast enough.

(End of user report)

The IR for the query is extremely and surprisingly complex, with ifs and choices, and the order of statements not what you'd expect.

This also takes a long time without the intermediate DECL:

codemarkup.FileEntityLocations {file="fbcode/dead_code_removal/invariant_thrift/test/DataCollectorThriftInterceptorTest.cpp", entity={cxx={decl={variable={name = {name=""}}}}}}

[simonmar]

That does look surprising. It'll be hard for me to repro without the real DB, but I might be able to try the query on a test DB and see if the statement ordering looks wrong.

[simonmar]

OK, I was able to repro the issue and I understand what's going on. The bad news is that there's no bug as such - things are working as expected. I'll explain further below. First, there is a workaround:

codemarkup.FileEntityLocations {file="...", entity={cxx={decl=DECL}}}; 
({} where DECL = {variable={name={name=""}}});
DECL

This should have the desired performance characteristics, that is it selects the declarations from the file first and then filters for the desired ones, rather than filtering all declarations first and then filtering by file.

background

Angle works by:

• Expanding the query into simple statements
• Re-ordering the statements so that the query is efficient

There's a tension between letting the compiler do all the reordering and allowing the author more control. Usually you want the compiler to do it all, because writing out all the statements in an explicit order is painstaking for the author. However, the compiler sometimes gets it wrong, and the human knows more about the data (e.g. in this case the human knows it's better to filter by file first).

So we allow the author to put some constraints on statement ordering. The current rules are:

1. an explicit fact match is never reordered with respect to the statements around it
2. statements are never floated outside of (a) a derived predicate or (b) a where clause

aside from these constraints, the compiler is free to float and reorder statements at will.

Note that these rules aren't set in stone: ideally we'd like to give the compiler more flexibility, but historically it's been hard to relax the rules because some queries will regress. There are a lot of regression tests, particularly the perf tests under glean/lang/codemarkup that tend to pick up regressions in this area.

what goes wrong with this particular query?

The original query is:

codemarkup.FileEntityLocations {file="...", entity={cxx={decl=DECL}}}; 
DECL = {variable={name={name=""}}};
DECL

Let's do the expansion that the Angle compiler does:

[
  ~ N = cxx1.Name "";
  ~ Q = cxx1.QName { name = N };
  ~ V = cxx1.VariableDeclaration { name = Q };
  ~ DECL = { variable = V };
  [ ... expansion of derived predicate codemarkup.FileEntityLocations ... ];
]

[...] indicates a group of statements; "~" indicates a statement that can be reordered with respect to the others in the group.

(I've simplified it a bit here, but you can see this intermediate form by setting the env var GLEAN_DEBUG=query and running the query locally, e.g. with the shell. Look for "flattened query". To see the final statement ordering, look for "reordered query").

You can see that the cxx1.QName match and cxx1.VariableDeclaration match are reorderable. That's because they were not explicit in the original query; they arose due to the implicit pattern match {variable = { name = { name = "" }}}.

If we make them explicit in the query, we can force the compiler to put them in the order we want (using constraint (1) above):

codemarkup.FileEntityLocations {file="...", entity={cxx={decl=DECL}}}; 
DECL = {variable=V}; N = cxx1.Name ""; Q = cxx1.QName {name=N}; V = cxx1.VariableDeclaration {name=Q}

Try it - this should work.

There's a simpler way to force the constraint that we want though, using constraint (2) above we can introduce a dummy where clause to act as a barrier to reordering.

codemarkup.FileEntityLocations {file="...", entity={cxx={decl=DECL}}}; 
({} where DECL = {variable={name={name=""}}});
DECL

what could we do?

1. Make the compiler smarter so that it can figure out the efficient ordering. This should be possible, but I've spent a ton of time on the optimiser already and I can tell you it's quite hard to make improvements without regressing something.
2. Make a more explicit way to force ordering constraints? The where clause trick is a bit subtle. Also we don't really want a where clause to introduce an ordering barrier, by relaxing that we might get better query optimisation in some cases.