HEAP: free-list contiguous block coalescing

Summary

The HEAP engine's delete free list is a singly-linked list of individual records. Each deleted record stores a uchar* pointer (8 bytes) to the next deleted record. All allocation and traversal is O(N) per record, even when records are physically contiguous in HP_BLOCK memory. The free list has no way to express contiguity, forcing record-by-record pointer chasing.

This affects:

• Single-record allocation (next_free_record_pos()): pops one record per call, one pointer dereference each
• Blob continuation chain allocation (hp_write_one_blob() Step 1): walks the entire free list checking pos == run_start - recbuffer to detect contiguity – O(free_list_length) per blob write
• Sequential scan (heap_scan()): steps through deleted records one by one, checking pos[visible] on each
• Table validation (heap_check_heap()): same one-by-one walk

For a table with 1M deleted contiguous records, this means up to 1M pointer dereferences for operations that could be answered with simple pointer arithmetic.

Solution: Contiguous Block Entries on the Free List

Transform the free list from a chain of individual records into a chain of contiguous blocks. Each block uses two records (first and last) to represent an arbitrarily large contiguous group. Middle records are "dark" – not on the free list, implicitly covered by the block's address range.

Record Layout

Deleted records already have a del_link pointer at bytes 0-7 and a flags byte at pos[visible] (zeroed for deleted records). Between them, bytes 8-10 are currently unused garbage (record data area of a deleted record). These are repurposed as block metadata:

• Byte 8 (del_flag): flag field with two bits defined:
  • Bit 0 (HP_DEL_BLOCK_END): this record is the last (highest address) of a contiguous free block
  • Bit 1 (HP_DEL_BLOCK_START): this record is the first (lowest address) of a contiguous free block
• Bytes 9-10 (del_count): uint16 record count, stored on block-start records only

Current deleted record layout (single record, unchanged for N=1):

+-----------------------+---------------+-------------+----- ... ------+---------+

| del_link              | del_flag      | garbage     | garbage        | flags   |

| (8 bytes, -> next)    | = 0           | (2 bytes)   |                | = 0     |

+-----------------------+---------------+-------------+----- ... ------+---------+

  byte 0                7               8             10               visible

Block-start record (first record of a contiguous block, rec[0]):

+-----------------------+---------------+-------------+----- ... ------+---------+

| del_link              | del_flag      | del_count   | garbage        | flags   |

| (8 bytes, -> next)    | = 0x02        | (uint16, N) |                | = 0     |

+-----------------------+---------------+-------------+----- ... ------+---------+

  byte 0                7 BLOCK_START   8             10               visible

Block-end record (last record of a contiguous block, rec[N-1]):

+-----------------------+---------------+-------------+----- ... ------+---------+

| del_link              | del_flag      | garbage     | garbage        | flags   |

| (8 bytes, -> rec[0])  | = 0x01        | (2 bytes)   |                | = 0     |

+-----------------------+---------------+-------------+----- ... ------+---------+

  byte 0                7 BLOCK_END     8             10               visible

Dark record (middle record, rec[1..N-2]) – metadata bytes zeroed:

+-----------------------+---------------+-------------+----- ... ------+---------+

| NULL                  | del_flag      | (untouched) | (untouched)    | flags   |

| (8 bytes, zeroed)     | = 0           |             |                | = 0     |

+-----------------------+---------------+-------------+----- ... ------+---------+

  byte 0  poisoned      7               8             10               visible

Block Structure

Free-list chain for a contiguous block of N deleted records:

share->del_link

      |

      v

  rec[N-1]  ----del_link----->  rec[0]  ----del_link----->  (next free-list entry)

  (BLOCK_END)                   (BLOCK_START, count=N)

  rec[1] .. rec[N-2] are "dark" -- not on the free list,

  metadata bytes zeroed (del_link, del_flag, visible)

For single records (N=1): del_flag = 0, current behavior unchanged.

Two Traversal Directions

Free-list direction (descending addresses – allocation and blob write):

Hit rec[N-1] (block-end), read pointer to rec[0], compute block size via pointer arithmetic or read the count from rec[0] bytes 9-10. Follow rec[0]'s del_link to the next entry. Two pointer reads per block instead of N.

Scan direction (ascending addresses – heap_scan(), heap_check_heap()):

Hit rec[0] (block-start), read count from bytes 9-10, batch-skip the entire block. Same pattern as the existing blob continuation run batch-skip.

Dark Records

Records rec[1] through rec[N-2] are "dark" – not individually chained on the free list. Dark records are cleared by the hp_clear_dark_records() helper, which walks at stride recbuffer and zeroes only the essential bytes per record: del_link (NULL), del_flag (0), and pos[visible] (0). This is cheaper than a contiguous bzero() when recbuffer is large (for short record lengths a contiguous bzero would be faster, but the crossover point has not been measured). The zeroing provides:

