Search operations in non-spatial databases can be optimized using indexes. This is true for spatial databases as well. With the help of a great variety of multi-dimensional indexing methods that have already been designed, it is possible to optimize spatial searches. The most typical of these are:
Point queries that search for all objects that contain a given point
Region queries that search for all objects that overlap a given region
MySQL uses R-Trees with quadratic splitting to index spatial columns. A spatial index is built using the MBR of a geometry. For most geometries, the MBR is a minimum rectangle that surrounds the geometries. For a horizontal or a vertical linestring, the MBR is a rectangle degenerated into the linestring. For a point, the MBR is a rectangle degenerated into the point.
MySQL can create spatial indexes using syntax similar to that for creating regular indexes, but extended with the SPATIAL keyword. Spatial columns that are indexed currently must be declared NOT NULL. The following examples demonstrate how to create spatial indexes.
With CREATE TABLE:
mysql> CREATE TABLE geom (g GEOMETRY NOT NULL, SPATIAL INDEX(g));
With ALTER TABLE:
mysql> ALTER TABLE geom ADD SPATIAL INDEX(g);
With CREATE INDEX:
mysql> CREATE SPATIAL INDEX sp_index ON geom (g);
To drop spatial indexes, use ALTER TABLE or DROP INDEX:
With ALTER TABLE:
mysql> ALTER TABLE geom DROP INDEX g;
With DROP INDEX:
mysql> DROP INDEX sp_index ON geom;
Example: Suppose that a table geom contains more than 32,000 geometries, which are stored in the column g of type GEOMETRY. The table also has an AUTO_INCREMENT column fid for storing object ID values.
mysql> DESCRIBE geom; +-------+----------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------+----------+------+-----+---------+----------------+ | fid | int(11) | | PRI | NULL | auto_increment | | g | geometry | | | | | +-------+----------+------+-----+---------+----------------+ 2 rows in set (0.00 sec) mysql> SELECT COUNT(*) FROM geom; +----------+ | count(*) | +----------+ | 32376 | +----------+ 1 row in set (0.00 sec)
To add a spatial index on the column g, use this statement:
mysql> ALTER TABLE geom ADD SPATIAL INDEX(g); Query OK, 32376 rows affected (4.05 sec) Records: 32376 Duplicates: 0 Warnings: 0
The optimizer investigates whether available spatial indexes can be involved in the search for queries that use a function such as MBRContains() or MBRWithin() in the WHERE clause. For example, let's say we want to find all objects that are in the given rectangle:
mysql> SELECT fid,AsText(g) FROM geom WHERE
mysql> MBRContains(GeomFromText('Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))'),g);
+-----+-----------------------------------------------------------------------------+
| fid | AsText(g) |
+-----+-----------------------------------------------------------------------------+
| 21 | LINESTRING(30350.4 15828.8,30350.6 15845,30333.8 15845,30333.8 15828.8) |
| 22 | LINESTRING(30350.6 15871.4,30350.6 15887.8,30334 15887.8,30334 15871.4) |
| 23 | LINESTRING(30350.6 15914.2,30350.6 15930.4,30334 15930.4,30334 15914.2) |
| 24 | LINESTRING(30290.2 15823,30290.2 15839.4,30273.4 15839.4,30273.4 15823) |
| 25 | LINESTRING(30291.4 15866.2,30291.6 15882.4,30274.8 15882.4,30274.8 15866.2) |
| 26 | LINESTRING(30291.6 15918.2,30291.6 15934.4,30275 15934.4,30275 15918.2) |
| 249 | LINESTRING(30337.8 15938.6,30337.8 15946.8,30320.4 15946.8,30320.4 15938.4) |
| 1 | LINESTRING(30250.4 15129.2,30248.8 15138.4,30238.2 15136.4,30240 15127.2) |
| 2 | LINESTRING(30220.2 15122.8,30217.2 15137.8,30207.6 15136,30210.4 15121) |
| 3 | LINESTRING(30179 15114.4,30176.6 15129.4,30167 15128,30169 15113) |
| 4 | LINESTRING(30155.2 15121.4,30140.4 15118.6,30142 15109,30157 15111.6) |
| 5 | LINESTRING(30192.4 15085,30177.6 15082.2,30179.2 15072.4,30194.2 15075.2) |
| 6 | LINESTRING(30244 15087,30229 15086.2,30229.4 15076.4,30244.6 15077) |
| 7 | LINESTRING(30200.6 15059.4,30185.6 15058.6,30186 15048.8,30201.2 15049.4) |
| 10 | LINESTRING(30179.6 15017.8,30181 15002.8,30190.8 15003.6,30189.6 15019) |
| 11 | LINESTRING(30154.2 15000.4,30168.6 15004.8,30166 15014.2,30151.2 15009.8) |
| 13 | LINESTRING(30105 15065.8,30108.4 15050.8,30118 15053,30114.6 15067.8) |
| 154 | LINESTRING(30276.2 15143.8,30261.4 15141,30263 15131.4,30278 15134) |
| 155 | LINESTRING(30269.8 15084,30269.4 15093.4,30258.6 15093,30259 15083.4) |
| 157 | LINESTRING(30128.2 15011,30113.2 15010.2,30113.6 15000.4,30128.8 15001) |
+-----+-----------------------------------------------------------------------------+
20 rows in set (0.00 sec)
Now let's use EXPLAIN to check the way this query is executed (the id column has been removed so the output better fits the page):
mysql> EXPLAIN SELECT fid,AsText(g) FROM geom WHERE
mysql> MBRContains(GeomFromText('Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))'),g);
+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| SIMPLE | geom | range | g | g | 32 | NULL | 50 | Using where |
+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)
Now let's check what would happen without a spatial index:
mysql> EXPLAIN SELECT fid,AsText(g) FROM g IGNORE INDEX (g) WHERE
mysql> MBRContains(GeomFromText('Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))'),g);
+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| SIMPLE | geom | ALL | NULL | NULL | NULL | NULL | 32376 | Using where |
+-------------+-------+------+---------------+------+---------+------+-------+-------------+
1 row in set (0.00 sec)
Let's execute the SELECT statement, ignoring the spatial key we have:
mysql> SELECT fid,AsText(g) FROM geom IGNORE INDEX (g) WHERE
mysql> MBRContains(GeomFromText('Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))'),g);
+-----+-----------------------------------------------------------------------------+
| fid | AsText(g) |
+-----+-----------------------------------------------------------------------------+
| 1 | LINESTRING(30250.4 15129.2,30248.8 15138.4,30238.2 15136.4,30240 15127.2) |
| 2 | LINESTRING(30220.2 15122.8,30217.2 15137.8,30207.6 15136,30210.4 15121) |
| 3 | LINESTRING(30179 15114.4,30176.6 15129.4,30167 15128,30169 15113) |
| 4 | LINESTRING(30155.2 15121.4,30140.4 15118.6,30142 15109,30157 15111.6) |
| 5 | LINESTRING(30192.4 15085,30177.6 15082.2,30179.2 15072.4,30194.2 15075.2) |
| 6 | LINESTRING(30244 15087,30229 15086.2,30229.4 15076.4,30244.6 15077) |
| 7 | LINESTRING(30200.6 15059.4,30185.6 15058.6,30186 15048.8,30201.2 15049.4) |
| 10 | LINESTRING(30179.6 15017.8,30181 15002.8,30190.8 15003.6,30189.6 15019) |
| 11 | LINESTRING(30154.2 15000.4,30168.6 15004.8,30166 15014.2,30151.2 15009.8) |
| 13 | LINESTRING(30105 15065.8,30108.4 15050.8,30118 15053,30114.6 15067.8) |
| 21 | LINESTRING(30350.4 15828.8,30350.6 15845,30333.8 15845,30333.8 15828.8) |
| 22 | LINESTRING(30350.6 15871.4,30350.6 15887.8,30334 15887.8,30334 15871.4) |
| 23 | LINESTRING(30350.6 15914.2,30350.6 15930.4,30334 15930.4,30334 15914.2) |
| 24 | LINESTRING(30290.2 15823,30290.2 15839.4,30273.4 15839.4,30273.4 15823) |
| 25 | LINESTRING(30291.4 15866.2,30291.6 15882.4,30274.8 15882.4,30274.8 15866.2) |
| 26 | LINESTRING(30291.6 15918.2,30291.6 15934.4,30275 15934.4,30275 15918.2) |
| 154 | LINESTRING(30276.2 15143.8,30261.4 15141,30263 15131.4,30278 15134) |
| 155 | LINESTRING(30269.8 15084,30269.4 15093.4,30258.6 15093,30259 15083.4) |
| 157 | LINESTRING(30128.2 15011,30113.2 15010.2,30113.6 15000.4,30128.8 15001) |
| 249 | LINESTRING(30337.8 15938.6,30337.8 15946.8,30320.4 15946.8,30320.4 15938.4) |
+-----+-----------------------------------------------------------------------------+
20 rows in set (0.46 sec)
When the index is not used, the execution time for this query rises from 0.00 seconds to 0.46 seconds.
In future releases, spatial indexes may also be used for optimizing other functions. See the section called “Functions for Testing Spatial Relations Between Geometric Objects”.