WL#12534: Support LIMIT in recursive common table expression

Affects: Server-8.0   —   Status: Complete

with recursive qn as
  (
   select cast("x" as char(100)) as a from dual
   union all select concat("x",qn.a) from qn where length(qn.a)<10 limit 3
   )
select * from qn;ERROR 1235 (42000): This version of MySQL doesn't yet support
'ORDER BY / LIMIT over UNION in recursive Common Table Expression'

We have had a request that LIMIT would terminate the filling of the CTE (above, 
when "qn" contains 3 rows in total).

It is a limit on the total number of rows in the final CTE, not on the
number of rows that each iteration may produce.
    
While it was already possible to put LIMIT on the outermost SELECT,
putting it inside the definition of the CTE has the advantage that
it stops the row generation algorithm as soon as it has produced the
requested number of rows; it's thus more efficient.

With LIMIT, the content of the recursive CTE is a subset of what it would
have been without LIMIT. Which rows end up in this subset depends on
the order of the generation of rows, which is implementation-defined
(and thus, not precisely specified). This order cannot be influenced
by adding ORDER BY as this is forbidden in a recursive CTE.
The order is loosely defined here:
https://dev.mysql.com/doc/refman/8.0/en/with.html#common-table-expressions-
recursive
    
So, this feature is intended to be used as "give me N rows, no matter
exactly which ones". Like "give me 10 descendents of this root ancestor".
Given our algorithm, it may usually be a breadth-first ordering, but
there's no guarantee. Even less if the recursive part contains a JOIN
to another table. The used indexes may also influence that.
    
This feature can also be used as a precaution against a runaway recursive CTE;
instead of hitting the @cte_max_recursion_depth maximum and stopping
with error, the query with LIMIT will stop, without error, after producing
that many rows.

OFFSET should be supported too.

We will still not allow ORDER BY over the UNION.

Note that:
with recursive qn as
  (
   select cast("x" as char(100)) as a from dual
   union all (select concat("x",qn.a) from qn where length(qn.a)<10 limit 3)
   )
select * from qn;
will continue throwing:
ERROR 1235 (42000): This version of MySQL doesn't yet support 'ORDER BY / LIMIT
/ SELECT DISTINCT in recursive query block of Common Table Expression'

This WL has a side-effect for a non-recursive CTE or derived table: if it has
UNION DISTINCT and LIMIT/OFFSET we now do direct materialization i.e. instead
of having one tmp table for storing the result of UNION and then another tmp
table for storing the result of LIMIT (forming the derived table or CTE), the
first tmp table is not created anymore: we have the UNION rows flowing directly
into the LIMIT filter and ending up stored into the final result tmp table (the
derived table or CTE). This will probably improve performance.

See also BUG#92857 Support LIMIT inside definition of recursive CTE