Performance Tuning and Query Optimization for Big Data Management

The substantial increase of real-life applications creates a large scale of ever-increasing raw heterogeneous data nowadays, correlating to the four Vs characteristics of big data: volume, variety, velocity and veracity. We discuss volume and variety challenges in this thesis. For volume, efficiently extracting valuable information and making predictions from these large-scale data are interesting to various quarters from academic researchers and industrial data scientists to customers and shareholders. For variety, much research addresses the challenges of effectively storing, collecting, processing, querying, and analyzing heterogeneous data. This thesis pushes approaches to optimize the performance with volume and variety challenges. For volume challenges, we aim at performance tuning for big data systems. In this part, to tackle cold-start situations with no statistics for models, we leverage cost-model and triangulation to model the performance, thus leading to cost-effective prediction. For variety challenges, we aim at optimizing join queries. In this part, to fill the gap of little research on join queries with heterogeneous data (i.e., relational and tree data), we research the size bound and the worst-case optimal join algorithm with relational and tree data in contrast with only relations. For parameter tuning, this thesis first contributes to propose a cost model for Spark workloads, which leverages Monte Carlo simulation to achieve cost-effective training. Specifically, we utilize a little part of resources and data to predict dependable performance for larger clusters and datasets even with data skewness and runtime deviations. Particularly, this work considers network and disk bounds so that it performs better with I/O-bounded workloads. Next, the thesis proposes $d$-simplexed, which models the Spark workloads by leveraging Delaunay Triangulation. Unlike other black-box ML methods, $d$-simplexed utilizes piece-wise linear regression models, which can be built faster and yield better prediction. Also, $d$-simplexed is built with an adaptive sampling technique which collects few training points but achieves accurate prediction. For join queries, this thesis studies the worst-case optimal join with relational and tree data. To this end, we first embark the study on the cross-model conjunctive query (CMCQ) with relational and tree data, and formally define the problem of CMCQ processing. We reveal that the computation of the worst-case size bound of a CMCQ is NP-hard w.r.t query expression complexity. We then develop a worst-case optimal join algorithm called CMJoin to match the size bound of a CMCQ under some circumstances.Nykypäivänä, kun dataa hyödyntävät sovellukset ovat merkittävästi lisääntyneet, myös heterogeenisen datan määrä kasvaa jatkuvasti. Datan ominaisuuksia kuvataan niin sanottujen neljän V:n avulla: volume (datan koko), variety (datan monimuotoisuus), velocity (datan kasvun ja muutoksen nopeus) ja veracity (datan tarkkuus). Tässä väitöskirjatyössä käsittelemme näistä datan kokoon ja datan monimuotoisuuteen liittyviä haasteita. Eräs datan kokoon liittyvistä haasteista on hyödyllisen informaation koostaminen ja luotettavien ennusteiden tekeminen laajoista datajoukoista. Tästä haasteesta ja sen sovelluksista ovat kiinnostuneet monet alat kuten akateemiset tutkijat, yrityksissä toimivat datatieteilijät sekä yritysten asiakkaat ja osakkeenomistajat. Heterogeenisen datan monimuotoisuuteen liittyviä haasteita taas ovat tiedon tehokas tallentaminen, kerääminen, prosessointi, kyselyiden suorittaminen ja analysointi. Tässä väitöskirjatyössä laajennamme tapoja, joilla datan kokoon ja monimuotoisuuteen liittyvien haasteiden ratkaisujen tehokkuutta voidaan optimoida. Datan kokoon liittyvien haasteiden optimoinnissa tähtäämme niin sanottujen big data -systeemien tehokkuuden parantamiseen. Tässä osassa hyödynnämme niin sanottua vaativuusmallia (cost-model) ja kolmiointia (triangulation) tilanteissa, joissa datan hallintaan käytettävistä systeemeistä ei ole kerätty ennakkotietoja. Näillä menetelmillä mallinnamme systeemien tehokkuutta. Nämä lähestymistavat johtavat luotettaviin ennusteisiin systeemien suorituskyvystä. Datan monimuotoisuuteen liittyvissä ongelmissa tähtäämme liitoskyselyiden (join queries) optimointiin. Tämä osa työtä edustaa verrattain pientä tutkimushaaraa, jossa tutkitaan liitoskyselyiden suorittamista monimuotoisten heterogeenisten datajoukkojen yli. Tässä tapauksessa keskitymme liitoskyselyiden suorittamiseen relaatioiden ja puumuotoisen tiedon välillä. Tutkimme liitoskyselyiden tulosten kokoon liittyviä ylärajoja sekä optimaalisia liitoskyselyiden suoritusalgoritmeja vaativimmissa tapauksissa. Vertaamme näitä lähestymistapoja myös vastaaviin relaatioiden liitoskyselyiden suoritustapoihin. Parametrien määrittämisen suhteen kehitämme tässä väitöskirjatyössä vaatimuksiin perustuvan mallin Spark-työmäärille. Hyödynnämme mallissa Monte Carlo -simulaatiota, jolloin saavutetaan suorituskyvyltään tehokas algoritmi. Erityisesti hyödynnämme vain pientä osaa resursseista ja datasta ennustaaksemme suurten klustereiden ja datajoukkojen keskenään riippuvuussuhteessa olevaa suoritustehoa jopa tilanteissa, joissa data on painottunut väärin tai systeemi kärsii ajon aikaisista poikkeamista. Lisäksi tarkastelemme tässä työssä tiedon verkottumisen ja levynkäytön ylärajoja, jotta systeemi suoriutuu paremmin tiedon siirrännän (I/O) suhteen rajoitetuista työmääristä. Tämän jälkeen kehitämme d-simplekseille perustuvan menetelmän, joka hyödyntää Delaunay-kolmiointia (Delaunay Triangulation). Verrattuna muihin musta laatikko -tyyppisiin koneoppimisalgoritmeihin d-simplekseihin perustuva algoritmi hyödyntää paloittain lineaarisia regressiomalleja, jotka voidaan laskea nopeammin ja joiden ennustustarkkuus on parempi. D-simplekseihin perustuvaa algoritmia käytettäessä voimme hyödyntää myös mukautuvaa näytteiden keräämistä datasta. Tällöin näytteiden vähäisestä määrästä huolimatta ennustukset ovat täsmällisiä. Tässä väitöskirjatyössä tutkitaan myös optimaalista tapaa suorittaa liitoskysely relaatioiden ja puumuotoisen tiedon välillä suorituskyvyn kannalta vaativimmassa tapauksessa. Aloitamme aiheen tutkimisen tarkastelemalla konjunktiivisia kyselyitä monimallisessa datassa, joka koostuu relaatioista ja puumuotoisesta tiedosta. Määrittelemme näihin kyselyihin liittyvän tutkimusongelman formaalisti. Osoitamme, että laskennallisen vaativuusteorian näkökulmasta konjuktiivisiin kyselyihin liittyvän koon ylärajan laskeminen kuuluu luokkaan NP, kun se lasketaan kyselyn lausekkeen perusteella. Kehitämme vaativimmassa tapauksessa optimaalisesti toimivan liitosalgoritmin nimeltään CMJoin. Tietyissä tilanteissa CMJoin suorittaa konjunktiivisen kyselyn kiinnitetyn ylärajan puitteissa