Optimization algorithms for simultaneous multidimensional queries in OLAP environments

Panos Kalnis; Dimitris Papadias

doi:10.1007/3-540-44801-2_26

Optimization algorithms for simultaneous multidimensional queries in OLAP environments

Panos Kalnis, Dimitris Papadias

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

Multi-Dimensional Expressions (MDX) provide an interface for asking several related OLAP queries simultaneously. An interesting problem is how to optimize the execution of an MDX query, given that most data warehouses maintain a set of redundant materialized views to accelerate OLAP operations. A number of greedy and approximation algorithms have been proposed for different versions of the problem. In this paper we evaluate experimentally their performance using the APB and TPC-H benchmarks, concluding that they do not scale well for realistic workloads. Motivated by this fact, we developed two novel greedy algorithms. Our algorithms construct the execution plan in a top-down manner by identifying in each step the most beneficial view, instead of finding the most promising query. We show by extensive experimentation that our methods outperform the existing ones in most cases.

Original language	English (US)
Title of host publication	Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings
Editors	Werner Winiwarter, Yahiko Kambayashi, Masatoshi Arikawa
Publisher	Springer Verlag
Pages	264-273
Number of pages	10
ISBN (Print)	3540425535, 9783540425533
DOIs	https://doi.org/10.1007/3-540-44801-2_26
State	Published - 2001
Externally published	Yes
Event	3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001 - Munich, Germany Duration: Sep 5 2001 → Sep 7 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2114
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001
Country/Territory	Germany
City	Munich
Period	09/5/01 → 09/7/01

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44801-2_26

Cite this

Kalnis, P., & Papadias, D. (2001). Optimization algorithms for simultaneous multidimensional queries in OLAP environments. In W. Winiwarter, Y. Kambayashi, & M. Arikawa (Eds.), Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings (pp. 264-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2114). Springer Verlag. https://doi.org/10.1007/3-540-44801-2_26

Kalnis, Panos ; Papadias, Dimitris. / Optimization algorithms for simultaneous multidimensional queries in OLAP environments. Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings. editor / Werner Winiwarter ; Yahiko Kambayashi ; Masatoshi Arikawa. Springer Verlag, 2001. pp. 264-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f6c61efdb32b4c1091d0f8c6cf16ebb1,

title = "Optimization algorithms for simultaneous multidimensional queries in OLAP environments",

abstract = "Multi-Dimensional Expressions (MDX) provide an interface for asking several related OLAP queries simultaneously. An interesting problem is how to optimize the execution of an MDX query, given that most data warehouses maintain a set of redundant materialized views to accelerate OLAP operations. A number of greedy and approximation algorithms have been proposed for different versions of the problem. In this paper we evaluate experimentally their performance using the APB and TPC-H benchmarks, concluding that they do not scale well for realistic workloads. Motivated by this fact, we developed two novel greedy algorithms. Our algorithms construct the execution plan in a top-down manner by identifying in each step the most beneficial view, instead of finding the most promising query. We show by extensive experimentation that our methods outperform the existing ones in most cases.",

author = "Panos Kalnis and Dimitris Papadias",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001 ; Conference date: 05-09-2001 Through 07-09-2001",

year = "2001",

doi = "10.1007/3-540-44801-2_26",

language = "English (US)",

isbn = "3540425535",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "264--273",

editor = "Werner Winiwarter and Yahiko Kambayashi and Masatoshi Arikawa",

booktitle = "Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings",

address = "Germany",

}

Kalnis, P & Papadias, D 2001, Optimization algorithms for simultaneous multidimensional queries in OLAP environments. in W Winiwarter, Y Kambayashi & M Arikawa (eds), Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2114, Springer Verlag, pp. 264-273, 3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001, Munich, Germany, 09/5/01. https://doi.org/10.1007/3-540-44801-2_26

Optimization algorithms for simultaneous multidimensional queries in OLAP environments. / Kalnis, Panos; Papadias, Dimitris.
Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings. ed. / Werner Winiwarter; Yahiko Kambayashi; Masatoshi Arikawa. Springer Verlag, 2001. p. 264-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2114).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimization algorithms for simultaneous multidimensional queries in OLAP environments

AU - Kalnis, Panos

AU - Papadias, Dimitris

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - Multi-Dimensional Expressions (MDX) provide an interface for asking several related OLAP queries simultaneously. An interesting problem is how to optimize the execution of an MDX query, given that most data warehouses maintain a set of redundant materialized views to accelerate OLAP operations. A number of greedy and approximation algorithms have been proposed for different versions of the problem. In this paper we evaluate experimentally their performance using the APB and TPC-H benchmarks, concluding that they do not scale well for realistic workloads. Motivated by this fact, we developed two novel greedy algorithms. Our algorithms construct the execution plan in a top-down manner by identifying in each step the most beneficial view, instead of finding the most promising query. We show by extensive experimentation that our methods outperform the existing ones in most cases.

AB - Multi-Dimensional Expressions (MDX) provide an interface for asking several related OLAP queries simultaneously. An interesting problem is how to optimize the execution of an MDX query, given that most data warehouses maintain a set of redundant materialized views to accelerate OLAP operations. A number of greedy and approximation algorithms have been proposed for different versions of the problem. In this paper we evaluate experimentally their performance using the APB and TPC-H benchmarks, concluding that they do not scale well for realistic workloads. Motivated by this fact, we developed two novel greedy algorithms. Our algorithms construct the execution plan in a top-down manner by identifying in each step the most beneficial view, instead of finding the most promising query. We show by extensive experimentation that our methods outperform the existing ones in most cases.

UR - http://www.scopus.com/inward/record.url?scp=33645424858&partnerID=8YFLogxK

U2 - 10.1007/3-540-44801-2_26

DO - 10.1007/3-540-44801-2_26

M3 - Conference contribution

AN - SCOPUS:33645424858

SN - 3540425535

SN - 9783540425533

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 264

EP - 273

BT - Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings

A2 - Winiwarter, Werner

A2 - Kambayashi, Yahiko

A2 - Arikawa, Masatoshi

PB - Springer Verlag

T2 - 3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001

Y2 - 5 September 2001 through 7 September 2001

ER -

Kalnis P, Papadias D. Optimization algorithms for simultaneous multidimensional queries in OLAP environments. In Winiwarter W, Kambayashi Y, Arikawa M, editors, Data Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings. Springer Verlag. 2001. p. 264-273. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44801-2_26

Optimization algorithms for simultaneous multidimensional queries in OLAP environments

Abstract

Publication series

Other

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this