Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1iuJkT-0007gt-3o for pgsql-hackers@arkaria.postgresql.org; Wed, 22 Jan 2020 17:25:01 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1iuJkR-0002OT-O7 for pgsql-hackers@arkaria.postgresql.org; Wed, 22 Jan 2020 17:24:59 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1iuJkR-0002O2-7K for pgsql-hackers@lists.postgresql.org; Wed, 22 Jan 2020 17:24:59 +0000 Received: from smtp03.optiver.com ([195.246.114.70]) by makus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1iuJkO-000207-Gl for pgsql-hackers@postgresql.org; Wed, 22 Jan 2020 17:24:58 +0000 Received: from pps.filterd (smtp03.optiver.com [127.0.0.1]) by smtp03.optiver.com (8.16.0.27/8.16.0.27) with SMTP id 00MHMB7A023503; Wed, 22 Jan 2020 18:24:45 +0100 Received: from opammb0561.comp.optiver.com (opammb0561.comp.optiver.com [10.131.160.1]) by smtp03.optiver.com with ESMTP id 2xkrg8aewp-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Wed, 22 Jan 2020 18:24:45 +0100 Received: from opammb0562.comp.optiver.com (10.131.160.2) by opammb0561.comp.optiver.com (10.131.160.1) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Wed, 22 Jan 2020 18:24:44 +0100 Received: from opammb0562.comp.optiver.com ([::1]) by opammb0562.comp.optiver.com ([fe80::8110:c13b:9056:efe5%17]) with mapi id 15.00.1473.003; Wed, 22 Jan 2020 18:24:44 +0100 From: Floris Van Nee To: Dmitry Dolgov <9erthalion6@gmail.com> CC: Peter Geoghegan , Jesper Pedersen , David Rowley , Tomas Vondra , Kyotaro Horiguchi , Alvaro Herrera , "Thomas Munro" , James Coleman , Rafia Sabih , Jeff Janes , "Bhushan Uparkar" , PostgreSQL-development , Alexander Korotkov Subject: Re: Index Skip Scan Thread-Topic: Index Skip Scan Thread-Index: AQHV0UggnO3FEZbS3kuZ9WKL9oebEg== Date: Wed, 22 Jan 2020 17:24:43 +0000 Message-ID: <1579713885361.64964@Optiver.com> References: <1e59d800b38141c5af2ad3a64cf9758e@opammb0562.comp.optiver.com> <802e46fa-dc2c-4c32-e55b-884e04aa7f12@redhat.com> <20200121160942.eu4bvbu46nt223ug@localhost> ,<20200122160441.ograupmzyytde2mi@localhost> In-Reply-To: <20200122160441.ograupmzyytde2mi@localhost> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-exchange-transport-fromentityheader: Hosted x-originating-ip: [10.131.160.182] x-tm-as-product-ver: SMEX-14.0.0.1158-8.5.1020-25182.007 x-tm-as-result: No-10--6.043700-8.000000 x-tmase-matchedrid: x2HXvaraFomnvGCyBToTI8G0UNgaZpYqGsvgUMYAn4UcI/pZs+xxL9k2 l7i3oc4zIoALBmt6oJrhhLoXIby/KCwwtxRkxyN3ydRP56yRRA8eIblhH0Sn6Up12IXZajx5tK+ zh1KtAiyd+hadbvZSHFLiBb0KSgWGAioGpYo1Fp2ZLh7IMX1BRzoSfZud5+GgUCgEErrUGFxfdO GeiKObmIuBwqiWOKVGgc0kqnflEUlJH11OOVB0yQLiZxZUfodHEDnDEqNPdupOEILBOBemLzaxf lEA+WYI+vraRbeMfe0ZqOyA4N+wON76sV0IE1xFiPIR0a1i6hfUHmaN+mm9YNup0fEawV9pQbx0 lvu7pJh4fegpHIieph2cZXId2QJQ3ybdhmCI5jxTNl9jB9u8gAeCHewokHM/SgypjNmDEOsHxtI o9CIHwJg6HLiA9518zTmXxAu2YgRZb7CPAaMFSabtlVLKF4zp9CFB7klVg4dBN/6rzo4BS8P2JG P0sgzGG8BsxeXdO95XKSrhSLigt7c+8pJXJ20jZwUuZO12AYViAbtMwkL0aQL+e4+Xk/QWp/zLC P4hxoMkDzmT2ewiDGwxGhOxvQNglRTb2s9TqjKrm7DrUlmNkH8mA3sDDq0A5MIx11wv+CNzFh5W t+L9QjB/7KjUOdczH4dlyTMUw7bHZi20z9ezJO0y0CohWw8KftwZ3X11IV0= x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No x-tmase-result: 10--6.043700-8.000000 x-tmase-version: SMEX-14.0.0.1158-8.5.1020-25182.007 x-tm-snts-smtp: 7179BE5E742018F7C60805D7DDC0F84E7CBFDD3784A60CDFC822C469F330C49D2000:8 Content-Type: multipart/alternative; boundary="_000_157971388536164964Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2020-01-22_07:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_157971388536164964Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Hi Dmitry, > > On Wed, Jan 22, 2020 at 07:50:30AM +0000, Floris Van Nee wrote: > > > > Anyone please correct me if I'm wrong, but I think one case where the c= urrent patch relies on some data from the page it has locked before it in c= hecking this hi/lo key. I think it's possible for the following sequence to= happen. Suppose we have a very simple one leaf-page btree containing four = elements: leaf page 1 =3D [2,4,6,8] > > We do a backwards index skip scan on this and have just returned our fi= rst tuple (8). The buffer is left pinned but unlocked. Now, someone else co= mes in and inserts a tuple (value 5) into this page, but suppose the page h= appens to be full. So a page split occurs. As far as I know, a page split c= ould happen at any random element in the page. One of the situations we cou= ld be left with is: > > Leaf page 1 =3D [2,4] > > Leaf page 2 =3D [5,6,8] > > However, our scan is still pointing to leaf page 1. > In case if we just returned a tuple, the next action would be either >> check the next page for another key or search down to the tree. Maybe But it won't look at the 'next page for another key', but rather at the 'sa= me page or another key', right? In the _bt_scankey_within_page shortcut we'= re taking, there's no stepping to a next page involved. It just locks the p= age again that it previously also locked. > I'm missing something in your scenario, but the latter will land us on a > required page (we do not point to any leaf here), and before the former > there is a check for high/low key. Is there anything else missing? Let me try to clarify. After we return the first tuple, so->currPos.buf is = pointing to page=3D1 in my example (it's the only page after all). We've re= turned item=3D8. Then the split happens and the items get rearranged as in = my example. We're still pointing with so->currPos.buf to page=3D1, but the = page now contains [2,4]. The split happened to the right, so there's a page= =3D2 with [5,6,8], however the ongoing index scan is unaware of that. Now _bt_skip gets called to fetch the next tuple. It starts by checking _bt= _scankey_within_page(scan, so->skipScanKey, so->currPos.buf, dir), the resu= lt of which will be 'true': we're comparing the skip key to the low key of = the page. So it thinks the next key can be found on the current page. It lo= cks the page and does a _binsrch, finding item=3D4 to be returned. The problem here is that _bt_scankey_within_page mistakenly returns true, t= hereby limiting the search to just the page that it's pointing to already. It may be fine to just fix this function to return the proper value (I gues= s it'd also need to look at the high key in this example). It could also be= fixed by not looking at the lo/hi key of the page, but to use the local tu= ple buffer instead. We already did a _read_page once, so if we have any mat= ching tuples on that specific page, we have them locally in the buffer alre= ady. That way we never need to lock the same page twice. --_000_157971388536164964Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Hi Dmitry,


