State of the Art Learned Index Structures
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3026813Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Sammendrag
"Learned Indexes" har vært et populært tema innen databasesamfunnet etter at den første Learned Index ble publisert, ved å introdusere maskinlæring til å løse indekseringsproblemet som lenge har vært dominert av tradisjonelle datastrukturer som B-trær. Siden da har det blitt publisert flere Learned Indexes. Noen av disse er laget for spesifikke situasjoner, mens andre er mer fleksible. De fleksible Learned Indexes kan utføre de samme oppgavene som et B-tre, ved å støtte en variasjon av forskjellige spørreoperasjoner. I denne oppgaven gir vi en teknisk analyse av to state of the art Learned Indexes, som begge kan brukes til generelle formål. Disse strukturene har mange av de samme egenskapene, selv om de er bygget på ulike tilnærminger. Vi dekker også to Learned Indexes som har gitt inspirasjon til, og introdusert mange viktige konsepter som blir brukt av state of the art Learned Indexes.
Vi lager en benchmark for to state of the art learned indexes kalt ALEX og PGM-Index, ved å bruke forfatternes egne implementasjoner av strukturene i C++. Vi viser at vi kan reprodusere lignende resultater som er rapportert av forfatterne, og gir en sammenligning av ytelsen til ALEX og PGM på samme datasett og med lik fordeling av spørringer. Vi fant ut at ALEX ga bedre ytelse for lesespørringer. PGM-Index ga mer konsistente resultater for alle datadistribusjoner og spørrefordelinger, og gav bedre resultater for skrivespørringer på en av datadistribusjonene. ”Learned Indexes” have been a hot topic within the database community after the releaseof the first learned index, which introduces machine learning to solve the indexing prob-lem that have for a long time, and still are, dominated by traditional structures like B-trees.There have since been created several learned indexes, some of which are created for spe-cific purposes, and some that prove to be very flexible. These flexible learned indexesmay serve the same purpose as the B-tree, by supporting a wide variety of workloads andstill providing great performance. In this thesis, we provide a technical analysis of twostate of the art, general purpose learned indexes; ALEX and PGM-Index. These structureshave many of the same characteristics while being built on different approaches. We alsocover two learned indexes that have given inspiration to, and introduced many importantconcepts that are being used by the state of the art learned indexes.
We create a benchmark for the two state of the art learned indexes, by using the authorsown implementations of their respective structures in C++. We show that we are ableto reproduce similar performance results as reported by the authors, as well as provide anovel side by side comparison of ALEX and PGM-Index on the same data distributionsand query workloads. We found that ALEX produced better query performance overallfor read-only workloads. PGM-Index performed more consistent for all data distribu-tions and workloads, and had better write performance than ALEX on one of the datadistributions.