Row order for tied ORDER BY keys in a MEMORY table changes between server restarts

A query over a MEMORY table whose ORDER BY leaves rows tied returns those rows in a different order after the server is restarted, with no change to the data or to the query. The rows themselves are correct; only their order moves.

How to repeat

CREATE TABLE m1 (a INT, b VARCHAR(8)) ENGINE=MEMORY;

INSERT INTO m1 SELECT 1, LPAD(seq,8,'0') FROM seq_1_to_500;

SET max_length_for_sort_data=4;

SET sort_buffer_size=1024;

SELECT b FROM m1 ORDER BY a LIMIT 6 OFFSET 200;

DROP TABLE m1;

Column a holds the same value in every row, so every row is tied on the ORDER BY and the window that LIMIT selects is decided entirely by how the sort breaks that tie.

Observed

Twenty runs of that script produced four different answers:

00000387,00000419,00000451,00000483,00000016,00000048

00000427,00000459,00000491,00000024,00000056,00000088

00000433,00000465,00000497,00000030,00000062,00000094

00000435,00000467,00000499,00000032,00000064,00000096

Repeating the SELECT inside one server process gives the same answer every time. The answer changes when the server is restarted.

Mechanism

ha_heap::position() publishes the record's address in memory as the rowid:

void ha_heap::position(const uchar *record)

{

  *(HEAP_PTR*) ref= heap_position(file);	// Ref is aligned

}

Sort_param::setup_lengths_and_limit() appends that rowid to the sort key, so that rows can be read back in rowid order:

    res_length= ref_length;

    /*

      The reference (rowid) to the record is considered as an additional

      sorted field as we want to access rows in rowid order if possible.

    */

    sort_length+= ref_length;

Sort keys are compared with memcmp, so tied rows come out ordered by the bytes of an address, least significant byte first on a little-endian machine. Each of the four answers above is the same arithmetic progression, stride 32, shifted by a constant, and the constant is wherever the allocator placed the engine's block in that server process.

For an engine whose rowid is a file position this ordering is stable, and it is the physical read order that the comment describes. For MEMORY it is neither stable nor a read order.

Scope

Lowering max_length_for_sort_data in the reproducer only makes the trigger reliable. filesort appends the rowid to the sort key whenever it decides against addon fields, which it does for any query whose sorted record is wider than max_length_for_sort_data, so a wide enough row reaches the same path at the default setting.

Affected versions

Both statements quoted above are present unchanged in 10.5, 10.6, 10.11, 11.4, 11.8, 12.0, 12.1, 12.2, 12.3, 13.0 and main, 11 of 11 branches checked. The runs above are on a build of main at b2a8c2234dbc276fe3947633c9ffea454badf48f.