Geospatial Routing Engine in MySQL

Abstract

Utvikling av en søkemotor for å finne korteste vei i geografiske grafer og integrering inn i MySQL for å danne en brukervennlig SQL funksjon. Tidligere var dette mulig i MySQL med brukerdefinerte rekursive funksjoner. En metode som både er mangelfull i ergonomi og funksjonalitet, men også generelt underpresterende. Implementasjonen laget i denne oppgaven har hovedsakelig to virkemåter. Enten er node geometri definert av brukeren, som forårsaker bruk av en passende heuristikk, eller så blir ingen heuristikk brukt. I løpet av ytelsestester ble det hintet til at løsningen brukt her er rundt tre og en halv gange raskere enn den gamle. Samtidig gjelder dette bare når man ikke bruker heuristikker. På grunn av den økte kompleksiteten og dataforbruket til romslige heuristikker ble det oppdaget at heuristikker gjorde metoden rundt tre ganger så treg som å ikke bruke heuristikker. Denne overraskende dårlige ytelsen ble til slutt bortforklart av de kortlevde grafstrukturene man får fra hver databasespørring.

Development of a geospatial routing engine and integration into MySQL to produce a user friendly SQL based method of deriving the shortest path between two nodes in a graph. Previously, this was possible in MySQL through use of recursive user defined functions. A method which is both lacking in ergonomics and functionality, but also generally underperforming. The implementation devised in this paper supports two modes. Either node geometry is declared by the user, in which case an appropriate heuristic will be used, or no heuristic is used. During performance testing it was indicated that this paper's method is roughly three and a half time faster than the old method. However, that was only the case when not applying heuristics. Given the increased data complexity and demand of spatial heuristics, using heuristics made the process three times slower compared to not using heuristics. This surprisingly poor performance was ultimately blamed on the ephemeral nature of graphs in dynamic query-based graph construction.