Re: [HACKERS] GSoC 2017 : Patch for predicate locking in Gist index

[Shubham Barai]

On 9 October 2017 at 18:57, Alexander Korotkov <a.korot...@postgrespro.ru>
wrote:

> On Thu, Oct 5, 2017 at 9:48 PM, Shubham Barai <shubhambara...@gmail.com>
> wrote:
>
>> On 3 October 2017 at 00:32, Alexander Korotkov <a.korot...@postgrespro.ru
>> > wrote:
>>
>>> On Mon, Oct 2, 2017 at 9:11 PM, Andrew Borodin <amborodi...@gmail.com>
>>> wrote:
>>>
>>>> On Mon, Oct 2, 2017 at 8:00 PM, Alexander Korotkov
>>>> <a.korot...@postgrespro.ru> wrote:
>>>> > What happen if exactly this "continue" fires?
>>>> >
>>>> >> if (GistFollowRight(stack->page))
>>>> >> {
>>>> >> if (!xlocked)
>>>> >> {
>>>> >> LockBuffer(stack->buffer, GIST_UNLOCK);
>>>> >> LockBuffer(stack->buffer, GIST_EXCLUSIVE);
>>>> >> xlocked = true;
>>>> >> /* someone might've completed the split when we unlocked */
>>>> >> if (!GistFollowRight(stack->page))
>>>> >> continue;
>>>> >
>>>> >
>>>> > In this case we might get xlocked == true without calling
>>>> > CheckForSerializableConflictIn().
>>>> Indeed! I've overlooked it. I'm remembering this issue, we were
>>>> considering not fixing splits if in Serializable isolation, but
>>>> dropped the idea.
>>>>
>>>
>>> Yeah, current insert algorithm assumes that split must be fixed before
>>> we can correctly traverse the tree downwards.
>>>
>>>
>>>> CheckForSerializableConflictIn() must be after every exclusive lock.
>>>>
>>>
>>> I'm not sure, that fixing split is the case to necessary call
>>> CheckForSerializableConflictIn().  This lock on leaf page is not taken
>>> to do modification of the page.  It's just taken to ensure that nobody else
>>> is fixing this split the same this.  After fixing the split, it might
>>> appear that insert would go to another page.
>>>
>>> > I think it would be rather safe and easy for understanding to more
>>>> > CheckForSerializableConflictIn() directly before gistinserttuple().
>>>> The difference is that after lock we have conditions to change page,
>>>> and before gistinserttuple() we have actual intent to change page.
>>>>
>>>> From the point of future development first version is better (if some
>>>> new calls occasionally spawn in), but it has 3 calls while your
>>>> proposal have 2 calls.
>>>> It seems to me that CheckForSerializableConflictIn() before
>>>> gistinserttuple() is better as for now.
>>>>
>>>
>>> Agree.
>>>
>>
>> I have updated the location of  CheckForSerializableConflictIn()  and
>> changed the status of the patch to "needs review".
>>
>
> Now, ITSM that predicate locks and conflict checks are placed right for
> now.
> However, it would be good to add couple comments to gistdoinsert() whose
> would state why do we call CheckForSerializableConflictIn() in these
> particular places.
>
> I also take a look at isolation tests.  You made two separate test specs:
> one to verify that serialization failures do fire, and another to check
> there are no false positives.
> I wonder if we could merge this two test specs into one, but use more
> variety of statements with different keys for both inserts and selects.
>

Please find the updated version of patch here. I have made suggested
changes.

Regards,
Shubham


Predicate-locking-in-gist-index_4.patch
Description: Binary data

-- 
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 : Patch for predicate locking in Gist index

[Shubham Barai]

 Sent with Mailtrack

<#>

On 3 October 2017 at 00:32, Alexander Korotkov 
wrote:

> On Mon, Oct 2, 2017 at 9:11 PM, Andrew Borodin 
> wrote:
>
>> On Mon, Oct 2, 2017 at 8:00 PM, Alexander Korotkov
>>  wrote:
>> > What happen if exactly this "continue" fires?
>> >
>> >> if (GistFollowRight(stack->page))
>> >> {
>> >> if (!xlocked)
>> >> {
>> >> LockBuffer(stack->buffer, GIST_UNLOCK);
>> >> LockBuffer(stack->buffer, GIST_EXCLUSIVE);
>> >> xlocked = true;
>> >> /* someone might've completed the split when we unlocked */
>> >> if (!GistFollowRight(stack->page))
>> >> continue;
>> >
>> >
>> > In this case we might get xlocked == true without calling
>> > CheckForSerializableConflictIn().
>> Indeed! I've overlooked it. I'm remembering this issue, we were
>> considering not fixing splits if in Serializable isolation, but
>> dropped the idea.
>>
>
> Yeah, current insert algorithm assumes that split must be fixed before we
> can correctly traverse the tree downwards.
>
>
>> CheckForSerializableConflictIn() must be after every exclusive lock.
>>
>
> I'm not sure, that fixing split is the case to necessary call
> CheckForSerializableConflictIn().  This lock on leaf page is not taken to
> do modification of the page.  It's just taken to ensure that nobody else is
> fixing this split the same this.  After fixing the split, it might appear
> that insert would go to another page.
>
> > I think it would be rather safe and easy for understanding to more
>> > CheckForSerializableConflictIn() directly before gistinserttuple().
>> The difference is that after lock we have conditions to change page,
>> and before gistinserttuple() we have actual intent to change page.
>>
>> From the point of future development first version is better (if some
>> new calls occasionally spawn in), but it has 3 calls while your
>> proposal have 2 calls.
>> It seems to me that CheckForSerializableConflictIn() before
>> gistinserttuple() is better as for now.
>>
>
> Agree.
>

I have updated the location of  CheckForSerializableConflictIn()  and
changed the status of the patch to "needs review".

Regards,
Shubham


Predicate-locking-in-gist-index_3.patch
Description: Binary data

-- 
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 : Patch for predicate locking in Gist index

[Shubham Barai]

On Sep 28, 2017 4:30 PM, "Alexander Korotkov" <a.korot...@postgrespro.ru>
wrote:

Hi!

On Wed, Jun 21, 2017 at 10:52 AM, Shubham Barai <shubhambara...@gmail.com>
wrote:

> Hi,
>
> On 21 June 2017 at 13:11, Heikki Linnakangas <hlinn...@iki.fi> wrote:
>
>> On 06/16/2017 01:24 PM, Shubham Barai wrote:
>>
>>> @@ -497,6 +499,13 @@ gistplacetopage(Relation rel, Size freespace,
>>> GISTSTATE *giststate,
>>> for (ptr = dist->next; ptr; ptr = ptr->next)
>>> UnlockReleaseBuffer(ptr->buffer);
>>> }
>>> +
>>> +   for (ptr = dist; ptr; ptr = ptr->next)
>>> +   PredicateLockPageSplit(rel,
>>> +
>>>  BufferGetBlockNumber(buffer),
>>> +
>>>  BufferGetBlockNumber(ptr->buffer));
>>> +
>>> +
>>>
>>
>> I think this new code needs to go before the UnlockReleaseBuffer() calls
>> above. Calling BufferGetBlockNumber() on an already-released buffer is not
>> cool.
>>
>> - Heikki
>>
>> I know that. This is the old version of the patch. I had sent updated
> patch later. Please have a look at updated patch.
>

I took a look on this patch.

In gistdoinsert() you do CheckForSerializableConflictIn() only if page
wasn't exclusively locked before (xlocked is false).

if (!xlocked)
> {
> LockBuffer(stack->buffer, GIST_UNLOCK);
> LockBuffer(stack->buffer, GIST_EXCLUSIVE);
> CheckForSerializableConflictIn(r, NULL, stack->buffer);
> xlocked = true;


However, page might be exclusively locked before.  And in this case
CheckForSerializableConflictIn() would be skipped.  That happens very
rarely (someone fixes incomplete split before we did), but nevertheless.


I agree with Andrey Borodin's view on locks. I am quoting his message
"if xlocked = true, page was already checked for conflict after setting
exclusive lock on it's buffer.  I still do not see any problem here..."

Regards,
Shubham

Re: [HACKERS] GSoC 2017: weekly progress reports (week 6)

[Shubham Barai]

On 1 October 2017 at 01:47, Alexander Korotkov <a.korot...@postgrespro.ru>
wrote:

> On Sat, Sep 30, 2017 at 6:12 PM, Shubham Barai <shubhambara...@gmail.com>
> wrote:
>
>> I have made changes according to your suggestions. Please have a look at
>> the updated patch.
>> I am also considering your suggestions for my other patches also. But, I
>> will need some time to
>> make changes as I am currently busy doing my master's.
>>
>
> I don't understand why sometimes you call PredicateLockPage() only when
> fast update is off.  For example:
>
> @@ -94,6 +101,9 @@ scanPostingTree(Relation index, GinScanEntry scanEntry,
>>   break; /* no more pages */
>>
>>   buffer = ginStepRight(buffer, index, GIN_SHARE);
>> +
>> + if (!GinGetUseFastUpdate(index))
>> + PredicateLockPage(index, BufferGetBlockNumber(buffer), snapshot);
>>   }
>>
>>   UnlockReleaseBuffer(buffer);
>
>
> But sometimes you call PredicateLockPage() unconditionally.
>
> @@ -131,6 +141,8 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack
>> *stack,
>>   attnum = scanEntry->attnum;
>>   attr = btree->ginstate->origTupdesc->attrs[attnum - 1];
>>
>> + PredicateLockPage(btree->index, stack->buffer, snapshot);
>> +
>>   for (;;)
>>   {
>>   Page page;
>
>
> As I understand, all page-level predicate locking should happen only when
> fast update is off.
>
> Also, despite general idea is described in README-SSI, in-code comments
> would be useful.
>
>
Hi Alexander,

Yes, page-level predicate locking should happen only when fast update is
off.
Actually, I forgot to put conditions in updated patch. Does everything else
look ok ?




Kind Regards,
Shubham

>

Re: [HACKERS] GSoC 2017: weekly progress reports (week 6)

[Shubham Barai]

<https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
<#>

On 28 September 2017 at 15:49, Alexander Korotkov <a.korot...@postgrespro.ru
> wrote:

> On Thu, Sep 28, 2017 at 12:45 AM, Alexander Korotkov <
> a.korot...@postgrespro.ru> wrote:
>
>> On Wed, Aug 9, 2017 at 6:30 PM, Shubham Barai <shubhambara...@gmail.com>
>> wrote:
>>
>>> Please find the updated patch for predicate locking in gin index here.
>>>
>>> There was a small issue in the previous patch. I didn't consider the case
>>> where only root page exists in the tree, and there is a predicate lock
>>> on it,
>>> and it gets split.
>>>
>>> If we treat the original page as a left page and create a new root and
>>> right
>>> page, then we just need to copy a predicate lock from the left to the
>>> right
>>> page (this is the case in B-tree).
>>>
>>> But if we treat the original page as a root and create a new left and
>>> right
>>> page, then we need to copy a predicate lock on both new pages (in the
>>> case of rum and gin).
>>>
>>> link to updated code and tests: https://github.com/shub
>>> hambaraiss/postgres/commit/6172639a104785f051cb4aa0d511c58f2bae65a6
>>>
>>
>> I've assigned to review this patch.  First of all I'd like to understand
>> general idea of this patch.
>>
>> As I get, you're placing predicate locks to both entry tree leaf pages
>> and posting tree leaf pages.  But, GIN implements so called "fast scan"
>> technique which allows it to skip some leaf pages of posting tree when
>> these pages are guaranteed to not contain matching item pointers.  Wherein
>> the particular order of posting list scan and skip depends of their
>> estimated size (so it's a kind of coincidence).
>>
>> But thinking about this more generally, I found that proposed locking
>> scheme is redundant.  Currently when entry has posting tree, you're locking
>> both:
>> 1) entry tree leaf page containing pointer to posting tree,
>> 2) leaf pages of corresponding posting tree.
>> Therefore conflicting transactions accessing same entry would anyway
>> conflict while accessing the same entry tree leaf page.  So, there is no
>> necessity to lock posting tree leaf pages at all.  Alternatively, if entry
>> has posting tree, you can skip locking entry tree leaf page and lock
>> posting tree leaf pages instead.
>>
>
> I'd like to note that I had following warnings during compilation using
> clang.
>
> gininsert.c:519:47: warning: incompatible pointer to integer conversion
>> passing 'void *' to parameter of type 'Buffer' (aka 'int')
>> [-Wint-conversion]
>> CheckForSerializableConflictIn(index, NULL, NULL);
>> ^~~~
>> /Applications/Xcode.app/Contents/Developer/Toolchains/
>> XcodeDefault.xctoolchain/usr/bin/../lib/clang/8.0.0/include/stddef.h:105:16:
>> note: expanded from macro 'NULL'
>> #  define NULL ((void*)0)
>>^~
>> ../../../../src/include/storage/predicate.h:64:87: note: passing
>> argument to parameter 'buffer' here
>> extern void CheckForSerializableConflictIn(Relation relation, HeapTuple
>> tuple, Buffer buffer);
>>
>> ^
>> 1 warning generated.
>> ginvacuum.c:163:2: warning: implicit declaration of function
>> 'PredicateLockPageCombine' is invalid in C99 [-Wimplicit-function-
>> declaration]
>> PredicateLockPageCombine(gvs->index, deleteBlkno, rightlink);
>> ^
>> 1 warning generated.
>
>
> Also, I tried to remove predicate locks from posting tree leafs.  At least
> isolation tests passed correctly after this change.
>
> However, after telegram discussion with Andrew Borodin, we decided that it
> would be better to do predicate locking and conflict checking for posting
> tree leafs, but skip that for entry tree leafs (in the case when entry has
> posting tree).  That would give us more granular locking and less false
> positives.
>
>
>
>
Hi Alexander,

I have made changes according to your suggestions. Please have a look at
the updated patch.
I am also considering your suggestions for my other patches also. But, I
will need some time to
make changes as I am currently busy doing my master's.


Kind Regards,
Shubham


Predicate-locking-in-gin-index_2.patch
Description: Binary data

-- 
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: weekly progress reports (week 4) and patch for hash index

[Shubham Barai]

Hi Thomas,

I have attached the rebased version of patch here.


Kind Regards,
Shubham

On 8 September 2017 at 06:37, Thomas Munro <thomas.mu...@enterprisedb.com>
wrote:

> Hi Shubham,
>
> On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <shubhambara...@gmail.com>
> wrote:
> > If these two hash keys (78988658 and 546789888) mapped to the same
> bucket, this will result in false serialization failure.
> > Please correct me if this assumption about false positives is wrong.
>
> I wonder if there is an opportunity to use computed hash values
> directly in predicate lock tags, rather than doing it on the basis of
> buckets.  Perhaps I'm missing something important about the way that
> locks need to escalate that would prevent that from working.
>
> > 3) tested my patch on the current head
>
> This no longer applies, but it's in "Needs review" status in the
> Commitfest.  Could you please post a rebased version?
>
> --
> Thomas Munro
> http://www.enterprisedb.com
>


Predicate-locking-in-hash-index_4.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017: weekly progress reports (week 9 and week 10)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,

In the last two weeks, I mostly worked on predicate locking in rum index.
Rum is based on gin access method. The main difference between rum and
gin is that rum stores additional information in posting tree to perform
a fast full-text search using tsvector and tsquery.

Also, rum has different scanning strategies that include
scangetItemRegular (gets the next heap pointer from scan),
scangetItemfast (gets the next item pointer using fast scan),
scangetItemfull (gets the next item pointer using full index scan).

We have to insert a call for PredicateLockPage at all appropriate places
where a leaf page of entry tree or posting tree is scanned.
Unlike gin, rum doesn't support fast update, so we don't have to worry
about acquiring a relation level lock.

In summary, I have done following things in last two weeks.

1) read the source code of rum to understand its access method

2) found appropriate places to insert calls to existing functions

3) modified  some function prototypes to include snapshot parameter
 (rum was forked before snapshot feature was added to PostgreSQL, and
  snapshot parameter is needed for predicate locking)

4) created tests (to verify serialization failures and to demonstrate the
feature of reduced false positives)