• Immediate SIGSEGV on accidental pointer dereference (NULL)
• Rapid corruption detection: any non-zero value in bytes 0-10 of a dark record indicates memory corruption
• Safety net in case the scan encounters a dark record (e.g., due to a bug): it sees pos[visible] == 0 and skips

visible Minimum Bumped to 11

Block metadata uses 11 bytes: 8 (del_link) + 1 (del_flag) + 2 (del_count). The visible minimum is bumped from sizeof(char*) (8) to 11. This has zero memory impact: recbuffer = ALIGN(visible + 1, 8). For reclength 1 through 10, recbuffer is 16 both before and after the bump. The 8-byte alignment absorbs the shift.

reclength  visible_old  recbuf_old  visible_new  recbuf_new

1-8        8            16          11           16          (no change)

9          9            16          11           16          (no change)

10         10           16          11           16          (no change)

11         11           16          11           16          (no change)

12+        reclength     unchanged   reclength    unchanged   (no change)

No conditional guards or fallback paths needed. Every table gets block coalescing unconditionally. The existing blob-specific bump (MY_MAX(visible_offset, HP_CONT_HEADER_SIZE + 1)) becomes redundant.

API

All encapsulated as static inline functions in heapdef.h.

Dark Record Clearing

• hp_clear_dark_records(from, to, recbuffer, visible) – strided loop that clears dark records from address from (inclusive) to to (exclusive) at stride recbuffer. Zeroes del_link (NULL), del_flag (0), and pos[visible] (0) per record. Used by hp_push_free_block() and hp_push_free_block_coalesce() for all dark record clearing.

Push Side (freeing records)

• hp_push_free_record(share, pos) – push a single record onto the free list. Sets del_link, del_flag = 0, pos[visible] = 0, adjusts counters. Used by heap_write() error path and as the count==1 fallback for hp_push_free_block_coalesce().
• hp_push_free_block(share, first, count) – push a contiguous block (count >= 2). Sets up block-start, block-end, clears dark records via hp_clear_dark_records(). Used as the count >= 2 fallback for hp_push_free_block_coalesce().
• hp_push_free_block_coalesce(share, first, count) – unified coalescing function for both single records (count=1) and contiguous blocks (count >= 2). Normalizes the free-list head to (head_first, head_count) regardless of whether it is a block or single record, then checks adjacency in two directions (above/below). Coalesces with the head if adjacent; falls back to hp_push_free_record() (count==1) or hp_push_free_block() (count >= 2) when no adjacency. Combined count capped at UINT_MAX16.
• hp_push_free_record_coalesce(share, pos) – thin wrapper: delegates to hp_push_free_block_coalesce(share, pos, 1). Used by heap_delete() and hp_free_run_chain() for single-record runs.

Traverse Side (read-only)

Free-list direction:

