InnoDB undo records scanning O(log n) complexity

[midenok]

Implementation: undo index and binary search

• Create undo index: undo index is associated with history of particular record; DB_ROLL_PTR points to index entry, index entry points to actual record (original DB_ROLL_PTR value). It must be possible to figure out first index entry (and header) from DB_ROLL_PTR of any record.
• Undo index header indicates allocated size, used size. Should undo index be reallocated or it should be of max history size at once (no need in allocated size in this case)?
• Decide where to place undo index (in undo segment, undo log?). Undo index is associated with first undo record, created when first undo record is created and freed when record is purged (or when undo segment/log is freed?).
• Fix any of API working with DB_ROLL_PTR to respect undo index. DATA_ROLL_PTR code invasion: 22.
• Replace linear seach with binary search in row_vers_build_for_consistent_read(). Search criteria: view->changes_visible(i) && !view->changes_visible(i-1), where i is index from undo index.

Local undo index as alternative

Scan undo records in row_vers_build_for_consistent_read() without trx_undo_prev_version_build(), build temporary undo index. Then do binary search. This avoids copying of whole records in linear scan.

This is much easier to implement than permanent undo index and it can be used as first stage of development.

References

• The basics of the InnoDB undo logging and history system
• The physical structure of records in InnoDB
• Data Organization in InnoDB
• InnoDB Redundant Row Format
• InnoDB Structures Diagrams