cid 4de13d171514cc6f8dfd07646d6cb9dcaa23a328790bd840855c010c892acbe6 · original · via openalex
Title: Rethink the Scan in MVCC Databases Authors: Jongbin Kim; Kihwang Kim; Hyunsoo Cho; Jaeseon Yu; Sooyong Kang; Hyungsoo Jung Venue: ACM SIGMOD International Conference on Management of Data (SIGMOD) Year: 2021 Canonical: doi:10.1145/3448016.3452783 URL: https://doi.org/10.1145/3448016.3452783 Collector: openalex OA: false ABSTRACT 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.