• hp_is_free_block_end(pos) – check del_flag & HP_DEL_BLOCK_END
• hp_free_block_first(pos) – read pointer to first record of block (from block-end's del_link)

Scan direction:

• hp_is_free_block_start(pos) – check del_flag & HP_DEL_BLOCK_START
• hp_free_block_start_count(pos) – read uint16 count from bytes 9-10

Consume Side (taking records from the free list)

• hp_pop_free_record(share) – pop one record from the free-list head. If the head is a single record, pops it directly. If the head is a block-end, delegates to hp_take_free_block(share, 1).
• hp_take_free_block(share, count) – take N records from the head block (partial or entire). Returns records from the high end of the block: taken_start = first + remaining * recbuffer. Three cases:
  • Block consumed entirely (remaining == 0): del_link advances to next entry via rec[0]'s pointer
  • Block collapses to 1 (remaining == 1, new_last == first): del_link = first. Critical: do NOT write first[0..7] – it already holds the chain to the next entry
  • Block shrinks (remaining >= 2): promote dark record to new block-end. Write new_last[0..7] = first, new_last[8] = HP_DEL_BLOCK_END, del_link = new_last. Update rec[0] count.

Allocation order note: single-record pops from coalesced blocks return records in address-descending order (highest position first), not in the original LIFO delete order. Without coalescing, individual free-list entries preserve LIFO (last deleted = first allocated). Coalescing merges adjacent entries into address-ordered blocks, losing the temporal delete ordering. This can change the physical position assignment for newly allocated records, which may change the scan presentation order for unordered queries using HEAP temp tables (e.g., compound EXCEPT ALL / UNION ALL queries that use unfold_record() to expand counter-based duplicates back into physical rows).

Affected Code Paths

Push paths

• heap_delete() (hp_delete.c) – single record delete: hp_push_free_record_coalesce() (delegates to hp_push_free_block_coalesce(share, pos, 1), coalesces with free-list head if adjacent)
• heap_write() error path (hp_write.c) – failed insert rollback: hp_push_free_record() (no coalescing needed for error rollback)
• hp_free_run_chain() (hp_blob.c) – blob continuation chain free: hp_push_free_block_coalesce() per multi-record run, hp_push_free_record_coalesce() for single-record runs. Adjacent runs and the primary record coalesce into one block.

Consume paths

• next_free_record_pos() (hp_write.c) – single record allocation: hp_pop_free_record()
• hp_take_free_list_runs() (hp_blob.c) – shared helper for Steps 1 and 3 of hp_write_one_blob(), parameterized by min_avail. Dispatches to hp_take_free_block() for blocks, hp_pop_free_record() for singles. Eliminates the O(N) contiguity detection walk entirely.

Scan paths (batch-skip deleted blocks)

• heap_scan() (hp_scan.c) – on deleted record, check hp_is_free_block_start(), read count, batch-skip entire block. Same pattern as continuation run batch-skip.
• heap_check_heap() (_check.c) – block-aware free-list count and scan; validates block-start/end flags, dark record zeroing (debug), bounds on block count vs total_records + deleted

Other affected paths

• hp_shrink_tail() (hp_blob.c) – reclaims entire blocks at the tail in one step when the free-list head is a block-end at the tail boundary

Delete Neighbor Coalescing

When heap_delete() frees a record, hp_push_free_record_coalesce() checks if the free-list head is one recbuffer away. If adjacent, it coalesces instead of pushing a separate single. All cases are O(1): one pointer comparison + a few byte writes.

All coalescing logic is unified in hp_push_free_block_coalesce(), which accepts count >= 1. hp_push_free_record_coalesce() is a thin wrapper that calls hp_push_free_block_coalesce(share, pos, 1). The function normalizes the free-list head by treating a single record as a block of count 1, reducing the logic to two directional branches (above/below) that handle all merge cases uniformly. Dark-record clearing ranges become empty no-ops where no dark records exist.

Cases

The function first normalizes the head: if the head is a block-end, read its head_first and head_count; if a single record, set head_first = head, head_count = 1. Then:

• Head immediately below new block (head == first - recbuffer): extend upward. Clear dark records from head_first + recbuffer to last (exclusive). New block-end at last, block-start at head_first, combined count.
• Head immediately above new block (head_first == last + recbuffer): extend downward. Read next_entry from head_first, clear dark records from first + recbuffer to head (exclusive). New block-start at first with next_entry chain, block-end at head, combined count.
• Combined count > UINT_MAX16: fall back to non-coalescing push
• No adjacency: fall back to hp_push_free_record() (count==1) or hp_push_free_block() (count >= 2)

Cross-Leaf False Adjacency

Not a concern. Each HP_BLOCK leaf is a separate my_malloc() allocation with at least 16 bytes of chunk header between consecutive allocations. The minimum gap between any two records in different leaves is recbuffer + header_overhead > recbuffer, so the pointer comparison pos == head +/- recbuffer can never falsely match across leaves.

UINT_MAX16 Limit

The block count field is uint16, capping individual blocks at 65535 records. Tables routinely have more records (e.g. 131K for default 16MB max_heap_table_size with recbuffer=16). When a block reaches the cap, the next adjacent free creates a new entry on the free list: multi-record runs from hp_free_run_chain push as a separate block, single-record deletes push a single that immediately coalesces with the next adjacent delete to start a new block. For 1M sequential deletes the free list contains ~16 blocks of 65535, each batch-skippable by scan and usable by the blob allocator.

Benefit

Sequential range deletes (e.g. DELETE FROM t WHERE id BETWEEN 100 AND 10000) cascade perfectly: each successive delete extends the block by one record. This turns what was N separate singles on the free list into a single block, benefiting both subsequent blob allocation (direct block take instead of scanning singles) and heap_scan() (batch-skip the entire block).

Test Result Update: main.except_all

The delete coalescing changes the free-list allocation order from temporal (LIFO) to spatial (address-descending) for adjacent deleted records within a coalesced block. This affects the compound query:

select * from t1 except all select * from t1

  union all select * from t1

  union all select * from t1

  except all select * from t2;

MariaDB's EXCEPT ALL implementation uses a counter-based algorithm: the temp table stores each distinct value once with a duplicate_cnt field. At the end (send_eof), unfold_record() expands counters back into physical rows by inserting copies via heap_write(). When the temp table has deleted entries from an earlier EXCEPT ALL step, the new rows are allocated from the free list.

The coalescing changes which physical position each value gets during the UNION ALL reinsert step (after t1 EXCEPT ALL t1 empties the temp table). This changes the interleaving of unfolded copies of different values in the final scan, producing a different (but equally valid) row order for the unordered query. Two rows (2,2 and 4,4) swap positions in the output.

The test result file is updated to match the new allocation order. The result set is identical; only the presentation order of an unordered query changed.