Hash Indexes

On Tue, May 10, 2016 at 5:39 PM, Amit Kapila <amit.kapila16@gmail.com>
wrote:

Incomplete Splits
--------------------------
Incomplete splits can be completed either by vacuum or insert as both
needs exclusive lock on bucket. If vacuum finds split-in-progress flag on
a bucket then it will complete the split operation, vacuum won't see this
flag if actually split is in progress on that bucket as vacuum needs
cleanup lock and split retains pin till end of operation. To make it work
for Insert operation, one simple idea could be that if insert finds
split-in-progress flag, then it releases the current exclusive lock on
bucket and tries to acquire a cleanup lock on bucket, if it gets cleanup
lock, then it can complete the split and then the insertion of tuple, else
it will have a exclusive lock on bucket and just perform the insertion of
tuple. The disadvantage of trying to complete the split in vacuum is that
split might require new pages and allocating new pages at time of vacuum is
not advisable. The disadvantage of doing it at time of Insert is that
Insert might skip it even if there is some scan on the bucket is going on
as scan will also retain pin on the bucket, but I think that is not a big
deal. The actual completion of split can be done in two ways: (a) scan
the new bucket and build a hash table with all of the TIDs you find
there. When copying tuples from the old bucket, first probe the hash
table; if you find a match, just skip that tuple (idea suggested by
Robert Haas offlist) (b) delete all the tuples that are marked as
moved_by_split in the new bucket and perform the split operation from the
beginning using old bucket.

I have completed the patch with respect to incomplete splits and delayed
cleanup of garbage tuples. For incomplete splits, I have used the option
(a) as mentioned above. The incomplete splits are completed if the
insertion sees split-in-progress flag in a bucket. The second major thing
this new version of patch has achieved is cleanup of garbage tuples i.e the
tuples that are left in old bucket during split. Currently (in HEAD), as
part of a split operation, we clean the tuples from old bucket after moving
them to new bucket, as we have heavy-weight locks on both old and new
bucket till the whole split operation. In the new design, we need to take
cleanup lock on old bucket and exclusive lock on new bucket to perform the
split operation and we don't retain those locks till the end (release the
lock as we move on to overflow buckets). Now to cleanup the tuples we need
a cleanup lock on a bucket which we might not have at split-end. So I
choose to perform the cleanup of garbage tuples during vacuum and when
re-split of the bucket happens as during both the operations, we do hold
cleanup lock. We can extend the cleanup of garbage to other operations as
well if required.

I have done some performance tests with this new version of patch and
results are on same lines as in my previous e-mail. I have done some
functional testing of the patch as well. I think more detailed testing is
required, however it is better to do that once the design is discussed and
agreed upon.

I have improved the code comments to make the new design clear, but still
one can have questions related to locking decisions I have taken in patch.
I think one of the important thing to verify in the patch is locking
strategy used for different operations. I have changed heavy-weight locks
to a light-weight read and write locks and a cleanup lock for vacuum and
split operation.

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

On Tue, May 10, 2016 at 8:09 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

For making hash indexes usable in production systems, we need to improve its concurrency and make them crash-safe by WAL logging them. The first problem I would like to tackle is improve the concurrency of hash indexes. First advantage, I see with improving concurrency of hash indexes is that it has the potential of out performing btree for "equal to" searches (with my WIP patch attached with this mail, I could see hash index outperform btree index by 20 to 30% for very simple cases which are mentioned later in this e-mail). Another advantage as explained by Robert [1] earlier is that if we remove heavy weight locks under which we perform arbitrarily large number of operations, it can help us to sensibly WAL log it. With this patch, I would also like to make hash indexes capable of completing the incomplete_splits which can occur due to interrupts (like cancel) or errors or crash.

I have studied the concurrency problems of hash index and some of the solutions proposed for same previously and based on that came up with below solution which is based on idea by Robert [1], community discussion on thread [2] and some of my own thoughts.

Maintain a flag that can be set and cleared on the primary bucket page, call it split-in-progress, and a flag that can optionally be set on particular index tuples, call it moved-by-split. We will allow scans of all buckets and insertions into all buckets while the split is in progress, but (as now) we will not allow more than one split for a bucket to be in progress at the same time. We start the split by updating metapage to incrementing the number of buckets and set the split-in-progress flag in primary bucket pages for old and new buckets (lets number them as old bucket - N+1/2; new bucket - N + 1 for the matter of discussion). While the split-in-progress flag is set, any scans of N+1 will first scan that bucket, ignoring any tuples flagged moved-by-split, and then ALSO scan bucket N+1/2. To ensure that vacuum doesn't clean any tuples from old or new buckets till this scan is in progress, maintain a pin on both of the buckets (first pin on old bucket needs to be acquired). The moved-by-split flag never has any effect except when scanning the new bucket that existed at the start of that particular scan, and then only if the split-in-progress flag was also set at that time.

You really need parentheses in (N+1)/2. Because you are not trying to
add 1/2 to N. https://en.wikipedia.org/wiki/Order_of_operations

Once the split operation has set the split-in-progress flag, it will begin scanning bucket (N+1)/2. Every time it finds a tuple that properly belongs in bucket N+1, it will insert the tuple into bucket N+1 with the moved-by-split flag set. Tuples inserted by anything other than a split operation will leave this flag clear, and tuples inserted while the split is in progress will target the same bucket that they would hit if the split were already complete. Thus, bucket N+1 will end up with a mix of moved-by-split tuples, coming from bucket (N+1)/2, and unflagged tuples coming from parallel insertion activity. When the scan of bucket (N+1)/2 is complete, we know that bucket N+1 now contains all the tuples that are supposed to be there, so we clear the split-in-progress flag on both buckets. Future scans of both buckets can proceed normally. Split operation needs to take a cleanup lock on primary bucket to ensure that it doesn't start if there is any Insertion happening in the bucket. It will leave the lock on primary bucket, but not pin as it proceeds for next overflow page. Retaining pin on primary bucket will ensure that vacuum doesn't start on this bucket till the split is finished.