5) debugged and fixed one issue in the previous patch for gin index.

6) created tests for predicate locking in B-tree.

link to the code for rum:
https://github.com/shubhambaraiss/rum/commit/e28e31d79fa6a0d1b6ef4bb7d7e5d0d334a069d9


Regards,
Shubham



 Sent with Mailtrack

Re: [HACKERS] GSoC 2017: weekly progress reports (week 6)

[Shubham Barai]

Hi,

Please find the updated patch for predicate locking in gin index here.

There was a small issue in the previous patch. I didn't consider the case
where only root page exists in the tree, and there is a predicate lock on
it,
and it gets split.

If we treat the original page as a left page and create a new root and right
page, then we just need to copy a predicate lock from the left to the right
page (this is the case in B-tree).

But if we treat the original page as a root and create a new left and right
page, then we need to copy a predicate lock on both new pages (in the case
of rum and gin).

link to updated code and tests:
https://github.com/shubhambaraiss/postgres/commit/6172639a104785f051cb4aa0d511c58f2bae65a6

Regards,
Shubham




<https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

On 17 July 2017 at 19:08, Shubham Barai <shubhambara...@gmail.com> wrote:

> Hi,
>
> I am attaching a patch for predicate locking in gin index.
>
>
> Regards,
> Shubham
>
>
>
> <https://mailtrack.io/> Sent with Mailtrack
> <https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
>
> On 11 July 2017 at 19:10, Shubham Barai <shubhambara...@gmail.com> wrote:
>
>> Project: Explicitly support predicate locks in index AMs besides b-tree
>>
>>
>> I have done following tasks during this week.
>>
>> 1) worked on how to detect rw conflicts when fast update is enabled
>>
>> 2) created tests for different gin operators
>>
>> 3) went through some patches on commitfest to review
>>
>> 4) solved some issues that came up while testing
>>
>> link to the code: https://github.com/shubhambaraiss/postgres/commit/1365
>> d75db36a4e398406dd266c3d4fe8e1ec30ff
>>
>> <https://mailtrack.io/> Sent with Mailtrack
>> <https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
>>
>
>


