Vis enkel innførsel

dc.contributor.advisorHauglid, Jon Olav
dc.contributor.authorVestrheim, Sevre
dc.date.accessioned2020-06-04T16:01:23Z
dc.date.available2020-06-04T16:01:23Z
dc.date.issued2019
dc.identifier.urihttps://hdl.handle.net/11250/2656664
dc.description.abstractNår en spørring blir optimalisert av spørreoptimalisatoren i en database er det mange faktorer som undersøkes før valg av spørreplan blir tatt. En av disse er rekkefølgen tabeller joines i. Rekkefølgen bestemmes i stor grad av kardinaliteten til tabllen. Dersom noen av predikatene kan benyttes til å filtere vekk rader i tabellene før join operasjonen begynner, vil det redusere kjøretiden. Dermed blir dette nesten alltid gjort. Selektiviteten til predikatene blir bestemt av antall rader i tabellen som tilfredstiller predikatet. Dette approksimeres enten ved hjelp av et histogram eller ved bruk av heuristikker. Heuristikker er kontstante verdier som blir bestemt av de som utvikler spørreoptimalisatoren. Disse gir sjelden et like nøyaktig estimat som et histogram. Det er dog slik at et histogram må beregnes, noe som tar opp tid og ressurser. Dersom dataen histogrammet er basert på endres uten at histogramet beregnes på nytt, vil histogrammet være feil og gi et unøyaktig selektivitets estimat. Effekten varierende histogram nøyaktighet og forskjellige oppdaterings startegier for histogram har på kjøretiden til spørringer evalueres i denne rapporten. Sammen med design av kravene til ,og implementeringen av, en database hvor histogram nøyaktighet har en effekt på kjørtiden til spørringer. Til å begynne med presenteres ni forskjellige oppdateringsmetoder hvorav fire implementeres. Senere presenteres fire nye som basis for fremtidig arbeid. Gjennom testing av de implementerte oppdaterings metodene og en gruppe med base metoder, vises det at i den gitte databasen yter unøyaktige histogram dårligere enn nøyaktige histogram, og også verre enn ingen histogram. Det vises videre at gjennom relativt enkle oppdaterings metoder kan ytelsen til databasen økes betraktelig sammenlignet med unøyaktige histogram. Det vises og at oppdaterings metodene som benyttes i to moderne system yter dårlig i vår database.
dc.description.abstractWhen the database query-optimiser optimises a query, several factors are taken into consideration while attempting to decide on the query plan to use. One of these factors is the order in which tables are joined. When determining the order in which tables should be joined, the cardinality of each table is one of the essential characteristics investigated. If any predicates can be applied to tables before join operations begin that will reduce the execution time, and is as such almost always performed. The selectivity of a predicate is determined by how many rows in the table which satisfy the predicate. It is approximated either by using histograms or heuristics. Heuristics are constant values chosen by the developers of the query-optimiser, and these will seldom provide as accurate estimates as a histogram. However, a histogram has to be computed, which takes time and resources. If the data on which the histogram is based changes without the histogram being updated, the histogram will become stale and will not provide accurate selectivity estimates. An evaluation of the effects of varying histogram accuracy levels and different strategies of maintaining accuracy is presented in this report. Along with designing the requirements for, and implementing, a use-case in which different levels of histogram accuracy affect query execution times. Initially, nine different updating methods are presented, of which four are implemented. later another four are suggested as a basis for future work. Through testing of the implemented updating methods and a set of base class methods, it is shown that in the given use-case stale histograms perform worse than accurate histograms, and also worse than no histograms. It is also shown that with relatively simple updating schemes performance can be significantly improved when compared to using stale histograms. Further, it is shown that the implemented updating scheme in two state-of-the-art systems performs very poorly in our use-case.
dc.languageeng
dc.publisherNTNU
dc.titleAutomatic updating of histograms in MySQL
dc.typeMaster thesis


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel