Spatial Index - Khi hai điều kiện phạm vi đụng nhau

Tìm kiếm theo vị trí địa lý (bounding box với kinh độ + vĩ độ) tạo ra HAI range condition - B+ tree chỉ tận dụng được MỘT.

Vấn đề

SELECT * FROM businesses
WHERE type = 'restaurant'
  AND longitude BETWEEN -74.0083 AND -73.9752
  AND latitude  BETWEEN  40.7216 AND  40.7422;
 
-- Index (type, longitude, latitude):
--   Bước 1: type='restaurant'     → equality, thu hẹp tốt ✓
--   Bước 2: longitude BETWEEN ... → range, quét ✓
--   Bước 3: latitude BETWEEN ...  → SAU range → KHÔNG thu hẹp được ✗
-- Với dữ liệu cả nước: longitude khớp = hàng triệu dòng
-- → Quét hàng triệu dòng chỉ để lọc latitude → CHẬM

Đây là Nguyên tắc 4 ở dạng không thể né: cả hai chiều đều là range thực sự.

Giải pháp: Spatial Index (R-tree thay vì B+ tree)

Loại index thiết kế riêng cho dữ liệu đa chiều:

-- PostgreSQL: kiểu GEOMETRY + GIST index
CREATE TABLE businesses (
    id BIGINT PRIMARY KEY,
    type VARCHAR(255) NOT NULL,
    location GEOMETRY(Point, 4326) NOT NULL  -- hệ tọa độ WGS 84
);
CREATE INDEX search_idx ON businesses USING GIST (type, location);
 
SELECT * FROM businesses
WHERE type = 'restaurant'
  AND location && ST_MakeEnvelope(-74.0083, 40.7216, -73.9752, 40.7422, 4326);
 
-- MySQL:
CREATE TABLE businesses (..., location POINT SRID 0 NOT NULL);
CREATE SPATIAL INDEX search_idx ON businesses (location);
SELECT * FROM businesses
WHERE type = 'restaurant'
  AND ST_CONTAINS(ST_MakeEnvelope(POINT(...), POINT(...)), location);

Khác biệt PostgreSQL vs MySQL

	PostgreSQL	MySQL
Nhiều cột trong spatial index	✓ (type + location cùng index)	✗ (chỉ 1 cột, phải lọc type riêng)
Hệ tọa độ SRID 4326 (độ cong trái đất)	✓	Một số hàm không hỗ trợ
Khoảng cách	Chính xác trên bề mặt cầu	Mặt phẳng (hơi sai với khoảng cách lớn)

Liên quan

• Range Condition phá vỡ Phễu - giới hạn B+ tree mà spatial index vượt qua
• B+ Tree - cấu trúc bị thay thế bằng R-tree ở đây
• Database Constraint - GIST còn dùng cho exclusion constraint