Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?

Summary: Compares scans and secondary index scans in main-memory columnar analytics using modeling and experiments. Shows both paths still useful; introduces a lightweight APS model that factors selectivity, concurrency, hardware, and system design for fast, integrated access-path choice. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5425
Venue: SIGMOD
Year: 2017
Pagerank: 6.3938006e-05
Overall Rank: 4,161 | 71.06%
DOI: 10.1145/3035918.3064049

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
1,855	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010315245
2,020	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.762624e-05
2,157	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	9.416022e-05
2,280	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.1111033e-05
3,608	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.924272e-05
4,227	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	6.3434324e-05
5,113	Columnstore and B+ tree – Are Hybrid Physical Designs Important?	2018	SIGMOD	5.687445e-05
5,749	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	5.3418923e-05
6,788	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	4.9252064e-05
6,984	Replicated Layout for In-Memory Database Systems	2022	VLDB	4.873081e-05
7,128	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	4.8230171e-05
7,831	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	4.6387445e-05
8,788	FishStore: Faster Ingestion with Subset Hashing	2019	SIGMOD	4.451039e-05
9,806	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	4.2805224e-05
9,937	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	4.2482599e-05
10,105	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.1945683e-05
11,212	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	4.1945683e-05
11,648	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 48 of 48 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.0014279444
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
35	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00076197749
60	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00064439773
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
131	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0004370331
179	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00037672155
213	THE 5 MINUTE RULE FOR TRADING MEMORY FOR DISC ACCESSES and THE 10 BYTE RULE FOR TRADING MEMORY FOR CPU TIME	1987	SIGMOD	0.00033660051
237	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00031726304
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031420034
305	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00028248614
310	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00028132402
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026768139
368	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.000254931
381	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024873637
418	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023729211
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
515	QPipe: A Simultaneously Pipelined Relational Query Engine	2005	SIGMOD	0.00021214633
542	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00020595648
596	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00019481482
830	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00016171897
940	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015173166
958	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015045316
1,026	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.00014589172
1,101	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00014070632
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
1,270	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012926086
1,299	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012751522
1,312	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012652548
1,477	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011770865
1,607	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011162682
1,618	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00011114015
1,731	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.0001073454
1,807	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00010487796
1,949	Positional Update Handling in Column Stores	2010	SIGMOD	9.9864085e-05
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
2,229	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.2350274e-05
2,372	Predictable Performance for Unpredictable Workloads	2009	VLDB	8.947963e-05
2,925	Shared Workload Optimization	2014	VLDB	7.888494e-05
3,408	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.1288167e-05
3,777	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	6.7750901e-05
4,680	To Share or Not to Share?	2007	VLDB	6.0039406e-05
4,959	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	5.8029448e-05
5,346	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	5.5561846e-05
5,532	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4548897e-05
5,604	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.4147933e-05
8,389	A Storage Advisor for Hybrid-Store Databases	2012	VLDB	4.5296588e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,737	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8033227e-05
4,282	Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement	2015	VLDB	6.293052e-05
7,465	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	4.7228742e-05
5,119	Design Tradeoffs of Data Access Methods	2016	SIGMOD	5.6807904e-05
6,374	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0927058e-05
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
795	Conjunctive Selection Conditions in Main Memory	2002	PODS	0.00016600368
5,604	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.4147933e-05
710	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00017765454
6,809	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.9206606e-05