More Web Proxy on the site http://driver.im/

research-article

Adaptive work placement for query processing on heterogeneous computing resources

Authors:

Tomas Karnagel,

Wolfgang LehnerAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 10, Issue 7

Pages 733 - 744

https://doi.org/10.14778/3067421.3067423

Published: 01 March 2017 Publication History

Abstract

The hardware landscape is currently changing from homogeneous multi-core systems towards heterogeneous systems with many different computing units, each with their own characteristics. This trend is a great opportunity for data-base systems to increase the overall performance if the heterogeneous resources can be utilized efficiently. To achieve this, the main challenge is to place the right work on the right computing unit. Current approaches tackling this placement for query processing assume that data cardinalities of intermediate results can be correctly estimated. However, this assumption does not hold for complex queries. To overcome this problem, we propose an adaptive placement approach being independent of cardinality estimation of intermediate results. Our approach is incorporated in a novel adaptive placement sequence. Additionally, we implement our approach as an extensible virtualization layer, to demonstrate the broad applicability with multiple database systems. In our evaluation, we clearly show that our approach significantly improves OLAP query processing on heterogeneous hardware, while being adaptive enough to react to changing cardinalities of intermediate query results.

References

[1]

D. Abadi, P. Boncz, S. Harizopoulos, S. Idreos, and S. Madden. The Design and Implementation of Modern Column-Oriented Database Systems. In Foundations and Trends in Databases, volume 5, pages 197--280, 2013.

Digital Library

[2]

J. Antony, P. P. Janes, and A. P. Rendell. Exploring Thread and Memory Placement on NUMA Architectures: Solaris and Linux, UltraSPARC/FirePlane and Opteron/Hypertransport. In Proceedings of HiPC, pages 338--352, 2006.

Digital Library

[3]

P. A. Boncz, M. L. Kersten, and S. Manegold. Breaking the Memory Wall in MonetDB. Communications ACM, 51(12):77--85, Dec. 2008.

Digital Library

[4]

P. A. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper-Pipelining Query Execution. In CIDR:225--237, 2005.

[5]

S. Breß. The Design and Implementation of CoGaDB: A Column-oriented GPU-accelerated DBMS. Datenbank-Spektrum, 14(3):199--209, 2014.

[6]

S. Breß and G. Saake. Why It is Time for a HyPE: A Hybrid Query Processing Engine for Efficient GPU Coprocessing in DBMS. Proc. VLDB Endow., 6(12):1398--1403, Aug. 2013.

Digital Library

[7]

A. Brinkmann, K. Salzwedel, and C. Scheideler. Compact, Adaptive Placement Schemes for Non-uniform Requirements. In Proceedings of SPAA, pages 53--62. ACM, 2002.

Digital Library

[8]

S. Christodoulakis. Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst., 9(2):163--186, June 1984.

Digital Library

[9]

A. Deshpande, Z. Ives, and V. Raman. Adaptive Query Processing. Found. Trends databases, 1(1):1--140, Jan. 2007.

Digital Library

[10]

H. Esmaeilzadeh, E. Blem, R. St. Amant, K. Sankaralingam, and D. Burger. Dark silicon and the end of multicore scaling. In Proceedings of ISCA, pages 365--376. ACM, 2011.

Digital Library

[11]

B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju, Q. Luo, and P. V. Sander. Relational Query Coprocessing on Graphics Processors. ACM Trans. Database Syst., 34(4):21:1--21:39, Dec. 2009.

Digital Library

[12]

B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander. Relational Joins on Graphics Processors. In Proceedings of the 2008 ACM SIGMOD, SIGMOD '08, pages 511--524, New York, NY, USA, 2008. ACM.

Digital Library

[13]

J. He, S. Zhang, and B. He. In-cache Query Co-processing on Coupled CPU-GPU Architectures. Proc. VLDB Endow., 8(4):329--340, Dec. 2014.

Digital Library

[14]

M. Heimel, M. Saecker, H. Pirk, S. Manegold, and V. Markl. Hardware-oblivious Parallelism for In-memory Column-stores. Proc. VLDB Endow., 6(9):709--720, July 2013.

Digital Library

[15]

Y. E. Ioannidis and S. Christodoulakis. On the propagation of errors in the size of join results. In Proceedings of ACM SIGMOD, pages 268--277. ACM, 1991.

Digital Library

[16]

S. Jha, B. He, M. Lu, X. Cheng, and H. P. Huynh. Improving Main Memory Hash Joins on Intel Xeon Phi Processors: An Experimental Approach. Proc. VLDB Endow.:642--653, 2015.

Digital Library

[17]

T. Karnagel, D. Habich, and W. Lehner. Local vs. Global Optimization: Operator Placement Strategies in Heterogeneous Environments. In Proceedings of the Workshops of the EDBT/ICDT, pages 48--55, 2015.

[18]

T. Karnagel, D. Habich, B. Schlegel, and W. Lehner. Heterogeneity-Aware Operator Placement in Column-Store DBMS. Datenbank-Spektrum, 14(3):211--221, 2014.

[19]

V. Leis, P. Boncz, A. Kemper, and T. Neumann. Morsel-driven parallelism: a NUMA-aware query evaluation framework for the many-core age. In Proceedings of the 2014 ACM SIGMOD, pages 743--754. ACM, 2014.

Digital Library

[20]

V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. How Good Are Query Optimizers, Really? Proc. VLDB Endow., 9(3):204--215, Nov. 2015.

Digital Library

[21]

B. Lepers, V. Quéma, and A. Fedorova. Thread and Memory Placement on NUMA Systems: Asymmetry Matters. In Proceedings of the 2015 USENIX, pages 277--289, 2015.

Digital Library

[22]

