Wie ooit in een bibliotheek een boek heeft gezocht, kent het voordeel van een goede catalogus. In databases bestaat zo’n ‘catalogus’ ofwel een index ook: een hulpmiddel waarmee je sneller vindt wat je zoekt. Maar het maken en bijhouden van een index kost tijd, geld en opslagruimte – daarom ontbreken indexen vaak. ‘Dat was de aanleiding voor de auteurs om alles op zijn kop te zetten’, vertelt Peter Boncz, groepsleider van Database Architectures, waaraan de auteurs destijds verbonden waren.
Het idee achter cracking
Hun idee was om tijdens het zoeken alvast een beetje op te ruimen. Database cracking noemden ze het, als in: data opbreken in hanteerbare stukjes. Het idee achter “cracking” is eenvoudig. Stel: je kamer is rommelig en je zoekt steeds je gymtas. Je kunt twee dingen doen: je ruimt eerst de hele kamer perfect op, ook op plekken waar je nooit komt (wat veel tijd kost), of je ruimt alleen op waar je op dat moment iets nodig hebt, en als je daar vaak komt, wordt dat hoekje steeds netter.
Dat tweede is het idee van database cracking. In plaats van vooraf alles netjes te ordenen, gebruikt de database elke zoekvraag als aanleiding om een klein deel van de data handiger neer te leggen voor volgende zoekvragen. In het artikel noemen de auteurs dit “continue fysieke reorganisatie”, waarbij de data in steeds beter bruikbare “stukjes” wordt verdeeld. Bovendien onthoudt het systeem welke stukjes waar liggen, zodat het bij een volgende vraag niet meer overal hoeft te kijken.
Het gevolg: delen van de database waar vaak gezocht wordt, worden steeds sneller toegankelijk. Delen waar nooit iemand zoekt, blijven ongeordend omdat opruimen daar niets oplevert.
Zelflerend systeem
Boncz noemt het idee interessant “omdat eindgebruikers niet alle indexerings-trucs kennen” en omdat de database de data niet per se hoeft te organiseren in de volgorde waarin die ooit is ingevoerd. “Het leuke van cracking is bovendien dat je geen mensen nodig hebt die weten hoe je een database moet indexeren.” Het systeem leert zichzelf als het ware aan hoe het sneller moet zoeken.
Dat CIDR nu juist dit artikel bekroont, past bij het karakter van de prijs. De Test-of-Time Award is bedoeld voor onderzoek dat na jaren nog steeds richting geeft aan het vakgebied. De auteurs ontvangen de award “voor het openen van een nieuwe onderzoeksrichting naar continue fysieke reorganisatie op basis van het zoekvragenpatroon”. Boncz benadrukt dat Database Cracking vooral wetenschappelijke impact had: er verschenen veel vervolgstudies die varianten op cracking onderzochten. “In de praktijk wordt dit nog niet gebruikt. Dat komt omdat het opruimen relatief duur is, maar daar wordt aan gewerkt. Het idee leeft dus nog wel voort.”
Over de auteurs
De bekroonde publicatie is geschreven door drie onderzoekers die destijds bij de Database Architectures (DA) groep van CWI werkten:
- Stefan Manegold is als senior onderzoeker nog steeds verbonden aan de DA groep, en stond eerder aan het hoofd van deze groep.
- Eerste auteur Stratos Idreos was in 2007 PhD student bij Manegold en Kersten. Database Cracking vormde de basis voor zijn promotieonderzoek. Zijn proefschrift won de ACM SIGMOD Jim Gray Doctoral Dissertation Award 2011, en hij ontving daarnaast de ERCIM Cor Baayen Early Career Researcher Award. Idreos is tegenwoordig hoogleraar aan Harvard's John A. Paulson School of Engineering and Applied Sciences.
- Martin Kersten (1953–2022) was in 2007 groepsleider van de DA groep en werd in 2011 benoemd tot CWI Fellow.
Over CIDR
CIDR staat voor Conference on Innovative Data Systems Research: een internationale conferentie over nieuwe ideeën in datasystemen. CIDR is in 2002 opgezet als podium voor vernieuwende systeemarchitecturen naast de grote “mainstream” databaseconferenties. Het eerste congres vond in 2003 plaats.
Sinds 2020 is CIDR jaarlijks en wisselt de locatie tussen Amsterdam en de VS. Dit jaar vindt CIDR plaats in de VS (Santa Cruz, CA) van 18-21 januari, waar Stefan Manegold en Stratos Idreos de Test of Time award in ontvangst zullen nemen.
