The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Efficient and extensible algorithms for multi query optimization
Abstract
Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expressions, either within a single query, or across multiple such queries run as a batch. Multiquery optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space. In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy, and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly. Our algorithms are designed to be easily added to existing optimizers. We present a performance study comparing the algorithms, using workloads consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Access path selection in a relational database management system
Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., & Price, T. G. (1979) · Proceedings of the 1979 ACM SIGMOD international conference on Management of data - SIGMOD '79 · doi:10.1145/582095.582099 · Cited by 2,188
Implementing data cubes efficiently
Harinarayan, V., Rajaraman, A., & Ullman, J. D. (1996) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/233269.233333 · Cited by 1,158
Sellis, T. K. (1988) · ACM Transactions on Database Systems · doi:10.1145/42201.42203 · Cited by 809
The Volcano optimizer generator: extensibility and efficient search
Graefe, G., & McKenna, W. J. (2002) · Proceedings of IEEE 9th International Conference on Data Engineering · doi:10.1109/icde.1993.344061 · Cited by 393
An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server
Chaudhuri, S., & Narasayya, V. R. (1997) · Cited by 355
Efficient and extensible algorithms for multi query optimization
Roy, P., Seshadri, S., Sudarshan, S., & Bhobe, S. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335419 · Cited by 231
Self-citationQuery optimization in the presence of limited access patterns
Florescu, D., Levy, A., Manolescu, I., & Suciu, D. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304210 · Cited by 164
Computing queries from derived relations
Larson, P.-Å., & Yang, H. Z. (1985) · Very Large Data Bases · Cited by 147
Query Transformation for PSJ-Queries
Yang, H. Z., & Larson, P.-Å. (1987) · Very Large Data Bases · Cited by 133
Chen, C. M., & Roussopoulos, N. (1994) · Lecture notes in computer science · doi:10.1007/3-540-57818-8_61 · Cited by 113
Cited by
VideoEdge: Processing Camera Streams using Hierarchical Clusters
Hung, C.-C., Ananthanarayanan, G., Bodik, P., Golubchik, L., Yu, M., Bahl, P., & Philipose, M. (2018) · 2018 IEEE/ACM Symposium on Edge Computing (SEC) · doi:10.1109/sec.2018.00016 · Cited by 287
C-SPARQL: A CONTINUOUS QUERY LANGUAGE FOR RDF DATA STREAMS
BARBIERI, D. F., BRAGA, D., CERI, S., VALLE, E. D., & GROSSNIKLAUS, M. (2010) · International Journal of Semantic Computing · doi:10.1142/s1793351x10000936 · Cited by 273
Metadata
- Authors
- Roy, P., Seshadri, S., Sudarshan, S., & Bhobe, S.
- Venue
- ACM SIGMOD Record
- Published
- 2000-05-16
- Volume
- 29
- Issue
- 2
- Pages
- 249-260
- ISSN
- 0163-5808 (ISSN-L)
- OpenAlex
- W2098416578
- Cited by
- 403
- References
- 11
- FWCI
- 23.75
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient and extensible algorithms for multi query optimization. https://app.cochat.ai/papers/10.1145/335191.335419
- The paper
- Roy, P., Seshadri, S., Sudarshan, S., & Bhobe, S. (2000). Efficient and extensible algorithms for multi query optimization. ACM SIGMOD Record. https://doi.org/10.1145/335191.335419
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