> > On Wed, Jan 22, 2020 at 07:50:30AM = +0000, Floris Van Nee wrote:
> >
> > Anyone please correct me if I'm wrong, but I think one case = where the current patch relies on some data from the page it has locked bef= ore it in checking this hi/lo key. I think it's possible for the following = sequence to happen. Suppose we have a very simple one leaf-page btree containing four elements: leaf page 1 =3D [2,4,= 6,8]
> > We do a backwards index skip scan on this and have just retu= rned our first tuple (8). The buffer is left pinned but unlocked. Now, some= one else comes in and inserts a tuple (value 5) into this page, but suppose= the page happens to be full. So a page split occurs. As far as I know, a page split could happen at any random element = in the page. One of the situations we could be left with is:
> > Leaf page 1 =3D [2,4]
> > Leaf page 2 =3D [5,6,8]
> > However, our scan is still pointing to leaf page 1.

> In case if we just returned a tuple, the next action would be eit= her
>> check the next page for another key or search down to the tre= e. Maybe

But it won't look at the 'next page for another key', but rather at th= e 'same page or another key', right? In the _bt_scankey_within_page shortcu= t we're taking, there's no stepping to a next page involved. It just locks = the page again that it previously also locked.

> I'm missing something in your scenario, but the latter will land = us on a
> required page (we do not point to any leaf here), and before the = former
> there is a check for high/low key. Is there anything else missing= ?
=
= Let me try to clarify. After we return the first tuple, so->currPos.buf = is pointing to page=3D1 in my example (it's the only page after all). We've= returned item=3D8. Then the split happens and the items get rearranged as in my example. We're still pointing with s= o->currPos.buf to page=3D1, but the page now contains [2,4]. The split h= appened to the right, so there's a page=3D2 with [5,6,8], however the ongoi= ng index scan is unaware of that.
= Now _bt_skip gets called to fetch the next tuple. It starts by checking _bt= _scankey_within_page(scan, so->skipScanKey, so->currPos.buf, dir), th= e result of which will be 'true': we're comparing the skip key to the low key of the page. So it thinks the next k= ey can be found on the current page. It locks the page and does a _binsrch,= finding item=3D4 to be returned.
=
= The problem here is that _bt_scankey_within_page mistakenly returns true, t= hereby limiting the search to just the page that it's pointing to already.<= br>
= It may be fine to just fix this function to return the proper value (I= guess it'd also need to look at the high key in this example). It could al= so be fixed by not looking at the lo/hi key of the page, but to use the local tuple buffer instead. We alread= y did a _read_page once, so if we have any matching tuples on tha= t specific page, we have them locally in the buffer already. That way = we never need to lock the same page twice.


--_000_157971388536164964Optivercom_--