Predicate-locking-in-gin-index.patch
Description: Binary data

-- 
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: weekly progress reports (week 8)

[Shubham Barai]

Hi.

I am attaching a patch for predicate locking in SP-Gist index


Regards,
Shubham



<https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

On 26 July 2017 at 20:50, Shubham Barai <shubhambara...@gmail.com> wrote:

> Project: Explicitly support predicate locks in index AMs besides b-tree
>
> Hi,
>
> During this week, I worked on predicate locking in spgist index. I think,
> for spgist index, predicate lock only on leaf pages will be enough as
> spgist searches can determine if there is a match or not only at leaf level.
>
> I have done following things in this week.
>
> 1) read the source code of spgist index to understand  the access method
>
> 2) found appropriate places to insert calls to existing functions
>
> 3) created tests (to verify serialization failures and to demonstrate the
> feature of reduced false positives) for 'point' and 'box' data types.
>
>
> link to code and tests: https://github.com/shub
> hambaraiss/postgres/commit/d9ae709c93ff038478ada411c621faeabe6813cb
>
> I will attach the patch shortly.
>
>
> Regards,
> Shubham
>
>
>
> <https://mailtrack.io/> Sent with Mailtrack
> <https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
>


Predicate-Locking-in-spgist-index.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017: weekly progress reports (week 8)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,

