get well (Actually how to query and sort!)

[Brent Pinkney]

> Everything sounds fantastic except I have one big question.
>  
>  > So if we maintain a new sorting-index..
>  
>  The positions in the other indices are not static, right?

If an object is added to a collection and it is somewhere in the middle of an indices sort order, then
we will have to increment the posiitons of all the oids 'after' this oid in the sort index.

For very big collections this will be slow. 

I have not thought this through so I did not want to mention it in my previous mail, but if we have a Magma collection of
n elements where n is very big but sill < 20 million. ie. n is much less than ( (2 raisedTo: 48) - ), then could we not use a multiple 
of the oids real position, eg 4, 54, 1008692 as the position in the index?

ie multiple each oids position by 10 million:

	4		->	40000000
	54		->	540000000
	1008692	->	10086920000000


So to return to the example in my previous mail:

        0001    -> 3, 3       
        0002    -> 4, 4
        0003    -> 5, 2
        0004    -> 1, 1
        0005    -> 2, 5

is now

        0001    -> 30000000, 30000000
        0002    -> 40000000, 40000000
        0003    -> 50000000, 20000000
        0004    -> 10000000, 10000000
        0005    -> 20000000, 50000000

If a new object with oid 0006 is added which happens to be in position 6 and position 3 respectively then we can map this to an entry 0006 -> 60000000, 30000000.
This is becuase position 6 is our new highest position for the forst index so its just gets multipled by the ordinal. However since the oid is inserting itself in position 
30000000 (= 3) in the second index, the oids currently at position 330000000 must be moved to position 30000001.

The sort index is now:

        0001    -> 30000000, 30000001
        0002    -> 40000000, 40000000
        0003    -> 50000000, 20000000
        0004    -> 10000000, 10000000
        0005    -> 20000000, 50000000
        0006    -> 60000000, 30000000


The result is that only one other sort entry is affected by the insertion.


Obviously, when the bitmap is enumerated these new contrived positions (e.g. 20000000) must be inspected module our multiplier 10000000 to determine the real position.


I have not have time to really inspect this algorithm, so it may be a dog. However, I hope such a spacing algorithm will allow Magma to keep inserting new objects quickly.


Regards

Brent