Skip to main content
Erschienen in:

01.11.2015 | SCHWERPUNKTBEITRAG

Placement-Safe Operator-Graph Changes in Distributed Heterogeneous Data Stream Systems

verfasst von: Niko Pollner, Christian Steudtner, Klaus Meyer-Wegener

Erschienen in: Datenbank-Spektrum | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

Data stream processing systems enable querying continuous data without first storing it. Data stream queries may combine data from distributed data sources like different sensors in an environmental sensing application. This suggests distributed query processing. Thus the amount of transferred data can be reduced and more processing resources are available.
However, distributed query processing on probably heterogeneous platforms complicates query optimization. This article investigates query optimization through operator graph changes and its interaction with operator placement on heterogeneous distributed systems. Pre-placement operator graph changes may prevent certain operator placements. Thereby the resource consumption of the query execution may unexpectedly increase. Based on the operator placement problem modeled as a task assignment problem (TAP), we prove that it is NP-hard to decide in general whether an arbitrary operator graph change may negatively influence the best possible TAP solution. We present conditions for several specific operator graph changes that guarantee to preserve the best possible TAP solution.

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 "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!

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!

Weitere Produktempfehlungen anzeigen
Literatur
1.
Zurück zum Zitat Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems, Revised Reprint. Siam Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems, Revised Reprint. Siam
2.
Zurück zum Zitat Daum M (2011) Verteilung globaler Anfragen auf heterogene Stromverarbeitungssysteme. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) Daum M (2011) Verteilung globaler Anfragen auf heterogene Stromverarbeitungssysteme. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
3.
Zurück zum Zitat Daum M, Lauterwald F, Baumgärtel P, Meyer-Wegener K (2010) Propagation of Densities of Streaming Data within Query Graphs. In: Proceedings of 22nd International Conference on Scientific and Statistical Database Management (SSDBM), Lecture Notes in Computer Science, vol. 6187. Springer-Verlag, Heidelberg, pp. 584–601 Daum M, Lauterwald F, Baumgärtel P, Meyer-Wegener K (2010) Propagation of Densities of Streaming Data within Query Graphs. In: Proceedings of 22nd International Conference on Scientific and Statistical Database Management (SSDBM), Lecture Notes in Computer Science, vol. 6187. Springer-Verlag, Heidelberg, pp. 584–601
4.
Zurück zum Zitat Daum M, Lauterwald F, Baumgärtel P, Pollner N, Meyer-Wegener K (2011) Black-box Determination of Cost Models` Parameters for Federated Stream-Processing Systems. In: Proceedings of the 15th International Database Engineering & Applications Symposium (IDEAS). Lisbon, pp. 226–232 Daum M, Lauterwald F, Baumgärtel P, Pollner N, Meyer-Wegener K (2011) Black-box Determination of Cost Models` Parameters for Federated Stream-Processing Systems. In: Proceedings of the 15th International Database Engineering & Applications Symposium (IDEAS). Lisbon, pp. 226–232
5.
Zurück zum Zitat Daum M, Lauterwald F, Baumgärtel P, Pollner N, Meyer-Wegener K (2011) Efficient and Cost-aware Operator Placement in Heterogeneous Stream-Processing Environments. In: Proceedings of the 5th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, New York, pp. 393–394 Daum M, Lauterwald F, Baumgärtel P, Pollner N, Meyer-Wegener K (2011) Efficient and Cost-aware Operator Placement in Heterogeneous Stream-Processing Environments. In: Proceedings of the 5th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, New York, pp. 393–394
6.
Zurück zum Zitat Hirzel M, Soulé R, Schneider S, Gedik B, Grimm R (2014) A Catalog of Stream Processing Optimizations. ACM Comput Surv 46(4):1–34 Hirzel M, Soulé R, Schneider S, Gedik B, Grimm R (2014) A Catalog of Stream Processing Optimizations. ACM Comput Surv 46(4):1–34
7.
Zurück zum Zitat Hueske F, Peters M, Sax MJ, Rheinländer A, Bergmann R, Krettek A, Tzoumas K (2012) Opening the Black Boxes in Data Flow Optimization. Proceedings VLDB Endowment 5(11):1256–1267 Hueske F, Peters M, Sax MJ, Rheinländer A, Bergmann R, Krettek A, Tzoumas K (2012) Opening the Black Boxes in Data Flow Optimization. Proceedings VLDB Endowment 5(11):1256–1267
8.
Zurück zum Zitat Jarke M, Koch J (1984) Query Optimization in Database Systems. ACM Comput Surv 16(2):111–152 Jarke M, Koch J (1984) Query Optimization in Database Systems. ACM Comput Surv 16(2):111–152
9.
Zurück zum Zitat Karnagel T, Habich D, Schlegel B, Lehner W (2014) Heterogeneity-Aware Operator Placement in Column-Store DBMS. Datenbank-Spektrum 14(3):211–221 Karnagel T, Habich D, Schlegel B, Lehner W (2014) Heterogeneity-Aware Operator Placement in Column-Store DBMS. Datenbank-Spektrum 14(3):211–221
10.
Zurück zum Zitat Ke Q, Isard M, Yu Y (2013) Optimus: A Dynamic Rewriting Framework for Data-parallel Execution Plans. In: Proceedings of the 8th ACM European Conference on Computer Systems (EuroSys). ACM, Prague, pp. 15–28 Ke Q, Isard M, Yu Y (2013) Optimus: A Dynamic Rewriting Framework for Data-parallel Execution Plans. In: Proceedings of the 8th ACM European Conference on Computer Systems (EuroSys). ACM, Prague, pp. 15–28
11.
Zurück zum Zitat Khandekar R, Hildrum K, Parekh S, Rajan D, Wolf J, Wu KL, Andrade H, Gedik B (2009) COLA: Optimizing stream processing applications via graph partitioning. In: Middleware, Lecture Notes in Computer Science, vol. 5896. Springer, Urbana Champaign, pp. 308–327 Khandekar R, Hildrum K, Parekh S, Rajan D, Wolf J, Wu KL, Andrade H, Gedik B (2009) COLA: Optimizing stream processing applications via graph partitioning. In: Middleware, Lecture Notes in Computer Science, vol. 5896. Springer, Urbana Champaign, pp. 308–327
12.
Zurück zum Zitat Kossmann D (2000) The State of the Art in Distributed Query Processing. ACM Comput Surv 32(4):422–469 Kossmann D (2000) The State of the Art in Distributed Query Processing. ACM Comput Surv 32(4):422–469
13.
Zurück zum Zitat Lo VM (1988) Heuristic Algorithms for Task Assignment in Distributed Systems. IEEE Transactions on Computers 37(11):1384–1397 Lo VM (1988) Heuristic Algorithms for Task Assignment in Distributed Systems. IEEE Transactions on Computers 37(11):1384–1397
14.
Zurück zum Zitat Nehme RV, Works K, Lei C, Rundensteiner EA, Bertino E (2013) Multi-route Query Processing and Optimization. J Comput System Sci 79(3):312–329 Nehme RV, Works K, Lei C, Rundensteiner EA, Bertino E (2013) Multi-route Query Processing and Optimization. J Comput System Sci 79(3):312–329
15.
Zurück zum Zitat Pollner N, Steudtner C, Meyer-Wegener K (2015) Operator Fission for Load Balancing in Distributed Heterogeneous Data Stream Processing Systems. In: Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, Oslo, pp. 332–335 Pollner N, Steudtner C, Meyer-Wegener K (2015) Operator Fission for Load Balancing in Distributed Heterogeneous Data Stream Processing Systems. In: Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, Oslo, pp. 332–335
16.
Zurück zum Zitat Pollner N, Steudtner C, Meyer-Wegener K (2015) Placement-Safe Operator-Graph Changes in Distributed Heterogeneous Data Stream Systems. In: Datenbanksysteme für Business, Technologie und Web (BTW) - Workshopband, Lecture Notes in Informatics (LNI) - Proceedings, vol. P-242. Gesellschaft für Informatik (GI), Hamburg, pp. 61–70 Pollner N, Steudtner C, Meyer-Wegener K (2015) Placement-Safe Operator-Graph Changes in Distributed Heterogeneous Data Stream Systems. In: Datenbanksysteme für Business, Technologie und Web (BTW) - Workshopband, Lecture Notes in Informatics (LNI) - Proceedings, vol. P-242. Gesellschaft für Informatik (GI), Hamburg, pp. 61–70
17.
Zurück zum Zitat Tian F, DeWitt DJ (2003) Tuple Routing Strategies for Distributed Eddies. In: Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). VLDB Endowment, Berlin, pp. 333–344 Tian F, DeWitt DJ (2003) Tuple Routing Strategies for Distributed Eddies. In: Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). VLDB Endowment, Berlin, pp. 333–344
18.
Zurück zum Zitat Viglas SD, Naughton JF (2002) Rate-based Query Optimization for Streaming Information Sources. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, Madison, pp. 37–48 Viglas SD, Naughton JF (2002) Rate-based Query Optimization for Streaming Information Sources. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, Madison, pp. 37–48
Metadaten
Titel
Placement-Safe Operator-Graph Changes in Distributed Heterogeneous Data Stream Systems
verfasst von
Niko Pollner
Christian Steudtner
Klaus Meyer-Wegener
Publikationsdatum
01.11.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Datenbank-Spektrum / Ausgabe 3/2015
Print ISSN: 1618-2162
Elektronische ISSN: 1610-1995
DOI
https://doi.org/10.1007/s13222-015-0196-z

Weitere Artikel der Ausgabe 3/2015

Datenbank-Spektrum 3/2015 Zur Ausgabe

COMMUNITY

News

EDITORIAL

Editorial

Premium Partner