Subject: Re: [BUG] Error in BRIN summarization
To: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: pgsql-hackers@lists.postgresql.org
References: <20200727172529.GA12531@alvherre.pgsql>
From: Anastasia Lubennikova <a.lubennikova@postgrespro.ru>
Message-ID: <2588667e-d07d-7e10-74e2-7e1e46194491@postgrespro.ru>
Date: Thu, 30 Jul 2020 16:40:46 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.10.0
MIME-Version: 1.0
In-Reply-To: <20200727172529.GA12531@alvherre.pgsql>
Content-Type: multipart/alternative;
 boundary="------------2136C76216F91538D099B3C5"
Content-Language: en-US
Precedence: bulk

This is a multi-part message in MIME format.
--------------2136C76216F91538D099B3C5
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit

On 27.07.2020 20:25, Alvaro Herrera wrote:
> On 2020-Jul-27, Anastasia Lubennikova wrote:
>
>> Here is the updated version of the fix.
>> The problem can be reproduced on all supported versions, so I suggest to
>> backpatch it.
>> Code slightly changed in v12, so here are two patches: one for versions 9.5
>> to 11 and another for versions from 12 to master.
>>
>>
>>
>> (I was also considering whether it needs to be a loop to reobtain root
>> tuples, in case a concurrent transaction can create a new item while
>> we're checking that item; but I don't think that can really happen for
>> one individual tuple.)
I don't think we need a recheck for a single tuple, because we only care 
about finding its root, which simply must exist somewhere on this page, 
as concurrent pruning is not allowed. We also may catch root_offsets[] 
for subsequent tuples, but it's okay if we don't. These tuples will do 
the same recheck on their turn.


While testing this fix, Alexander Lakhin spotted another problem. I 
simplified  the test case to this:

1) prepare a table with brin index

create table tbl (iint, bchar(1000)) with (fillfactor=10);
insert into tbl select i, md5(i::text) from generate_series(0,1000) as i;
create index idx on tbl using brin(i, b) with (pages_per_range=1);

2) run brin_desummarize_range() in a loop:

echo "-- desummarize all ranges
  SELECT FROM generate_series(0, pg_relation_size('tbl')/8192 - 1) as i, lateral (SELECT brin_desummarize_range('idx', i)) as d;
-- summarize them back
VACUUM tbl" > brin_desum_test.sql

pgbench postgres -f  brin_desum_test.sql -n -T 120


3) run a search that invokes bringetbitmap:

  set enable_seqscan to off;
  explain analyze select * from tbl where i>10 and i<100; \watch 1

After a few runs, it will fail with "ERROR: corrupted BRIN index: 
inconsistent range map"

The problem is caused by a race in page locking in 
brinGetTupleForHeapBlock [1]:

(1) bitmapsan locks revmap->rm_currBuf and finds the address of the 
tuple on a regular page "page", then unlocks revmap->rm_currBuf
(2) in another transaction desummarize locks both revmap->rm_currBuf and 
"page", cleans up the tuple and unlocks both buffers
(1) bitmapscan locks buffer, containing "page", attempts to access the 
tuple and fails to find it


At first, I tried to fix it by holding the lock on revmap->rm_currBuf 
until we locked the regular page, but it causes a deadlock with 
brinsummarize(), It can be easily reproduced with the same test as above.
Is there any rule about the order of locking revmap and regular pages in 
brin? I haven't found anything in README.

As an alternative, we can leave locks as is and add a recheck, before 
throwing an error.

What do you think?

[1] 
https://github.com/postgres/postgres/blob/master/src/backend/access/brin/brin_revmap.c#L269

-- 
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


--------------2136C76216F91538D099B3C5
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <div class="moz-cite-prefix">On 27.07.2020 20:25, Alvaro Herrera
      wrote:<br>
    </div>
    <blockquote type="cite"
      cite="mid:20200727172529.GA12531@alvherre.pgsql">
      <pre class="moz-quote-pre" wrap="">On 2020-Jul-27, Anastasia Lubennikova wrote:

