Christopher Kings-Lynne wrote:
Hey Teodor,
How's this going?
I think you were looking at the same paper I was reading about GiST indexes. I found the GiST source code somewhat over my head, however.
I hope you'll still working on it and haven't given up!
I hoped begining of year will be quiet, but it's not. Our customers give to us a lot of work... So I havn't a much time work with GiST. :(
Ok, I suppose that the basic papers is "Access methods for next-generation database systems" by Marcel Kornaker and "Concurrency and Recovery in Generalized Search Trees" by Kornaker, C.Mohan and Joseph M. Hellerstein.
But it seems to me it's not enough to us. When I began to work with GiST in pgsql I found that split operation may fails with variable-size key. Just for one reason: user-defined method pickSplit doesn't guarantee that size of free space on new page will be enough for insertion of new key. For example: page contains small keys which all equals and one - not (small too). We want to insert a big key, so pickSplit is called. It distribute equals keys to one page and different - to another and we want insert new key in first page - and we hasn't enough free space. Contrib/intarray and contrib/tsearch* modules often produce similar situation. For this reason, in current implementation gistSplit (gist.c) method is recursive, and more - it splits 'virtual' page with already inserted new key (look gist.c near 523 line).
As I can see in papers, it's algorithm isn't protected for a such case. So, now I think on two directions:
1 How to adopt paper's insertion algorithm. But without success now :(
2 More simple algorithm, but with less concurrerncy based on 'update locks' which described at http://www-db.stanford.edu/~ullman/dscb.html (I don't known who was fisrt, but I readed about it in book).
Update lock looks as shared lock while asking and as exclusive while deducted.
Matrix of locks:
S X U
S y n y
X n n n
U n n n
So, insertion algorithm with two-phase locking: Find leaf to insert key (with U locking all parent pages) Define which parent will be changed ( let I call it P-page :) ). Update lock to X all pages from P-Page to leaf page. Release U-locks from root to P-page Insert and update pages from P-page to leaf Realese all locks.
So, the defect of this scheme is: nobody can start (but work with other pages is possible) work with index while insert process locks root even if root locked only with U lock. And we need to add U lock in lock manager of pgsql.
So, I still thinking. If you has other thought/idea, pls, don't be quiet.
-- Teodor Sigaev E-mail: [EMAIL PROTECTED]
---------------------------(end of broadcast)--------------------------- TIP 2: you can get off all lists at once with the unregister command (send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])
