Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

For things like find nearest neighbors, I can undertand that R=Tree can outperform B-Tree. R-Tree can kick out more obviously false points.

However, for simple check of a point in a rectangle, it's effectively

min

If x and y is indexed by b tree, they too can kick out a lot of false points.

So I did an experiment with spatial index

SELECT DISTINCT
  TB.ID,
  TB.Latitude,
  TB.Longitude,
  111151.29341326*SQRT(pow(-6.185-TB.Latitude,2)+pow(106.773-TB.Longitude,2)*0.98839228980165) AS Distance
FROM
  `tablebusiness` AS TB
   join tableauxiliary as TA on TA.BusinessID=TB.ID
WHERE
MBRContains(
   GeomFromText ('MULTIPOINT(-6.2317830813328 106.72621691867,-6.1382169186672  106.81978308133)'),
   TA.Latlong
   )
   AND 
MATCH (FullTextSearch) AGAINST ('kucing*' IN BOOLEAN MODE)
ORDER BY
  Distance
LIMIT
  0, 20

This is pretty fast. .24 seconds

And then I do

SELECT DISTINCT
  TB.ID,
  TB.Latitude,
  TB.Longitude,
  111151.29341326*SQRT(pow(-6.185-TB.Latitude,2)+pow(106.773-TB.Longitude,2)*0.98839228980165) AS Distance
FROM
  `tablebusiness` AS TB
   join tableauxiliary as TA
WHERE
  -6.2317830813328 < TB.Latitude
AND
  TB.Latitude < -6.1382169186672
AND
  106.72621691867 < TB.Longitude
AND
  TB.Longitude <106.81978308133
AND 
   MATCH (TA.FullTextSearch) AGAINST ('kucing*' IN BOOLEAN MODE)
ORDER BY
  Distance
LIMIT
  0, 20

This is very slow.

I wonder why. It doesn't make sense.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

R-tree structure works in a way that two nearby points are "closer" in the R-tree index - because both coordinates and both with same weight are used to decide where (in the index) a new point is to be placed.

So, it's easy to identify points that are "near" a fixed point - meaning points that have both coordinates near the fixed point coordinates.


B-tree indexes on the other way work differently. Even if you have a compound index, say (Latitude, Longitude), where both coordinates are included the index, they do not have the same weight. In other words, two points with different Latitude and the same exact Longitude will be very far apart (in the index structure). Much more apart than two points with same Latitude and different Longitude.

So, searching for nearby points (with the above (Lat, Long) index) could possibly find fast nearby points with the exact same Latitude. But for all the other points, it will not be very efficient.

As an example, consider you are looking for places nearby a village in Africa - a village that has the same Latitude with London. Your query would spend lots of time calculating the distances between your village and all the (millions) points in UK that have the same (or almost the same) latitude with it. And then reject those points because they are too far apart.


You might think then that two B-tree indices, one on (Latitude) and one on (Longitude) would be fine for such queries. After all, why shouldn't both indices be used in a query that has a:

WHERE Latitude  BETWEEN @LatStart  AND @LatEnd 
  AND Longitude BETWEEN @LongStart AND @LongEnd

I think that DBMS cannot use two (B-tree) indices like that in a query (MySQL cannot AFAIK). Even if it could though, it wouldn't be very good, preformance-wise, as both conditions may not narrow the search much. So, after these two index scans, a million rows found that match one condition would have to be merged with a million rows from the other one. And this merge will probably require sorting as well - which will kill performance if the subresults are big.

In general, any query that has more than one range condition on the same table is difficult to be optimized by B-tree indices. (for other DBMS that have other types of indices, like Hash or Bitmap, I can't speak about).

That's why R-trees and other indices that perform well in spatial searches were invented in the first place. They kind of "interleave" both coordinates (or all 3 or 4 in higher dimensional indices) in the index structure and no coordinate has higher weight than the others.

share|improve this answer
    
So that's the issue. MySQL cannot. The issue is not the btree versus rtree. The issue is MySQL cannot interleave 2 indexes. Hmnm... –  Jim Thio Jun 21 '12 at 13:00
    
No. As I said, even if there are DBMS that can, it would still be less efficient than an R-Tree. –  ypercube Jun 21 '12 at 13:02
    
+1 B-Trees traverse on dimension at a time only. R-Trees traverse both dimensions simultaneously. –  Remus Rusanu Jun 21 '12 at 13:47
    
Even when we're not looking for nearest neighbor we are only looking for whether the points are in the box? –  Jim Thio Jun 21 '12 at 13:51
    
@JimThio: Yes, even if you search for points in the box with corners (0,0) and (1,1) the B-tree index can only be useful to narrow the search inside the (0,-Inf) and (1,+Inf) strip. –  ypercube Jun 21 '12 at 13:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.