In the second-to-last sentence, I believe you have reversed the words
"lock" and "pin".

Insertion will happen by scanning the appropriate bucket and needs to retain pin on primary bucket to ensure that concurrent split doesn't happen, otherwise split might leave this tuple unaccounted.

What do you mean by "unaccounted"?

Now for deletion of tuples from (N+1/2) bucket, we need to wait for the completion of any scans that began before we finished populating bucket N+1, because otherwise we might remove tuples that they're still expecting to find in bucket (N+1)/2. The scan will always maintain a pin on primary bucket and Vacuum can take a buffer cleanup lock (cleanup lock includes Exclusive lock on bucket and wait till all the pins on buffer becomes zero) on primary bucket for the buffer. I think we can relax the requirement for vacuum to take cleanup lock (instead take Exclusive Lock on buckets where no split has happened) with the additional flag has_garbage which will be set on primary bucket, if any tuples have been moved from that bucket, however I think for squeeze phase (in this phase, we try to move the tuples from later overflow pages to earlier overflow pages in the bucket and then if there are any empty overflow pages, then we move them to kind of a free pool) of vacuum, we need a cleanup lock, otherwise scan results might get effected.

affected, not effected.

I think this is basically correct, although I don't find it to be as
clear as I think it could be. It seems very clear that any operation
which potentially changes the order of tuples in the bucket chain,
such as the squeeze phase as currently implemented, also needs to
exclude all concurrent scans. However, I think that it's OK for
vacuum to remove tuples from a given page with only an exclusive lock
on that particular page. Also, I think that when cleaning up after a
split, an exclusive lock is likewise sufficient to remove tuples from
a particular page provided that we know that every scan currently in
progress started after split-in-progress was set. If each scan holds
a pin on the primary bucket and setting the split-in-progress flag
requires a cleanup lock on that page, then this is always true.

(Plain text email is preferred to HTML on this mailing list.)

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Thu, Jun 16, 2016 at 3:28 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Incomplete splits can be completed either by vacuum or insert as both
needs exclusive lock on bucket. If vacuum finds split-in-progress flag on a
bucket then it will complete the split operation, vacuum won't see this flag
if actually split is in progress on that bucket as vacuum needs cleanup lock
and split retains pin till end of operation. To make it work for Insert
operation, one simple idea could be that if insert finds split-in-progress
flag, then it releases the current exclusive lock on bucket and tries to
acquire a cleanup lock on bucket, if it gets cleanup lock, then it can
complete the split and then the insertion of tuple, else it will have a
exclusive lock on bucket and just perform the insertion of tuple. The
disadvantage of trying to complete the split in vacuum is that split might
require new pages and allocating new pages at time of vacuum is not
advisable. The disadvantage of doing it at time of Insert is that Insert
might skip it even if there is some scan on the bucket is going on as scan
will also retain pin on the bucket, but I think that is not a big deal. The
actual completion of split can be done in two ways: (a) scan the new bucket
and build a hash table with all of the TIDs you find there. When copying
tuples from the old bucket, first probe the hash table; if you find a match,
just skip that tuple (idea suggested by Robert Haas offlist) (b) delete all
the tuples that are marked as moved_by_split in the new bucket and perform
the split operation from the beginning using old bucket.

I have completed the patch with respect to incomplete splits and delayed
cleanup of garbage tuples. For incomplete splits, I have used the option
(a) as mentioned above. The incomplete splits are completed if the
insertion sees split-in-progress flag in a bucket.

It seems to me that there is a potential performance problem here. If
the split is still being performed, every insert will see the
split-in-progress flag set. The in-progress split retains only a pin
on the primary bucket, so other backends could also get an exclusive
lock, which is all they need for an insert. It seems that under this
algorithm they will now take the exclusive lock, release the exclusive
lock, try to take a cleanup lock, fail, again take the exclusive lock.
That seems like a lot of extra monkeying around. Wouldn't it be
better to take the exclusive lock and then afterwards check if the pin
count is 1? If so, even though we only intended to take an exclusive
lock, it is actually a cleanup lock. If not, we can simply proceed
with the insertion. This way you avoid unlocking and relocking the
buffer repeatedly.

The second major thing
this new version of patch has achieved is cleanup of garbage tuples i.e the
tuples that are left in old bucket during split. Currently (in HEAD), as
part of a split operation, we clean the tuples from old bucket after moving
them to new bucket, as we have heavy-weight locks on both old and new bucket
till the whole split operation. In the new design, we need to take cleanup
lock on old bucket and exclusive lock on new bucket to perform the split
operation and we don't retain those locks till the end (release the lock as
we move on to overflow buckets). Now to cleanup the tuples we need a
cleanup lock on a bucket which we might not have at split-end. So I choose
to perform the cleanup of garbage tuples during vacuum and when re-split of
the bucket happens as during both the operations, we do hold cleanup lock.
We can extend the cleanup of garbage to other operations as well if
required.

