Bug #67889 Non-spatial index on a POINT column yields incorrect spatial query results

• Submitted: 12 Dec 2012 21:02
• Modified: 1 Feb 2013 17:18
• Reporter: Karlos Abel
• Status: Closed
• Category: MySQL Server: GIS
• Severity: S2 (Serious)
• Version: 5.1.68, 5.5.31, 5.6.8
• OS: Linux
• Assigned to: Jørgen Løland
• CPU Architecture: Any

[12 Dec 2012 21:02] Karlos Abel

Description:
Contains/Within queries on a table with a non-spatial, non-unique index on a POINT column with no NULL values returns zero results.  If the key is removed or ignored, or a spatial index on the same column is forced, the correct results are returned for the same query.

The behavior was first observed using ST_Contains, but can be replicated with ST_Contains, ST_Within, MBRContains, MBRWithin, Contains, and Within.

The issue could not be reproduced using MySQL version 5.5.28 and Contains/Within.

How to repeat:
-- (spatial data shamelessly cribbed from http://bugs.mysql.com/bug.php?id=64533)

DROP TABLE IF EXISTS spatial_test;
CREATE TABLE spatial_test (
      id INT UNSIGNED NOT NULL AUTO_INCREMENT
    , shape_data POLYGON NOT NULL
    , PRIMARY KEY (id)
    , SPATIAL KEY s_idx_shape_data(shape_data)
) ENGINE=MyISAM;

-- Populate with two polygons, only ID: 2 should show up in any subsequent queries.
INSERT INTO spatial_test (shape_data)
VALUES
      (GeomFromText('POLYGON((37.961911 23.731155,37.965159 23.752441,37.977068 23.753128,37.977068 23.728065,37.961911 23.731155))'))
    , (GeomFromText('POLYGON((38.034195 23.840504,38.016413 23.845568,38.019186 23.873892,38.050524 23.875523,38.034195 23.840504))'))
;

DROP TABLE IF EXISTS point_test;
CREATE TABLE point_test (
      id INT UNSIGNED NOT NULL AUTO_INCREMENT
    , point_data POINT NOT NULL
    , PRIMARY KEY (id)
    , SPATIAL KEY s_idx_point_data(point_data)
    , KEY idx_point_data(point_data)
) ENGINE=MyISAM;

-- Populate with two points, alternating to fill the table to a point where the query optimizer will not employ a full-table scan.  Only even-numbered points should appear in subsequent queries.
INSERT INTO point_test (point_data)
VALUES
      (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
    , (GeomFromText('Point(37.0248492 23.8512726)'))
    , (GeomFromText('Point(38.0248492 23.8512726)'))
;
 
-- Returns ID: 2
SELECT id
FROM spatial_test
WHERE ST_Contains(shape_data, GeomFromText('Point(38.0248492 23.8512726)'))
;

-- Returns all even-numbered IDs.
SELECT id
FROM point_test
WHERE ST_Contains(point_data, GeomFromText('Point(38.0248492 23.8512726)'))
;

-- Should return all even-numbered IDs, returns empty set.
SELECT
      point_test.id
    , spatial_test.id
FROM spatial_test, point_test
WHERE (ST_Contains(shape_data, point_data))
;

-- Returns all even-numbered IDs
SELECT
      point_test.id
    , spatial_test.id
FROM spatial_test FORCE INDEX(s_idx_shape_data), point_test IGNORE INDEX(idx_point_data)
WHERE (ST_Contains(shape_data, point_data))
;

-- Should return all even-numbered IDs, returns empty set.
SELECT
      point_test.id
    , spatial_test.id
FROM spatial_test IGNORE INDEX(s_idx_shape_data), point_test USE INDEX(idx_point_data)
WHERE (ST_Contains(shape_data, point_data))
;

[12 Dec 2012 23:56] Sveta Smirnova

Thank you for the report.

Verified as described.

[30 Jan 2013 14:25] Jørgen Løland

With a slight rewrite of the test case, the problem is reproducible in all
versions from 5.1 and up:

CREATE and INSERT as described in "how to", then rewrite "WHERE Contains
(shape_data, point_data)" to "WHERE Within(point_data, shape_data)":

---
# Output from 5.1.68
# Should return all even-numbered IDs, returns empty set.
# Contains

SELECT point_test.id, spatial_test.id
FROM spatial_test, point_test force index(idx_point_data)
WHERE (Contains(shape_data, point_data));
id      id
2       2
4       2
6       2
...
62      2
64      2
66      2

# Rewritten to Within
SELECT point_test.id, spatial_test.id
FROM spatial_test, point_test force index(idx_point_data)
WHERE (Within(point_data, shape_data));
id      id

^empty set
-----
Non-spatial indexes only support exact match lookup for spatial columns. In this bug, range access on a non-spatial index is used for a CONTAINS comparison operator over a POINT column. Range access should not be used for such cases.

[1 Feb 2013 17:18] Paul DuBois

Noted in 5.6.11, 5.7.1 changelogs.

Nonspatial indexes only support exact-match lookups for spatial
columns, but the optimizer incorrectly used range access in some
cases, leading to incorrect results.