Performance Benchmarking and Query Optimization for Multi-Model Databases

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-951-51-7198-6
Title: Performance Benchmarking and Query Optimization for Multi-Model Databases
Author: Zhang, Chao
Contributor: University of Helsinki, Faculty of Science
Doctoral Programme in Computer Science
Publisher: Helsingin yliopisto
Date: 2021-04-19
URI: http://urn.fi/URN:ISBN:978-951-51-7198-6
http://hdl.handle.net/10138/328312
Thesis level: Doctoral dissertation (article-based)
Abstract: Multi-Model DataBases (MMDBs) are database management systems that utilize a single platform to store, manipulate, and query data in various data models, e.g., relational, tree, and graph models. Numerous MMDBs have been developed to facilitate multi-model data management, but they differ fundamentally in data storage, query language, and query processing. Existing tools are not suitable for benchmarking MMDBs because they do not consider the multi-model data and workloads. Therefore, it is of paramount importance to provide a new benchmark to evaluate the performance of MMDBs. Furthermore, MMDBs bring new issues for query optimization as traditional techniques cannot properly optimize the queries due to the lack of consideration of multi-model operators and storage. Thus, it calls for new approaches to optimize multi-model queries. This thesis is divided into two parts to accomplish the above two goals, respectively. In the first part, we developed a new benchmark system for MMDBs in a scenario of social commerce with five data models, i.e., relational, JSON, XML, graph, and key-value. This benchmark system is an end-to-end tool that consists of various components, including synthetic data generation, workload specification, parameter curation, and execution client. Moreover, we leveraged the developed system to conduct a holistic experimental evaluation of the state-of-the-art MMDBs to compare their performance and identify their performance bottlenecks in handling multi-model workloads. In the second part, we proposed two query optimization techniques for MMDBs. Firstly, we proposed a kernel density estimation (KDE)-based model to estimate the selectivity of multi-model joins that involve predicates for relational and tree data models. The estimation method can serve as a building block for selecting an optimal joining order in a cross-model query execution plan. We also proposed two approaches, the max-min approximation (MMA) and grid-based approximation (GBA) models, to approximate the KDE contribution while improving the estimation efficiency for large data samples. Secondly, we studied the problem of view selection in the relational-based graph databases to avoid the costly joins in the relational engine. Particularly, we proposed an end-to-end system that can automatically create, evaluate, and select views for accelerating the query processing. We proposed an extended graph view that can answer the subgraph and supergraph queries simultaneously. We devised a filtering-and-verification framework that enables the verification of the query containment by graph views. We formalized the view selection problem as a 0-1 Knapsack problem, then we developed a view selection algorithm, named graph gene algorithm (GGA), which explores the graph view transformations to reduce the view space and optimize the view benefit. Overall, the present thesis advances MMDBs in three aspects, i.e., performance benchmarking, join selectivity estimation, and automatic view selection.Usean mallin tietokannat (MMDB) ovat tietokannan hallintajärjestelmiä, jotka käyttävät yhtä alustaa tietojen tallentamiseen, käsittelyyn ja kyselyihin erilaisissa tietomalleissa, esimerkiksi relaatio-, puu- ja verkkomalleissa. Lukuisia MMDB-tietokantoja on kehitetty helpottamaan monimalleihin perustuvaa tiedonhallintaa, mutta nämä tietokannat eroavat toisistaan ​​perusteellisesti tietojen tallennuksen, kyselykielen ja kyselyjen käsittelyn suhteen. Olemassa olevat työkalut eivät sovellu MMDB-tietokantojen vertailuanalyysiin, koska ne eivät ota huomioon usean yhtäaikaisen mallin vaatimuksia ja niiden aiheuttamia kuormituksia. Siksi on ensiarvoisen tärkeää tarjota uusia vertailuarvoja MMDB-tietokantojen suorituskyvyn arvioimiseksi. Lisäksi MMDB-tietokannat tuottavat uusia haasteita kyselyjen optimoinnille, koska perinteiset tekniikat eivät pysty optimoimaan kyselyjä kunnolla, ja monimalliset operaattorit ja tallennustila eivät ole riittävän tarkkoja. Näiden syiden vuoksi MMDB-tietokannat vaativat uusia lähestymistapoja monimallikyselyjen optimoimiseksi. Tämä opinnäytetyö jakautuu kahteen osaan vastaavasti kahden edellä mainitun tavoitteen saavuttamiseksi. Ensimmäisessä osassa kehitämme uuden vertailujärjestelmän MMDB-tietokannoille sosiaalisen kaupankäynnin skenaariossa, jossa on käytössä viisi datamallia, eli relaatio-, JSON-, XML-, verkko- ja avainarvomallit. Lisäksi hyödynnämme kehittämäämme järjestelmää suorittaaksemme kokonaisvaltaisen, kokeellisen arvioinnin huipputason MMDB-tietokannoista, jotta voimme verrata niiden suorituskykyjä sekä tunnistaa suorituskyvyn pullonkauloja monimallisten työmäärien käsittelyssä. Toisessa osassa ehdotamme kahta kyselyjen optimointitekniikkaa MMDB-tietokannoille. Ensinnäkin esitämme ytimen tiheyden arviointiin (KDE) perustuvan mallin arvioimaan selektiivisyyttä monimallisissa liitoksissa, joihin sisältyy predikaatteja relaatio- ja puudatamalleista. Arviointimenetelmä voi toimia rakennuspalikkana optimaalisen liitoksen yhdistämisjärjestyksen valitsemiselle mallien välisessä kyselyn suoritussuunnitelmassa. Toiseksi tutkimme näkymätaulun valinnan ongelmaa relaatiopohjaisissa verkkotietokannoissa välttääksemme suorittamasta kalliita liitoksia relaatiomoottorissa. Ehdotamme erityisesti end-to-end-järjestelmää, joka voi automaattisesti luoda, arvioida ja valita näkymiä kyselyjen käsittelyn nopeuttamiseksi. Muotoilemme näkymän valintaongelman 0-1 Knapsack -ongelmaksi. Kehitämme näkymänvalinta-algoritmin, nimeltään graafisen geenin algoritmi (GGA), joka tutkii verkkotietokannan näkymän muunnoksia näkymän pienentämiseksi ja näkymän hyödyn optimoimiseksi. Kaiken kaikkiaan tässä opinnäytetyössä edistetään MMDB-tietokantoja kolmesta näkökulmasta: suorituskyvyn vertailu, liitoksien selektiivisyyden arviointi ja automaattinen näkymän valinta.
Subject: computer Science
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
zhang_chao_dissertation_2021.pdf 900.5Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record