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 1hf0Iq-0000YO-4m for pgsql-hackers@arkaria.postgresql.org; Sun, 23 Jun 2019 11:04:56 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hf0In-0008V3-VO for pgsql-hackers@arkaria.postgresql.org; Sun, 23 Jun 2019 11:04:53 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hf0In-0008Ll-Mp for pgsql-hackers@lists.postgresql.org; Sun, 23 Jun 2019 11:04:53 +0000 Received: from smtp03.optiver.com ([195.246.114.70]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hf0Ii-0007H9-Ih for pgsql-hackers@postgresql.org; Sun, 23 Jun 2019 11:04:51 +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 x5NB233b001640; Sun, 23 Jun 2019 13:04:31 +0200 Received: from opammb0561.comp.optiver.com (opammb0561.comp.optiver.com [10.131.160.1]) by smtp03.optiver.com with ESMTP id 2t99x58dmx-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Sun, 23 Jun 2019 13:04:31 +0200 Received: from opammb0561.comp.optiver.com (10.131.160.1) by opammb0561.comp.optiver.com (10.131.160.1) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Sun, 23 Jun 2019 13:04:31 +0200 Received: from opammb0561.comp.optiver.com ([fe80::9d46:f4ee:846a:2858]) by opammb0561.comp.optiver.com ([fe80::9d46:f4ee:846a:2858%17]) with mapi id 15.00.1473.003; Sun, 23 Jun 2019 13:04:31 +0200 From: Floris Van Nee To: Peter Geoghegan CC: Dmitry Dolgov <9erthalion6@gmail.com>, David Rowley , James Coleman , "jesper.pedersen@redhat.com" , Rafia Sabih , Jeff Janes , Thomas Munro , Tomas Vondra , "Thomas Munro" , PostgreSQL-development , Alexander Korotkov Subject: Re: Index Skip Scan Thread-Topic: Index Skip Scan Thread-Index: AQHVKbNuPGh6JFJE0E+VNrKWzjW9ag== Date: Sun, 23 Jun 2019 11:04:30 +0000 Message-ID: <1561287884806.46718@Optiver.com> References: <2685f020-f302-9bf6-1b5c-ebc2bcebc635@2ndquadrant.com> <1559361698401.22864@Optiver.com> <1559362223126.18661@Optiver.com> <988b7763-5c55-1be1-b7b6-f3a68eff0d40@redhat.com> <1559763453006.85615@Optiver.com> <1559763570329.85227@Optiver.com> <4d469bf2-49ff-bc3d-a428-6c7b5d87d526@redhat.com> <1561198638439.56867@Optiver.com> <1561241730766.23014@Optiver.com>, In-Reply-To: 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-11.0.0.1284-8.100.1062-24706.007 x-tm-as-result: No--11.221700-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_156128788480646718Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-06-23_09:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_156128788480646718Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable > Try the attached patch -- it has DEBUG1 traces with the contents of > index tuples from key points during index scans, allowing you to see > what's going on both as a B-Tree is descended, and as a range scan is > performed. It also shows details of the insertion scankey that is set > up within _bt_first(). This hasn't been adopted to the patch at all, > so you'll probably need to do that. Thanks! That works quite nicely. I've pinpointed the problem to within _bt_skip. I'll try to illustrate with= my test case. The data in the table is (a,b)=3D(1,1), (1,2) ... (1,10000),= (2, 1), (2,2), ... (2,10000) until (5,10000). Running the query SELECT DISTINCT ON (a) a,b FROM a WHERE b=3D2; The flow is like this: _bt_first is called first - it sees there are no suitable scan keys to star= t at a custom location in the tree, so it just starts from the beginning an= d searches until it finds the first tuple (1,2). After the first tuple was yielded, _bt_skip kicks in. It constructs an inse= rt scan key with a=3D1 and nextkey=3Dtrue, so doing the _bt_search + _bt_bi= nsrch on this, it finds the first tuple larger than this: (2,1). This is no= t the tuple that it stops at though, because after that it does this: if (ScanDirectionIsForward(dir)) /* Move back for _bt_next */ offnum =3D OffsetNumberPrev(offnum); .... /* Now read the data */ if (!_bt_readpage(scan, dir, offnum)) { /* * There's no actually-matching data on this page. Try to advance to * the next page. Return false if there's no matching data at all. */ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK); if (!_bt_steppage(scan, dir)) First, it takes the previous tuple with OffsetNumberPrev (so tuple before (= 2,1), which is (1,10000)). This is done, because if this tuple were to be r= eturned, there would be a call to _bt_next afterwards, which would then con= veniently be on the tuple (2,1) that we want. However, _bt_readpage messes = things up, because it only reads tuples that match all the provided keys (s= o where b=3D2). The only tuple it'll return is (2,2). This will be the tupl= e that is set, however, on the call to _bt_next, the tuple is first increme= nted, so we'll find (2,3) there which doesn't match our keys. This leads it= to skip (2,2) in our result set. I was wondering about something else: don't we also have another problem wi= th updating this current index tuple by skipping before calling btgettuple/= _bt_next? I see there's some code in btgettuple to kill dead tuples when sc= an->kill_prior_tuple is true. I'm not too familiar with the concept of kill= ing dead tuples while doing index scans, but by looking at the code it seem= s to be possible that btgettuple returns a tuple, caller processes it and s= ets kill_prior_tuple to true in order to have it killed. However, then the = skip scan kicks in, which sets the current tuple to a completely different = tuple. Then, on the next call of btgettuple, the wrong tuple gets killed. I= s my reasoning correct here or am I missing something? -Floris --_000_156128788480646718Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable


> Try the attached patch -- it has DEBUG1 = traces with the contents of
> index tuples from key points during index scans, allowing you to = see
Thanks! That works quite nicely.

I've pinpointed the problem to within _bt_skip. I'= ll try to illustrate with my test case. The data in the table is (a,b)=3D(1= ,1), (1,2) ... (1,10000), (2, 1), (2,2), ... (2,10000) until (5,10000).
Running the query
SELECT DISTINCT ON (a) a,b FROM a WHERE b=3D2;
The flow is like this:
_bt_first is called first - it sees there = are no suitable scan keys to start at a custom location in the tree, so it = just starts from the beginning and searches until it finds the first tuple = (1,2).
After the first tuple was yielded, _bt_skip kicks = in. It constructs an insert scan key with a=3D1 and nextkey=3Dtrue, so doin= g the _bt_search + _bt_binsrch on this, it finds the fir= st tuple larger than this: (2,1). This is not the tuple that it stops at though, because after that it does this:

if (ScanDirectionIsForward(dir)= )
/* Move back for _bt_next */
offnum =3D OffsetNumberPrev(off= num);
....
/* Now read the data */
    if (!_bt_readpage(scan, dir, offnum))
{
/*
* There's no actually-matching = data on this page.  Try to advance to
* the next page.  Return f= alse if there's no matching data at all.
*/
LockBuffer(so->currPos.buf, = BUFFER_LOCK_UNLOCK);
if (!_bt_steppage(scan, dir))

First, it takes the previous tuple with OffsetNumb= erPrev (so tuple before (2,1), which is (1,10000)). This is done, beca= use if this tuple were to be returned, there would be a call to _bt_next af= terwards, which would then conveniently be on the tuple (2,1) that we want. However, _bt_readpage messes things up= , because it only reads tuples that match all the provided keys (so where b= =3D2). The only tuple it'll return is (2,2). This will be the tuple that is= set, however, on the call to _bt_next, the tuple is first incremented, so we'll find (2,3) there which doesn't ma= tch our keys. This leads it to skip (2,2) in our result set.

I was wondering about something else: don't we als= o have another problem with updating this current index tuple by skipping&n= bsp;before calling btgettuple/_bt_next? I see there's some code in&nbs= p;btgettuple to kill dead tuples when scan->kill_prior_tuple is true. I'm not too familiar with the concept of killing dead tuples whil= e doing index scans, but by looking at the code it seems to be possible tha= t btgettuple returns a tuple, caller processes it and sets kill_prior_tuple= to true in order to have it killed. However, then the skip scan kicks in, which sets the current tuple to a co= mpletely different tuple. Then, on the next call of btgettuple, the wrong t= uple gets killed. Is my reasoning correct here or am I missing something?

-Floris


--_000_156128788480646718Optivercom_--