Since my last post I've found out that using the 'morton' number to index spatial number is also referred to as the Z-order.
To index using this order, you can use this stored function:
CREATE FUNCTION getGeoMorton(lat DOUBLE, lng DOUBLE) RETURNS BIGINT UNSIGNED DETERMINISTIC
BEGIN
-- 11930464 is round(maximum value of a 32bit integer / 360 degrees)
DECLARE bit, morton, pos BIGINT UNSIGNED DEFAULT 0;
SET @lat = CAST((lat + 90) * 11930464 AS UNSIGNED);
SET @lng = CAST((lng + 180) * 11930464 AS UNSIGNED);
SET bit = 1;
WHILE bit <= @lat || bit <= @lng DO
IF(bit & @lat) THEN SET morton = morton | ( 1 << (2 * pos + 1)); END IF;
IF(bit & @lng) THEN SET morton = morton | ( 1 << (2 * pos)); END IF;
SET pos = pos + 1;
SET bit = 1 << pos;
END WHILE;
RETURN morton;
END;
Some caveats
- Since the function is using floating-point numbers, there will be rounding errors. These are generally very small, and for us well within the acceptable margin of error.
- More significantly, this function assumes euclidean geometry (i.e.: a flat surface). The earth obviously isn't, so as you get closer to the poles you might get back results from outside your rectangle, or miss results from within.
- It's not recommended to use this function directly in your WHERE clause. Even though the function is marked deterministic (i.e.: it will always yield the same results for the same arguments), the MySQL query optimizer currently ignored that modifier. So, set it in a temporary variable first (SET @number =) and use the variable in your where clause.
- Don't forget dealing with queries spanning over the -180°, 180° longitude line.
- Also store your actual longitude and latitude values in the DB. This function is not intended to be exact.
- When you do your queries, select both on the morton number, and longitude and latitude.
A better way to do it?
In my research I've found the Hilbert Curve to be an even better algorithm, but haven't yet gone through the effort of trying to express it in SQL.