Improving alphanumeric selectivity estimation in MySQL using histograms of closed frequent itemsets

Abstract

Mengden data som lagres i databasesystemer verden over er i konstant vekst. På grunn av dette blir det viktigere og viktigere å ha nøyaktige metoder for å estimere størrelsen av midlertidige resultater i vilkårige spørringer. Denne avhandlingen fokuserer på selektivitetsestimater for LIKE-operatoren i MySQL.

En modifisert versjon av SPH-algoritmen for selektivitetsestimering (presentert i Aytimur and Çakmak, 2018) blir nøye testet ved bruk av tre genererte sett med spørringer. Resultatene blir deretter sammenlignet med de nåværende løsningene for selektivitetsestimering i MySQL og PostgreSQL. Til slutt blir 73 komplekse spørringer fra 'Join Order Benchmark' kjørt for å observere den nye løsningens effekt på MySQL i en praktisk situasjon.

Resultatene viser at den modifiserte SPH-algoritmen gir en nøyaktighet som er sammenlignbar med PostgreSQL og langt bedre enn den nåværende løsningen i MySQL for de genererte spørringene. For de 73 mer komplekse spørringene viser resultatene en reduksjon i kjøretid på 26% sammenlignet med den nåværende løsningen i MySQL.

As the data volume stored in databases increases by the day, it is becoming critical to have accurate approaches for estimating temporary results sizes for arbitrary queries. This thesis focuses on the estimation of result sizes for predicates using the LIKE operator in MySQL.

By using a set of three generated query workloads, a modified version of the SPH approach for selectivity estimation introduced in Aytimur and Çakmak, 2018 is thoroughly tested and compared to existing approaches in MySQL and PostgreSQL. Further, some more complex queries from the Join Order Benchmark are run to inspect the new approach’s impact on the MySQL system in a practical setting.

The results show that the modified SPH approach gives an estimation accuracy comparable to PostgreSQL and superior to MySQL for the generated workloads. For the 73 complex queries of the Join Order Benchmark, the selectivity estimates provided by the modified SPH approach gives a 26% improvement to execution time compared to the current solution in MySQL.