SQL: How to select elements in a rectangle range from a large continuous matrix? **UPDATED**

Question

I'm having a hard time working out the following problem efficiently.

I have a 15000x15000 xy matrix. I'm storing element locations in this matrix by defining a x,y coordinate for the element. I want to display a part of the matrix in a so called viewport. The viewport dimensions are e.g. 1600x1000

Consider the following db structure:

Element (element_id, image, width, height)
Globe_Element (ge_id, x, y, element_id)

With the only input being a x,y coordinate somehwere in the grid (500x500) how can I select all the Globe_Element rows which are visible in the viewport (6x4)?

The above image demonstrates the issues. The small orange squares are elements which should be included, small red squares shouldn't (looking at the nearest viewport). The big colored blocks (blue, yellow, green and red (yes again, sorry for confusion) are viewports. One color is one viewport. Gray circles define the input coordinates.

Answer 1

Assuming your coordinate parameter is the upper left corner of the viewport, something like this is generally how to select the corresponding rows:

select * from globe_element g, element e

where

e.element_id = g.element_id and

((x < width and x between @x_param and (@x_param + 6)) or (x >-1 and x between (@x_param - width) and (@x_param - width + 6)))

and

((y_loc < height and y_loc between @y_param and (@y_param + 4)) or (y_loc >-1 and y_loc between (@y_param - height) and (@y_param - height + 4)))

This is just generic sql, not mysql specific (the parameters, at least).

Generally: Select where x is between the x_param and x_param+ view_port_width, and y is between y_param and y+param + view_port_height. If the calculated coordinate is greater than the view_port_width/height, subtract 500 to get the corresponding wrapped location.

This does not order the coordinates in any way.

Also, your "Spherical" environment doesn't really appear to be spherical at all.... how are you mapping a grid to a sphere? Just like degrees lat/long on the earth where the area of each square unit shrinks as you get to the poles? If that's the case, then this will work. If not, then what I've posted is rubbish. However, if that's the case then solving this in SQL is also.... wrong.

Answer 2

For doing this efficiently in SQL I would recommend you to choose a DBMS with spatial support (often going under the name GIS support) or with support for two- or multi-dimensional indexes (I don't know any such).

I think only then will you be able to make your queries use indexes to perform efficiently.

Postgres has spatial support (under the name PostGIS), as does MS SQL 2008 and Oracle. I only used MS SQL 2008 for spatial, here is a nice overview of how its spatial index subdivides the surface.

Without multi-dimensional indexes you'll have your objects on disk ordered along one coordinate axis, consequently you will only be able to narrow down the table scan for objects only along one coordinate axis.

---

If you want to stay with MySQL (reply to OP comment below):

I think it is better to create the query with concrete values - whether you do that in PHP or in a stored procedure on the SQL side, is a different question. But it is simple and easy enough to do in PHP so I would recommend that.

You can make decisions like whether the viewport is in a non-wraparound position (blue in your diagram above) and then its enough to emit a single query with a simple WHERE xmin>=viewport_xmin AND xmax<=viewport_xmax AND ymin>=viewport_ymin AND ymax<=viewport_ymax clause. Or see that the viewport wraps, and then experiment whether it is faster to execute 2/4 separate simple queries for each of the 2/4 unwrapping parts of the portal, or put all the 2/4 simple queries with ORs between them in one big query. You will have to see which one will be faster, experiment with indexes, look at query plans, etc.