GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree"

Hi guys,

My name is Shubham Barai and I am a final year student at Maharashtra
Institute of Technology, Pune, India. I am very interested in contributing
Postgresql this year through GSoC project.

I am particularly interested in working on the project "Explicitly support
predicate locks in index access methods besides btree". I have gone through
some research papers which were recommended on https://wiki.postgresql.
org/wiki/GSoC_2017 to understand the concept of Serializable Snapshot
Isolation used in PostgreSQL. I have also browsed through the codebase to
get some idea of different access methods for gin, gist, and hash indexes.
I want to discuss my proposal to get some feedback before I write my final
proposal. Sorry, I am discussing my proposal little late. I was really busy
in my academics.

Currently, only B+-trees support page level predicate locking.For other
indexes, it acquires relation level lock which can lead to unnecessary
serialization failure due to rw dependency caused by any insert into the
index. So, the main task of this project is to support page level predicate
locking for remaining indexes.

* Gist Index

B+tree index acquires predicate locks only on leaf pages as index tuples
with record pointers are stored on leaf pages. But for Gist index, we have
to consider locking at each index level as index tuples can be stored in
buffers associated with internal pages or in leaf pages.
So, the functions where we need to insert a call for

1. PredicateLockPage()

->gistScanPage()
after acquiring a shared lock on a buffer

2.CheckForSerializableConflictIn()

-> gistdoinsert()
after acquiring an exclusive lock on a target buffer and before inserting a
tuple

3. PredicateLockPageSplit()

->gistplacetopage()

If there is not enough space for insertion, we need to copy predicate lock
from an old page to all new pages generated after a successful split
operation.

PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber
a lot) is used by b+-tree where two pages are involved in a split
operation. For Gist index, we can define a similar function where more
than one page can be generated after split operation.

* Gin Index

Gin index consists of a B-tree index over key values, where each key is an
element of some indexed items and each tuple in a leaf page contains either
a posting list if the list is small enough or a pointer to posting tree.

1. PredicateLockPage()

->startscanentry()
before calling collectMatchBitmap()

->scanPostingTree()
after acquiring a shared lock on a leaf page

2.CheckForSerializableConflictIn()

-> ginentryinsert()

->gininsertitempointers()
in case of insertion in a posting tree

3. PredicateLockPageSplit()

-> dataBeginPlacetoPageLeaf()

after calling dataPlacetoPageLeafSplit()

* Hash Index

1. PredicateLockPage()

->hashgettuple()
->_hash_first()
->_hash_readnext()
->_hash_readprev()

2.CheckForSerializableConflictIn()

-> _hash_doinsert()

3. PredicateLockPageSplit()

currently, I am trying to understand how the splitting of bucket works.
should we acquire predicate lock on every page from an old and new bucket
in case there is a predicate lock on a page of an old bucket?

There may be a lot of other places where we need to insert function calls
for predicate locking that I haven't included yet. I didn't go into details
of every index AM.

can anyone help me find existing tests for b-tree?

Regards,
Shubham