S. Meraji, B. Schiefer, L. Pham, L. Chu, P. Kokosielis, A. Storm, W. Young, C. Ge, G. Ng, and K. Kanagaratnam. Towards a Hybrid Design for Fast Query Processing in DB2 with BLU Acceleration Using Graphical Processing Units: A Technology Demonstration. In Proceedings of SIGMOD, pages 1951--1960. ACM, 2016.

Digital Library

[23]

R. Mueller, J. Teubner, and G. Alonso. Data Processing on FPGAs. Proc. VLDB Endow., 2(1):910--921, Aug. 2009.

Digital Library

[24]

T. Neumann. Efficiently compiling efficient query plans for modern hardware. Proc. VLDB Endow., 4(9):539--550, 2011.

Digital Library

[25]

P. ONeil, E. ONeil, X. Chen, and S. Revilak. The star schema benchmark and augmented fact table indexing. In Technology Conference on Performance Evaluation and Benchmarking, pages 237--252. Springer, 2009.

Digital Library

[26]

K. Wang, K. Zhang, Y. Yuan, S. Ma, R. Lee, X. Ding, and X. Zhang. Concurrent Analytical Query Processing with GPUs. Proc. VLDB Endow., 7(11):1011--1022, July 2014.

Digital Library

[27]

Y.-P. You, H.-J. Wu, Y.-N. Tsai, and Y.-T. Chao. VirtCL: A Framework for OpenCL Device Abstraction and Management. In Proceedings of PPoPP, pages 161--172. ACM, 2015.

Digital Library

[28]

Y. Yuan, R. Lee, and X. Zhang. The Yin and Yang of Processing Data Warehousing Queries on GPU Devices. Proc. VLDB Endow., 6(10):817--828, Aug. 2013.

Digital Library

Cited By

Yogatama BGong WYu X(2024)Scaling your Hybrid CPU-GPU DBMS to Multiple GPUsProceedings of the VLDB Endowment10.14778/3704965.370497717:13(4709-4722)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.14778/3704965.3704977
Carvalho MSimitsis AQueralt ARomero O(2024)Workload Placement on Heterogeneous CPU-GPU SystemsProceedings of the VLDB Endowment10.14778/3685800.368584517:12(4241-4244)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685845
Kroviakov AKurapov PAnneser CGiceva J(2024)Heterogeneous Intra-Pipeline Device-Parallel AggregationsProceedings of the 20th International Workshop on Data Management on New Hardware10.1145/3662010.3663441(1-10)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3662010.3663441
Show More Cited By

Adaptive work placement for query processing on heterogeneous computing resources
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

View-based query processing: On the relationship between rewriting, answering and losslessness

As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
Exploiting Constraints in Query Processing: Query transformation using interity constraints and views
Adaptive Multi-join Query Processing in PDBMS
ICDE '09: Proceedings of the 2009 IEEE International Conference on Data Engineering

Traditionally, distributed databases assume that the small) set of nodes participating in a query is known apriori, the data is well placed, and the statistics are readily available. However, these assumptions are no longer valid in a Peer-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 10, Issue 7

March 2017

132 pages

ISSN:2150-8097

Editors:
Peter Boncz
CWI
,
Ken Salem
University of Waterloo

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 March 2017

Published in PVLDB Volume 10, Issue 7

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
417
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)2

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yogatama BGong WYu X(2024)Scaling your Hybrid CPU-GPU DBMS to Multiple GPUsProceedings of the VLDB Endowment10.14778/3704965.370497717:13(4709-4722)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.14778/3704965.3704977
Carvalho MSimitsis AQueralt ARomero O(2024)Workload Placement on Heterogeneous CPU-GPU SystemsProceedings of the VLDB Endowment10.14778/3685800.368584517:12(4241-4244)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685845
Kroviakov AKurapov PAnneser CGiceva J(2024)Heterogeneous Intra-Pipeline Device-Parallel AggregationsProceedings of the 20th International Workshop on Data Management on New Hardware10.1145/3662010.3663441(1-10)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3662010.3663441
Habich DPietrzyk JBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)SIMDified Data Processing - Foundations, Abstraction, and Advanced TechniquesCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654694(613-621)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654694
Oh SMoon GPark S(2024)ML-Based Dynamic Operator-Level Query Mapping for Stream Processing Systems in Heterogeneous Computing Environments2024 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER59578.2024.00027(226-237)Online publication date: 24-Sep-2024
https://doi.org/10.1109/CLUSTER59578.2024.00027
Berthold ASchmidt LObersteiner AHabich DLehner WSchirmeier H(2024)On-The-Fly Data Distribution to Accelerate Query Processing in Heterogeneous Memory SystemsAdvances in Databases and Information Systems10.1007/978-3-031-70626-4_12(170-183)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-70626-4_12
Jungmair MGiceva J(2023)Declarative Sub-Operators for Universal Data ProcessingProceedings of the VLDB Endowment10.14778/3611479.361153916:11(3461-3474)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.14778/3611479.3611539
Yogatama BMiller BWang YMarkall GHemstad JKimball GYu X(2023)Accelerating User-Defined Aggregate Functions (UDAF) with Block-wide Execution and JIT Compilation on GPUsProceedings of the 19th International Workshop on Data Management on New Hardware10.1145/3592980.3595307(19-26)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3592980.3595307
VL DPA JMathew K P(2023)Secure query processing and optimization in cloud environment: a reviewInformation Security Journal: A Global Perspective10.1080/19393555.2023.227097633:2(172-191)Online publication date: 20-Dec-2023
https://doi.org/10.1080/19393555.2023.2270976
Yogatama BGong WYu X(2022)Orchestrating data placement and query execution in heterogeneous CPU-GPU DBMSProceedings of the VLDB Endowment10.14778/3551793.355180915:11(2491-2503)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551809
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents