MySQL Bugs: #78213: Spatial index causes incorrect cardinality for all non-primary indexes

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

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.

> 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.

Hello Christopher Middleton,

Thank you for the report and test case.

Thanks,
Umesh

// 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)

// 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)

// 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)

Posted by developer:
 
Only affects MyISAM, not InnoDB.

Noted in 5.8.0 changelog.

Adding a SPATIAL index to a MyISAM table could cause the cardinality
of other indexes to become incorrect.

Noted in 5.7.10 changelog.