I think it's OK for the squeeze phase to be deferred until vacuum or a
subsequent split, but simply removing dead tuples seems like it should
be done earlier if possible. As I noted in my last email, it seems
like any process that gets an exclusive lock can do that, and probably
should. Otherwise, the index might become quite bloated.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Tue, Jun 21, 2016 at 9:26 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Tue, May 10, 2016 at 8:09 AM, Amit Kapila <amit.kapila16@gmail.com>

wrote:

Once the split operation has set the split-in-progress flag, it will

begin scanning bucket (N+1)/2. Every time it finds a tuple that properly
belongs in bucket N+1, it will insert the tuple into bucket N+1 with the
moved-by-split flag set. Tuples inserted by anything other than a split
operation will leave this flag clear, and tuples inserted while the split
is in progress will target the same bucket that they would hit if the split
were already complete. Thus, bucket N+1 will end up with a mix of
moved-by-split tuples, coming from bucket (N+1)/2, and unflagged tuples
coming from parallel insertion activity. When the scan of bucket (N+1)/2
is complete, we know that bucket N+1 now contains all the tuples that are
supposed to be there, so we clear the split-in-progress flag on both
buckets. Future scans of both buckets can proceed normally. Split
operation needs to take a cleanup lock on primary bucket to ensure that it
doesn't start if there is any Insertion happening in the bucket. It will
leave the lock on primary bucket, but not pin as it proceeds for next
overflow page. Retaining pin on primary bucket will ensure that vacuum
doesn't start on this bucket till the split is finished.

In the second-to-last sentence, I believe you have reversed the words
"lock" and "pin".

Yes. What, I mean to say is release the lock, but retain the pin on primary
bucket till end of operation.

Insertion will happen by scanning the appropriate bucket and needs to

retain pin on primary bucket to ensure that concurrent split doesn't
happen, otherwise split might leave this tuple unaccounted.

What do you mean by "unaccounted"?

It means that split might leave this tuple in old bucket even if it can be
moved to new bucket. Consider a case where insertion has to add a tuple on
some intermediate overflow bucket in the bucket chain, if we allow split
when insertion is in progress, split might not move this newly inserted
tuple.

Now for deletion of tuples from (N+1/2) bucket, we need to wait for the

completion of any scans that began before we finished populating bucket
N+1, because otherwise we might remove tuples that they're still expecting
to find in bucket (N+1)/2. The scan will always maintain a pin on primary
bucket and Vacuum can take a buffer cleanup lock (cleanup lock includes
Exclusive lock on bucket and wait till all the pins on buffer becomes zero)
on primary bucket for the buffer. I think we can relax the requirement for
vacuum to take cleanup lock (instead take Exclusive Lock on buckets where
no split has happened) with the additional flag has_garbage which will be
set on primary bucket, if any tuples have been moved from that bucket,
however I think for squeeze phase (in this phase, we try to move the tuples
from later overflow pages to earlier overflow pages in the bucket and then
if there are any empty overflow pages, then we move them to kind of a free
pool) of vacuum, we need a cleanup lock, otherwise scan results might get
effected.

affected, not effected.

I think this is basically correct, although I don't find it to be as
clear as I think it could be. It seems very clear that any operation
which potentially changes the order of tuples in the bucket chain,
such as the squeeze phase as currently implemented, also needs to
exclude all concurrent scans. However, I think that it's OK for
vacuum to remove tuples from a given page with only an exclusive lock
on that particular page.

How can we guarantee that it doesn't remove a tuple that is required by
scan which is started after split-in-progress flag is set?

Also, I think that when cleaning up after a
split, an exclusive lock is likewise sufficient to remove tuples from
a particular page provided that we know that every scan currently in
progress started after split-in-progress was set.

I think this could also have a similar issue as above, unless we have
something which prevents concurrent scans.

(Plain text email is preferred to HTML on this mailing list.)

If I turn to Plain text [1]http://www.mail-signatures.com/articles/how-to-add-or-change-an-email-signature-in-gmailgoogle-apps/, then the signature of my e-mail also changes
to Plain text which don't want. Is there a way, I can retain signature
settings in Rich Text and mail content as Plain Text.

[1]: http://www.mail-signatures.com/articles/how-to-add-or-change-an-email-signature-in-gmailgoogle-apps/
http://www.mail-signatures.com/articles/how-to-add-or-change-an-email-signature-in-gmailgoogle-apps/

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

On Tue, Jun 21, 2016 at 9:33 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Thu, Jun 16, 2016 at 3:28 AM, Amit Kapila <amit.kapila16@gmail.com>

wrote:

Incomplete splits can be completed either by vacuum or insert as both
needs exclusive lock on bucket. If vacuum finds split-in-progress

flag on a

bucket then it will complete the split operation, vacuum won't see

this flag

if actually split is in progress on that bucket as vacuum needs

cleanup lock

and split retains pin till end of operation. To make it work for

Insert

operation, one simple idea could be that if insert finds

split-in-progress

flag, then it releases the current exclusive lock on bucket and tries

to

acquire a cleanup lock on bucket, if it gets cleanup lock, then it can
complete the split and then the insertion of tuple, else it will have a
exclusive lock on bucket and just perform the insertion of tuple. The
disadvantage of trying to complete the split in vacuum is that split

might

require new pages and allocating new pages at time of vacuum is not
advisable. The disadvantage of doing it at time of Insert is that

Insert

might skip it even if there is some scan on the bucket is going on as

scan

will also retain pin on the bucket, but I think that is not a big

deal. The

actual completion of split can be done in two ways: (a) scan the new

bucket

and build a hash table with all of the TIDs you find there. When

copying

tuples from the old bucket, first probe the hash table; if you find a

