Have Geek Brain

How do I optimize this SQL query for a rectangular area?

I am trying to optimize the following query, but it is not clear to me which index or indexes would be better. I am storing tiles in a 2D plane and I am querying rectangular areas of that plane. For the purposes of this question, the table has the following columns:

  • id: integer number of primary keys
  • world_id: an integer foreign key that acts as a namespace for a subset of elements
  • tileY: integer Y-coordinates
  • tileX: integer X-coordinates
  • value: the content of this tile, varchar if relevant.

I have the following indices:

  • "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 query I am 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 ("tileX" <= 9) AND ("tileX" >= (-2)))
 Total runtime: 80.194 ms

So the world is fixed and we are asking for a rectangular area of ​​tiles. Additional information that may be relevant:

All tiles for the requested area may or may not be present.The height and width of the requested rectangle is usually around 10x10-20x20 For any pair (world, X) or (world, Y) there could be an unlimited number of matching tiles, but in the worst case, currently around 10,000, and usually much less. New tiles are created much less frequently than existing ones, updated (changing the "value"), and this is much less frequent than just reading, as in the query above.

The only thing I can think of is indexing (world, X) and (world, Y). My guess is that the database will be able to take these two sets and traverse them. The problem is that there is a potentially unlimited number of matches for any of them. Is there any other index that would be more appropriate?

+2


source to share


3 answers


copy the table to "ywot_tile_world_id_key", the primary key seems to be just an artificial id. If you have more unique vertical values ​​than horizontal, you can change the order (world-id, y, x). Also remove the single index on world-id, it is duplicated by the composite index.



+2


source


GIST for your X, Y is the same as PostGIS. In fact you could even use the PostGIS extension for Postgresql and get quite a bit of buzz for your dollar



+1


source


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

  • Loaded the btree_gist contrib module
  • Created the following index: 
    CREATE INDEX CONCURRENTLY ywot_tile_boxes ON ywot_tile USING gist (world_id, box (point ("tileX", "tileY"), point ("tileX", "tileY")));
  • Included queries so they 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 greatly appreciated.

0


source






More articles:


All Articles