Semi-Automatic Statistics Management: Exploiting Existing Data Streams to Improve Selectivity Estimation in MySQL's Hypergraph Optimizer

Abstract

MySQLs nye hypergraf optimizer benytter flere kostnadsbaserte valg sammenlignet med den orginale optimizeren, og bør derfor kunne utnytte database-statistikk i større grad. Innledende eksperimenter synliggjør effekten av nøyaktig statistikk hvor korrekte selektiviter for Join Order Benchmark-spørringer fører til økt ytelse. Dette understreker viktigheten av nøyaktig og oppdatert statistikk i databaser, som leder inn på ideen om å utnytte eksisterende datastrømmer i MySQL for å lage, oppdatere og vedlikeholde slik statistikk.

Denne avhandlingen presenterer en ny implementasjon av count-min og count-min mean skisser for estimering av datadistribusjon i MySQL, og sammenligner ytelsen med histogrammer for Join Order Benchmark. Resultatene indikerer en helhetlig forbedring i ytelse samt bedre treffsikkerhet på selektivitetsestimering, riktignok med enkelte unntak der ytelsen blir påvirket negativt. Senere implementasjoner av hypergraf-optimizeren med en mer robust kostnadsmodell er antatt å redusere graden av slike hendelser. Eksperimentene viser lovende resultater i retning mot å utnytte eksisterende datastrømmer for å generere statistikk i MySQL. Dette legger grunnlaget for påfølgende implementasjoner av semi-automatisk håndtering av statistikk.

MySQL's new hypergraph optimizer employs more cost-based decision-making compared to the original optimizer, and should therefore more prominently utilize database statistics. The initial experiment highlights the effect of accurate statistics, where injected correct selectivities for the Join Order Benchmark queries leads to improved performance. This emphasizes the importance of accurate and up-to-date statistics, leading to the idea of exploiting existing data streams in MySQL to create, update and manage such statistics.

This thesis presents a novel implementation of count-min and count-min mean sketch for estimating data distribution in MySQL and compares the performance with histograms on the Join Order Benchmark. Results indicate an overall improvement in performance and selectivity estimation accuracy, albeit with some exceptions where performance is negatively affected. Later implementations of the hypergraph optimizer with a more refined cost model are assumed to reduce the degree of such occurrences. The experimental results show promise regarding the exploitation of existing data streams to generate statistics in MySQL, serving as a foundation for subsequential implementations of semi-automatic statistic management.