Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Datenbank-Spektrum
Published in: Datenbank-Spektrum 3/2015

01-11-2015 | SCHWERPUNKTBEITRAG

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

Authors: Niko Pollner, Christian Steudtner, Klaus Meyer-Wegener

Published in: Datenbank-Spektrum | Issue 3/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Query Optimization in Heterogenous Event Processing Federations
next article Modulares Verteilungskonzept für Datenstrommanagementsysteme

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Show more products
Literature
1.
Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems, Revised Reprint. Siam
2.
Daum M (2011) Verteilung globaler Anfragen auf heterogene Stromverarbeitungssysteme. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
3.
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.
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.
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.
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.
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.
Jarke M, Koch J (1984) Query Optimization in Database Systems. ACM Comput Surv 16(2):111–152
9.
Karnagel T, Habich D, Schlegel B, Lehner W (2014) Heterogeneity-Aware Operator Placement in Column-Store DBMS. Datenbank-Spektrum 14(3):211–221
10.
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.
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.
Kossmann D (2000) The State of the Art in Distributed Query Processing. ACM Comput Surv 32(4):422–469
13.
Lo VM (1988) Heuristic Algorithms for Task Assignment in Distributed Systems. IEEE Transactions on Computers 37(11):1384–1397
14.
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.
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.
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.
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.
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
Metadata
Title
Placement-Safe Operator-Graph Changes in Distributed Heterogeneous Data Stream Systems
Authors
Niko Pollner
Christian Steudtner
Klaus Meyer-Wegener
Publication date
01-11-2015
Publisher
Springer Berlin Heidelberg
Published in
Datenbank-Spektrum / Issue 3/2015
Print ISSN: 1618-2162
Electronic ISSN: 1610-1995
DOI
https://doi.org/10.1007/s13222-015-0196-z

Other articles of this Issue 3/2015

Datenbank-Spektrum 3/2015 Go to the issue

SCHWERPUNKTBEITRAG

Modulares Verteilungskonzept für Datenstrommanagementsysteme

COMMUNITY

News

DISSERTATIONEN

Dissertationen

SCHWERPUNKTBEITRAG

Genome sequence analysis with MonetDB

SCHWERPUNKTBEITRAG

Query Optimization in Heterogenous Event Processing Federations

DATENBANKGRUPPEN VORGESTELLT

Die Arbeitsgruppe Datenbanksysteme an der Philipps-Universität Marburg

Premium Partner

    Image Credits