Database Cracking zal zoekresultaten versnellen

2 juli 2010

Onderzoeker Stratos Idreos van het Centrum Wiskunde & Informatica (CWI) in Amsterdam heeft een techniek ontwikkeld om grote databestanden sneller te doorzoeken. Hij noemt zijn methode ‘database cracking’. Daarbij wordt bij elke zoekopdracht de data opnieuw gesorteerd. Daardoor ontstaat een steeds betere sortering en kan bij elke volgende zoekopdracht het antwoord sneller worden gevonden. Binnen de databasetechnologie worden zoekopdracht meestal uitgevoerd via index-structuren. Daarbij wordt vantevoren een zoekindex opgezet en vastgelegd. Idreos claimt de eerste techniek ontwikkeld te hebben waarbij het databasesysteem de rol van de beheerder overneemt. Idreos verdedigt zijn proefschrift 24 juni 2010 aan de Universiteit van Amsterdam.


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 Idreos 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.

 

Share This:

Leave a Reply

Your email address will not be published. Required fields are marked *