</pre>
      <blockquote type="cite">
        <pre class="moz-quote-pre" wrap="">Here is the updated version of the fix.
The problem can be reproduced on all supported versions, so I suggest to
backpatch it.
Code slightly changed in v12, so here are two patches: one for versions 9.5
to 11 and another for versions from 12 to master.


(I was also considering whether it needs to be a loop to reobtain root
tuples, in case a concurrent transaction can create a new item while
we're checking that item; but I don't think that can really happen for
one individual tuple.)
</pre>
      </blockquote>
    </blockquote>
    I don't think we need a recheck for a single tuple, because we only
    care about finding its root, which simply must exist somewhere on
    this page, as concurrent pruning is not allowed. We also may catch
    root_offsets[] for subsequent tuples, but it's okay if we don't.
    These tuples will do the same recheck on their turn.<br>
    <br>
    <br>
    <p>While testing this fix, Alexander Lakhin spotted another problem.
      I simplified  the test case to this:<br>
      <br>
      1) prepare a table with brin index<br>
    </p>
    <pre class="code-java">create table tbl (i <span class="code-object">int</span>, b <span class="code-object">char</span>(1000)) with (fillfactor=10);
insert into tbl select i, md5(i::text) from generate_series(0,1000) as i;
create index idx on tbl using brin(i, b) with (pages_per_range=1);
</pre>
    <p>2) run brin_desummarize_range() in a loop:<br>
    </p>
    <pre class="code-java">echo "-- desummarize all ranges
 SELECT FROM generate_series(0, pg_relation_size(<span class="code-quote">'tbl'</span>)/8192 - 1) as i, lateral (SELECT brin_desummarize_range(<span class="code-quote">'idx'</span>, i)) as d; 
-- summarize them back 
VACUUM tbl" &gt; brin_desum_test.sql

pgbench postgres -f  brin_desum_test.sql -n -T 120</pre>
    <p><br>
      3) run a search that invokes bringetbitmap:<br>
    </p>
    <pre class="code-java"> set enable_seqscan to off;
 explain analyze select * from tbl where i&gt;10 and i&lt;100; \watch 1
</pre>
    <p>After a few runs, it will fail with "ERROR: corrupted BRIN index:
      inconsistent range map"<br>
      <br>
      The problem is caused by a race in page locking in
      brinGetTupleForHeapBlock [1]:<br>
      <br>
      (1) bitmapsan locks revmap-&gt;rm_currBuf and finds the address of
      the tuple on a regular page "page", then unlocks
      revmap-&gt;rm_currBuf<br>
      (2) in another transaction desummarize locks both
      revmap-&gt;rm_currBuf and "page", cleans up the tuple and unlocks
      both buffers<br>
      (1) bitmapscan locks buffer, containing "page", attempts to access
      the tuple and fails to find it<br>
    </p>
    <p><br>
      At first, I tried to fix it by holding the lock on
      revmap-&gt;rm_currBuf until we locked the regular page, but it
      causes a deadlock with brinsummarize(), It can be easily
      reproduced with the same test as above.<br>
      Is there any rule about the order of locking revmap and regular
      pages in brin? I haven't found anything in README.<br>
      <br>
      As an alternative, we can leave locks as is and add a recheck,
      before throwing an error.<br>
      <br>
      What do you think?<br>
      <br>
      [1] <a
href="https://github.com/postgres/postgres/blob/master/src/backend/access/brin/brin_revmap.c#L269"
        class="external-link" target="_blank" rel="nofollow noopener">https://github.com/postgres/postgres/blob/master/src/backend/access/brin/brin_revmap.c#L269</a></p>
    <pre class="moz-signature" cols="72">-- 
Anastasia Lubennikova
Postgres Professional: <a class="moz-txt-link-freetext" href="http://www.postgrespro.com">http://www.postgrespro.com</a>
The Russian Postgres Company</pre>
  </body>
</html>

--------------2136C76216F91538D099B3C5--