Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding

Summary: Lazy RID-list intersection forms lists on demand during conjunction, cutting IO/sort costs and reducing fragility to misestimates on skewed data. An adaptive set-intersection method replaces AND-tree, robust to cardinality errors; experiments show efficiency and predictability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3901e2fca1398074
Venue: SIGMOD
Year: 2007
Pagerank: 7.1896153e-05
Overall Rank: 3,584 | 75.91%
DOI: 10.1145/1247480.1247566

Incoming Non-self Citations Over Time

Authors

1. Vijayshankar Raman (IBM)
2. Lin Qiao (IBM)
3. Wei Han (IBM)
4. Inderpal S. Narang (IBM)
5. Ying-Lin Chen (IBM)
6. Kou-Horng Yang (IBM)
7. Fen-Lin Ling (IBM)

BibTeX Citation

@inproceedings{raman_sigmod07,
        title = {{Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding}},
        author = {Raman, Vijayshankar and Qiao, Lin and Han, Wei and Narang, Inderpal S. and Chen, Ying-Lin and Yang, Kou-Horng and Ling, Fen-Lin},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247566},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247566},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,769	Improving the Performance of List Intersection	2009	VLDB	9.6869284e-05
1,834	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.537823e-05
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
6,906	MILC: Inverted List Compression in Memory	2017	VLDB	5.6498626e-05
7,631	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD	5.4798152e-05
8,001	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.4092483e-05
9,201	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	5.2083769e-05
12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068998927
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
827	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013632674

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,780	QPPT: Query Processing on Prefix Trees	2013	CIDR
2	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
3	12,188	Document Reordering for Faster Intersection	2019	VLDB
4	13,047	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
5	10,885	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB
6	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
7	11,765	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
8	11,059	Index Intersection for High-Dimensional Range Queries	2026	VLDB
9	1,836	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
10	1,769	Improving the Performance of List Intersection	2009	VLDB