Article

Optimizing queries using materialized views: a practical, scalable solution

Authors:

Jonathan Goldstein,

Per-Åke LarsonAuthors Info & Claims

SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of data

Pages 331 - 342

https://doi.org/10.1145/375663.375706

Published: 01 May 2001 Publication History

Get Access

Abstract

Materialized views can provide massive improvements in query processing time, especially for aggregation queries over large tables. To realize this potential, the query optimizer must know how and when to exploit materialized views. This paper presents a fast and scalable algorithm for determining whether part or all of a query can be computed from materialized views and describes how it can be incorporated in transformation-based optimizers. The current version handles views composed of selections, joins and a final group-by. Optimization remains fully cost based, that is, a single “best” rewrite is not selected by heuristic rules but multiple rewrites are generated and the optimizer chooses the best alternative in the normal way. Experimental results based on an implementation in Microsoft SQL Server show outstanding performance and scalability. Optimization time increases slowly with the number of views but remains low even up to a thousand.

References

[1]

S. Agrawal, S. Chaudhuri, V. R. Narasayya: Automated Selection of Materialized Views and Indexes in SQL Databases. VLDB 2000: 496-505

Digital Library

Google Scholar

[2]

R.G. Bello, K. Dias, J. Feenan, J. Finnerty, W.D. Norcott, H. Sun, A. Witkowski, M. Ziauddin, Materialized Views in Oracle, VLDB 1998, 659-664.

Digital Library

Google Scholar

[3]

J. Chang and S. Lee, Query Reformulation Using Materialized Views in Data Warehousing Environment, First ACM Int'l Workshop on Data Warehousing and OLAP (DOLAP), 1998, 54-59.

Digital Library

Google Scholar

[4]

S.Chaudhuri,S.Krishnamurthy,S.Potamianos,K.Shim,Optimizing Queries with Materialized Views, ICDE 1995, 190-200.

Digital Library

Google Scholar

[5]

S. Cohen, W. Nutt, A. Serebrenik, Rewriting Aggregate Queries Using Views, PODS, 1999, 155-166.

Digital Library

Google Scholar

[6]

G. Graefe, The Cascades Framework for Query Optimization, Data Engineering Bulletin, 18(3), 1995, 19-29.

Google Scholar

[7]

G. Graefe and W. J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, ICDE 1993, 209-218.

Digital Library

Google Scholar

[8]

S. Grumbach, M. Rafanelli, L. Tininini, Querying Aggregate Data, PODS 1999, 174-184.

Digital Library

Google Scholar

[9]

A. Gupta, V. Harinarayan, D. Quass, Aggregate Query Processing in Data WareHousing Environments, VLDB 1995, 358-369.

Digital Library

Google Scholar

[10]

P.-A. Larson and H. Z. Yang, Computing Queries from Derived Relations, VLDB 1985, 259-269.

Google Scholar

[11]

A.Levy,A.O.Mendelzon,Y.Sagiv,D.Srivastava,Answering Queries Using Views, PODS 1995, 95-104.

Digital Library

Google Scholar

[12]

W. Nutt, Y. Sagiv, S. Shurin, Deciding Equivalence Among Aggregate Queries, PODS 1998, 214-223.

Digital Library

Google Scholar

[13]

C.-S. Park, M. H. Kim and Y.-J. Lee, Rewriting OLAP Queries Using Materialized Views and Dimension Hierarchies in Data Warehouses, Korea Advanced Institute of Science and Technology, CS/TR-2000-156.

Google Scholar

[14]

R. Pottinger, A. Levy, A Scalable Algorithm for Answering Queries Using Views, VLDB 2000, 484-495.

Digital Library

Google Scholar

[15]

D.Srivastava,S.Dar,H.V.Jagadish,A.Levy,AnsweringQueries with Aggregation Using Views, VLDB 1996, 318-329.

Digital Library

Google Scholar

[16]

W. P. Yan and P. -A. Larson, Eager Aggregation and Lazy Aggregation, VLDB 1995, 345-357.

Digital Library

Google Scholar

[17]

H. Z. Yang and P. -A. Larson, Query Transformation for PSJ Queries, VLDB 1987, 245-254.

Digital Library

Google Scholar

[18]

M. Zaharioudakis, R. Cochrane, G. Lapis, H. Pirahesh, M. Urata, Answering Complex SQL Queries Using Automatic Summary Tables, SIG- MOD 2000, 105-116

Digital Library

Google Scholar

Cited By

View all

Zhang CFarouk T(2024)Sharing Queries with Nonequivalent User-defined Aggregate FunctionsACM Transactions on Database Systems10.1145/364913349:2(1-46)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3649133
Shah KGandhi AGandhi KBhise M(2024)Workload Prediction for Edge ComputingProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3632522(286-291)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3632522
Gurumurthy BBidarkar VBroneske DPionteck TSaake G(2024)Exploiting Shared Sub-Expression and Materialized View Reuse for Multi-Query OptimizationInformation Systems Frontiers10.1007/s10796-024-10506-wOnline publication date: 25-Jun-2024
https://doi.org/10.1007/s10796-024-10506-w
Show More Cited By

Index Terms

