Re: Hash Indexes

Hi All,

I have executed few test-cases to validate the v12 patch for
concurrent hash index shared upthread and have found no issues. Below
are some of the test-cases i ran,

1) pgbench test on a read-write workload with following configuration
(This was basically to validate the locking strategy not for
performance testing)

postgresql non-default configuration:
----------------------------------------------------
min_wal_size=15GB
max_wal_size=20GB
checkpoint_timeout=900
maintenance_work_mem=1GB
checkpoint_completion_target=0.9
max_connections=200
shared buffer=8GB

pgbench settings:
-------------------------
Scale Factor=300
run time= 30 mins
pgbench -c $thread -j $thread -T $time_for_reading -M prepared postgres


2) As v12 patch mainly has locking changes related to bucket squeezing
in hash index, I have ran a small test-case to build hash index with
good number of overflow pages and then ran deletion operation to see
if the bucket squeezing has happened. The test script
"test_squeezeb_hindex.sh" used for this testing is attached with this
mail and the results are shown below:

=====Number of bucket and overflow pages before delete=====
 274671 Tuples only is on.
 148390
 131263  bucket
  17126  overflow
      1  bitmap

=====Number of bucket and overflow pages after delete=====
 274671 Tuples only is on.
 141240
 131263  bucket
   9976  overflow
      1  bitmap

With Regards,
Ashutosh Sharma
EnterpriseDB: http://www.enterprisedb.com

