State of the Art Learned Index Structures

Abstract

"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 release of 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 indexes may serve the same purpose as the B-tree, by supporting a wide variety of workloads and still providing great performance. In this thesis, we provide a technical analysis of two state of the art, general purpose learned indexes; ALEX and PGM-Index. These structures have many of the same characteristics while being built on different approaches. We also cover two learned indexes that have given inspiration to, and introduced many important concepts 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 authors own implementations of their respective structures in C++. We show that we are able to reproduce similar performance results as reported by the authors, as well as provide a novel side by side comparison of ALEX and PGM-Index on the same data distributions and query workloads. We found that ALEX produced better query performance overall for 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 data distributions.