During this week, I worked on predicate locking in spgist index. I think,
for spgist index, predicate lock only on leaf pages will be enough as
spgist searches can determine if there is a match or not only at leaf level.

I have done following things in this week.

1) read the source code of spgist index to understand  the access method

2) found appropriate places to insert calls to existing functions

3) created tests (to verify serialization failures and to demonstrate the
feature of reduced false positives) for 'point' and 'box' data types.


link to code and tests: https://github.com/shub
hambaraiss/postgres/commit/d9ae709c93ff038478ada411c621faeabe6813cb

I will attach the patch shortly.


Regards,
Shubham



 Sent with Mailtrack

Re: [HACKERS] GSoC 2017: weekly progress reports (week 7)

[Shubham Barai]

Hi Robert,

I had detailed discussion about this with my mentor. Sorry, I didn't share
details on hackers list.

B-tree, gist, spgist, and gin are all tree based indexes where we scan and
acquire predicate lock
on only some and not all internal pages or leaf pages. So, here we have
scope to reduce false positives.
In BRIN index, each tuple stores summarizing values in the consecutive
group of heap pages.
So initially I thought we could implement tuple level predicate locking in
BRIN. But, here we scan
the whole index which forces us to acquire predicate lock on all tuples.
Acquiring predicate lock on all
tuples will be no different than a relation level predicate lock.


