How to optimize this SQL query for a rectangular region?

I'm trying to optimize the following query, but it's not clear to me what index or indexes would be best. I'm storing tiles in a two-dimensional plane and querying for rectangular regions of that plane. The table has, for the purposes of this question, the following columns:

• id: a primary key integer
• world_id: an integer foreign key which acts as a namespace for a subset of tiles
• tileY: the Y-coordinate integer
• tileX: the X-coordinate integer
• value: the contents of this tile, a varchar if it matters.

I have the following indexes:

• "ywot_tile_pkey" PRIMARY KEY, btree (id)
• "ywot_tile_world_id_key" UNIQUE, btree (world_id, "tileY", "tileX")
• "ywot_tile_world_id" btree (world_id)

And this is the query I'm trying to optimize:

ywot=> EXPLAIN ANALYZE SELECT * FROM "ywot_tile" WHERE ("world_id" = 27685  AND "tileY" <= 6  AND "tileX" <= 9  AND "tileX" >= -2  AND "tileY" >= -1 );                                                                    QUERY PLAN                                                                 -------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on ywot_tile  (cost=11384.13..149421.27 rows=65989 width=168) (actual time=79.646..80.075 rows=96 loops=1)
   Recheck Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tileX" <= 9) AND ("tileX" >= (-2)))
   ->  Bitmap Index Scan on ywot_tile_world_id_key  (cost=0.00..11367.63 rows=65989 width=0) (actual time=79.615..79.615 rows=125 loops=1)
         Index Cond: ((world_id = 27685) AND ("tileY" <= 6) AND ("tileY" >= (-1)) AND ("tile开发者_如何学CX" <= 9) AND ("tileX" >= (-2)))
 Total runtime: 80.194 ms

So the world is fixed, and we are querying for a rectangular region of tiles. Some more information that might be relevant:

All the tiles for a queried region may or may not be present

The height and width of a queried rectangle are typically about 10x10-20x20

For any given (world, X) or (world, Y) pair, there may be an unbounded number of matching tiles, but the worst case is currently around 10,000, and typically there are far fewer.

New tiles are created far less frequently than existing ones are updated (changing the 'value'), and that itself is far less frequent that just reading as in the query above.

The only thing I can think of would be to index on (world, X) and (world, Y). My guess is that the database would be able to take those two sets and intersect them. The problem is that there is a potentially unbounded number of matches for either for either of those. Is there some other kind of index that would be more appropriate?

---

cluster the table on "ywot_tile_world_id_key", the primary key seems like it is simply an artificial id. If you have more unique vertical values, than horizontal you might want to reverse the order (world-id, y, x). Also remove the lone index on world-id, it is duplicated by the compound index.

---

GIST for your X,Y much the same as PostGIS does. As a matter of fact you could even use the PostGIS extension for Postgresql and get quite a bit of bang for your buck

---

Here's what I ended up doing. The queries are now ~20ms instead of 80, which is a decent improvement, though not amazing.

1. Loaded the btree_gist contrib module
2. Created the following index:

   CREATE INDEX CONCURRENTLY ywot_tile_boxes ON ywot_tile USING gist (world_id, box(point("tileX","tileY"),point("tileX","tileY")));

3. Switched the queries to look like this:

   SELECT * FROM "ywot_tile" WHERE world_id = 27685 AND box(point("tileX","tileY"),point("tileX","tileY")) && box(point(-2,-1),point(9,6));

Any further suggestions would be much appreciated.