SEO

Hello group,

I have searched everywhere and cannot find a solution, I hope your
collective wisdom can help.

My database has a Places table with a few million records, indexed on
latitude and longitude. I want to search for places close to a
particular point. Easy:

SELECT id, name, lat, lon FROM Places
WHERE lat > 55.5 AND lat < 55.7
AND lon > 12.0 AND lon < 12.1;

The query works fine, but MySQL uses only one index, so it takes about
one second instead of a few milliseconds as it should. There is no way
I can put this in production with thousands of users... The EXPLAIN
say:

+----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len |
ref | rows | Extra |
+----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+
| 1 | SIMPLE | Places | range | ixlat,ixlon | ixlon | 6 |
NULL | 4299 | Using where |
+----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+

Same behaviour with MyISAM and InnoDB. I have seen conversations
mentioning that the MySQL query planner is restricted to using only one
index per table per query. This sounds like a strange limitation to
have, but I guess we have no choice. As a workaround, maybe there is a
way to rewrite this with a subquery, but I have not found a convincing
syntax which brings the expected performance gain.

The new Index Merge optimization sounds promising, but it does not seem
to help in my case, as the documentation says:
"If a range scan is possible on some key, an Index Merge is not
considered"
so in my case the range scan has priority, and even if I use FORCE
INDEX (ixlat, ixlon), the query planner still chooses to perform only
one range scan, either on ixlat or on ixlon. I want it to perform the
range scan on both indexes, and then give me the intersection of
results.

Any help will be greatly appreciated. Thanks!

JFG

"J.F. Groff" <jfgroff@gmail.com> wrote:
>
> My database has a Places table with a few million records, indexed on
> latitude and longitude. I want to search for places close to a
> particular point.
>
> The query works fine, but MySQL uses only one index
>
> +----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+
>| id | select_type | table | type | possible_keys | key | key_len |
> ref | rows | Extra |
> +----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+
>| 1 | SIMPLE | Places | range | ixlat,ixlon | ixlon | 6 |
> NULL | 4299 | Using where |
> +----+-------------+--------+-------+---------------+-------+---------+------+------+-------------+

Seems you don't know of multi-column-indexes nor of the spatial
indexing extension (MyISAM only)

http://dev.mysql.com/doc/refman/5.0/...ate-index.html
http://dev.mysql.com/doc/refman/5.0/...xtensions.html

both would help you much

> I have seen conversations
> mentioning that the MySQL query planner is restricted to using only one
> index per table per query.

This is right and even index merging does not change it. Index merging
will use multiple indexes to retrieve part of the result set using one
index and part of the resultset using another index. But for each
single row of the result set only one index will be used.


XL
--
Axel Schwenke, Senior Software Developer, MySQL AB

Online User Manual: http://dev.mysql.com/doc/refman/5.0/en/
MySQL User Forums: http://forums.mysql.com/

Hello Axel,

Thanks for your reply.

> Seems you don't know of multi-column-indexes nor of the spatial
> indexing extension (MyISAM only)
>
> http://dev.mysql.com/doc/refman/5.0/...ate-index.html
> http://dev.mysql.com/doc/refman/5.0/...xtensions.html

Yes, I knew about those. However I fail to see how a multi-column index
would help in this case. Could you elaborate? If I create an index on
(lat, lon), will it be able to retrieve ranges efficiently? About the
spatial indexing, I did not want to go into this as it seems overkill
for my needs. But if you say it's the way to go, I'll give it a try.

As you're from MySQL, any plans on allowing future versions to use two
indexes in the same query?

Cheers,

JFG

>I want it to perform the
>range scan on both indexes, and then give me the intersection of
>results.

Do you have any evidence that this would be *faster*? It sounds like
query pessimization to me.

Gordon L. Burditt

>>I want it to perform the
>>range scan on both indexes, and then give me the intersection of
>>results.
>
> Do you have any evidence that this would be *faster*? It sounds like
> query pessimization to me.

Well, I'm no expert on database internals, but it only seemed logical
to me that if a range scan on one index takes a few ms (selecting a few
thousand records out of millions), and a range scan on the second index
also takes a few ms (again selecting a few thousand records out of
millions), then finding the rows that are only selected in both scans
(a few dozen) would be a piece of cake.

If you have a suggestion how to make this sort of query easier on the
system, please let me know.

JFG

