Add observability to the query optimizer

[antiguru]

Feature request

The query optimizer currently only exposes information about its inner workings as part of EXPLAIN, which suffers from limitations. It needs to be explicitly issued, and it only shows the state of a query at discrete points, for example after decorrelation. It does not allow us to observe the behavior and performance of the optimizer in a more complete approach.

To improve the situation we should add per-transform statistics that capture:

• How long a certain transform took, and
• Whether it changed the AST or not.

This data could be represented as a table containing a timing histogram per transformation and whether it changed its inputs.

Related: https://github.com/MaterializeInc/materialize/issues/13140

[aalexandrov]

Several optimizations run multiple times per pipeline, so I think we should consider using the stage path (which identifies a transform application within the pipeline) rather than the transform name as the key for this table.

I can think about the following additional metrics for which it will be good to collect histograms:

• Number of inputs of a query.
• Total number of input columns of a query.
• Number of output columns of a query.
• Presence of aggregates.
• Presence of window functions.
• Number of inner joins.
• Number of outer joins.

For the general optimization pass:

• Total number of views (including transitive views) inlined during the pass.
• Maybe the types of sources referenced by the optimized query.

For some key moments of the pipeline:

• Number of nodes in the tree at this moment.
• Depth of the tree at this moment.

We don't need to implement all of those at once, but if we build an infrastructure for collecting histograms these are some optimizer-related metrics that I think can be a good fit.

It will be quite nice if we have direct access to these statistics so we can use them as part of our automation and alerting.

[aalexandrov]

[...] it only shows the state of a query at discrete points, for example after decorrelation.

Strictly speaking this is not correct. With EXPLAIN OPTIMIZER TRACE you get information about the timing and the plan after each stage of the optimizer. It's quite expensive to collect this full trace at every step, though.

[ggevay]

We can also add metrics for window functions:

• which window functions are used
• with what frames
• what data types occur in the ordering (e.g., to know whether we need to figure out a way to support ordering window partitions by a string).