[OSM-talk] OGL, OSM, NASA

[Nick Hill]

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.
>