get well (Actually how to query and sort!)
Brent Pinkney
brent.pinkney at aircom.co.za
Fri May 19 07:30:47 UTC 2006
> 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
More information about the Magma
mailing list