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.
Database cracking
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. Hierdoor onstaat volgens Idreos automatisch een steeds betere sortering, waardoor bij elke volgende opdracht sneller een antwoord wordt gevonden. Omdat vooraf geen zoekindex wordt ontwikkeld bespaart de nieuwe techniek volgens de onderzoeker bovendien 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.'
Hoe kan je nu sneller zoeken als je eerst moet sorteren tijdens je zoekopdracht? Als je eerst sorteert (buiten productie tijd of op schaduw gegevens) en dan zoekt is volgens mij altijd sneller in het zoeken. Hoe gaat het algoritme om met een andere zoekmogelijkheid bv alle tweeën in een stapel kaarten. Hoe slaat hij deze sortering vervolgens op? (Index?) Vol verwachting tot Hugo’s proefschrift openbaar wordt.
Lees net over het amerikaanse Palantir (zie ook Techcrunch), denk dat die nog een stap of twee verder zijn …
Dat is wat een huidige database met caching probeert te realiseren. Lijkt me interessant te weten hoe dit werkt.
Zou graag een proefschrift hebben.
Alle harten netjes bij elkaar leggen en dan blijkt dat er de volgende keer op zwart gezocht wordt of op kaarten met een scheurtje erin. Zou leuk zijn als het systeem een index zou maken voor veel gebruikte zoekopdrachten of voor zoekopdrachten die moeilijk zijn en daardoor normaliter (te) lang duren. Als dat bedoeld wordt heeft men wel een omslachtige manier gevonden om het uit te leggen.
Ik weet ook niet precies wat ze hier bedoelen.
Indexen bouwen over indexen heen?