mysql> -- Исходные данные
mysql> CREATE TABLE `m` (
    ->   `id` INT,
    ->   `x1` INT,
    ->   `y1` INT,
    ->   `x2` INT,
    ->   `y2` INT
    -> );
Query OK, 0 rows affected (0.03 sec)

mysql> INSERT INTO `m` (`id`, `x1`, `y1`, `x2`, `y2`) VALUES
    -> (1, 3, 0, 6, 4),
    -> (2, 8, 0, 9, 2),
    -> (3, 0, 1, 2, 2),
    -> (4, 0, 3, 2, 5),
    -> (5, 7, 3, 9, 7),
    -> (6, 1, 6, 6, 7),
    -> (7, 1, 8, 2, 10);
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

mysql>
mysql> -- Промежуточная таблица (но можно было добавить и поле в исходную)
mysql> CREATE TABLE p(id INT, rng GEOMETRY);
Query OK, 0 rows affected (0.02 sec)

mysql> INSERT INTO p (id,rng) SELECT id,ST_GeomFromText(CONCAT('Polygon((',x1,' ',y1,',',x1,' ',y2,',',x2,' ',y2,',',x2,' ',y1,',',x1,' ',y1,'))')) FROM m;
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

mysql>
mysql> -- Временная таблица, в реальном запросе не создаётся, используется как подзапрос
mysql> CREATE TEMPORARY TABLE x(x1 int, y1 int, p GEOMETRY);
Query OK, 0 rows affected (0.11 sec)

mysql> INSERT INTO x(x1, y1, p)
    -> SELECT x1,y1, ST_GeomFromText(CONCAT('Polygon((',x1+0.5,' ',y1+0.5,',',x1+0.5,' ',y1+1.5,',',x1+1.5,' ',y1+1.5,',',x1+1.5,' ',y1+0.5,',',x1+0.5,' ',y1+0.5,'))'))
    -> FROM (SELECT 0 x1 UNION ALL
    ->    SELECT 1 UNION ALL
    ->    SELECT 2 UNION ALL
    ->    SELECT 3 UNION ALL
    ->    SELECT 4 UNION ALL
    ->    SELECT 5 UNION ALL
    ->    SELECT 6 UNION ALL
    ->    SELECT 7 UNION ALL
    ->    SELECT 8
    ->    ) t1,
    ->   (SELECT 0 y1 UNION ALL
    ->    SELECT 1 UNION ALL
    ->    SELECT 2 UNION ALL
    ->    SELECT 3 UNION ALL
    ->    SELECT 4 UNION ALL
    ->    SELECT 5 UNION ALL
    ->    SELECT 6 UNION ALL
    ->    SELECT 7 UNION ALL
    ->    SELECT 8
    ->    ) t2
    -> ;
Query OK, 81 rows affected (0.01 sec)
Records: 81  Duplicates: 0  Warnings: 0

mysql>
mysql> -- Ну и получение всех мест, где помещается 2х2. Ежели много, есть LIMIT
mysql> SELECT x.x1,x.y1
    -> FROM p,x
    -> GROUP BY x.x1,x.y1
    -> HAVING SUM(MBRIntersects(p,rng)) = 0
    -> ;
+------+------+
| x1   | y1   |
+------+------+
|    2 |    4 |
|    2 |    7 |
|    2 |    8 |
|    3 |    4 |
|    3 |    7 |
|    3 |    8 |
|    4 |    4 |
|    4 |    7 |
|    4 |    8 |
|    5 |    4 |
|    5 |    7 |
|    5 |    8 |
|    6 |    0 |
|    6 |    1 |
|    6 |    7 |
|    6 |    8 |
|    7 |    7 |
|    7 |    8 |
|    8 |    7 |
|    8 |    8 |
+------+------+
20 rows in set (0.00 sec)