Evaluation of Learned Index with String Keys

Abstract

I de siste par årene har det blitt gjort forsøk på å integrere maskinlæring i databasesystemer. Spesielt har konseptet lærte indekser åpnet for mye forskning ettersom det teoretisk kan oppnå svært høy innhenting av informasjon. Til nå har det meste av forskningen vært sentrert rundt numerisk data, ettersom det å jobbe med strenger introduserer en stor grad mer kompleksitet for maskinlæringsmodeller. Dette arveidets mål var å undersøke hvor godt konseptet med lærte indekser har blitt utviklet til å jobbe med strengedata. Lærte indekser som har sett på strengedata og har vist god ytelse på numerisk data har ikke klart å utkonkurrere indekser som minner om B-trær, som regnes som en vanlig grunnlinje for strengedata.

I dette arbeidet har en dedikert lært strengeindeksstruktur kalt SIndex blitt sammenlignet med trie-baserte strengeindekser ART, et adaptivt radix-tre og HOT, en høydeoptimalisert trie. En hovedminne B-tre implementasjon ble brukt som grunnlinje. De relative ytelsene av indeksene ble evaluert for både syntetisk og ekte datasett basert på lese- og skrive-gjennomstrømning, samt gjennomstrømning under varierte arbeidsbyrde.

Resultatene viser at SIndex klart utkonkurrerer B-treet ved å gi dobbel gjennomstrømning for lese-, skrive- og varierte arbeidsbyrder. Men, det yter klart dårligere når det sammenliknes med ART og HOT indekser, spesielt for mindre datasett. I tillegg gir nødvendigheten av å tilpasse SIndex-parametrene for å tilpasse modellen til et gitt datasett en utfordring i å implementere SIndex i dynamiske omgivelser, noe som er en grunnleggende funksjon for alle maskinærlingmodeller.

In the past few years, efforts have been undertaken to integrate machine learning into database systems. Particularly the concept of learned index has facilitated a lot of research since it can theoretically achieve record retrieval in constant time. However, most of the work was centered around numerical data, since handling strings introduces considerable complexity for machine learning models. This work's aim was to investigate how well the concept of learned index has been developed to work with string data. Learned indexes that have looked at string data, and have shown good performance with numerical data, haven't been able to outperform B-tree like indexes, a popular baseline for string data. In this work a dedicated learned string index structure called SIndex was compared to trie based string indexes ART, an adaptive radix tree and HOT, a height optimized trie. As baseline a main memory B-tree implementation was used. The relative performances of indexes were evaluated for synthetic and real-world datasets based on read- and write- throughput, as well as throughput under mixed workloads.

The results show that SIndex is clearly outperforming the baseline B-tree, providing double the throughput for read, write and mixed workload performance. However, it is clearly inferior when compared with ART and HOT indexes, particularly for smaller datasets. Additionally, the need to adjust SIndex parameters to tailor the model to a given dataset make it a challenge implementing SIndex in dynamic environments, which is the nature of all machine learning models. At the moment there is no learned string index structure that can outperform existing string indexes.