EXPLAIN EXTENDED

Many webmasters and network service providers keep a database of IP addresses that are not allowed to access their resources.

Such a database can be efficiently queried using MySQL's spatial abilities.

Let's create and fill the sample tables:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE t_ban (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
start INTEGER UNSIGNED NOT NULL,
end INTEGER UNSIGNED NOT NULL,
mask TINYINT NOT NULL,
geonetwork LINESTRING NOT NULL
) ENGINE=MyISAM;

CREATE SPATIAL INDEX sx_ban_geonetwork ON t_ban(geonetwork);

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(1000000);
COMMIT;

INSERT
INTO    t_ban (start, end, mask, geonetwork)
SELECT  @_start := network & (0xFFFFFFFF & ~((1 << mask) - 1)) AS start,
        @_end := network | (1 << mask) - 1 AS end,
        mask,
        GeomFromText(CONCAT('LINESTRING(', @_start, ' -1, ', @_end, ' 1)'))
FROM    (
        SELECT  (CAST(0x100000000 AS UNSIGNED) * RAND(20090404)) AS network,
                -FLOOR(LOG2(RAND(20090404 << 1))) AS mask
        FROM    filler
        ) q;

We have a database of randomly generated IP networks.

Normally, only two columns are required to identify a banned network: address (UNSIGNED INT) and mask (TINYINT). But in our table there are more columns, just to illustrate the task.

If someone tries to access the network resource, we take his address and check it against the database. First record found is enough to ban, that's why we can use LIMIT clause in our query:

SELECT  CONCAT(INET_NTOA(start), '/', mask)
FROM    t_ban
WHERE   INET_ATON('10.1.1.1') BETWEEN start AND end
LIMIT 1

Almost half a second, not good. On a busy service that can be a problem.

Now, let's see into the spatial data.

We keep our the network ranges as the euclidian plane entities.

Each banned range is kept as a line that starts at (start, -1) and ends at (end, 1). This range is the diagonal of its minimal bounding rectangle (MBR).

Therefore, any point with Y coordinate of 0 will be contained within this MBR if and only if its X coordinate lies between start and end.

If we encode the visitor's IP address in such a point, we can test if the point's MBR is contained within some other MBR in the database and deny access if it is.

To test if the point's MBR is contained in the LineString's MBR, we use MySQL function MBRContains which can be tested using the spatial indexes:

EXPLAIN EXTENDED
SELECT  CONCAT(INET_NTOA(start), '/', mask)
FROM    t_ban
WHERE   MBRContains(geonetwork, GeomFromText(CONCAT('POINT(', INET_ATON('10.1.1.1'), ' 0)')))
LIMIT 1

Now, let's run the query:

SELECT  CONCAT(INET_NTOA(start), '/', mask)
FROM    t_ban
WHERE   MBRContains(geonetwork, GeomFromText(CONCAT('POINT(', INET_ATON('10.1.1.1'), ' 0)')))
LIMIT 1

Almost instant.