match,

just skip that tuple (idea suggested by Robert Haas offlist) (b)

delete all

the tuples that are marked as moved_by_split in the new bucket and

perform

the split operation from the beginning using old bucket.

I have completed the patch with respect to incomplete splits and delayed
cleanup of garbage tuples. For incomplete splits, I have used the

option

(a) as mentioned above. The incomplete splits are completed if the
insertion sees split-in-progress flag in a bucket.

It seems to me that there is a potential performance problem here. If
the split is still being performed, every insert will see the
split-in-progress flag set. The in-progress split retains only a pin
on the primary bucket, so other backends could also get an exclusive
lock, which is all they need for an insert. It seems that under this
algorithm they will now take the exclusive lock, release the exclusive
lock, try to take a cleanup lock, fail, again take the exclusive lock.
That seems like a lot of extra monkeying around. Wouldn't it be
better to take the exclusive lock and then afterwards check if the pin
count is 1? If so, even though we only intended to take an exclusive
lock, it is actually a cleanup lock. If not, we can simply proceed
with the insertion. This way you avoid unlocking and relocking the
buffer repeatedly.

We can do it in the way as you are suggesting, but there is another thing
which we need to consider here. As of now, the patch tries to finish the
split if it finds split-in-progress flag in either old or new bucket. We
need to lock both old and new buckets to finish the split, so it is quite
possible that two different backends try to lock them in opposite order
leading to a deadlock. I think the correct way to handle is to always try
to lock the old bucket first and then new bucket. To achieve that, if the
insertion on new bucket finds that split-in-progress flag is set on a
bucket, it needs to release the lock and then acquire the lock first on old
bucket, ensure pincount is 1 and then lock new bucket again and ensure that
pincount is 1. I have already maintained the order of locks in scan (old
bucket first and then new bucket; refer changes in _hash_first()).
Alternatively, we can try to finish the splits only when someone tries to
insert in old bucket.

The second major thing
this new version of patch has achieved is cleanup of garbage tuples i.e

the

tuples that are left in old bucket during split. Currently (in HEAD),

as

part of a split operation, we clean the tuples from old bucket after

moving

them to new bucket, as we have heavy-weight locks on both old and new

bucket

till the whole split operation. In the new design, we need to take

cleanup

lock on old bucket and exclusive lock on new bucket to perform the split
operation and we don't retain those locks till the end (release the

lock as

we move on to overflow buckets). Now to cleanup the tuples we need a
cleanup lock on a bucket which we might not have at split-end. So I

choose

to perform the cleanup of garbage tuples during vacuum and when

re-split of

the bucket happens as during both the operations, we do hold cleanup

lock.

We can extend the cleanup of garbage to other operations as well if
required.

I think it's OK for the squeeze phase to be deferred until vacuum or a
subsequent split, but simply removing dead tuples seems like it should
be done earlier if possible.

Yes, probably we can do it at time of insertion in a bucket, if we don't
have concurrent scan issue.

--

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

On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Insertion will happen by scanning the appropriate bucket and needs to
retain pin on primary bucket to ensure that concurrent split doesn't happen,
otherwise split might leave this tuple unaccounted.

What do you mean by "unaccounted"?

It means that split might leave this tuple in old bucket even if it can be
moved to new bucket. Consider a case where insertion has to add a tuple on
some intermediate overflow bucket in the bucket chain, if we allow split
when insertion is in progress, split might not move this newly inserted
tuple.

OK, that's a good point.

Now for deletion of tuples from (N+1/2) bucket, we need to wait for the
completion of any scans that began before we finished populating bucket N+1,
because otherwise we might remove tuples that they're still expecting to
find in bucket (N+1)/2. The scan will always maintain a pin on primary
bucket and Vacuum can take a buffer cleanup lock (cleanup lock includes
Exclusive lock on bucket and wait till all the pins on buffer becomes zero)
on primary bucket for the buffer. I think we can relax the requirement for
vacuum to take cleanup lock (instead take Exclusive Lock on buckets where no
split has happened) with the additional flag has_garbage which will be set
on primary bucket, if any tuples have been moved from that bucket, however I
think for squeeze phase (in this phase, we try to move the tuples from later
overflow pages to earlier overflow pages in the bucket and then if there are
any empty overflow pages, then we move them to kind of a free pool) of
vacuum, we need a cleanup lock, otherwise scan results might get effected.

affected, not effected.

I think this is basically correct, although I don't find it to be as
clear as I think it could be. It seems very clear that any operation
which potentially changes the order of tuples in the bucket chain,
such as the squeeze phase as currently implemented, also needs to
exclude all concurrent scans. However, I think that it's OK for
vacuum to remove tuples from a given page with only an exclusive lock
on that particular page.

How can we guarantee that it doesn't remove a tuple that is required by scan
which is started after split-in-progress flag is set?

If the tuple is being removed by VACUUM, it is dead. We can remove
dead tuples right away, because no MVCC scan will see them. In fact,
the only snapshot that will see them is SnapshotAny, and there's no
problem with removing dead tuples while a SnapshotAny scan is in
progress. It's no different than heap_page_prune() removing tuples
that a SnapshotAny sequential scan was about to see.

If the tuple is being removed because the bucket was split, it's only
a problem if the scan predates setting the split-in-progress flag.
But since your design involves out-waiting all scans currently in
progress before setting that flag, there can't be any scan in progress
that hasn't seen it. A scan that has seen the flag won't look at the
tuple in any case.

(Plain text email is preferred to HTML on this mailing list.)

