A scan is one of the fundamental operations in databases for retrieving tuples from tables, and research on access methods has been of importance to query optimization. However, our community is aware of the inconvenient truth that its performance may plummet amid steep increases in search costs when acting on MVCC databases since multi-versioning may forfeit all the benefits of using database indexes. An execution plan for a query on multi-versioned data often comprises a series of point lookup operations, of which each internally executes a linear traversal of record versions. Therefore, the generated plan is surprisingly worse than a full table (or version store) scan, mainly due to redundant access to database pages. To address such an all-or-nothing approach, we propose version weaver (vWeaver), a light-weight access method for record versions, that expedites a scan on record versions with each being augmented by just a few pointer fields. vWeaver incrementally constructs a version search structure over even an append-only version store (e.g., undo space) and allows a scan to traverse new version search structures for fast lookup. We applied vWeaver to in-memory and disk-based MVCC databases and demonstrated that the systems with vWeaver generally improved scan performance under various workloads with negligible space overhead.

Many systems use snapshot isolation, or something similar, as defaults, and multi-version concurrency control (MVCC) remains essential to offering such point-in-time consistency. One major issue in MVCC is the timely removal of unnecessary versions of data items, especially in the presence of long-lived transactions (LLTs). We have observed that the latest versions of MySQL and PostgreSQL are still vulnerable to LLTs. Our analysis of existing proposals suggests that new solutions to this matter must provide rigorous rules for completely identifying unnecessary versions, and elaborate designs for version cleaning lest old versions required for LLTs should suspend garbage collection. In this paper, we formalize such rules into our version pruning theorem and version classification, of which all form theoretical foundations for our new version management system, vDriver, that bases its record versioning on a new principle: Single In-row Remaining Off-row (SIRO) versioning. We implemented a prototype of vDriver and integrated it with MySQL-8.0 and PostgreSQL-12.0. The experimental evaluation demonstrated that the engines with Driver continue to perform the reclamation of dead versions in the face of LLTs while retaining transaction throughput with reduced space consumption.