Regards,
Shubham



<https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

On 20 July 2017 at 21:18, Robert Haas <robertmh...@gmail.com> wrote:

> On Tue, Jul 18, 2017 at 10:36 AM, Shubham Barai <shubhambara...@gmail.com>
> wrote:
>
>> During this week, I read documentation and source code of BRIN index to
>> understand its implementation.
>> But later I found out that it is unlikely to implement page level or
>> tuple level predicate locking in BRIN index.
>> In this week, I also fixed a small issue and updated my previous patch
>> for gin index. Currently, I am working on
>> sp-gist index.
>>
>
> It's a shame that nobody seems to be answering emails like this, but you
> also haven't provided much detail here - e.g. *why* is BRIN unlikely to
> work out well?  I think I know the answer, but it'd be good to spell out
> your thoughts on the subject, I think.
>
> --
> Robert Haas
> EnterpriseDB: http://www.enterprisedb.com
> The Enterprise PostgreSQL Company
>

[HACKERS] GSoC 2017: weekly progress reports (week 7)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,

During this week, I read documentation and source code of BRIN index to
understand its implementation.
But later I found out that it is unlikely to implement page level or tuple
level predicate locking in BRIN index.
In this week, I also fixed a small issue and updated my previous patch for
gin index. Currently, I am working on
sp-gist index.


Regards,
Shubham

 Sent with Mailtrack

Re: [HACKERS] GSoC 2017: weekly progress reports (week 6)

[Shubham Barai]

Hi,

I am attaching a patch for predicate locking in gin index.


Regards,
Shubham



<https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

On 11 July 2017 at 19:10, Shubham Barai <shubhambara...@gmail.com> wrote:

> Project: Explicitly support predicate locks in index AMs besides b-tree
>
>
> I have done following tasks during this week.
>
> 1) worked on how to detect rw conflicts when fast update is enabled
>
> 2) created tests for different gin operators
>
> 3) went through some patches on commitfest to review
>
> 4) solved some issues that came up while testing
>
> link to the code: https://github.com/shubhambaraiss/postgres/commit/
> 1365d75db36a4e398406dd266c3d4fe8e1ec30ff
>
> <https://mailtrack.io/> Sent with Mailtrack
> <https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
>


0001-Predicate-locking-in-gin-index.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017: weekly progress reports (week 6)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree


I have done following tasks during this week.

1) worked on how to detect rw conflicts when fast update is enabled

2) created tests for different gin operators

3) went through some patches on commitfest to review

4) solved some issues that came up while testing

link to the code:
https://github.com/shubhambaraiss/postgres/commit/1365d75db36a4e398406dd266c3d4fe8e1ec30ff

 Sent with Mailtrack

[HACKERS] GSoC 2017: weekly progress reports (week 5) and Proposal for predicate locking in gin index

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree


Hi,

During this week, I read documentation and source code of gin index to find
appropriate places to insert calls to existing functions.

Proposal

Gin index consists of a Btree 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.
As gin searches have to go all the way to leaf pages to determine whether
there is a match or not, we just need a predicate lock on leaf pages.

Also, gin index has a feature called fast update which postpones the
insertion of tuples by temporarily storing them into pending list. The
pending list is eventually flushed during vacuum. So this creates a problem
because even if a scan acquires a page level predicate lock on the pending
list, we will not be able to detect r-w conflict because a new insert will
just append tuples on the pending list. So, I think if a fast update is
enabled, we need a predicate lock on the entire relation.

The possible places where we need to insert calls to existing
functions are as follows

1. PredicateLockPage()

-> entryLoadMoreItems()

->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()




   Sent with Mailtrack

[HACKERS] GSoC 2017: weekly progress reports (week 4) and patch for hash index

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,

During this week, I continued my work on predicate locking in the hash
index and created a patch for it. As I have written in my proposal for the
hash index, every scan operation acquires a predicate lock on the primary
page of the bucket.
And hash indexes are used for equality comparison. So, this can still
generate false positives when a scan operation and an insert operation are
trying to access the same bucket but are looking for different tuples.
Let's see that with an example.

setup:

