Distributed join algorithms on thousands of cores
Authors:
Open Access
- 1 January 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 10 (5) , 517-528
Abstract
Traditional database operators such as joins are relevant not only in the context of database engines but also as a building block in many computational and machine learning algorithms. With the advent of big data, there is an increasing demand for efficient join algorithms that can scale with the input data size and the available hardware resources. In this paper, we explore the implementation of distributed join algorithms in systems with several thousand cores connected by a low-latency network as used in high performance computing systems or data centers. We compare radix hash join to sort-merge join algorithms and discuss their implementation at this scale. In the paper, we explain how to use MPI to implement joins, show the impact and advantages of RDMA, discuss the importance of network scheduling, and study the relative performance of sorting vs. hashing. The experimental results show that the algorithms we present scale well with the number of cores, reaching a throughput of 48.7 billion input tuples per second on 4,096 cores.Keywords
This publication has 26 references indexed in Scilit:
- Rack-Scale In-Memory Join Processing using RDMA2015
- Track join2014
- Locality-sensitive operators for parallel main-memory database clusters2014
- Enabling highly-scalable remote memory access programming with MPI-3 one sided2013
- Multi-core, main-memory joinsProceedings of the VLDB Endowment, 2013
- Main-memory hash joins on multi-core CPUs: Tuning to the underlying hardware2013
- Massively parallel sort-merge joins in main memory multi-core database systemsProceedings of the VLDB Endowment, 2012
- Sort vs. Hash revisitedProceedings of the VLDB Endowment, 2009
- Optimizing main-memory join on modern hardwareIEEE Transactions on Knowledge and Data Engineering, 2002
- Samplesort: A Sampling Approach to Minimal Storage Tree SortingJournal of the ACM, 1970