"J.F. Groff" <jfgroff@gmail.com> wrote:
>
>> Seems you don't know of multi-column-indexes nor of the spatial
>> indexing extension (MyISAM only)
>>
>> http://dev.mysql.com/doc/refman/5.0/...ate-index.html
>> http://dev.mysql.com/doc/refman/5.0/...xtensions.html
>
> Yes, I knew about those. However I fail to see how a multi-column index
> would help in this case. Could you elaborate? If I create an index on
> (lat, lon), will it be able to retrieve ranges efficiently?

MySQL will do a range scan on the index then. This should be signifi-
cantly faster than the scan over the records itself. With an index on
only `lat` (or `lon`) the engine has to fetch all candidate records in
the respective `lat` (`lon`) range and look into the records which
fulfill the condition on `lon` (`lat`). This is a (partial) table scan.
It is expensive mostly because of the many head movement operations of
your disks.

With a combined index on (lat,lon) the engine would scan the part of
the index where the `lat` condition is fulfilled and pick all records
where the `lon` condition holds true as well. This is a (partial) index
scan. It is supposed to be much faster because

a) the index is much smaller than the complete records
b) the index is supposed to be in memory anyway (no external I/O costs)

If you try EXPLAIN with different ranges for `lat` and `lon` you will
notice that the optimizer will pick either the `lat` or the `lon`
index, depending on which range is more selective. To achive the same
behaviour with a combined index you have to create two indexes as well,
one (lat,lon) and one (lon,lat). If you know beforehand, that your
`lat` range will be more selective in your queries, you might go with
just the (lat,lon) index. Feel free to experiment :-)

> About the
> spatial indexing, I did not want to go into this as it seems overkill
> for my needs. But if you say it's the way to go, I'll give it a try.

You definitely should. This is exactly what the spatial indexing was
made for. However it is a bit complicated to deal with all those
geometry representations. Have a look at the examples in the manual.

I would suggest to try both a combined index and the spatial index.
I never used spatial indexes by myself but I would expect a (minor)
performance boost by using them.

> As you're from MySQL, any plans on allowing future versions to use two
> indexes in the same query?

"In the same query" is already addressed by the index merging
algorithm. But I'm afraid the "each record will be looked up in only
one index" will hold true for quite a while. But I'm not so familiar
with the future plans of the optimizer team. You should go and ask
that in the optimizer forum at forums.mysql.com.


XL
--
Axel Schwenke, Senior Software Developer, MySQL AB

Online User Manual: http://dev.mysql.com/doc/refman/5.0/en/
MySQL User Forums: http://forums.mysql.com/

>>>I want it to perform the
>>>range scan on both indexes, and then give me the intersection of
>>>results.
>>
>> Do you have any evidence that this would be *faster*? It sounds like
>> query pessimization to me.
>
>Well, I'm no expert on database internals, but it only seemed logical
>to me that if a range scan on one index takes a few ms (selecting a few
>thousand records out of millions), and a range scan on the second index
>also takes a few ms (again selecting a few thousand records out of
>millions), then finding the rows that are only selected in both scans
>(a few dozen) would be a piece of cake.

And I don't think finding the rows that are only selected in both
scans is a piece of cake. The lookup part is. You'd probably have
to sort at least one of the result sets (by record address). Sorting
gets expensive. Sequential search is worse. Especially if it
doesn't fit in memory.

Thought experiment: try it with hypothetical phone books. Look
up "Smith" as a last name in the sorted-by-last-name phone book,
and look up "J" as a middle name/initial in the
sorted-by-middle-name/initial phone book. Now make a list of all
the records for "J. Smith" (with any first initial/name).

Gordon L. Burditt

Alex and Gordon,

Thanks a lot for your detailed explanations. The situation is a lot
clearer to me now, especially the trick to perform the range scan on
the index instead of the full records -- but this index is so big that
I'm afraid it won't fit in memory either. Which settings can I adjust
to reserve enough memory for my most heavily-used indexes?

I'll do some experiments to optimize those queries. I was also thinking
of creating a quadrant field which would hold a combination of lat and
lon at the required precision (0.1 degrees should be enough given the
distribution of locations in my db), then a lookup of places in the
same quadrant would be instantaneous, and I can probably get decent
performance even if I have to fetch some places from the neighbouring
quadrants.

I'll post my results after the experiments are done. Thanks again,

JFG

"jfgroff@gmail.com" <jfgroff@gmail.com> wrote:
> Alex and Gordon,
^^^^
Permutation of characters...

> Thanks a lot for your detailed explanations. The situation is a lot
> clearer to me now, especially the trick to perform the range scan on
> the index instead of the full records -- but this index is so big that
> I'm afraid it won't fit in memory either.