create table hash_tbl(id int4, p integer);

create index hash_pointidx on hash_tbl using hash(p);

insert into hash_tbl (id, p)
select g, g*2 from generate_series(1, 1000) g;

read operation:
select * from hash_tbl where p=78988658;

insert operation:
insert into hash_tbl values(, 546789888);

If these two hash keys (78988658 and 546789888) mapped to the same bucket,
this will result in false serialization failure.
Please correct me if this assumption about false positives is wrong.


In summary, I have done following things in this week.

1)  found appropriate places in the hash index AM to insert calls to
existing functions (PredicateLockPage(),  CheckForSerializableConflictIn()
...etc)

2) created tests to check serialization failures and false positives

3) tested my patch on the current head



Regards,

Shubham




   Sent with Mailtrack



Predicate-Locking-in-hash-index_3.patch
Description: Binary data

-- 
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 predicate locking in hash index

[Shubham Barai]

Hi,

On 22 June 2017 at 21:12, Alvaro Herrera <alvhe...@2ndquadrant.com> wrote:

> Shubham Barai wrote:
> > Hi,
> >
> > Now that hash index support write-ahead logging, it will be great if we
> add
> > support for predicate locking to it.
> > Implementation of predicate locking in hash index seems very simple.
> > I have already made changes in the code. I am currently working on
> testing.
>
> So if I understand correctly, this would only cause a false positive if
> two transactions have a rw/ww conflict in different tuples in the same
> bucket.  Is that what we expect?
>
> Yes, I think so. Is there any way to further reduce false positives in
the same bucket?

Regards,
Shubham


  <https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

[HACKERS] GSoC 2017 Proposal for predicate locking in hash index

[Shubham Barai]

Hi,

Now that hash index support write-ahead logging, it will be great if we add
support for predicate locking to it.
Implementation of predicate locking in hash index seems very simple.
I have already made changes in the code. I am currently working on testing.

Here is my approach

1) PredicateLockPage()

->_hash_first()

During a scan operation, acquire a predicate lock on the primary page of a
bucket.

2) CheckForSerializableConflictIn()

->_hash_doinsert()

During an insert operation, check if there is any predicate lock on the
primary page of a bucket.


3) PredicateLockPageSplit()

In case of a bucket split, copy predicate lock from the primary page of an
old bucket to the primary page of a new bucket.

Any suggestions or corrections will be appreciated.

Regards,
Shubham



   Sent with Mailtrack

Re: [HACKERS] GSoC 2017 : Patch for predicate locking in Gist index

[Shubham Barai]

Hi,

On 21 June 2017 at 13:11, Heikki Linnakangas <hlinn...@iki.fi> wrote:

> On 06/16/2017 01:24 PM, Shubham Barai wrote:
>
>> @@ -497,6 +499,13 @@ gistplacetopage(Relation rel, Size freespace,
>> GISTSTATE *giststate,
>> for (ptr = dist->next; ptr; ptr = ptr->next)
>> UnlockReleaseBuffer(ptr->buffer);
>> }
>> +
>> +   for (ptr = dist; ptr; ptr = ptr->next)
>> +   PredicateLockPageSplit(rel,
>> +
>>  BufferGetBlockNumber(buffer),
>> +
>>  BufferGetBlockNumber(ptr->buffer));
>> +
>> +
>>
>
> I think this new code needs to go before the UnlockReleaseBuffer() calls
> above. Calling BufferGetBlockNumber() on an already-released buffer is not
> cool.
>
> - Heikki
>
> I know that. This is the old version of the patch. I had sent updated
patch later. Please have a look at updated patch.

Regards,
Shubham



  <https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>


Predicate-Locking-in-Gist-index_2.patch
Description: Binary data

-- 
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 weekly progress reports (week 3)

[Shubham Barai]

Hi ,

On 19 June 2017 at 22:49, Alvaro Herrera <alvhe...@2ndquadrant.com> wrote:

> Shubham Barai wrote:
> > Project: Explicitly support predicate locks in index AMs besides b-tree
> >
> > Hi,
> >
> >
> > During this week, I continued my work on testing and created my first
> patch
> > for gist index.
>
> Please post it.
>

I have already sent my patch on 16th June. I have also registered it on
commitfest. In case you missed it, please have a look at attached patch.

Regards,
Shubham


>
> --
> Álvaro Herrerahttps://www.2ndQuadrant.com/
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>


Predicate-Locking-in-Gist-index_2.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017 weekly progress reports (week 3)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,


During this week, I continued my work on testing and created my first patch
for gist index. I have also started working on the hash index. In summary,
I have done following things in this week.

1) updated tests to check false positives

2) created tests for index scan

3) fixed a small issue with "make check"

4) fixed a small bug in the code by updating the location of
predicatelockpagesplit().

5) read the source code of hash index to understand its implementation

Regards,
Shubham



   Sent with Mailtrack

Re: [HACKERS] GSoC 2017 : Patch for predicate locking in Gist index

[Shubham Barai]

Hi,

Please find the updated patch here.

Regards,
Shubham

