Skip to main content
Erschienen in: The VLDB Journal 5/2018

17.08.2017 | Special Issue Paper

Efficient generation of query plans containing group-by, join, and groupjoin

verfasst von: Marius Eich, Pit Fender, Guido Moerkotte

Erschienen in: The VLDB Journal | Ausgabe 5/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

It has been a recognized fact for many years that query execution can benefit from pushing grouping operators down in the operator tree and applying them before a join. This so-called eager aggregation reduces the size(s) of the join argument(s), making join evaluation faster. Lately, the idea enjoyed a revival when it was applied to outer joins for the first time and incorporated in a state-of-the-art plan generator. However, the recent approach is highly dependent on the use of heuristics because of the exponential growth of the search space that goes along with eager aggregation. Finding an optimal solution for larger queries calls for effective optimality-preserving pruning mechanisms to reduce the search space size as far as possible. By a more thorough investigation of functional dependencies and keys, we provide a set of new pruning criteria and extend the idea of eager aggregation further by combining it with the introduction of groupjoins. We evaluate the resulting plan generator with respect to runtime and memory consumption.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
By closure we mean the set of all dependencies derivable from a given set of dependencies, as the term is commonly understood.
 
Literatur
1.
Zurück zum Zitat von Bültzingsloewen, G.: Optimizing SQL queries for parallel execution. SIGMOD Rec. 18, 17–22 (1989)CrossRef von Bültzingsloewen, G.: Optimizing SQL queries for parallel execution. SIGMOD Rec. 18, 17–22 (1989)CrossRef
2.
Zurück zum Zitat Chaudhuri, S., Shim, K.: Including group-by in query optimization. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 94, pp. 354–366 (1994) Chaudhuri, S., Shim, K.: Including group-by in query optimization. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 94, pp. 354–366 (1994)
3.
Zurück zum Zitat Cluet, S., Moerkotte, G.: Efficient evaluation of aggregates on bulk types. In: International Workshop on Database Programming Languages (1995) Cluet, S., Moerkotte, G.: Efficient evaluation of aggregates on bulk types. In: International Workshop on Database Programming Languages (1995)
4.
Zurück zum Zitat Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)MATH Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)MATH
5.
Zurück zum Zitat Eich, M., Fender, P., Moerkotte, G.: Faster plan generation through consideration of functional dependencies and keys. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 9(10), pp. 756–767 (2016)CrossRef Eich, M., Fender, P., Moerkotte, G.: Faster plan generation through consideration of functional dependencies and keys. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 9(10), pp. 756–767 (2016)CrossRef
6.
Zurück zum Zitat Eich, M., Fender, P., Moerkotte, G.: Efficient generation of query plans containing group-by, join, and groupjoin. Technical report, University of Mannheim (2017) Eich, M., Fender, P., Moerkotte, G.: Efficient generation of query plans containing group-by, join, and groupjoin. Technical report, University of Mannheim (2017)
7.
Zurück zum Zitat Eich, M., Moerkotte, G.: Dynamic programming: The next step. Technical report, University of Mannheim (2014) Eich, M., Moerkotte, G.: Dynamic programming: The next step. Technical report, University of Mannheim (2014)
8.
Zurück zum Zitat Eich, M., Moerkotte, G.: Dynamic programming: the next step. In: Proceedings of IEEE Conference on Data Engineering, pp. 903–914 (2015) Eich, M., Moerkotte, G.: Dynamic programming: the next step. In: Proceedings of IEEE Conference on Data Engineering, pp. 903–914 (2015)
9.
Zurück zum Zitat Galindo-Legaria, C., Joshi, M.: Orthogonal optimization of subqueries and aggregation. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 571–581 (2001)CrossRef Galindo-Legaria, C., Joshi, M.: Orthogonal optimization of subqueries and aggregation. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 571–581 (2001)CrossRef
10.
Zurück zum Zitat Galindo-Legaria, C., Rosenthal, A.: Outerjoin simplification and reordering for query optimization. ACM Trans. Database Syst. 22(1), 43–74 (1997)CrossRef Galindo-Legaria, C., Rosenthal, A.: Outerjoin simplification and reordering for query optimization. ACM Trans. Database Syst. 22(1), 43–74 (1997)CrossRef
11.
Zurück zum Zitat Kemper, A., Neumann, T.: Hyper: A hybrid OLTP & OLAP main memory database system based on virtual memory snapshots. In: Proceedings of IEEE Conference on Data Engineering, pp. 195–206 (2011) Kemper, A., Neumann, T.: Hyper: A hybrid OLTP & OLAP main memory database system based on virtual memory snapshots. In: Proceedings of IEEE Conference on Data Engineering, pp. 195–206 (2011)
12.
Zurück zum Zitat Moerkotte, G., Fender, P., Eich, M.: On the correct and complete enumeration of the core search space. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 493–504 (2013) Moerkotte, G., Fender, P., Eich, M.: On the correct and complete enumeration of the core search space. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 493–504 (2013)
13.
Zurück zum Zitat Moerkotte, G., Neumann, T.: Dynamic programming strikes back. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 539–552 (2008) Moerkotte, G., Neumann, T.: Dynamic programming strikes back. In: Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 539–552 (2008)
14.
Zurück zum Zitat Moerkotte, G., Neumann, T.: Accelerating queries with group-by and join by groupjoin. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 4(11) (2011) Moerkotte, G., Neumann, T.: Accelerating queries with group-by and join by groupjoin. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 4(11) (2011)
15.
Zurück zum Zitat Paulley, G.: Exploiting functional dependence in query optimization. Ph.D. thesis, University of Waterloo (2000) Paulley, G.: Exploiting functional dependence in query optimization. Ph.D. thesis, University of Waterloo (2000)
16.
Zurück zum Zitat Yan, W.: Rewriting optimization of SQL queries containing group-by. Ph.D. thesis, University of Waterloo (1995) Yan, W.: Rewriting optimization of SQL queries containing group-by. Ph.D. thesis, University of Waterloo (1995)
17.
Zurück zum Zitat Yan, W., Larson, P.A.: Performing group-by before join. Technical Report CS 93-46, Dept. of Computer Science, University of Waterloo, Canada (1993) Yan, W., Larson, P.A.: Performing group-by before join. Technical Report CS 93-46, Dept. of Computer Science, University of Waterloo, Canada (1993)
18.
Zurück zum Zitat Yan, W., Larson, P.A.: Performing group-by before join. In: Proceedings of IEEE Conference on Data Engineering, pp. 89–100 (1994) Yan, W., Larson, P.A.: Performing group-by before join. In: Proceedings of IEEE Conference on Data Engineering, pp. 89–100 (1994)
19.
Zurück zum Zitat Yan, W., Larson, P.A.: Eager aggregation and lazy aggregation. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 95, pp. 345–357 (1995) Yan, W., Larson, P.A.: Eager aggregation and lazy aggregation. In: Proceedings of International Conference on Very Large Data Bases (VLDB), vol 95, pp. 345–357 (1995)
20.
Zurück zum Zitat Yan, W., Larson, P.A.: Interchanging the order of grouping and join. Technical Report CS 95-09, Dept. of Computer Science, University of Waterloo, Canada (1995) Yan, W., Larson, P.A.: Interchanging the order of grouping and join. Technical Report CS 95-09, Dept. of Computer Science, University of Waterloo, Canada (1995)
Metadaten
Titel
Efficient generation of query plans containing group-by, join, and groupjoin
verfasst von
Marius Eich
Pit Fender
Guido Moerkotte
Publikationsdatum
17.08.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 5/2018
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-017-0476-3

Weitere Artikel der Ausgabe 5/2018

The VLDB Journal 5/2018 Zur Ausgabe