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: 5426
Venue: SIGMOD
Year: 2017
Pagerank: 6.3886736e-05
Overall Rank: 4,160 | 71.09%
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,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
1,856	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010319105
2,022	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.7623022e-05
2,153	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	9.418541e-05
2,286	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.102574e-05
3,611	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.9178844e-05
4,227	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	6.3381409e-05
5,114	Columnstore and B+ tree – Are Hybrid Physical Designs Important?	2018	SIGMOD	5.6813929e-05
5,762	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	5.3367636e-05
6,789	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	4.9206048e-05
6,962	Replicated Layout for In-Memory Database Systems	2022	VLDB	4.8771234e-05
7,127	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	4.8184276e-05
7,837	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	4.6342964e-05
8,785	FishStore: Faster Ingestion with Subset Hashing	2019	SIGMOD	4.4467731e-05
9,787	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	4.2799988e-05
9,929	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	4.2470891e-05
10,105	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.1905499e-05
11,214	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	4.1905499e-05
11,653	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.1905499e-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.0040465394
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.001426258
20	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086163998
35	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00076209479
59	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.0006445664
104	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049475932
132	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00043697853
179	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00037637319
214	THE 5 MINUTE RULE FOR TRADING MEMORY FOR DISC ACCESSES and THE 10 BYTE RULE FOR TRADING MEMORY FOR CPU TIME	1987	SIGMOD	0.00033644457
237	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00031727601
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031314629
307	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00028226342
310	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.0002815547
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
367	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00025518228
382	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024888997
417	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023734582
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
515	QPipe: A Simultaneously Pipelined Relational Query Engine	2005	SIGMOD	0.00021209491
539	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00020615453
594	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00019515008
826	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00016161625
934	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015201246
959	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015034808
1,027	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.0001458537
1,100	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00014062265
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013751593
1,267	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012917585
1,296	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012742585
1,300	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012711153
1,473	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011786148
1,610	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011155922
1,622	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00011104582
1,726	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010734339
1,801	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00010485628
1,949	Positional Update Handling in Column Stores	2010	SIGMOD	9.9934641e-05
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
2,231	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.2367968e-05
2,372	Predictable Performance for Unpredictable Workloads	2009	VLDB	8.940791e-05
2,928	Shared Workload Optimization	2014	VLDB	7.881485e-05
3,402	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.134261e-05
3,760	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	6.7790524e-05
4,677	To Share or Not to Share?	2007	VLDB	5.9988869e-05
4,964	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	5.7974073e-05
5,341	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	5.5592799e-05
5,541	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4501856e-05
5,612	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.4104818e-05
8,387	A Storage Advisor for Hybrid-Store Databases	2012	VLDB	4.5255213e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,731	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8074069e-05
4,277	Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement	2015	VLDB	6.2878362e-05
7,462	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	4.7189301e-05
5,118	Design Tradeoffs of Data Access Methods	2016	SIGMOD	5.6781464e-05
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
790	Conjunctive Selection Conditions in Main Memory	2002	PODS	0.0001659522
5,612	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.4104818e-05
708	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00017753572
6,807	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.915939e-05