On 16 June 2017 at 15:54, Shubham Barai <shubhambara...@gmail.com> wrote:

> Hi, hackers!
>
> I have created my first patch for predicate locking in gist index. It
> includes a test for verification of serialization failures and a test to
> check false positives.
> I am submitting my patch little late because there were some issues with
> "make check" that I was trying to solve. Now, the patch passes all existing
> tests.
>
> Regards,
> Shubham
>
>
>
>   <https://mailtrack.io/> Sent with Mailtrack
> <https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>
>


Predicate-Locking-in-Gist-index_2.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017 : Patch for predicate locking in Gist index

[Shubham Barai]

Hi, hackers!

I have created my first patch for predicate locking in gist index. It
includes a test for verification of serialization failures and a test to
check false positives.
I am submitting my patch little late because there were some issues with
"make check" that I was trying to solve. Now, the patch passes all existing
tests.

Regards,
Shubham



   Sent with Mailtrack



0001-Predicate-Locking-in-Gist-index.patch
Description: Binary data

-- 
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 weekly progress reports (week 2)

[Shubham Barai]

On 15 June 2017 at 07:23, Alvaro Herrera <alvhe...@2ndquadrant.com> wrote:

> Shubham Barai wrote:
> > Hi,
> >
> > I have made some changes in tests and pushed them to my branch.
> >
> > Thanks for helping me out with testing.
> >
> > Now, current head produces false positives but, with my patch, it
> doesn't.
> >
> > Here is the link for updated tests:
> > https://github.com/shubhambaraiss/postgres/commit/
> 2c02685a50a2b30654beb5c52542a57a46219c39
>
> Nice.  Please provide patches, so that it can be considered for commit.
>

Yes, I will provide a patch shortly. I just need to update documentation
first.

>
> --
> Álvaro Herrerahttps://www.2ndQuadrant.com/
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>




  <https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

Re: [HACKERS] GSoC 2017 weekly progress reports (week 2)

[Shubham Barai]

Hi,

I have made some changes in tests and pushed them to my branch.

Thanks for helping me out with testing.

Now, current head produces false positives but, with my patch, it doesn't.

Here is the link for updated tests:
https://github.com/shubhambaraiss/postgres/commit/2c02685a50a2b30654beb5c52542a57a46219c39


Regards,
Shubham



  <https://mailtrack.io/> Sent with Mailtrack
<https://mailtrack.io/install?source=signature=en=shubhambara...@gmail.com=22>

On 13 June 2017 at 23:32, Andrew Borodin <boro...@octonica.com> wrote:

> 2017-06-13 18:00 GMT+05:00 Shubham Barai <shubhambara...@gmail.com>:
> >
> > Project: Explicitly support predicate locks in index AMs besides b-tree
> >
> Hi, Shubham
> Good job!
>
> So, in current HEAD test predicate_gist_2.spec generate false
> positives, but with your patch, it does not?
> I'd suggest keeping spec tests with your code in the same branch, it's
> easier. Also it worth to clean up specs style and add some words to
> documentation.
>
> Kevin, all, how do you think, is it necessary to expand these tests
> not only on Index Only Scan, but also on Bitmap Index Scan? And may be
> KNN version of scan too?
> I couldn't find such tests for B-tree, do we have them?
>
> Best regards, Andrey Borodin, Octonica.
>

[HACKERS] GSoC 2017 weekly progress reports (week 2)

[Shubham Barai]

Project: Explicitly support predicate locks in index AMs besides b-tree

Hi,

During this week, I mostly worked on testing to verify my code and on
debugging to solve some issues I was having. I have specifically created
two tests. The first test is about verifying serialization failure when
there is a read-write conflict. The second one is about checking false
positives. We need to make sure that it doesn't generate false positive
serialization failures.  So far, I have got expected results. Any feedback
on results will be appreciated.

link to the code :
https://github.com/shubhambaraiss/postgres/commit/0a76b02b80f8e4edb63370540005515a7cd9d549

For more details about testing, please have a look at attached files.




Regards,
Shubham



   Sent with Mailtrack



predicate_gist.out
Description: Binary data


predicate_gist.spec
Description: Binary data


predicate_gist_2.out
Description: Binary data


predicate_gist_2.spec
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] GSoC 2017 weekly progress reports ("Explicitly support predicate locks in index access methods besides b-tree")

[Shubham Barai]

GSoC (week 1)


Hi,

Here is the list of things I have done during this week.

1. read documentation on how to set up development environment

2. installed PostgreSQL on Ubuntu from source code

3. read documentation on gist index (http://www.sai.msu.su/~
megera/postgres/gist/)

4. went through source code of gist index to understand its implementation

5. found appropriate places in gist index AM to insert calls to existing
functions (PredicateLockPage(),  CheckForSerializableConflictIn() ...etc)

Re: [HACKERS] GSoC 2017 : Proposal for predicate locking in gist index

[Shubham Barai]

Hi, Kevin sir!

On 1 June 2017 at 02:20, Kevin Grittner <kgri...@gmail.com> wrote:

