Nieuwe techniek database cracking versnelt zoekproces in grote databestanden

Digitale bestanden van bedrijven en organisaties worden steeds omvangrijker. Ook in de wetenschap komen steeds grotere hoeveelheden data beschikbaar uit bijvoorbeeld sterrenkundige waarnemingen en DNA-analyses. Om in deze steeds groter wordende datasets de juiste informatie te vinden zijn nieuwe eisen aan databasetechnologieën nodig.

Publication date: 25-06-2010

 

Digitale bestanden van bedrijven en organisaties worden steeds omvangrijker. Ook in de wetenschap komen steeds grotere hoeveelheden data beschikbaar uit bijvoorbeeld sterrenkundige waarnemingen en DNA-analyses. Om in deze steeds groter wordende datasets de juiste informatie te vinden zijn nieuwe eisen aan databasetechnologieën nodig. In zijn proefschrift ‘Database Cracking: Towards Auto-tuning Database Kernels’ ontwikkelde Stratos Idreos van het Centrum Wiskunde & Informatica (CWI) in Amsterdam, een nieuwe techniek waarmee het zoekproces kan worden versneld.

Of we nu online onze bankzaken regelen, een vliegticket boeken of een digitaal bestand van de overheid raadplegen, dagelijks maken we op grote schaal gebruik van databasetechnologie. Om de meest optimale manier te vinden om een zoekopdracht uit te voeren worden index-structuren gebruikt. Van te voren wordt hierin een zoekindex opgezet en vastgelegd waar mensen naar zoeken. Het nadeel van index-structuren is dat het aanmaken en onderhouden veel tijd en ruimte van de beheerder in beslag nemen en daarmee een kostbaar proces zijn geworden. De door Idreos ontwikkelde techniek, database cracking,  is de eerste techniek waarbij het databasesysteem de rol van de beheerder overneemt en zelf over een aanpassend vermogen beschikt. Idreos promoveerde 24 juni aan de Universiteit van Amsterdam

Bij database cracking wordt niet alles vooraf precies geïndexeerd. Bij elke nieuwe zoekopdracht wordt de data hergesorteerd. Het systeem schrijft de data in een nieuwe volgorde terug waardoor automatisch een steeds betere sortering ontstaat en bij elke volgende opdracht sneller een antwoord wordt gevonden. Omdat vooraf geen zoekindex wordt ontwikkeld, bespaart de nieuwe techniek veel tijd en kosten.  Idreos licht het principe toe aan de hand van een stapel ongeordende speelkaarten: “Als een gebruiker vraagt naar een harten twee, kan het systeem ook wel meteen alle harten die het onderweg tegenkomt op een stapel met alleen harten leggen en alle niet-harten op een tweede stapel. Bij een volgende vraag naar alle klaveren weet het syteem dat het alleen hoeft te zoeken in de stapel niet-harten.“

De database cracking methode is door de onderzoeksgroep Database Architectures van het CWI  toegepast op de Sloan Digital Sky Server, de grootste wetenschappelijke database ter wereld die ruim drie terabyte aan gegevens over waargenomen sterren bevat. In deze database kon met de cracking techniek het zoekproces met factor tien tot twintig worden versneld. Het platform voor de Sloan Digital Sky Server is gerealiseerd met het door het CWI ontwikkelde open-source database systeem MonetDB dat wereldwijd wordt gebruikt.