SFRDF+: Join Plans for SPARQL Processing in Apache Flink

Clausen, Jesper ; Otkjær, Mathias Eriksen

4. term

Software, Master

2017

2017-06-05

64

RDF er en måde at repræsentere information på nettet som simple udsagn (tripler), og mængderne af sådanne data er vokset til milliard-skala. For at håndtere så store datasæt kræves distribuerede systemer, der kan behandle data på tværs af mange maskiner. SFRDF er et af disse systemer og bygger på Apache Flink (et distribueret databehandlingsframework) og en partitioneringsteknik kaldet ExtVP, som deler data op for at gøre forespørgsler hurtigere. SFRDF var ved sin tilblivelse i efteråret 2016 næsten på niveau med tidens førende systemer. Vi præsenterer en forbedret udgave, SFRDF+, som tilføjer flere forbedringer. De spænder fra en enkel ændring som dictionary encoding (at erstatte tekstværdier med numeriske id’er for at gøre lagring og sammenligninger mere effektive) til mere avancerede funktioner som optimering af join-rækkefølge for at generere bedre forespørgselsplaner. For at finde den bedste måde at lave disse planer på implementerer og evaluerer vi metoder fra både RDF-verdenen (f.eks. CliqueSquare) og traditionelle databasesystemer (f.eks. DPCCP og en grådig/greedy strategi). Vores evaluering af dictionary encoding og de forskellige join-rækkefølgemetoder viser, at den eneste praktisk anvendelige tilgang i vores system er den grådige strategi. Vi ændrer også omkostningsfunktionen for den grådige tilgang for at favorisere “bushy” planer (mere balancerede kombinationer i stedet for en lang kæde) for at se, om det giver bedre ydeevne. Det gjorde det ikke for de planer, vores algoritme genererede, men den standard grådige algoritme gav lovende resultater med samlet set kortere svartider på forespørgsler.

RDF is a way to represent information on the Web as simple statements (triples), and such datasets have grown to billions of triples. Handling data at this scale requires distributed processing across many machines. SFRDF is one such system; it is built on Apache Flink (a distributed data processing framework) and a partitioning technique called ExtVP that splits data to speed up queries. When created in fall 2016, SFRDF was nearly competitive with state-of-the-art systems. We present an improved version, SFRDF+, which adds several enhancements. These range from dictionary encoding (replacing text values with numeric IDs to make storage and comparisons more efficient) to more advanced features such as join order optimization to produce better query plans. To identify the best way to generate query plans, we implement and evaluate approaches from RDF processing (e.g., CliqueSquare) and from traditional database management systems (e.g., DPCCP and a greedy strategy). Our evaluation of dictionary encoding and join order strategies shows that the only feasible approach for our system is the greedy one. We also modify the cost function of the greedy method to prefer bushy plans (more balanced combinations instead of a long chain) to see whether that improves performance. It did not for the plans produced by our algorithm, but the standard greedy algorithm delivered promising results with an overall reduction in query response times.

[This abstract was generated with the help of AI]

SFRDF ; Flink ; Bushy ; Join order optimization ; Dictionary Encoding ; SPARQL ; RDF

Download
View record in AAU Student Projects