Optimizing queries using materialized views: a practical, scalable solution
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
  2. Information retrieval
    1. Information retrieval query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Optimizing queries using materialized views: a practical, scalable solution

Materialized views can provide massive improvements in query processing time, especially for aggregation queries over large tables. To realize this potential, the query optimizer must know how and when to exploit materialized views. This paper presents ...
Query evaluation using overlapping views: completeness and efficiency
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data

We study the problem of finding efficient equivalent view-based rewritings of relational queries, focusing on query optimization using materialized views under the assumption that base relations cannot contain duplicate tuples. A lot of work in the ...
Answering XML queries using materialized views revisited
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Answering queries using views is a well-established technique in databases. In this context, two outstanding problems can be formulated. The first one consists in deciding whether a query can be answered exclusively using one or multiple materialized ...

Reviews

Reviewer: Evgueni V Ogouretchnikov

Materialized views are a very new area in the world of relational database management systems (RDBMS). They can provide massive improvements in query processing time, especially for aggregation queries over large tables. However, using materialized views efficiently in query optimizers can be difficult. The solution described in this paper is implemented in a production RDBMS, and is supported by experimental results that show outstanding performance and scalability. As the authors state, the main contributions of this paper are an efficient view-matching algorithm for views composed of selections, joins, and a final group-by (SPJG views); and a novel index structure that quickly narrows the search to a small set of candidate views on which view-matching is applied. The version of the algorithm described here is limited to SPJG views, and produces single-view substitutes. Section 2 describes the class of materialized views supported, and defines the problem to be solved. Section 3 describes the algorithm for deciding if a query expression can be computed from a view. Section 4 introduces lattice index structure. Section 5 presents experimental results based on a prototype implementation. Related work is discussed in section 6. Section 7 contains a summary and a brief discussion of possible extensions. This paper is scientifically and practically valuable, and is appropriate for researches and skillful database developers. However, understanding the paper requires deep knowledge of structured query language (SQL) optimization issues. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of data

May 2001

630 pages

ISBN:1581133324

DOI:10.1145/375663

ACM SIGMOD Record Volume 30, Issue 2
June 2001
625 pages
ISSN:0163-5808
DOI:10.1145/376284
Editors:
Timos Sellis
National Technical Univ. of Athens
,
Sharad Mehrotra
Univ. of California at Irvine
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS01

Sponsor:

SIGMOD

SIGMOD/PODS01: ACM SIGMOD International Conference on Management of Data

May 21 - 24, 2001

California, Santa Barbara, USA

Acceptance Rates

SIGMOD '01 Paper Acceptance Rate 44 of 293 submissions, 15%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

207
Total Citations
View Citations
2,533
Total Downloads

Downloads (Last 12 months)69
Downloads (Last 6 weeks)14

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang CFarouk T(2024)Sharing Queries with Nonequivalent User-defined Aggregate FunctionsACM Transactions on Database Systems10.1145/364913349:2(1-46)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3649133
Shah KGandhi AGandhi KBhise M(2024)Workload Prediction for Edge ComputingProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3632522(286-291)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3632522
Gurumurthy BBidarkar VBroneske DPionteck TSaake G(2024)Exploiting Shared Sub-Expression and Materialized View Reuse for Multi-Query OptimizationInformation Systems Frontiers10.1007/s10796-024-10506-wOnline publication date: 25-Jun-2024
https://doi.org/10.1007/s10796-024-10506-w
Khamis MNgo HPichler RSuciu DRemy Wang Y(2022)Datalog in WonderlandACM SIGMOD Record10.1145/3552490.355249251:2(6-17)Online publication date: 29-Jul-2022
https://dl.acm.org/doi/10.1145/3552490.3552492
Wang YAbo Khamis MNgo HPichler RSuciu DIves ZBonifati AEl Abbadi A(2022)Optimizing Recursive Queries with Progam SynthesisProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517827(79-93)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517827
Litwin W(2022)Natural Stored and Inherited RelationsProcedia Computer Science10.1016/j.procs.2021.12.225198(171-178)Online publication date: 2022
https://doi.org/10.1016/j.procs.2021.12.225
Ghosh PGoto TMandal JSen S(2022)View materialization using fuzzy MAX–MIN composition with association rule mining (VMFCA)Innovations in Systems and Software Engineering10.1007/s11334-022-00484-0Online publication date: 5-Oct-2022
https://doi.org/10.1007/s11334-022-00484-0
Litwin W(2022)Stored and Inherited Relations with PKN Foreign KeysNew Trends in Database and Information Systems10.1007/978-3-031-15743-1_45(487-499)Online publication date: 29-Aug-2022
https://doi.org/10.1007/978-3-031-15743-1_45
Mhedhbi AGupta PKhaliq SSalihoglu S(2021)A+ Indexes: Tunable and Space-Efficient Adjacency Lists in Graph Database Management Systems2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00130(1464-1475)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00130
Xia QRen WLi MRen J(2020)Age-Aware Query Evaluation for Big Data Analytics in Mobile Edge Clouds2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC-SmartCity-DSS50907.2020.00027(214-222)Online publication date: Dec-2020
https://doi.org/10.1109/HPCC-SmartCity-DSS50907.2020.00027
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations