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: he655a7282463a40f
Venue: SIGMOD
Year: 2017
Pagerank: 7.1528863e-05
Overall Rank: 3,606 | 75.83%
DOI: 10.1145/3035918.3064049

Incoming Non-self Citations Over Time

Authors

1. Michael S. Kester (Harvard University)
2. Manos Athanassoulis (Harvard University)
3. Stratos Idreos (Harvard University)

BibTeX Citation

@inproceedings{kester_sigmod17,
        title = {{Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?}},
        author = {Kester, Michael S. and Athanassoulis, Manos and Idreos, Stratos},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064049},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064049},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011759683
1,282	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00011197535
1,400	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	0.00010759064
1,611	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010066379
1,722	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.781628e-05
2,965	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.7894987e-05
3,489	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2421958e-05
4,701	Columnstore and B+ tree – Are Hybrid Physical Designs Important?	2018	SIGMOD	6.44638e-05
5,632	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0402517e-05
6,690	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.6917141e-05
6,730	Replicated Layout for In-Memory Database Systems	2022	VLDB	5.6801409e-05
6,977	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	5.6135617e-05
7,505	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.4920201e-05
8,983	FishStore: Faster Ingestion with Subset Hashing	2019	SIGMOD	5.2317424e-05
9,335	Rethink Query Optimization in HTAP Databases	2023	SIGMOD	5.1791475e-05
10,017	The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format	2024	SIGMOD	5.0825892e-05
10,664	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9605343e-05
10,903	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9605343e-05
11,777	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	4.9605343e-05
12,192	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.9605343e-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.0023948467
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081781676
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068985264
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00063972112
21	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00056737487
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039323387
68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037861537
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00030314403
151	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028611216
161	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027629724
177	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026571747
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024554257
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024446892
218	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024342426
259	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022881075
280	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022267903
289	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021955394
342	THE 5 MINUTE RULE FOR TRADING MEMORY FOR DISC ACCESSES and THE 10 BYTE RULE FOR TRADING MEMORY FOR CPU TIME	1987	SIGMOD	0.00020487166
390	QPipe: A Simultaneously Pipelined Relational Query Engine	2005	SIGMOD	0.00019232929
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018411252
436	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018274105
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015430074
670	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014929358
707	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00014613324
768	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.00014096379
871	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013313281
912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013092547
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012798312
1,039	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012349128
1,043	The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses	2010	SIGMOD	0.00012325755
1,044	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.0001232071
1,119	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011927356
1,340	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010962559
1,383	H2O: A Hands-free Adaptive Store	2014	SIGMOD	0.00010826996
1,461	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010557729
1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010312002
1,637	Positional Update Handling in Column Stores	2010	SIGMOD	9.9898497e-05
1,696	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.8272691e-05
1,926	Predictable Performance for Unpredictable Workloads	2009	VLDB	9.3500398e-05
2,237	Shared Workload Optimization	2014	VLDB	8.7777395e-05
2,888	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.8895201e-05
3,383	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	7.3393628e-05
4,411	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	6.5996653e-05
4,594	To Share or Not to Share?	2007	VLDB	6.4994689e-05
4,789	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4016324e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
5,839	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	5.957817e-05
8,630	A Storage Advisor for Hybrid-Store Databases	2012	VLDB	5.2843511e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,094	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB
2	4,036	Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement	2015	VLDB
3	7,509	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
4	4,897	Design Tradeoffs of Data Access Methods	2016	SIGMOD
5	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
6	27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB
7	766	Conjunctive Selection Conditions in Main Memory	2002	PODS
8	5,839	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB
9	635	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB
10	6,803	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD