Bug #78213 Spatial index causes incorrect cardinality for all non-primary indexes
Submitted: 25 Aug 2015 20:03 Modified: 7 Oct 2015 17:19
Reporter: Christopher Middleton Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.6, 5.6.26, 5.5.46, 5.1.77 OS:Any (Mac OS X 10.9 and CentOS 6)
Assigned to: CPU Architecture:Any
Tags: cardinality, explain, Geometry, Optimizer, spatial index

[25 Aug 2015 20:03] Christopher Middleton
Description:
When a table contains a GEOMETRY column with a spatial index, the cardinality of all indexes except for the primary key is not calculated correctly.

This causes the query optimizer to avoid using the spatial index (or other indexes), which results in a select of type "ALL", causing a very large slowdown. This can be worked around by using FORCE INDEX whenever for each index you want to use (USE INDEX doesn't help).

In my case, it was the difference between a 5 second query on a zip code table and a 0.01 second query. On a larger table, this could be the difference between very fast service and a server-client connection timeout, so it's important to be fixed.

How to repeat:
While the table in my case was fairly big, you can see the effect on a table with only a few entries.

(1) First, let's make a table with a spatial index, for which the cardinality calculations are wrong.

CREATE TABLE geomtest (
  id INT NOT NULL AUTO_INCREMENT,
  name VARCHAR(10) NOT NULL,
  plot GEOMETRY NOT NULL,
  pet VARCHAR(5) NOT NULL,
  PRIMARY KEY (id),
  SPATIAL INDEX (plot),
  INDEX name (name),
  INDEX pet (pet)
);

# Note: the GeomFromWKB value below is meaningless and probably doesn't make sense in this context. Please ignore the specific value.

INSERT geomtest SET name = 'George', pet = 'cat', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'Sally', pet = 'cat', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'George', pet = 'dog', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'Sally', pet = 'dog', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'George', pet = 'bird', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'Sarah', pet = 'bird', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));
INSERT geomtest SET name = 'Sarah', pet = 'cat', plot = (GeomFromWKB(0x0101000000000000000000F03F000000000000F03F));

# etc.

SELECT id, name, pet, "..." as plot FROM geomtest;

+----+--------+------+------+
| id | name   | pet  | plot |
+----+--------+------+------+
|  1 | George | cat  | ...  |
|  2 | Sally  | cat  | ...  |
|  3 | George | dog  | ...  |
|  4 | Sally  | dog  | ...  |
|  5 | George | bird | ...  |
|  6 | Sarah  | bird | ...  |
|  7 | Sarah  | cat  | ...  |
+----+--------+------+------+

ANALYZE TABLE geomtest;

+------------------+---------+----------+----------+
| Table            | Op      | Msg_type | Msg_text |
+------------------+---------+----------+----------+
| imaging.geomtest | analyze | status   | OK       |
+------------------+---------+----------+----------+

SHOW INDEXES FROM geomtest;

+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+
| geomtest |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL | NULL   |      | BTREE      | 
| geomtest |          1 | plot     |            1 | plot        | A         |           1 |       32 | NULL   |      | SPATIAL    |
| geomtest |          1 | name     |            1 | name        | A         |           1 |     NULL | NULL   |      | BTREE      |
| geomtest |          1 | pet      |            1 | pet         | A         |           1 |     NULL | NULL   |      | BTREE      |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+

# (!) Note the "1" in the Cardinality column for each index except for the PRIMARY index.

(2) Make this table with the GEOMETRY column but without the SPATIAL INDEX and you will get: 

+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+
| Table     | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type |
+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+
| geomtest2 |          0 | PRIMARY  |            1 | id          | A         |           5 |     NULL | NULL   |      | BTREE      |
| geomtest2 |          1 | name     |            1 | name        | A         |           2 |     NULL | NULL   |      | BTREE      |
| geomtest2 |          1 | pet      |            1 | pet         | A         |           5 |     NULL | NULL   |      | BTREE      |
+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+

So it appears to be the existence of the spatial index and not the GEOMETRY column itself that causes that "Cardinality" error.

Suggested fix:
Whatever is calculating the cardinalities needs to be fixed when a SPATIAL INDEX is used.
[25 Aug 2015 22:49] Christopher Middleton
> This causes the query optimizer to avoid using the spatial index (or other indexes)

This is incorrect. It should say "This causes the query optimizer to avoid using the indexes." I don't know whether or not the spatial index also suffers from the query optimization error caused by a cardinality of 1.
[4 Sep 2015 7:25] Umesh Shastry
Hello Christopher Middleton,

Thank you for the report and test case.

Thanks,
Umesh
[4 Sep 2015 7:25] Umesh Shastry
// with myisam - 5.6.26, 5.5.46 - affected

mysql> SHOW INDEXES FROM geomtest;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| geomtest |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | plot     |            1 | plot        | A         |           1 |       32 | NULL   |      | SPATIAL    |         |               |
| geomtest |          1 | name     |            1 | name        | A         |           1 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | pet      |            1 | pet         | A         |           1 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)

mysql> drop index plot on geomtest;
Query OK, 7 rows affected (0.02 sec)
Records: 7  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE geomtest;
+---------------+---------+----------+----------+
| Table         | Op      | Msg_type | Msg_text |
+---------------+---------+----------+----------+
| test.geomtest | analyze | status   | OK       |
+---------------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> SHOW INDEXES FROM geomtest;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| geomtest |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | name     |            1 | name        | A         |           3 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | pet      |            1 | pet         | A         |           3 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
3 rows in set (0.00 sec)
[4 Sep 2015 7:26] Umesh Shastry
// 5.7.9 ( Innodb used )

mysql> show variables like '%version%';
+-------------------------+---------------------------------------------------------+
| Variable_name           | Value                                                   |
+-------------------------+---------------------------------------------------------+
| innodb_version          | 5.7.9                                                   |
| protocol_version        | 10                                                      |
| slave_type_conversions  |                                                         |
| version                 | 5.7.9-enterprise-commercial-advanced                    |
| version_comment         | MySQL Enterprise Server - Advanced Edition (Commercial) |
| version_compile_machine | x86_64                                                  |
| version_compile_os      | linux-glibc2.5                                          |
+-------------------------+---------------------------------------------------------+
7 rows in set, 1 warning (0.01 sec)

mysql> SHOW INDEXES FROM geomtest;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| geomtest |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | plot     |            1 | plot        | A         |           7 |       32 | NULL   |      | SPATIAL    |         |               |
| geomtest |          1 | name     |            1 | name        | A         |           3 |     NULL | NULL   |      | BTREE      |         |               |
| geomtest |          1 | pet      |            1 | pet         | A         |           3 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)
[4 Sep 2015 7:37] Umesh Shastry
// 5.1.77(myisam) - same as 5.5, 5.6

mysql> SHOW INDEXES FROM geomtest;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| geomtest |          0 | PRIMARY  |            1 | id          | A         |           7 |     NULL | NULL   |      | BTREE      |         |
| geomtest |          1 | plot     |            1 | plot        | A         |           1 |       32 | NULL   |      | SPATIAL    |         |
| geomtest |          1 | name     |            1 | name        | A         |           1 |     NULL | NULL   |      | BTREE      |         |
| geomtest |          1 | pet      |            1 | pet         | A         |           1 |     NULL | NULL   |      | BTREE      |         |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
4 rows in set (0.00 sec)

mysql> show variables like '%version%';
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| protocol_version        | 10                  |
| version                 | 5.1.77              |
| version_comment         | Source distribution |
| version_compile_machine | x86_64              |
| version_compile_os      | unknown-linux-gnu   |
+-------------------------+---------------------+
5 rows in set (0.00 sec)
[4 Sep 2015 8:02] Norvald Ryeng
Posted by developer:
 
Only affects MyISAM, not InnoDB.
[7 Oct 2015 17:19] Paul Dubois
Noted in 5.8.0 changelog.

Adding a SPATIAL index to a MyISAM table could cause the cardinality
of other indexes to become incorrect.
[23 Oct 2015 12:55] Paul Dubois
Noted in 5.7.10 changelog.