GSoC 2017: weekly progress reports (week 6)

Hi,

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

Regards,
Shubham

<https://mailtrack.io/&gt; Sent with Mailtrack
<https://mailtrack.io/install?source=signature&amp;lang=en&amp;referral=shubhambaraiss@gmail.com&amp;idSignature=22&gt;

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

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/&gt; Sent with Mailtrack
<https://mailtrack.io/install?source=signature&amp;lang=en&amp;referral=shubhambaraiss@gmail.com&amp;idSignature=22&gt;

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

Hi!

On Wed, Aug 9, 2017 at 6:30 PM, Shubham Barai <shubhambaraiss@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/
shubhambaraiss/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.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, Sep 28, 2017 at 12:45 AM, Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:

On Wed, Aug 9, 2017 at 6:30 PM, Shubham Barai <shubhambaraiss@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.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

<https://mailtrack.io/&gt; Sent with Mailtrack
<https://mailtrack.io/install?source=signature&amp;lang=en&amp;referral=shubhambaraiss@gmail.com&amp;idSignature=22&gt;
<#>

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

wrote:

On Thu, Sep 28, 2017 at 12:45 AM, Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:

On Wed, Aug 9, 2017 at 6:30 PM, Shubham Barai <shubhambaraiss@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

On Sat, Sep 30, 2017 at 6:12 PM, Shubham Barai <shubhambaraiss@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.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

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

On Sat, Sep 30, 2017 at 6:12 PM, Shubham Barai <shubhambaraiss@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

On Sun, Oct 1, 2017 at 11:53 AM, Shubham Barai <shubhambaraiss@gmail.com>
wrote:

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 ?

I think that isolation tests should be improved. It doesn't seems that any
posting tree would be generated by the tests that you've provided, because
all the TIDs could fit the single posting list. Note, that you can get
some insight into GIN physical structure using pageinspect contrib.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Tue, Oct 3, 2017 at 1:51 AM, Alexander Korotkov
<a.korotkov@postgrespro.ru> wrote:

I think that isolation tests should be improved. It doesn't seems that any
posting tree would be generated by the tests that you've provided, because
all the TIDs could fit the single posting list. Note, that you can get some
insight into GIN physical structure using pageinspect contrib.

This thread had no updates for almost two months, so I am marking it
as returned with feedback.
--
Michael

On 2 October 2017 at 22:21, Alexander Korotkov <a.korotkov@postgrespro.ru>
wrote:

On Sun, Oct 1, 2017 at 11:53 AM, Shubham Barai <shubhambaraiss@gmail.com>
wrote:

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 ?

I think that isolation tests should be improved. It doesn't seems that
any posting tree would be generated by the tests that you've provided,
because all the TIDs could fit the single posting list. Note, that you can
get some insight into GIN physical structure using pageinspect contrib.

I have created new isolation tests. Please have a look at
updated patch.

Regards,
Shubham

On Wed, Jan 3, 2018 at 4:31 AM, Shubham Barai <shubhambaraiss@gmail.com> wrote:

I have created new isolation tests. Please have a look at
updated patch.

Hi Shubham,

Could we please have a rebased version of the gin one?

--
Thomas Munro
http://www.enterprisedb.com

On 28 February 2018 at 05:51, Thomas Munro <thomas.munro@enterprisedb.com>
wrote:

On Wed, Jan 3, 2018 at 4:31 AM, Shubham Barai <shubhambaraiss@gmail.com>
wrote:

I have created new isolation tests. Please have a look at
updated patch.

Hi Shubham,

Could we please have a rebased version of the gin one?

Sure. I have attached a rebased version

Regards,
Shubham

This appears to be a duplicate of https://commitfest.postgresql.org/17/1466/ - as the other one is older, I'm closing this one.

Hi!

28 февр. 2018 г., в 22:19, Shubham Barai <shubhambaraiss@gmail.com> написал(а):

Sure. I have attached a rebased version

I've looked into the code closely again. The patch is heavily reworked since GSoC state :)
Tests are looking fine and locking is fine-grained.
But there is one thing I could not understand:
Why do we take a lock during moveRightIfItNeeded()?
This place is supposed to be called whenever page is split just before we a locking it and right after we've come to the page from parent.

Best regards, Andrey Borodin.

Andres Freund wrote:

This appears to be a duplicate of https://commitfest.postgresql.org/17/1466/ - as the other one is older, I'm closing this one.

This comment makes no sense from the POV of the mail archives. I had to
look at the User-Agent in your email to realize that you wrote it in the
commitfest app. I see three problems here

1. impersonating the "From:" header is a bad idea; needs fixed much as
we did with the bugs and doc comments submission forms
2. it should have had a header indicating it comes from CF app
3. it would be great to include in said header a link to the CF entry
to which the comment was attached.

Thanks

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

I suggest to create a new function GinPredicateLockPage() that checks
whether fast update is enabled for the index. The current arrangement
looks too repetitive and it seems easy to make a mistake.

Stylistically, please keep #include lines ordered alphabetically, and
cut long lines to below 80 chars.

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi,

On 2018-03-07 11:58:51 -0300, Alvaro Herrera wrote:

This appears to be a duplicate of https://commitfest.postgresql.org/17/1466/ - as the other one is older, I'm closing this one.

This comment makes no sense from the POV of the mail archives. I had to
look at the User-Agent in your email to realize that you wrote it in the
commitfest app.

Yea, I stopped doing so afterwards...

1. impersonating the "From:" header is a bad idea; needs fixed much as
we did with the bugs and doc comments submission forms
2. it should have had a header indicating it comes from CF app
3. it would be great to include in said header a link to the CF entry
to which the comment was attached.

Sounds reasonable.

Greetings,

Andres Freund

On 07-Mar-2018 11:00 PM, "Alvaro Herrera" <alvherre@2ndquadrant.com> wrote:

I suggest to create a new function GinPredicateLockPage() that checks
whether fast update is enabled for the index. The current arrangement
looks too repetitive and it seems easy to make a mistake.

Stylistically, please keep #include lines ordered alphabetically, and
cut long lines to below 80 chars.

Okay, I will update the patch.

On Wed, Mar 7, 2018 at 8:30 PM, Alvaro Herrera <alvherre@2ndquadrant.com>
wrote:

I suggest to create a new function GinPredicateLockPage() that checks
whether fast update is enabled for the index. The current arrangement
looks too repetitive and it seems easy to make a mistake.

BTW, should we also skip CheckForSerializableConflictIn() when
fast update is enabled? AFAICS, now it doesn't cause any errors or
false positives, but makes useless load. Is it correct?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company