On Wed, Nov 23, 2016 at 7:20 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:
> On Thu, Nov 17, 2016 at 3:08 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>> On Sat, Nov 12, 2016 at 12:49 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
>>> You are right and I have changed the code as per your suggestion.
>>
>> So...
>>
>> +        /*
>> +         * We always maintain the pin on bucket page for whole scan operation,
>> +         * so releasing the additional pin we have acquired here.
>> +         */
>> +        if ((*opaquep)->hasho_flag & LH_BUCKET_PAGE)
>> +            _hash_dropbuf(rel, *bufp);
>>
>> This relies on the page contents to know whether we took a pin; that
>> seems like a bad plan.  We need to know intrinsically whether we took
>> a pin.
>>
>
> Okay, changed to not rely on page contents.
>
>> +     * If the bucket split is in progress, then we need to skip tuples that
>> +     * are moved from old bucket.  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.  Here, we have to be cautious about
>>
>> It wouldn't be a problem if VACUUM removed tuples from the new bucket,
>> because they'd have to be dead anyway.   It also wouldn't be a problem
>> if it removed tuples from the old bucket that were actually dead.  The
>> real issue isn't vacuum anyway, but the process of cleaning up after a
>> split.  We need to hold the pin so that tuples being moved from the
>> old bucket to the new bucket by the split don't get removed from the
>> old bucket until our scan is done.
>>
>
> Updated comments to explain clearly.
>
>> +        old_blkno = _hash_get_oldblock_from_newbucket(rel,
>> opaque->hasho_bucket);
>>
>> Couldn't you pass "bucket" here instead of "hasho->opaque_bucket"?  I
>> feel like I'm repeating this ad nauseum, but I really think it's bad
>> to rely on the special space instead of our own local variables!
>>
>
> Okay, changed as per suggestion.
>
>> -            /* we ran off the end of the bucket without finding a match */
>> +            /*
>> +             * We ran off the end of the bucket without finding a match.
>> +             * Release the pin on bucket buffers.  Normally, such pins are
>> +             * released at end of scan, however scrolling cursors can
>> +             * reacquire the bucket lock and pin in the same scan multiple
>> +             * times.
>> +             */
>>              *bufP = so->hashso_curbuf = InvalidBuffer;
>>              ItemPointerSetInvalid(current);
>> +            _hash_dropscanbuf(rel, so);
>>
>> I think this comment is saying that we'll release the pin on the
>> primary bucket page for now, and then reacquire it later if the user
>> reverses the scan direction.  But that doesn't sound very safe,
>> because the bucket could be split in the meantime and the order in
>> which tuples are returned could change.  I think we want that to
>> remain stable within a single query execution.
>>
>
> As explained [1], this shouldn't be a problem.
>
>> +            _hash_readnext(rel, &buf, &page, &opaque,
>> +                       (opaque->hasho_flag & LH_BUCKET_PAGE) ? true : false);
>>
>> Same comment: don't rely on the special space to figure this out.
>> Keep track.  Also != 0 would be better than ? true : false.
>>
>
> After gluing scan of old and new buckets in _hash_read* API's, this is
> no more required.
>
>> +                            /*
>> +                             * setting hashso_skip_moved_tuples to false
>> +                             * ensures that we don't check for tuples that are
>> +                             * moved by split in old bucket and it also
>> +                             * ensures that we won't retry to scan the old
>> +                             * bucket once the scan for same is finished.
>> +                             */
>> +                            so->hashso_skip_moved_tuples = false;
>>
>> I think you've got a big problem here.  Suppose the user starts the
>> scan in the new bucket and runs it forward until they end up in the
>> old bucket.  Then they turn around and run the scan backward.  When
>> they reach the beginning of the old bucket, they're going to stop, not
>> move back to the new bucket, AFAICS.  Oops.
>>
>> _hash_first() has a related problem: a backward scan starts at the end
>> of the new bucket and moves backward, but it should start at the end
>> of the old bucket, and then when it reaches the beginning, flip to the
>> new bucket and move backward through that one.  Otherwise, a backward
>> scan and a forward scan don't return tuples in opposite order, which
>> they should.
>>
>> I think what you need to do to fix both of these problems is a more
>> thorough job gluing the two buckets together.  I'd suggest that the
>> responsibility for switching between the two buckets should probably
>> be given to _hash_readprev() and _hash_readnext(), because every place
>> that needs to advance to the next or previous page that cares about
>> this.  Right now you are trying to handle it mostly in the functions
>> that call those functions, but that is prone to errors of omission.
>>
>
> Changed as per this idea to change the API's and fix the problem.
>
>> Also, I think that so->hashso_skip_moved_tuples is badly designed.
>> There are two separate facts you need to know: (1) whether you are
>> scanning a bucket that was still being populated at the start of your
>> scan and (2) if yes, whether you are scanning the bucket being
>> populated or whether you are instead scanning the corresponding "old"
>> bucket.  You're trying to keep track of that using one Boolean, but
>> one Boolean only has two states and there are three possible states
>> here.
>>
>
> Updated patch is using two boolean variables to track the bucket state.
>
>> +    if (H_BUCKET_BEING_SPLIT(pageopaque) && IsBufferCleanupOK(buf))
>> +    {
>> +
>> +        /* release the lock on bucket buffer, before completing the split. */
>>
>> Extra blank line.
>>
>
> Removed.
>
>> +moved-by-split flag on a tuple indicates that tuple is moved from old to new
>> +bucket.  The concurrent scans can skip such tuples till the split operation is
>> +finished.  Once the tuple is marked as moved-by-split, it will remain
>> so forever
>> +but that does no harm.  We have intentionally not cleared it as that
>> can generate
>> +an additional I/O which is not necessary.
>>
>> The first sentence needs to start with "the" but the second sentence shouldn't.
>>
>
> Changed.
>
>> It would be good to adjust this part a bit to more clearly explain
>> that the split-in-progress and split-cleanup flags are bucket-level
>> flags, while moved-by-split is a per-tuple flag.  It's possible to
>> figure this out from what you've written, but I think it could be more
>> clear.  Another thing that is strange is that the code uses THREE
>> flags, bucket-being-split, bucket-being-populated, and
>> needs-split-cleanup, but the README conflates the first two and uses a
>> different name.
>>
>
> Updated patch to use bucket-being-split and bucket-being-populated to
> explain the split operation in README.  I have also changed the readme
> to clearly indicate which the bucket and tuple level flags.
>
>> +previously-acquired content lock, but not pin and repeat the process using the
>>
>> s/but not pin/but not the pin,/
>>
>
> Changed.
>
>>  A problem is that if a split fails partway through (eg due to insufficient
>> -disk space) the index is left corrupt.  The probability of that could be
>> -made quite low if we grab a free page or two before we update the meta
>> -page, but the only real solution is to treat a split as a WAL-loggable,
>> +disk space or crash) the index is left corrupt.  The probability of that
>> +could be made quite low if we grab a free page or two before we update the
>> +meta page, but the only real solution is to treat a split as a WAL-loggable,
>>  must-complete action.  I'm not planning to teach hash about WAL in this
>> -go-round.
>> +go-round.  However, we do try to finish the incomplete splits during insert
>> +and split.
>>
>> I think this paragraph needs a much heavier rewrite explaining the new
>> incomplete split handling.  It's basically wrong now.  Perhaps replace
>> it with something like this:
>>
>> --
>> If a split fails partway through (e.g. due to insufficient disk space
>> or an interrupt), the index will not be corrupted.  Instead, we'll
>> retry the split every time a tuple is inserted into the old bucket
>> prior to inserting the new tuple; eventually, we should succeed.  The
>> fact that a split is left unfinished doesn't prevent subsequent
>> buckets from being split, but we won't try to split the bucket again
>> until the prior split is finished.  In other words, a bucket can be in
>> the middle of being split for some time, but ti can't be in the middle
>> of two splits at the same time.
>>
>> Although we can survive a failure to split a bucket, a crash is likely
>> to corrupt the index, since hash indexes are not yet WAL-logged.
>> --
>>
>
> s/ti/it
> Fixed the typo and used the suggested text in README.
>
>> +        Acquire cleanup lock on target bucket
>> +        Scan and remove tuples
>> +        For overflow page, first we need to lock the next page and then
>> +        release the lock on current bucket or overflow page
>> +        Ensure to have buffer content lock in exclusive mode on bucket page
>> +        If buffer pincount is one, then compact free space as needed
>> +        Release lock
>>
>> I don't think this summary is particularly correct.  You would never
>> guess from this that we lock each bucket page in turn and then go back
>> and try to relock the primary bucket page at the end.  It's more like:
>>
>> acquire cleanup lock on primary bucket page
>> loop:
>>     scan and remove tuples
>>     if this is the last bucket page, break out of loop
>>     pin and x-lock next page
>>     release prior lock and pin (except keep pin on primary bucket page)
>> if the page we have locked is not the primary bucket page:
>>     release lock and take exclusive lock on primary bucket page
>> if there are no other pins on the primary bucket page:
>>     squeeze the bucket to remove free space
>>
>
> Yeah, it is clear, so I have used it in README.
>
>> Come to think of it, I'm a little worried about the locking in
>> _hash_squeezebucket().  It seems like we drop the lock on each "write"
>> bucket page before taking the lock on the next one.  So a concurrent
>> scan could get ahead of the cleanup process.  That would be bad,
>> wouldn't it?
>>
>
> As discussed [2], I have changed the code to use lock-chaining during
> squeeze phase.
>
>
> Apart from above, I have fixed a bug in calculation of lowmask in
> _hash_get_oldblock_from_newbucket().
>
> [1] - https://www.postgresql.org/message-id/CAA4eK1JJDWFY0_Ezs4ZxXgnrGtTn48vFuXniOLmL7FOWX-tKNw%40mail.gmail.com
> [2] - https://www.postgresql.org/message-id/CAA4eK1J%2B0OYWKswWYNEjrBk3LfGpGJ9iSV8bYPQ3M%3D-qpkMtwQ
> %40mail.gmail.com
>
>
> --
> 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
>