Indexes are compressed (simple prefix-compression works well, because
values are ordered anyway). Typically that saves a lot of memory.

> Which settings can I adjust
> to reserve enough memory for my most heavily-used indexes?

For MyISAM there's the key_buffer, caching only indexes. InnoDB uses
the innodb_buffer_pool to cache all kinds of pages. Secondary indexes
use their own pages, the primary key is clustered with the records.
Depending on the table type(s) used, each of those buffers (but not
both) could be set as high as 50-80% of the available memory. The
manual contains some hints on how to tune those parameters.


XL
--
Axel Schwenke, Senior Software Developer, MySQL AB

Online User Manual: http://dev.mysql.com/doc/refman/5.0/en/
MySQL User Forums: http://forums.mysql.com/

Hi Axel,

Sorry for messing up your name; it was late ;-)

I did a few tests today, and here are my results. From a fresh database
loaded with about 4 million records, I always perform the same query
yielding 34 results near København:
SELECT id, name, lat, lon FROM Places
WHERE lat > 55.5 AND lat < 55.7
AND lon > 12.0 AND lon < 12.1;


The query cache is disabled for these tests, although it would be
enabled in production.

1) Using InnoDB
- with no index: 6.50 seconds
- with indexes on lat and lon (range of about 8000 rows using ixlon):
1.25 seconds
- repeating the same query: 0.85 seconds
- forcing use of ixlat (range of about 16000 rows): 1.21 seconds
- repeating the same query: 1.01 seconds
- with a combined index on (lat,lon), forcing its use (range of about
20000 rows): 0.91 seconds
- repeating the same query: 0.92 seconds


2) Using MyISAM
- with no index: 4.41 seconds
- with indexes on lat and lon (range of about 4000 rows using ixlon):
1.54 seconds
- repeating the same query: 0.07 seconds
- forcing use of ixlat (range of about 8000 rows): 0.28 seconds
- repeating the same query: 0.22 seconds
- with a combined index on (lat,lon), forcing its use (range of about
8000 rows): 0.21 seconds
- similar queries on random locations take between 0.11 and 0.19
seconds (letting the query planner choose its preferred index)
- when forced to use the combined index, they take between 0.11 and
0.28 seconds

Conclusions:
- Use of a combined index does not bring any significant performance
improvement, and it consumes a lot of extra disk space: abandoned.
- MyISAM is about 4 times faster than InnoDB for this situation.
- But with a sustained rate of 5 requests per second, we still can't
put this in production... Our goal is 100 rps.
- MyISAM is more efficient at re-using data from previous queries,
essentially thanks to the built-in key cache.
- So let's try to tune the key cache!

3) MyISAM with pre-loaded key cache
- set global key_buffer_size=200*1000*1024; (200 MB can accomodate
our full indexes in the key cache)
- LOAD INDEX INTO CACHE Places;
- now the usual query takes 0.12 seconds
- similar queries on random locations take between 0.07 and 0.13
seconds

We are now standing at 10 requests per second with a moderate memory
expense; good progress but still not enough.

4) Mapping (lat,lon) to a single integer key
- we add an INT column called quadrant calculated as INT(lat*10) *
10000 + INT((lon + 180) * 10)
- each quadrant maps to a 0.1 x 0.1 degrees (lat,lon) rectangle,
precise enough for our needs
- our standard query becomes:
SELECT id, name, lat, lon FROM Places
WHERE quadrant = 5561920;
- it returns 25 results in 0.00 seconds, not exactly the same results
due to rounding of positions, but that's easy to take into account in
the client application
- we can extend the query to the neighbouring quadrants, e.g. for a
0.3 x 0.2 degrees rectangle:
SELECT id, name, lat, lon FROM Places
WHERE quadrant = 5551920 OR quadrant = 5561920 OR quadrant = 5571920
OR quadrant = 5551921 OR quadrant = 5561921 OR quadrant = 5571921;
- this query returns 128 results in 0.00 seconds
- random queries anywhere take between 0.00 and 0.01 seconds
- we need more precise time measurement but it looks like this is the
way to get the desired performance
- we haven't tuned the key cache and query cache yet...

Conclusion: optimizing the queries is nice, optimizing the caches is
nicer, optimizing the data is nicest ;-)

As a side note, I didn't think we should move back to MyISAM, but this
looks good for infrequently-updated tables which need fast selects and
don't hold critical customer data.

Thanks again for your help.

JFG