Fwd: [HACKERS] GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree"
-- Forwarded message -- From: anant khandelwal <anantbie...@gmail.com> Date: Mon, Apr 3, 2017 at 11:13 PM Subject: Re: [HACKERS] GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree" To: Kevin Grittner <kgri...@gmail.com> First ,I have read from this https://github.com/postgres/postgres/blob/master/src/ backend/storage/lmgr/README-SSI --Other Index AM implementation then i understand that at https://github.com/postgres/postgres/tree/master/ src/backend/access/gist gistplacetopage is the workhorse function that performs one step of the insertion. If the tuple fits, it inserts it to the given page, otherwise it splits the page, and constructs the new downlink tuples for the split pages. The caller must then call gistplacetopage() on the parent page to insert the downlink tuples. then i look at how btree does that it does that by having a function - https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/ nbtinsert.c PredicateLockPageSplit(rel,BufferGetBlockNumber(buf), BufferGetBlockNumber(rbuf)); then i find how PredicateLockPage is called from https://github.com/ postgres/postgres/blob/master/src/backend/access/nbtree/nbtsearch.c then i find how CheckPredicateLocking() is locking is implemented - https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/ nbtinsert.c The only conflict predicate locking cares about for indexes is when * an index tuple insert conflicts with an existing lock. Since the * actual location of the insert is hard to predict because of the * random search used to prevent O(N^2) performance when there are * many duplicate entries, we can just use the "first valid" page. then gistScanPage() - https://github.com/postgres/postgres/blob/master/ src/backend/access/gist/gistget.c Scan all items on the GiST index page identified by *pageItem, and insert * them into the queue (or directly to output areas) So we need to put the predicateLockPage() there I think i have provided sufficient proof for the Index AM gist if you want i can give proof for all other ones also. Thanks Anant On Mon, Apr 3, 2017 at 10:03 PM, Kevin Grittner <kgri...@gmail.com> wrote: > On Sat, Apr 1, 2017 at 9:03 AM, anant khandelwal <anantbie...@gmail.com> > wrote: > > > My name is Anant Khandelwal currently i am pursuing masters from IIT - > Delhi > > and previously i am a software engineer. > > > > I am particularly interested in working on the project "Explicitly > support > > predicate locks in index access methods besides b tree". > > Anant, > > Your post was mostly identical (as in copy/paste level identical) to a > post by Shubham Barai four days earlier. > > https://www.postgresql.org/message-id/CALxAEPvRcJzz0SJ2KB_gh > atrrdej08rygurftr5nuqxc6ut...@mail.gmail.com > > https://www.postgresql.org/message-id/CAD=a8SBZWGD4U-TASJP0O > wtpileffhoz5o5ev0um6digqbv...@mail.gmail.com > > Unless you can produce convincing proof to the contrary, your proposal > will be disqualified because of plagiarism. > > -- > Kevin Grittner >
Re: [HACKERS] GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree"
On Sat, Apr 1, 2017 at 9:03 AM, anant khandelwalwrote: > My name is Anant Khandelwal currently i am pursuing masters from IIT - Delhi > and previously i am a software engineer. > > I am particularly interested in working on the project "Explicitly support > predicate locks in index access methods besides b tree". Anant, Your post was mostly identical (as in copy/paste level identical) to a post by Shubham Barai four days earlier. https://www.postgresql.org/message-id/calxaepvrcjzz0sj2kb_ghatrrdej08rygurftr5nuqxc6ut...@mail.gmail.com https://www.postgresql.org/message-id/CAD=a8sbzwgd4u-tasjp0owtpileffhoz5o5ev0um6digqbv...@mail.gmail.com Unless you can produce convincing proof to the contrary, your proposal will be disqualified because of plagiarism. -- Kevin Grittner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree"
On Sat, Apr 1, 2017 at 9:03 AM, anant khandelwalwrote: > From my findings the dependencies which create the anomalies in Snapshot > isolation are: > > wr-dependencies: if T1 writes a version of an object, and T2 > reads that version, then T1 appears to have executed before T2 > ww-dependencies: if T1 writes a version of some object, and > T2 replaces that version with the next version, then T1 appears > to have executed before T2 > ww-dependencies: if T1 writes a version of some object, and > T2 replaces that version with the next version, then T1 appears > to have executed before T2 I think you meant to replace one of those ww-dependencies sections with rw-dependencies -- which are, after all, the ones that cause all the trouble :-). > but due to the rw dependency caused by any insert into the index indexes > other than the btree acquires relation level lock which causes serialization > failure. That's both a bit strong and a bit narrow. A better statement might be that the relation-level predicate locks can lead to false positive serialization failures. After all, detection of a single write to the index doesn't all by itself lead to a serialization failure, and the problem when it does is that it might be a "false positive" -- in some cases where the serialization failure occurs there would not actually be a serialization anomaly without that failure. > So the main task is to implement page-level predicate locking in the > remaining core index AMs > > * Gist Index > > B+tree index acquires predicate locks only on leaf pages Well, if memory serves, we sometimes need to lock at the relation level (e.g., an empty index), but as far as *page* locks go, that seems correct because a scan doesn't exit early during the descent to the leaf level. The point is that predicate locks on indexes are intended to lock gaps between the index entries found. Any index entry read at the leaf level is dead (but not yet vacuumed away), points to a tuple not visible to the scanning snapshot, or points to a tuple which *is* visible to the snapshot. In the first two cases we don't need any predicate lock; in the last one the lock on the heap tuple covers things. What we need the locks on the indexes for is to cover the "gaps" into which later writes may occur. So the need is to ensure that during any insert of an index tuple that points to a heap tuple we might have read had it existed at the time of the index scan, we run into a predicate lock to allow us to recognize the rw-dependency. > 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. Yes, because a gist scan can return with a "not found" indication before it gets to the leaf level. > 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. We could always call the existing function more than once, but there might be enough performance benefit to justify a new function with an array of page references. I would want to do it without changing the API first, and if time permits benchmark that versus a new function. Without measurable benefit, I don't want to complicate the API. > * 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() I have not looked in detail at this point, but that seems plausible and indicates admirable research effort in drafting this proposal. > This is just an idea
[HACKERS] GSoC 2017 Proposal for "Explicitly support predicate locks in index access methods besides btree"
Hi guys, My name is Anant Khandelwal currently i am pursuing masters from IIT - Delhi and previously i am a software engineer. I am particularly interested in working on the project "Explicitly support predicate locks in index access methods besides b tree".I have gone through http://hdl.handle.net/2123/5353 http://drkp.net/papers/ssi-vldb12.pdf to understand how serializable implemented through the use of Snapshot isolation in PostgreSQL also gone through the codebase get some idea of different access methods for gin, gist, and hash indexes. I want to discuss my idea.Then i move to make the proposal Sorry for late i am busy with the academics. >From my findings the dependencies which create the anomalies in Snapshot isolation are: *wr-dependencies*: if T1 writes a version of an object, and T2 reads that version, then T1 appears to have executed before T2 * ww-dependencies*: if T1 writes a version of some object, and T2 replaces that version with the next version, then T1 appears to have executed before T2 *ww-dependencies*: if T1 writes a version of some object, and T2 replaces that version with the next version, then T1 appears to have executed before T2 where T1 and T2 are the transaction but due to the rw dependency caused by any insert into the index indexes other than the btree acquires relation level lock which causes serialization failure.So the main task is to implement page-level predicate locking in the remaining core index AMs * 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() This is just an idea also i understand that Page level predicate locking exists in the btree AM, where it required the addition of 17 function calls to implement, but remains unimplemented in the gin, gist, spgist, brin, and hash index AMs. So we nned to insert function calls at other places also. Also tell me can we evaluate the performance on PostgreSQL on the following workloads - SIBENCH microbenchMark - TPC-c++
[HACKERS] 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