Performance Tuning and Query Optimization for Big Data Management

Show simple item record

dc.contributor.author Chen, Yuxing
dc.date.accessioned 2021-11-11T12:26:20Z
dc.date.available 2021-11-22
dc.date.available 2021-11-11T12:26:20Z
dc.date.issued 2021-12-02
dc.identifier.uri URN:ISBN:978-951-51-7740-7
dc.identifier.uri http://hdl.handle.net/10138/336226
dc.description.abstract 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. en
dc.description.abstract 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. fi
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-951-51-7739-1
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject computer Science
dc.title Performance Tuning and Query Optimization for Big Data Management en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Artikkeliväitöskirja fi
dc.type.ontasot Artikelavhandling sv
dc.ths Lu, Jiaheng
dc.opn Abelló, Alberto
dc.type.dcmitype Text
dc.contributor.organization University of Helsinki, Faculty of Science en
dc.contributor.organization Doctoral Programme in Computer Science en
dc.contributor.organization Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor.organization Tietojenkäsittelytieteen tohtoriohjelma fi
dc.contributor.organization Helsingfors universitet, matematisk-naturvetenskapliga fakulteten sv
dc.contributor.organization Doktorandprogrammet i datavetenskap sv
dc.type.okm 113 Tietojenkäsittely- ja informaatiotieteet fi
dc.type.okm 113 Data- och informationsvetenskap sv
dc.type.okm 113 Computer and information sciences en
dc.type.publication doctoralThesis

Files in this item

Total number of downloads: Loading...

Files Size Format View
chen_yuxing_dissertation_2021.pdf 775.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record