Recursive CTE silently loses rows when its increment table is converted to an on-disk temporary table

A recursive CTE whose increment table outgrows the in-memory temporary table returns a wrong result. The row that overflows the increment table is replaced by an all-NULL record, so that row and every row the recursion would have derived from it are missing from the answer. No error and no warning is raised.

How to repeat

SET SESSION max_recursive_iterations=1000000;

CREATE TABLE t (id INT);

INSERT INTO t

WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i+1 FROM n WHERE i < 100)

SELECT i FROM n;

SET SESSION tmp_memory_table_size=16777216, max_heap_table_size=16777216;

WITH RECURSIVE r AS (SELECT 1 AS lvl, CAST(REPEAT('x',200) AS CHAR(200)) AS pad

                     UNION ALL SELECT lvl+1, pad FROM r, t WHERE lvl < 3)

SELECT COUNT(*) AS cnt, COUNT(pad) AS nonnull_pad, SUM(lvl) AS sum_lvl FROM r;

SET SESSION tmp_memory_table_size=16384, max_heap_table_size=16384;

WITH RECURSIVE r AS (SELECT 1 AS lvl, CAST(REPEAT('x',200) AS CHAR(200)) AS pad

                     UNION ALL SELECT lvl+1, pad FROM r, t WHERE lvl < 3)

SELECT COUNT(*) AS cnt, COUNT(pad) AS nonnull_pad, SUM(lvl) AS sum_lvl FROM r;

DROP TABLE t;

The two runs differ only in the temporary table sizes. The first is large enough to keep the increment table in memory, the second is not. The sizes are set explicitly so that the test does not depend on the server defaults.

Result

The first statement is correct. The second, which is the same statement, is not:

tmp_memory_table_size = 16777216, no conversion

+-------+-------------+---------+

| cnt   | nonnull_pad | sum_lvl |

+-------+-------------+---------+

| 10101 |       10101 |   30201 |

+-------+-------------+---------+

tmp_memory_table_size = 16384, increment table converted

+-------+-------------+---------+

| cnt   | nonnull_pad | sum_lvl |

+-------+-------------+---------+

| 10001 |       10001 |   29901 |

+-------+-------------+---------+

The correct count is 1 + 100 + 10000. The deficit is exactly 100 rows and exactly 300 in the sum of lvl, that is one level-2 row and the 100 level-3 rows it would have produced. The value of nonnull_pad drops with cnt, so the substituted row is not merely reordered.

Analysis

select_union_recursive::send_data() writes the row it has just built, which lives in table->record[0], into the increment table. When that write overflows the in-memory table it asks for the increment table to be converted:

    if ((err= incr_table->file->ha_write_tmp_row(table->record[0])))

    {

      bool is_duplicate;

      rc= create_internal_tmp_table_from_heap(thd, incr_table,

                                              tmp_table_param.start_recinfo, 

                                              &tmp_table_param.recinfo,

                                              err, 1, &is_duplicate);

    }

The conversion copies every stored row into the new table and then appends the row that did not fit. It takes that row from the record[0] of the table it was given:

  /* copy row that filled HEAP table */

  if (unlikely((write_err=new_table.file->ha_write_tmp_row(table->record[0]))))

Here table is the function's own parameter, so this reads incr_table->record[0]. The row that overflowed is in the record[0] of a different table, the union result table, and nothing ever fills the increment table's own record[0]: TABLE::insert_all_rows_into_tmp_table() reads into the destination's record[0], and the recursive scan reads the recursive result table. That buffer therefore still holds the empty record the table was opened with.

Observed at a breakpoint on the conversion call, with the two buffers side by side:

incr_table->record[0]  ff 00 00 00 00 ...              empty record, null bits set

table->record[0]       f9 02 00 00 00 c8 00 78 78 78   lvl=2, pad='xxx...'

So the overflowing row is dropped and an all-NULL row is appended in its place. The increment table is created with no grouping and no distinct flag, so it carries no key and the substituted row is not rejected. On the next iteration that row has a NULL lvl, the recursion predicate lvl < 3 evaluates to NULL, and it produces no descendants.

Every other caller of the conversion leaves the overflowing row in the record[0] of the table being converted, which is why the defect is confined to the recursive CTE increment table.

Versions tested

Reproduced on a debug build of main at a1b3f980ddd. That build is unmodified upstream. Both code sites quoted above are present there in the form shown.

No lower bound was established. Older release series were not tested, so the version fields should be set from a check against them rather than from this report. Both sites are long standing, so earlier series are worth checking.