So let me see if I understand, when searching for everyone within radius
"r" of point (a,b), the gist index will be used like this:
* C is the circle centered on (a,b) of radius "r"
1.
Traverse down the tree, starting at the root. Only go down nodes whose
bounding-box has a non-empty intersection with the circle C (how fast is
this verification?)
2. Once the leaves are reached, verify for everyone of them whether they're inside C or not, returning those that are.
If
this really is how it happens, then I ask: What about boxes that
intersect (does that happen)? What if the boxes aren't "nice" (boxes
with a very small desired intersection with the circle and a very large
quantity of unwanted rows).
Also, you've said that with b-tree indexes on two orthogonal
coordinates (two columns) postgresql would need to check the ENTIRE
vertical strip bounded by a-1 and a+1 and the ENTIRE horizontal strip
bounded by b-1 and b+1 (two limitless, "infinite" rectangles)? This
leads me to another question:
- Isn't there an equality check between all the rows returned by
both indexes, and then the actual distance calculations are performed
only for those returned by both indexes? What if I have many more
indexes on my table, how are things done?
And if I may, one last question:
- Is box-bounding the index strategy used for all geometric operations with gist indexes?
Also, to Oleg:
I
had personally tested the use of gist indexes (without limiting the
number of returned rows, however) for more than 15 million rows (with
their coordinates distributed a VERY LARGE area, sadly). The results
were still impressive to me (although I didn't know what to expect,
maximum running times of around 17ms seemed great to me!).
And sorry for sending this message to your personal email (my mistake).
Thanks a lot for all the help, if you can lead me to any docs/articles, I'll gladly read them.
