[OSM-talk] OGL, OSM, NASA
Nick Hill
nick at nickhill.co.uk
Wed Apr 26 11:23:33 BST 2006
Hello Raphael
I supose we will have to learn more about how R-trees work. The problem
with the point types is not just that they use doubles, but they use 4
doubles and that the R-tree index doubles that again for the test on a
10M point field.
We shouldn't assume any design decision is pathological but instead
assume there is a good reason, and find out why.
Really, we need an R-tree-like index which is far more economical than
any implementation I have seen. Getting that level of economy may or may
not be mathematically possible using the R-tree design.
At this point, we should investigate the fundamental design of R-tree
indexes.
Questions:
1) Do geometric R-tree type indexes need 2, 4 or 8 indexed values per point?
2) Do geometric R-tree indexes grow in a non-linear fashion with number
of indexed rows?
3) Does the R-tree indexing time for new points necessarily grow in a
non-linear fashion with number of indexed rows?
4) If the R-tree can't fit in memory, is there an R-tree implementation
which can substantially cut down the number of disc seeks?
5) Are there any other relevant questions to using R-trees? If we get
positive answers to the above questions, we need to re-run tests in the
light of those answers to check this.
We than need to compare the results to the possible optimisations we can
make to b-trees.
This way, we can save a lot of work for others by mathematically
establishing the design decisions we must offset for the open streetmap
database.
Raphael Jacquot wrote:
>>
>> Hello Raphael
>>
>> I haven't checked, but do you know if postgress can do R-trees on two
>> 4 byte columns? Or can the datatypes within the geometric point type
>> be changed easily?
>>
>> Regards
>>
>>
>> Nick.
>>
>
> the standard points,box, lseg and others are made out of doubles.
> however, postgresql being an object oriented database, it's entirely
> possible for you to build your own datatypes from 32 bit integers and
> copy/paste the code that do the fast work to work with that.
>
More information about the talk
mailing list