Adding Parallelism to Shredded Yannakakis

Abstract

Join-operaties zijn een belangrijk deel van query engines, ze laten ons toe om data te combineren vanuit verschillende tabellen. Met dat de datasets die we gebruiken groeien, wordt het belangrijk dat de efficiëntie van deze operatoren meegroeit. Hiervoor bestaan algoritmen als Yannakakis' algoritme die deze berekeningen kunnen versnellen. Recent werk heeft een aangepaste versie van het algoritme gemaakt om het bruikbaar te maken in de praktijk. Om dit mogelijks nog verder te versnellen, kunnen we berekeningen in parallel laten verlopen. Deze thesis heeft als doel om parallellisme te implementeren in de bestaande implementatie van Shredded Yannakakis in Apache DataFusion. Hiervoor werd een exchange operator gemaakt die werkt als meta-operator, hij zal data partitioneren en parallelle werkers opstarten die de partities tegelijk kunnen verwerken. De operator werd dan in de 2-phase NSA plannen die bij Shredded Yannakakis horen verwerkt. Evaluatie van de parallelle runtimes toonde aan dat verticale en horizontale parallellisme aanwezig was via de nieuwe operator, waardoor de meeste runtimes versterkt werden. Het kiezen van het correcte aantal partities om de data in op te splitsen bleek een belangrijke factor te zijn in de efficiëntie van de parallellisatie. Uit deze resultaten kunnen we ook verder bewijzen dat een correcte integratie van parallellisme tijdswinsten kan opbrengen in praktische query engines.