If I turn to Plain text [1], then the signature of my e-mail also changes to
Plain text which don't want. Is there a way, I can retain signature
settings in Rich Text and mail content as Plain Text.

Nope, but I don't see what you are worried about. There's no HTML
content in your signature anyway except for a link, and most
mail-reading software will turn that into a hyperlink even without the
HTML.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

We can do it in the way as you are suggesting, but there is another thing
which we need to consider here. As of now, the patch tries to finish the
split if it finds split-in-progress flag in either old or new bucket. We
need to lock both old and new buckets to finish the split, so it is quite
possible that two different backends try to lock them in opposite order
leading to a deadlock. I think the correct way to handle is to always try
to lock the old bucket first and then new bucket. To achieve that, if the
insertion on new bucket finds that split-in-progress flag is set on a
bucket, it needs to release the lock and then acquire the lock first on old
bucket, ensure pincount is 1 and then lock new bucket again and ensure that
pincount is 1. I have already maintained the order of locks in scan (old
bucket first and then new bucket; refer changes in _hash_first()).
Alternatively, we can try to finish the splits only when someone tries to
insert in old bucket.

Yes, I think locking buckets in increasing order is a good solution.
I also think it's fine to only try to finish the split when the insert
targets the old bucket. Finishing the split enables us to remove
tuples from the old bucket, which lets us reuse space instead of
accelerating more. So there is at least some potential benefit to the
backend inserting into the old bucket. On the other hand, a process
inserting into the new bucket derives no direct benefit from finishing
the split.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Wed, Jun 22, 2016 at 8:44 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

I think this is basically correct, although I don't find it to be as
clear as I think it could be. It seems very clear that any operation
which potentially changes the order of tuples in the bucket chain,
such as the squeeze phase as currently implemented, also needs to
exclude all concurrent scans. However, I think that it's OK for
vacuum to remove tuples from a given page with only an exclusive lock
on that particular page.

How can we guarantee that it doesn't remove a tuple that is required by scan
which is started after split-in-progress flag is set?

If the tuple is being removed by VACUUM, it is dead. We can remove
dead tuples right away, because no MVCC scan will see them. In fact,
the only snapshot that will see them is SnapshotAny, and there's no
problem with removing dead tuples while a SnapshotAny scan is in
progress. It's no different than heap_page_prune() removing tuples
that a SnapshotAny sequential scan was about to see.

If the tuple is being removed because the bucket was split, it's only
a problem if the scan predates setting the split-in-progress flag.
But since your design involves out-waiting all scans currently in
progress before setting that flag, there can't be any scan in progress
that hasn't seen it.

For above cases, just an exclusive lock will work.

A scan that has seen the flag won't look at the
tuple in any case.

Why so? Assume that scan started on new bucket where
split-in-progress flag was set, now it will not look at tuples that
are marked as moved-by-split in this bucket, as it will assume to find
all such tuples in old bucket. Now, if allow Vacuum or someone else
to remove tuples from old with just an Exclusive lock, it is quite
possible that scan miss the tuple in old bucket which got removed by
vacuum.

(Plain text email is preferred to HTML on this mailing list.)

If I turn to Plain text [1], then the signature of my e-mail also changes to
Plain text which don't want. Is there a way, I can retain signature
settings in Rich Text and mail content as Plain Text.

Nope, but I don't see what you are worried about. There's no HTML
content in your signature anyway except for a link, and most
mail-reading software will turn that into a hyperlink even without the
HTML.

Okay, I didn't knew that mail-reading software does that. Thanks for
pointing out.

--

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

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

On Wed, Jun 22, 2016 at 8:48 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

We can do it in the way as you are suggesting, but there is another thing
which we need to consider here. As of now, the patch tries to finish the
split if it finds split-in-progress flag in either old or new bucket. We
need to lock both old and new buckets to finish the split, so it is quite
possible that two different backends try to lock them in opposite order
leading to a deadlock. I think the correct way to handle is to always try
to lock the old bucket first and then new bucket. To achieve that, if the
insertion on new bucket finds that split-in-progress flag is set on a
bucket, it needs to release the lock and then acquire the lock first on old
bucket, ensure pincount is 1 and then lock new bucket again and ensure that
pincount is 1. I have already maintained the order of locks in scan (old
bucket first and then new bucket; refer changes in _hash_first()).
Alternatively, we can try to finish the splits only when someone tries to
insert in old bucket.

Yes, I think locking buckets in increasing order is a good solution.

Okay.

I also think it's fine to only try to finish the split when the insert
targets the old bucket. Finishing the split enables us to remove
tuples from the old bucket, which lets us reuse space instead of
accelerating more. So there is at least some potential benefit to the
backend inserting into the old bucket. On the other hand, a process
inserting into the new bucket derives no direct benefit from finishing
the split.

makes sense, will change that way and will add a comment why we are
just doing it for old bucket.

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

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

On Wed, Jun 22, 2016 at 10:13 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

A scan that has seen the flag won't look at the
tuple in any case.

Why so? Assume that scan started on new bucket where
split-in-progress flag was set, now it will not look at tuples that
are marked as moved-by-split in this bucket, as it will assume to find
all such tuples in old bucket. Now, if allow Vacuum or someone else
to remove tuples from old with just an Exclusive lock, it is quite
possible that scan miss the tuple in old bucket which got removed by
vacuum.

Oh, you're right. So we really need to CLEAR the split-in-progress
flag before removing any tuples from the old bucket. Does that sound
right?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Thu, Jun 23, 2016 at 10:56 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Jun 22, 2016 at 10:13 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