> On Wed, May 31, 2017 at 3:02 PM, Shubham Barai <shubhambara...@gmail.com>
> wrote:
>
> > I have been accepted as GSoC student for the project "Explicitly support
> > predicate locks in index access methods besides b-tree". I want to share
> my
> > approach for implementation of page level predicate locking in gist
> index.
>
> For the benefit of all following the discussion, implementing
> support in an index AM conceptually consists of two things:
> (1) Any scan with user-visible results must create SIRead predicate
> locks on "gaps" scanned.  (For example, a scan just to find an
> insertion spot for an index entry does not generally count, whereas
> a scan to satisfy a user "EXISTS" test does.)
> (2) Any insert into the index must CheckForSerializableConflictIn()
> at enough points that at least one of them will detect an overlap
> with a predicate lock from a preceding scan if the inserted index
> entry might have changed the results of that preceding scan.
>
> Detecting such a conflict does not automatically result in a
> serialization failure, but is only part of tracking the information
> necessary to make such a determination.  All that is handled by the
> existing machinery if the AM does the above.
>
> With a btree index, locking gaps at the leaf level is normally
> sufficient, because both scan and insertion of an index entry must
> descend that far.
>
> > The main difference between b-tree and gist index while searching for a
> > target tuple is that in gist index, we can determine if there is a match
> or
> > not at any level of the index.
>
> Agreed.  A gist scan can fail at any level, but for that scan to
> have produced a different result due to insertion of an index entry,
> *some* page that the scan looked at must be modified.
>
> > The simplest way to do that will be by inserting a call for
> > prdicatelockpage() in gistscanpage().
>
> Yup.
>
> > Insertion algorithm also needs to check for conflicting predicate locks
> at
> > each level of the index.
>
> Yup.
>
> > We can insert a call for CheckForSerializableConflictIn() at two places
> in
> > gistdoinsert().
> >
> > 1. after acquiring an exclusive lock on internal page (in case we are
> trying
> > to replace an old search key)
> >
> > 2. after acquiring an exclusive lock on leaf page
> >
> > If there is not enough space for insertion, we have to copy predicate
> lock
> > from an old page to all new pages generated after a successful split
> > operation. For that, we can insert a call for PredicateLockPageSplit() in
> > gistplacetopage().
>
> That all sounds good.  When you code a patch, don't forget to add
> tests to src/test/isolation.
>

> Do you need any help getting a development/build/test environment
> set up?
>

 Yes, any link to the documentation will be helpful.

>
> --
> Kevin Grittner
> VMware vCenter Server
> https://www.vmware.com/
>

[HACKERS] GSoC 2017 : Proposal for predicate locking in gist index

[Shubham Barai]

Hello everyone,



I have been accepted as GSoC student for the project "Explicitly support
predicate locks in index access methods besides b-tree". I want to share my
approach for implementation of page level predicate locking in gist index.
Any suggestions will be appreciated.



Proposal



The main difference between b-tree and gist index while searching for a
target tuple is that in gist index, we can determine if there is a match or
not at any level of the index. In gist, index entry of internal nodes
contains a predicate which is used as a search key to search all reachable
tuples from that node. To insert a tuple in the index, we first check the
key representing a target subtree. If it doesn't already cover the key we
are inserting, we have to replace it with the union of old key and the key
we are inserting. After considering all these points, it seems logical to
acquire a predicate lock at each level of the index.

The simplest way to do that will be by inserting a call for
prdicatelockpage() in gistscanpage().

Insertion algorithm also needs to check for conflicting predicate locks at
each level of the index.

We can insert a call for CheckForSerializableConflictIn() at two places in
gistdoinsert().

1. after acquiring an exclusive lock on internal page (in case we are
trying to replace an old search key)

2. after acquiring an exclusive lock on leaf page

If there is not enough space for insertion, we have to copy predicate lock
from an old page to all new pages generated after a successful split
operation. For that, we can insert a call for PredicateLockPageSplit() in
gistplacetopage().



Regards,

Shubham

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

[Shubham Barai]

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

[HACKERS] about google summer of code 2016

[Shubham Barai]

Hello everyone,

I am currently pursuing my bachelor of engineering in computer science
at Maharashtra
Institute of Technology, Pune ,India. I am very excited about contributing
to postgres through google summer of code program.

Is postgres   applying for gsoc 2016 as mentoring organization ?


Thanks,
Shubham Barai

[HACKERS] Optimization- Check the set of conditionals on a WHERE clause against CHECK constraints.

[Shubham Barai]

Hello hackers,

I was searching for project ideas and found this

1.Optimization- Check the set of conditionals on a WHERE clause against
CHECK constraints  on the table being queried and remove any conditionals
which *must* be true due to the CHECK constraints.

Is it expensive for  simple queries?

will it optimize  general queries ?

Any thoughts will be helpful.
Thanks.

[HACKERS] UNIQUE capability to hash indexes

[Shubham Barai]

Hello hackers ,
I wanted to know if anyone is working on these projects from todo list.

1.Add UNIQUE capability to hash indexes

2.Allow multi-column hash indexes

I couldn't find any discussion about these projects.

Thanks,
Shubham Barai