Re: Concurrence GiST - Mailing list pgsql-hackers

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
whichparent will be changed ( let I call it P-page :) ).   Update lock to X all pages from P-Page to leaf page.
ReleaseU-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: teodor@sigaev.ru