A scan that has seen the flag won't look at the
tuple in any case.

Why so? Assume that scan started on new bucket where
split-in-progress flag was set, now it will not look at tuples that
are marked as moved-by-split in this bucket, as it will assume to find
all such tuples in old bucket. Now, if allow Vacuum or someone else
to remove tuples from old with just an Exclusive lock, it is quite
possible that scan miss the tuple in old bucket which got removed by
vacuum.

Oh, you're right. So we really need to CLEAR the split-in-progress
flag before removing any tuples from the old bucket.

I think that alone is not sufficient, we also need to out-wait any
scan that has started when the flag is set and till it is cleared.
Before vacuum starts cleaning particular bucket, we can certainly
detect if it has to clean garbage tuples (the patch sets has_garbage
flag in old bucket for split operation) and only for that case we can
out-wait the scans. So probably, how it can work is during vacuum,
take Exclusive lock on bucket, check if has_garbage flag is set and
split-in-progress flag is cleared on bucket, if so then wait till the
pin-count on bucket is 1, else if has_garbage is not set, then just
proceed with clearing dead tuples from bucket. This will reduce the
requirement of having cleanup lock only when it is required (namely
when bucket has garbage tuples).

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

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

On Thu, Jun 16, 2016 at 12:58 PM, Amit Kapila <amit.kapila16@gmail.com>
wrote:

I have a question regarding code changes in *_hash_first*.

+        /*
+         * Conditionally get the lock on primary bucket page for search
while
+        * holding lock on meta page. If we have to wait, then release the
meta
+         * page lock and retry it in a hard way.
+         */
+        bucket = _hash_hashkey2bucket(hashkey,
+
 metap->hashm_maxbucket,
+
 metap->hashm_highmask,
+
 metap->hashm_lowmask);
+
+        blkno = BUCKET_TO_BLKNO(metap, bucket);
+
+        /* Fetch the primary bucket page for the bucket */
+        buf = ReadBuffer(rel, blkno);
+        if (!ConditionalLockBufferShared(buf))

Here we try to take lock on bucket page but I think if successful we do not
recheck whether any split happened before taking lock. Is this not
necessary now?

Also  below "if" is always true as we enter here only when outer "if
(retry)" is true.
+                        if (retry)
+                        {
+                                if (oldblkno == blkno)
+                                        break;
+                                _hash_relbuf(rel, buf);
+                        }

--
Thanks and Regards
Mithun C Y
EnterpriseDB: http://www.enterprisedb.com

On Fri, Jun 24, 2016 at 2:38 PM, Mithun Cy <mithun.cy@enterprisedb.com> wrote:

On Thu, Jun 16, 2016 at 12:58 PM, Amit Kapila <amit.kapila16@gmail.com>
wrote:

I have a question regarding code changes in _hash_first.

+        /*
+         * Conditionally get the lock on primary bucket page for search
while
+        * holding lock on meta page. If we have to wait, then release the
meta
+         * page lock and retry it in a hard way.
+         */
+        bucket = _hash_hashkey2bucket(hashkey,
+
metap->hashm_maxbucket,
+
metap->hashm_highmask,
+
metap->hashm_lowmask);
+
+        blkno = BUCKET_TO_BLKNO(metap, bucket);
+
+        /* Fetch the primary bucket page for the bucket */
+        buf = ReadBuffer(rel, blkno);
+        if (!ConditionalLockBufferShared(buf))

Here we try to take lock on bucket page but I think if successful we do not
recheck whether any split happened before taking lock. Is this not necessary
now?

Yes, now that is not needed, because we are doing that by holding the
read lock on metapage. Split happens by having a write lock on
metapage. The basic idea of this optimization is that if we get the
lock immediately, then do so by holding metapage lock, else if we
decide to wait for getting a lock on bucket page then we still
fallback to previous kind of mechanism.

Also  below "if" is always true as we enter here only when outer "if
(retry)" is true.
+                        if (retry)
+                        {
+                                if (oldblkno == blkno)
+                                        break;
+                                _hash_relbuf(rel, buf);
+                        }

Good catch, I think we don't need this retry check now. We do need
similar change in _hash_doinsert().

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

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

On Wed, Jun 22, 2016 at 8:44 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Insertion will happen by scanning the appropriate bucket and needs to
retain pin on primary bucket to ensure that concurrent split doesn't happen,
otherwise split might leave this tuple unaccounted.

What do you mean by "unaccounted"?

It means that split might leave this tuple in old bucket even if it can be
moved to new bucket. Consider a case where insertion has to add a tuple on
some intermediate overflow bucket in the bucket chain, if we allow split
when insertion is in progress, split might not move this newly inserted
tuple.

I think this is basically correct, although I don't find it to be as
clear as I think it could be. It seems very clear that any operation
which potentially changes the order of tuples in the bucket chain,
such as the squeeze phase as currently implemented, also needs to
exclude all concurrent scans. However, I think that it's OK for
vacuum to remove tuples from a given page with only an exclusive lock
on that particular page.

How can we guarantee that it doesn't remove a tuple that is required by scan
which is started after split-in-progress flag is set?

If the tuple is being removed by VACUUM, it is dead. We can remove
dead tuples right away, because no MVCC scan will see them. In fact,
the only snapshot that will see them is SnapshotAny, and there's no
problem with removing dead tuples while a SnapshotAny scan is in
progress. It's no different than heap_page_prune() removing tuples
that a SnapshotAny sequential scan was about to see.

