 |
 |
|
|
| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
It is known that search operations in non-spatial databases can be optimised 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's possible to optimise spatial searches. The most typical of these are:
MySQL utilises 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.
| 11.6.1 Creating Spatial Indexes | ||
| 11.6.2 Using a Spatial Index |
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.
CREATE TABLE:
mysql> CREATE TABLE geom (g GEOMETRY NOT NULL, SPATIAL INDEX(g)); |
ALTER TABLE:
mysql> ALTER TABLE geom ADD SPATIAL INDEX(g); |
CREATE INDEX:
mysql> CREATE SPATIAL INDEX sp_index ON geom (g); |
To drop spatial indexes, use ALTER TABLE or DROP INDEX:
ALTER TABLE:
mysql> ALTER TABLE geom DROP INDEX g; |
DROP INDEX:
mysql> DROP INDEX sp_index ON geom; |
Example: Suppose that a table geom contains more than 32000 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> SHOW FIELDS FROM 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 optimiser 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 check the way this query is executed, using EXPLAIN:
mysql> EXPLAIN SELECT fid,AsText(g) FROM geom WHERE
mysql> MBRContains(GeomFromText('Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))'),g);
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | geom | range | g | g | 32 | NULL | 50 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)
|
Now let's check what would happen if we didn't have 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);
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| 1 | SIMPLE | geom | ALL | NULL | NULL | NULL | NULL | 32376 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
1 row in set (0.00 sec)
|
Let's execute the above query, 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 will also be used for optimising other functions. See section Functions For Testing Spatial Relations Between Geometric Objects.
| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] |
Hosting by: Hurra Communications Ltd.
Generated: 2007-01-26 17:58:46