EXPLAIN EXTENDED

How to create fast database queries

My latest article on SQL in general: 5 Claims About SQL, Explained. You're welcome to read and comment on it.

Banning IP’s

with 3 comments

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

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

CONCAT(INET_NTOA(start), '/', mask)
10.1.0.0/16
1 row fetched in 0.0001s (0.4971s)

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
id select_type table type possible_keys key key_len ref rows filtered Extra
1 SIMPLE t_ban range sx_ban_geonetwork sx_ban_geonetwork 32 1 100.00 Using where
1 row fetched in 0.0003s (0.0030s)

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
CONCAT(INET_NTOA(start), '/', mask)
10.1.0.0/16
1 row fetched in 0.0001s (0.0016s)

Almost instant.

Written by Quassnoi

April 4th, 2009 at 11:00 pm

Posted in MySQL

3 Responses to 'Banning IP’s'

Subscribe to comments with RSS or TrackBack to 'Banning IP’s'.

  1. Nice post, I’d probably try a standard index first though — given non-overlapping ranges, lookup in that should be fairly simple & efficient with performance = O(log N).

    Thomas W

    18 Oct 13 at 12:13

  2. Brilliant – this saved me a lot of frustration (I’m a spatial index newbie). Thanks.

    Just one thing I don’t understand – from my reading of the docs, MySQL only seems to support a 2-dimensional model – whereas IP address data is one dimensional. But is there a reason for defining the range as ( start -1, end 1) rather than (start 0, end 0)? Surely (ip 0) lies within both ranges?

    symcbean

    12 Dec 13 at 16:05

  3. @symcbean: R-Tree requires ordering its elements by area to function properly.

    If you used ((start, 0), (end, 0)), all elements would have zero area and be effectively not ordered.

    A proper implementation of R-Tree should have fallen back to perimeter comparison should the areas be equal, but MySQL does not do this.

    See here for more detail: http://explainextended.com/2010/02/01/join-on-overlapping-date-ranges/

    Quassnoi

    13 Dec 13 at 14:48

Leave a Reply