While again thinking about this case, it seems to me that we need a
cleanup lock even for dead tuple removal. The reason for the same is
that scans that return multiple tuples always restart the scan from
the previous offset number from which they have returned last tuple.
Now, consider the case where the first tuple is returned from offset
number-3 in page and after that another backend removes the
corresponding tuple from heap and vacuum also removes the dead tuple
corresponding to offset-3. When the scan will try to get the next
tuple, it will start from offset-3 which can lead to incorrect
results.

Now, one way to solve above problem could be if we change scan for
hash indexes such that it works page at a time like we do for btree
scans (refer BTScanPosData and comments on top of it). This has an
additional advantage that it will reduce lock/unlock calls for
retrieving tuples from a page. However, I think this solution can only
work for MVCC scans. For non-MVCC scans, still there is a problem,
because after fetching all the tuples from a page, when it tries to
check the validity of tuples in heap, we won't be able to detect if
the old tuple is deleted and a new tuple has been placed at that
location in heap.

I think what we can do to solve this for non-MVCC scans is that allow
vacuum to always take a cleanup lock on a bucket and MVCC-scans will
release both the lock and pin as it proceeds. Non-MVCC scans and
scans that are started during split-in-progress will release the lock,
but not a pin on primary bucket. This way, we can allow vacuum to
proceed even if there is a MVCC-scan going on a bucket if it is not
started during a bucket split operation. For btree code, we do
something similar, which means that vacuum always take cleanup lock on
a bucket and non-MVCC scan retains a pin on the bucket.

The insertions should work as they are currently in patch, that is
they always need to retain a pin on primary bucket to avoid the
concurrent split problem as mentioned above (refer the first paragraph
discussion of this mail).

Thoughts?

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

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

On Wed, Jun 22, 2016 at 8:48 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:

We can do it in the way as you are suggesting, but there is another thing
which we need to consider here. As of now, the patch tries to finish the
split if it finds split-in-progress flag in either old or new bucket. We
need to lock both old and new buckets to finish the split, so it is quite
possible that two different backends try to lock them in opposite order
leading to a deadlock. I think the correct way to handle is to always try
to lock the old bucket first and then new bucket. To achieve that, if the
insertion on new bucket finds that split-in-progress flag is set on a
bucket, it needs to release the lock and then acquire the lock first on old
bucket, ensure pincount is 1 and then lock new bucket again and ensure that
pincount is 1. I have already maintained the order of locks in scan (old
bucket first and then new bucket; refer changes in _hash_first()).
Alternatively, we can try to finish the splits only when someone tries to
insert in old bucket.

Yes, I think locking buckets in increasing order is a good solution.
I also think it's fine to only try to finish the split when the insert
targets the old bucket. Finishing the split enables us to remove
tuples from the old bucket, which lets us reuse space instead of
accelerating more. So there is at least some potential benefit to the
backend inserting into the old bucket. On the other hand, a process
inserting into the new bucket derives no direct benefit from finishing
the split.

Okay, following this suggestion, I have updated the patch so that only
insertion into old-bucket can try to finish the splits. Apart from
that, I have fixed the issue reported by Mithun upthread. I have
updated the README to explain the locking used in patch. Also, I
have changed the locking around vacuum, so that it can work with
concurrent scans when ever possible. In previous patch version,
vacuum used to take cleanup lock on a bucket to remove the dead
tuples, moved-due-to-split tuples and squeeze operation, also it holds
the lock on bucket till end of cleanup. Now, also it takes cleanup
lock on a bucket to out-wait scans, but it releases the lock as it
proceeds to clean the overflow pages. The idea is first we need to
lock the next bucket page and then release the lock on current bucket
page. This ensures that any concurrent scan started after we start
cleaning the bucket will always be behind the cleanup. Allowing scans
to cross vacuum will allow it to remove tuples required for sanctity
of scan. Also for squeeze-phase we are just checking if the pincount
of buffer is one (we already have Exclusive lock on buffer of bucket
by that time), then only proceed, else will try to squeeze next time
the cleanup is required for that bucket.

Thoughts/Suggestions?

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

I did some basic testing of same. In that I found one issue with cursor.

+BEGIN;

+SET enable_seqscan = OFF;

+SET enable_bitmapscan = OFF;

+CREATE FUNCTION declares_cursor(int)

+ RETURNS void

+ AS 'DECLARE c CURSOR FOR SELECT * from con_hash_index_table WHERE keycol
= $1;'

+LANGUAGE SQL;

+

+SELECT declares_cursor(1);

+MOVE FORWARD ALL FROM c;

+MOVE BACKWARD 10000 FROM c;

+ CLOSE c;

+ WARNING: buffer refcount leak: [5835] (rel=base/16384/30537,
blockNum=327, flags=0x93800000, refcount=1 1)

ROLLBACK;

closing the cursor comes with the warning which say we forgot to unpin the
buffer.

I have also added tests [1]Some tests to cover hash_index. </messages/by-id/CAD__OugeoQuu3mP09erV3gBdF-nX7o844kW7hAnwCF_rdzr6Qw@mail.gmail.com&gt; for coverage improvements.

[1]: Some tests to cover hash_index. </messages/by-id/CAD__OugeoQuu3mP09erV3gBdF-nX7o844kW7hAnwCF_rdzr6Qw@mail.gmail.com&gt;
</messages/by-id/CAD__OugeoQuu3mP09erV3gBdF-nX7o844kW7hAnwCF_rdzr6Qw@mail.gmail.com&gt;

On Thu, Jul 14, 2016 at 4:33 PM, Amit Kapila <amit.kapila16@gmail.com>
wrote:

