• "add schema as a field of QueryExpr, then add a rewriting pass that fills this value": Could you expand on this a bit, and why you think it would be a better approach? My first thought is that having an additional field that may or may not be set at a given point in time will make things less clear.

Yes, I initially proposed to have a separate intermediary object but it was super hard to prototype this and start making progress in that direction. After discussing this with @Maegereg, I changed the proposal to instead use a series of rewrite rules, in a similar way than how KeySets now work. This does lead to a situation where some fields start being not set and then get set in rewrite rules, but I think we will still end up with much cleaner logic — with a clear separation between successive rewrite rules, and each one being simpler and self-contained. In that world, it would sense to me to also have schema determination be one of the rewrite rules (but I'm not 100% sure about this, in particular I'm not super clear on when this would need to happen in the sequence of rewrite rules). I would love your feedback on this!

• Not something for this MR, but it seems like _query_expr.py is getting very long, and we haven't incorporated that much of the compilation into it yet. Should we consider breaking it up into a multi-file submodule?

Yes, I think this PR basically gets this file into "should be broken up if we add more logic" territory; I may do this as a follow-up issue if I need to add more stuff in there.

Ah, I see where you're coming from. For some properties I could see that, but for schemas specifically: are there situations where the rewrite of a particular expression changes the resulting schema? It seems to me that shouldn't happen for the expression end-to-end (though some of the intermediate pieces may have their schemas changed/rearranged in the rewrite). That might be why it's unclear when the rewrite rule that fills in the schema should run -- there's no obvious good time, because it should work equivalently at any point. On a related note, what would a rewrite rule that fills in the schemas look like? We presumably don't want to embed all the schema logic in that rewrite rule (that just gets us back to something like the schema visitor), which means calling some QueryExpr method... which is exactly what this MR is doing already, but now there's this extra step and the property isn't always defined.

(This is slightly complicated by the fact that rewrite rules need to be able to do things like "pull out this entire expression and turn it into a separate query to get groups from it", but I think the above idea about the rewrites not changing the schema still holds: we're replacing a general expression that does a groupby where the groups have a particular schema with a concrete groupby referencing a new expression with that same output schema, so the overall schema of the original expression doesn't change.)

Hmm, you're right, so maybe the way of computing the schema in this PR is the right approach.

Also, I think I agree with Tom - doing schemas as a rewrite seems worse than this approach.