Updates to derived-with-keys, window functions determining records per key

Enabling derived keys optimization for derived.col = const pushed conditions.

Estimating records per key in derived key for the optimizer based on form and/or size of components of a derived table.

Consider a derived table of the form

SELECT ..., ROW_NUMBER ()  OVER (PARTITION BY c1,c2 order by ...)

FROM t1, t2, t3 ...

WHERE ...

If the optimizer generates a key on this derived table because of a constraint being pushed into it, it currently will not consider key components of the form column = const

We lift this constraint and add code to TABLE::add_tmp_key to search for a window function ROW_NUMBER() in our item list. From the partition list c1, c2 we can in infer an estimate of the number of rows we expect to see for each key value. The optimizer can then use this number to determine a better table join order.

On estimating of rec_per_key(ROW_NUMBER () OVER PARTITION BY)

Can we reuse estimates from estimate_post_group_cardinality() here?

Estimating post-GROUP BY cardinality

For GROUP BY output size estimation, we use "pessimistic" approach. That means we prefer to compute a "safe upper bound" of the number of GROUP BY groups.

If we're processing

select * from t1 group by expr(t1) 

and we don't have statistics for expr(t1), we will assume that

ndv(expr(t1))= n_rows(t1)

For multiple GROUP BY elements:

select * from t1,t2 ... group by expr(t1), expr(t2) 

we again take the conservative approach and produce the upper bound of # of groups:

  MAX( join_output_card, ndv(expr(t1))*ndv(expr(t2)))

Applying it to rec_per_key (PARTITION BY )

When estimating rec_per_key of

  ROW_NUMBER () OVER ( PARTITION BY expr(t1)  ... )

If we followed the GROUP BY approach and assumed that (every value of expr(t1) is unique)

  ndv(expr(t1))= n_rows(t1)

that would be optimistic. rec_per_key=1 will have us assume that derived_with_keys optimization will be highly advantageous as any index lookup would return 1 row. The reality could be much worse.

To follow the principle of using a pessimistic approach, we'll have to assume that:

  ndv(expr(t1))= 1.

unless there is [column] statistics that tells otherwise.

If the PARTITION BY clause has multiple elements:

  ROW_NUMBER () OVER ( PARTITION BY col1, col2, [ORDER BY ...])

pessimistic approach would the formula

  row_number_ndv = MAX( ndv(col1), ndv(col2), ... )