Routing in MySQL - a memory aware approach

Abstract

Denne masteroppgaven ser på implementasjoner av routing / beregning av korteste sti i databaser og argumenterer for at selv om det finnes en implementasjon for PostgreSQL, så er det imperative grensesnittet brukt der suboptimalt i et databasesystem. For å demonstrere et alternativ implementerer oppgaven en prototype på en deklarativ routingmodul i MySQL, og undersøker noen av konsekvensene av å velge et slikt deklarativt grensesnitt. Prototypen blir eksperimentelt evaluert og det blir funnet at den bruker store mengder I/O, med påfølgende stort tidsforbruk som en konsekvens. En mer effektiv strategi for bruk av bufferet blir foreslått basert på resultatene fra evalueringen.

This thesis looks at implementations of routing / shortest path calculation in databases and argues that while there exists an implementation for PostgreSQL, its imperative approach is suboptimal in a database system. To demonstrate an alternative, the thesis implements a prototype of a declarative routing module in MySQL and examines some of the consequences of a declarative interface. The prototype is experimentally evaluated and found to use large amounts of I/O, with large time consumption as a consequence. A more effective buffering strategy is suggested based on the results from the evaluation.