On Wed, Jun 22, 2016 at 8:48 PM, Robert Haas <robertmhaas@gmail.com>
wrote:

On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila <amit.kapila16@gmail.com>

wrote:

We can do it in the way as you are suggesting, but there is another

thing

which we need to consider here. As of now, the patch tries to finish

the

split if it finds split-in-progress flag in either old or new bucket.

We

need to lock both old and new buckets to finish the split, so it is

quite

possible that two different backends try to lock them in opposite order
leading to a deadlock. I think the correct way to handle is to always

try

to lock the old bucket first and then new bucket. To achieve that, if

the

insertion on new bucket finds that split-in-progress flag is set on a
bucket, it needs to release the lock and then acquire the lock first on

old

bucket, ensure pincount is 1 and then lock new bucket again and ensure

that

pincount is 1. I have already maintained the order of locks in scan (old
bucket first and then new bucket; refer changes in _hash_first()).
Alternatively, we can try to finish the splits only when someone tries

to

insert in old bucket.

Yes, I think locking buckets in increasing order is a good solution.
I also think it's fine to only try to finish the split when the insert
targets the old bucket. Finishing the split enables us to remove
tuples from the old bucket, which lets us reuse space instead of
accelerating more. So there is at least some potential benefit to the
backend inserting into the old bucket. On the other hand, a process
inserting into the new bucket derives no direct benefit from finishing
the split.

Okay, following this suggestion, I have updated the patch so that only
insertion into old-bucket can try to finish the splits. Apart from
that, I have fixed the issue reported by Mithun upthread. I have
updated the README to explain the locking used in patch. Also, I
have changed the locking around vacuum, so that it can work with
concurrent scans when ever possible. In previous patch version,
vacuum used to take cleanup lock on a bucket to remove the dead
tuples, moved-due-to-split tuples and squeeze operation, also it holds
the lock on bucket till end of cleanup. Now, also it takes cleanup
lock on a bucket to out-wait scans, but it releases the lock as it
proceeds to clean the overflow pages. The idea is first we need to
lock the next bucket page and then release the lock on current bucket
page. This ensures that any concurrent scan started after we start
cleaning the bucket will always be behind the cleanup. Allowing scans
to cross vacuum will allow it to remove tuples required for sanctity
of scan. Also for squeeze-phase we are just checking if the pincount
of buffer is one (we already have Exclusive lock on buffer of bucket
by that time), then only proceed, else will try to squeeze next time
the cleanup is required for that bucket.

Thoughts/Suggestions?

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

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

--
Thanks and Regards
Mithun C Y
EnterpriseDB: http://www.enterprisedb.com

On Thu, Aug 4, 2016 at 8:02 PM, Mithun Cy <mithun.cy@enterprisedb.com> wrote:

I did some basic testing of same. In that I found one issue with cursor.

Thanks for the testing. The reason for failure was that the patch
didn't take into account the fact that for scrolling cursors, scan can
reacquire the lock and pin on bucket buffer multiple times. I have
fixed it such that we release the pin on bucket buffers after we scan
the last overflow page in bucket. Attached patch fixes the issue for
me, let me know if you still see the issue.

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

On 08/05/2016 07:36 AM, Amit Kapila wrote:

On Thu, Aug 4, 2016 at 8:02 PM, Mithun Cy <mithun.cy@enterprisedb.com> wrote:

I did some basic testing of same. In that I found one issue with cursor.

Thanks for the testing. The reason for failure was that the patch
didn't take into account the fact that for scrolling cursors, scan can
reacquire the lock and pin on bucket buffer multiple times. I have
fixed it such that we release the pin on bucket buffers after we scan
the last overflow page in bucket. Attached patch fixes the issue for
me, let me know if you still see the issue.

Needs a rebase.

hashinsert.c

+ * reuse the space. There is no such apparent benefit from finsihing the

-> finishing

hashpage.c

+ * retrun the buffer, else return InvalidBuffer.

-> return

+	if (blkno == P_NEW)
+		elog(ERROR, "hash AM does not use P_NEW");

Left over ?

+ * for unlocking it.

-> for unlocking them.

hashsearch.c

+ * bucket, but not pin, then acuire the lock on new bucket and again

-> acquire

hashutil.c

+ * half. It is mainly required to finsh the incomplete splits where we are

-> finish

Ran some tests on a CHAR() based column which showed good results. Will
have to compare with a run with the WAL patch applied.

make check-world passes.

Best regards,
Jesper

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

On Thu, Sep 1, 2016 at 11:33 PM, Jesper Pedersen
<jesper.pedersen@redhat.com> wrote:

On 08/05/2016 07:36 AM, Amit Kapila wrote:

Needs a rebase.

Done.

+       if (blkno == P_NEW)
+               elog(ERROR, "hash AM does not use P_NEW");

Left over ?

No. We need this check similar to all other _hash_*buf API's, as we
never expect caller of those API's to pass P_NEW. The new buckets
(blocks) are created during split and it uses different mechanism to
allocate blocks in bulk.

I have fixed all other issues you have raised. Updated patch is
attached with this mail.

Ran some tests on a CHAR() based column which showed good results. Will have
to compare with a run with the WAL patch applied.

Okay, Thanks for testing. I think WAL patch is still not ready for
performance testing, I am fixing few issues in that patch, but you can
do the design or code level review of that patch at this stage. I
think it is fine even if you share the performance numbers with this
and or Mithun's patch [1]https://commitfest.postgresql.org/10/715/.

[1]: https://commitfest.postgresql.org/10/715/

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