An evaluation of join-strategies in a distributed MySQL plugin architecture

Abstract

Join-spørringer i distribuerte database-systemer kan utføres på forskjellig vis ved bruk av ulike strategier. De ulike strategiene kan variere i kommunikasjons-, prosesserings-behov, og kompleksitet. Vi presenterer i denne rapporten en sammenlikning av flere ulike join-strategier i et distribuert MySQL system. Designet og utviklingen av 5 metoder inspirert av litteratur og aktuelle systemer blir fremlagt, samt et plugin-system for å fasillitere distribusjon i MySQL. Data-to-query, semi-join, bloom-join, hash redistribusjon og sort-merge blir testet gjennom flere scenarioer, med en diskusjon rundt deres relative ytelse og egenskaper. I resultatene vises fordelene med å parallellisere utføringen ved hash redistribusjon. Semi- og bloom-join sin gode ytelse viser hvordan smart ressurshåndtering kan påvirke ytelse i distribuerte systemer, og hvordan distribuerte join-spørringer er tjent med å bruke andre teknikker enn sentraliserte joins. Implementasjonen av sort-merge, som er laget mer fra bunnen opp, viser verdien av å bruke en spesialisert join algoritme når det kommer til prosessor-utnyttelse. Og den naive strategien data-to-query viser seg å være stabil, men er totalt sett den treigeste. En diskusjon rundt plugin-arkitekturen blir også fremlagt, samt tanker rundt fremtidig utvikling.

Join-queries in distributed database systems can be executed using a number of strategies that vary in communication requirements, compute-heaviness, and complexity. An evaluation of several join-strategies in a distributed MySQL system is presented. The design and implementation of 5 methods, inspired by literature and state-of-the-art, and a plugin system enabling distribution in MySQL are detailed. Data-to-query, semi-join, bloom-join, hash redistribution, and sort-merge are tested in a number of scenarios, leading to a discussion about their relative performance and viability. In the results, the benefits of parallelism are displayed through hash redistribution. And semi- and bloom-join show how being clever with resources can lead to great performance in distributed systems, and how distributed joins can benefit from different approaches than centralized joins. The more bottom-up implementation of sort-merge shows the value of using a specialized join algorithm in terms of processor utilization. And the more naïve data-to-query strategy is shown to be consistent, but generally the slowest. A discussion about the viability of the plugin architecture is also provided, with potential avenues for further development laid out in future work.