Compilation perf: consider not exhaustively including all query sub-nodes in hash calculation

[roji]

Our hash code calculation currently meticulously traverses the entire subtree of a given node. Unlike with equality, this isn't necessary, and may cost us significant compilation time. For example, we could decide to stop hashcode calculation at the first SelectExpression we see.

See also #19860, which is about caching hashcodes and could obviate this (not sure).
See #19737 for a case where exhaustive hash code calculation caused exponential calculation.

[roji]

Related: #21700

[sulton-max]

@roji

I was confused why ExpressionEqualityComparer didn't visit all nodes to compute hash, this lead me to this issue, can you help with how to implement hashing of query ?

If it's already implemented in internal infrastructure could you share references ?

I'm struggling to implement my own expression tree visitor, because I thought it would be as simple as calling ExpressionEqualityComparer.GetHashCode for each node, but that didn't work, now I'm trying to address all LINQ methods one by one

If there is already solution for this, that could really help for my work, thank you

[roji]

@sulton-max unless I'm mistaken, ExpressionEqualityComparer does currently visit all nodes to compute the tree hashcode (https://github.com/dotnet/efcore/blob/main/src/EFCore/Query/ExpressionEqualityComparer.cs#L34). Are you seeing a case where it does not visit a node or something?

[ranma42]

Our hash code calculation currently meticulously traverses the entire subtree of a given node. Unlike with equality, this isn't necessary, and may cost us significant compilation time. For example, we could decide to stop hashcode calculation at the first SelectExpression we see.

This is not 100% clear to me; is the plan something like saying that instead of recursing into a SelectExpression we simply use a constant to represent it?

Assuming that each hash code is computed upon construction, using the sub-expression hash should be about as cheap (no visit, just a memory access vs a constant).

[roji]

Yeah, on second thought, you're probably right that if we cache the hash code, then there's no real point in doing something here, as it's already super cheap. I'll go ahead and close.

[roji]

BTW we still can compute the hash code lazily on 1st need, rather than upon construction, since it's not sure that we'll actually need the hash code for all expressions. At that point it may be beneficial to not recurse all the way (that was the original thinking here I think), but it doesn't seem important enough.