Implementing Z-ordering as Spatial Index in MySQL

Abstract

I denne masteroppgaven ble Z-ordering implementert og integrert i MySQL Server som en prototyp for indeksering av geografiske data. Prototypen sammenlignes mot MySQL's R-tre for vinduspørringer på en stort (4 millioner) datasett av geografiske punkter.

Eksperimentene viser as R-treet yter bedre enn prototypen. Men det oppdages også at indeksen i prototypen har en dårlig og inkonsistent filtrerings-nøyaktighet. Uten en algoritme som reduserer søkeintervallet av Z-verdier i et vindu så er vinduer i prototypen utsatt for mulige "uheldige" krysninger av store delelinjer i rutenettet. Dette leder til en potensielt enorm mengde av rader som blir returnert fra indeksen - selv om mengden av rader i resultatet er liten.

Selv om det ikke ble testet gjennom eksperimenter så viser de registrerte tidene for opprettelse av indekser at prototypen var signifikant raskere enn R-treet.

I tillegg ble rutenettet som manifesteres som følge av å bruke Z-order-kurven til å inndele jorden utforsket. Forskjellige aspekter ved rutenettet blir presentert og diskutert. De varierende celle-størrelsene og det at celle-kantene ikke følger den korteste veien mellom to punkter vises å være særlig utfordrende. Kort sagt, kurvingen av jorden gjør at spesielle hensyn må tas for nedbrytning av geometrier til celler og for k-NN søk.

In this thesis, Z-ordering is implemented and integrated into MySQL Server to serve as a prototype spatial index. The prototype is compared to MySQL's R-tree for window queries on a large (4 million) data set of geographic points.

The experiments show that the R-tree outperforms the prototype. However, it is also discovered that the prototype index exhibits poor and inconsistent filtering accuracy. Without an algorithm that prunes the search range of Z-values in a window, it is susceptible to crossing 'unlucky' borders in the grid, leading to a potentially enormous amount of rows being returned from the index - even though the amount of rows in the result is small.

Although not tested through experiments, the indexing times recorded during the experiment setup showed that the prototype's indexing time was significantly faster than the R-tree's time.

Additionally, the grid that is manifested as a result of applying the Z-order curve to Earth is explored. Various aspects of the grid are presented and discussed. In particular, the varying cell sizes and non-geodesic cell sides/edges are shown to be problematic. In short, the curvature of the Earth mandates special considerations for geometry decomposition and k-NN search.