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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

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, 10000000) g;

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

insert operation:
insert into hash_tbl values(99999999, 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


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

Predicate-Locking-in-hash-index_3.patch (39K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Thomas Munro-3
Hi Shubham,

On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <[hidden email]> 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


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> wrote:
Hi Shubham,

On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <[hidden email]> 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



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

Predicate-locking-in-hash-index_4.patch (41K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Alexander Korotkov-3
In reply to this post by Thomas Munro-3
On Fri, Sep 8, 2017 at 4:07 AM, Thomas Munro <[hidden email]> wrote:
Hi Shubham,

On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <[hidden email]> 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.

+1,
Very nice idea!  Locking hash values directly seems to be superior over locking hash index pages.
Shubham, do you have any comment on this?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Michael Paquier
In reply to this post by Shubham Barai
On Mon, Sep 25, 2017 at 10:34 PM, Shubham Barai
<[hidden email]> wrote:
> I have attached the rebased version of patch here.

The patch does not apply and there has been no reviews as well. In
consequence, I am moving it to next CF with "waiting on author" as
status. Please provide a rebased patch.
--
Michael

Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Stephen Frost
Greeting Shubham, all,

* Michael Paquier ([hidden email]) wrote:
> On Mon, Sep 25, 2017 at 10:34 PM, Shubham Barai
> <[hidden email]> wrote:
> > I have attached the rebased version of patch here.
>
> The patch does not apply and there has been no reviews as well. In
> consequence, I am moving it to next CF with "waiting on author" as
> status. Please provide a rebased patch.

Shubham, would you mind providing an updated patch which applies
cleanly, so we can change this to Needs Review and hopefully get someone
looking at it?  Also, it would be good to respond to Alexander's as to
if it would work or not (and perhaps updating the patch accordingly).
Otherwise, I'm afriad this patch may end up just getting bumped to the
next CF or ending up as 'returned with feedback'.  Would be great to get
this up to a point where it could be committed.

Thanks!

Stephen

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Shubham Barai


On 15 January 2018 at 08:03, Stephen Frost <[hidden email]> wrote:
Greeting Shubham, all,

* Michael Paquier ([hidden email]) wrote:
> On Mon, Sep 25, 2017 at 10:34 PM, Shubham Barai
> <[hidden email]> wrote:
> > I have attached the rebased version of patch here.
>
> The patch does not apply and there has been no reviews as well. In
> consequence, I am moving it to next CF with "waiting on author" as
> status. Please provide a rebased patch.

Shubham, would you mind providing an updated patch which applies
cleanly, so we can change this to Needs Review and hopefully get someone
looking at it?  Also, it would be good to respond to Alexander's as to
if it would work or not (and perhaps updating the patch accordingly).
Otherwise, I'm afriad this patch may end up just getting bumped to the
next CF or ending up as 'returned with feedback'.  Would be great to get
this up to a point where it could be committed.



Hi Stephen,

The new approach was suggested after completion of GSoC. So, I didn't get
enough time to implement this approach. Also, I was constantly updating my
patches for gist and gin index based on reviews.

Here, I am attaching the rebased version of the patch (which is based on an old approch:
acquiring a predicate lock on primary page of a bucket)

Kind Regards,
Shubham


Predicate-Locking-in-hash-index_v5.patch (39K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

akapila
In reply to this post by Alexander Korotkov-3
On Fri, Sep 29, 2017 at 8:20 PM, Alexander Korotkov
<[hidden email]> wrote:

> On Fri, Sep 8, 2017 at 4:07 AM, Thomas Munro <[hidden email]>
> wrote:
>>
>> Hi Shubham,
>>
>> On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <[hidden email]>
>> 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.
>
>
> +1,
> Very nice idea!  Locking hash values directly seems to be superior over
> locking hash index pages.
> Shubham, do you have any comment on this?
>

As Shubham seems to be running out of time, I thought of helping him
by looking into the above-suggested idea.  I think one way to lock a
particular hash value is we can use TID of heap tuple associated with
each index entry (index entry for the hash index will be hash value).
However, do we really need it for implementing predicate locking for
hash indexes?  If we look at the "Index AM implementations" section of
README-SSI, it doesn't seem to be required.  Basically, if we look at
the strategy of predicate locks in btree [1], it seems to me locking
at page level for hash index seems to be a right direction as similar
to btree, the corresponding heap tuple read will be locked.

What do you think?

[1] -
    * B-tree index searches acquire predicate locks only on the index
*leaf* pages needed to lock the appropriate index range. If, however,
a search discovers that no root page has yet been created, a predicate
lock on the index relation is required.


--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Alexander Korotkov-3
On Sat, Jan 20, 2018 at 4:24 PM, Amit Kapila <[hidden email]> wrote:
On Fri, Sep 29, 2017 at 8:20 PM, Alexander Korotkov
<[hidden email]> wrote:
> On Fri, Sep 8, 2017 at 4:07 AM, Thomas Munro <[hidden email]>
> wrote:
>>
>> Hi Shubham,
>>
>> On Tue, Jun 27, 2017 at 9:21 PM, Shubham Barai <[hidden email]>
>> 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.
>
>
> +1,
> Very nice idea!  Locking hash values directly seems to be superior over
> locking hash index pages.
> Shubham, do you have any comment on this?
>

As Shubham seems to be running out of time, I thought of helping him
by looking into the above-suggested idea.  I think one way to lock a
particular hash value is we can use TID of heap tuple associated with
each index entry (index entry for the hash index will be hash value).

Sorry, I didn't get what do you particularly mean.  If locking either TID of
associated heap tuple or TID of hash index tuple, then what will we lock
in the case when nothing found?  Even if we found nothing, we have
to place some lock according to search key in order to detect cases when
somebody has inserted the row which we might see according to that search key.
 
However, do we really need it for implementing predicate locking for
hash indexes?  If we look at the "Index AM implementations" section of
README-SSI, it doesn't seem to be required.  Basically, if we look at
the strategy of predicate locks in btree [1], it seems to me locking
at page level for hash index seems to be a right direction as similar
to btree, the corresponding heap tuple read will be locked.

Btree uses leaf-pages locking because it supports both range searches
and exact value searches.  And it needs to detect overlaps between
these two kinds of searches.  Therefore, btree locks leaf-pages in both
cases.  Hash index case is different.  Hash index doesn't support and
isn't going to support range searches.  Assuming, that hash index
supports only exact value searches, locking hash values would be
superior over page locking (unless I'm missing something), because
it would provide better locality of locks.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

akapila
On Thu, Jan 25, 2018 at 7:29 PM, Alexander Korotkov
<[hidden email]> wrote:

> On Sat, Jan 20, 2018 at 4:24 PM, Amit Kapila <[hidden email]>
> wrote:
>>
>> On Fri, Sep 29, 2017 at 8:20 PM, Alexander Korotkov
>> <[hidden email]> wrote:
>> > +1,
>> > Very nice idea!  Locking hash values directly seems to be superior over
>> > locking hash index pages.
>> > Shubham, do you have any comment on this?
>> >
>>
>> As Shubham seems to be running out of time, I thought of helping him
>> by looking into the above-suggested idea.  I think one way to lock a
>> particular hash value is we can use TID of heap tuple associated with
>> each index entry (index entry for the hash index will be hash value).
>
>
> Sorry, I didn't get what do you particularly mean.  If locking either TID of
> associated heap tuple or TID of hash index tuple, then what will we lock
> in the case when nothing found?  Even if we found nothing, we have
> to place some lock according to search key in order to detect cases when
> somebody has inserted the row which we might see according to that search
> key.
>

Okay, but if you use hash value as lock tag (which is possible) how
will we deal with things like page split?  I think even if use
blocknumber/page/bucketnumber corresponding to the hash value along
with hash value in lock tag, then also it doesn't appear to work.  I
think using page level locks for index makes sense, especially because
it will be convinient to deal with page splits.  Also, as predicate
locks stay in-memory, so creating too many such locks doesn't sound
like a nice strategy even though we have a way to upgrade it to next
level (page) as that has a separate cost to it.

>>
>> However, do we really need it for implementing predicate locking for
>> hash indexes?  If we look at the "Index AM implementations" section of
>> README-SSI, it doesn't seem to be required.  Basically, if we look at
>> the strategy of predicate locks in btree [1], it seems to me locking
>> at page level for hash index seems to be a right direction as similar
>> to btree, the corresponding heap tuple read will be locked.
>
>
> Btree uses leaf-pages locking because it supports both range searches
> and exact value searches.  And it needs to detect overlaps between
> these two kinds of searches.  Therefore, btree locks leaf-pages in both
> cases.
>

Also, probably using page level locks makes it easier to deal index
operations like page split.

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

akapila
On Sun, Jan 28, 2018 at 7:28 AM, Amit Kapila <[hidden email]> wrote:

> On Thu, Jan 25, 2018 at 7:29 PM, Alexander Korotkov
> <[hidden email]> wrote:
>>> As Shubham seems to be running out of time, I thought of helping him
>>> by looking into the above-suggested idea.  I think one way to lock a
>>> particular hash value is we can use TID of heap tuple associated with
>>> each index entry (index entry for the hash index will be hash value).
>>
>>
>> Sorry, I didn't get what do you particularly mean.  If locking either TID of
>> associated heap tuple or TID of hash index tuple, then what will we lock
>> in the case when nothing found?  Even if we found nothing, we have
>> to place some lock according to search key in order to detect cases when
>> somebody has inserted the row which we might see according to that search
>> key.
>>
>
> Okay, but if you use hash value as lock tag (which is possible) how
> will we deal with things like page split?  I think even if use
> blocknumber/page/bucketnumber corresponding to the hash value along
> with hash value in lock tag, then also it doesn't appear to work.  I
> think using page level locks for index makes sense, especially because
> it will be convinient to deal with page splits.
>

What I intend to say here is that we already have a mechanism like
PredicateLockPageSplit() which can deal with predicate locks during
page split if we operate at page level.  However, if we want to go for
has value locking technique, it can be quite complex and expensive to
make it work as we have to search all the locks that belong to the
bucket being split and then move them for the new bucket.

Alexander/Thomas, do you have better ideas to make it work, otherwise,
I think we can proceed to review the Shubham's current approach/patch?

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Reply | Threaded
Open this post in threaded view
|

Re: GSoC 2017: weekly progress reports (week 4) and patch for hash index

Thomas Munro-3
On Tue, Feb 13, 2018 at 4:28 PM, Amit Kapila <[hidden email]> wrote:

> On Sun, Jan 28, 2018 at 7:28 AM, Amit Kapila <[hidden email]> wrote:
>> On Thu, Jan 25, 2018 at 7:29 PM, Alexander Korotkov
>> <[hidden email]> wrote:
>>>> As Shubham seems to be running out of time, I thought of helping him
>>>> by looking into the above-suggested idea.  I think one way to lock a
>>>> particular hash value is we can use TID of heap tuple associated with
>>>> each index entry (index entry for the hash index will be hash value).
>>>
>>>
>>> Sorry, I didn't get what do you particularly mean.  If locking either TID of
>>> associated heap tuple or TID of hash index tuple, then what will we lock
>>> in the case when nothing found?  Even if we found nothing, we have
>>> to place some lock according to search key in order to detect cases when
>>> somebody has inserted the row which we might see according to that search
>>> key.
>>>
>>
>> Okay, but if you use hash value as lock tag (which is possible) how
>> will we deal with things like page split?  I think even if use
>> blocknumber/page/bucketnumber corresponding to the hash value along
>> with hash value in lock tag, then also it doesn't appear to work.  I
>> think using page level locks for index makes sense, especially because
>> it will be convinient to deal with page splits.
>>
>
> What I intend to say here is that we already have a mechanism like
> PredicateLockPageSplit() which can deal with predicate locks during
> page split if we operate at page level.  However, if we want to go for
> has value locking technique, it can be quite complex and expensive to
> make it work as we have to search all the locks that belong to the
> bucket being split and then move them for the new bucket.

True.

One way to avoid all that might be to use pseudo page numbers that
don't suffer from splits.   I don't know how you'd choose the
constant, but it could be something like pseudo page number = hash
value % 1024.  In other words, you'd use the full hash value for the
'tuple' part of the predicate lock tag, and a shorter hash value for
the 'page' part of the predicate lock tag, so you'd never have to
handle split, and promotion from fine grained 'tuple' (= hash value)
locks to coarse grained 'page' = (short hash value) locks would still
work automatically when space runs out.

> Alexander/Thomas, do you have better ideas to make it work, otherwise,
> I think we can proceed to review the Shubham's current approach/patch?

I think we should proceed to review the current patch.  As far as I
can see, adding more fine-grained locking would remain a possibility
for future improvement.  With this patch we get page-level hash index
SIREAD locks, and perhaps in a future patch we could add fine grained
hash value SIREAD locks (maybe as described above, if that works...)

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

Previous Thread Next Thread