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 1huZtN-0005DW-Li for pgsql-hackers@arkaria.postgresql.org; Mon, 05 Aug 2019 10:07: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 1huZsM-0006XW-SZ for pgsql-hackers@arkaria.postgresql.org; Mon, 05 Aug 2019 10:05:58 +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 1huZsM-0006XP-Iu for pgsql-hackers@lists.postgresql.org; Mon, 05 Aug 2019 10:05:58 +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 1huZsJ-00048S-Op for pgsql-hackers@postgresql.org; Mon, 05 Aug 2019 10:05: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 x758V04W000366; Mon, 5 Aug 2019 12:05:40 +0200 Received: from opammb0562.comp.optiver.com (opammb0562.comp.optiver.com [10.131.160.2]) by smtp03.optiver.com with ESMTP id 2u4yv4rfd9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Mon, 05 Aug 2019 12:05:40 +0200 Received: from opammb0561.comp.optiver.com (10.131.160.1) by opammb0562.comp.optiver.com (10.131.160.2) with Microsoft SMTP Server (TLS) id 15.0.1473.3; Mon, 5 Aug 2019 12:05:39 +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; Mon, 5 Aug 2019 12:05:39 +0200 From: Floris Van Nee To: Kyotaro Horiguchi , "jesper.pedersen@redhat.com" CC: Dmitry Dolgov <9erthalion6@gmail.com>, David Rowley , Thomas Munro , "James Coleman" , Rafia Sabih , "Jeff Janes" , Peter Geoghegan , Tomas Vondra , Thomas Munro , Bhushan Uparkar , PostgreSQL-development , Alexander Korotkov Subject: Re: Index Skip Scan Thread-Topic: Index Skip Scan Thread-Index: AQHVS3E4rk0fIMDqbE+7Lw7HT8ft5A== Date: Mon, 5 Aug 2019 10:05:39 +0000 Message-ID: <1564999539204.96859@Optiver.com> References: <1d917274-73c1-24de-9faf-c1d2c542cb23@redhat.com> <20190725.201737.192223037.horikyota.ntt@gmail.com> <20190725.202950.257050501.horikyota.ntt@gmail.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-24822.006 x-tm-as-result: No--16.774300-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_156499953920496859Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-08-05_04:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_156499953920496859Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Thanks for the new patch. I've reviewed the skip scan patch, but haven't ta= ken a close look at the uniquekeys patch yet. In my previous review I mentioned that queries of the form: select distinct on(a) a,b from a where a=3D1; do not lead to a skip scan with the patch, even though the skip scan would = be much faster. It's about this piece of code in planner.c /* Consider index skip scan as well */ if (enable_indexskipscan && IsA(path, IndexPath) && ((IndexPath *) path)->indexinfo->amcanskip && root->distinct_pathkeys !=3D NIL) The root->distinct_pathkeys is already filtered for redundant keys, so colu= mn 'a' is not in there anymore. Still, it'd be much faster to use the skip = scan here, because a regular scan will scan all entries with a=3D1, even th= ough we're really only interested in the first one. In previous versions, t= his would be fixed by changing the check in planner.c to use root->uniq_dis= tinct_pathkeys instead of root->distinct_pathkeys, but things change a bit = now that the patch is rebased on the unique-keys patch. Would it be valid t= o change this check to root->query_uniquekeys !=3D NIL to consider skip sca= ns also for this query? Second is about the use of _bt_skip and _bt_read_closest in nbtsearch.c. I = don't think _bt_read_closest is correctly implemented, and I'm not sure if = it can be used at all, due to concerns by Tom and Peter about such approach= . I had a similar idea to only partially read items from a page for another= use case, for which I submitted a patch last Friday. However, both Tom and= Peter find this idea quite scary [1]. You could take a look at my patch on= that thread to see the approach taken to correctly partially read a page (= well, correct as far as I can see so far...), but perhaps we need to just u= se the regular _bt_readpage function which reads everything, although this = is unfortunate from a performance point of view, since most of the time we'= re indeed just interested in the first tuple. Eg. it looks like there's some mixups between index offsets and heap tid's = in _bt_read_closest: /* * Save the current item and the previous, even if the * latter does not pass scan key conditions */ ItemPointerData tid =3D prevItup->t_tid; OffsetNumber prevOffnum =3D ItemPointerGetOffsetNumber(&tid); _bt_saveitem(so, itemIndex, prevOffnum, prevItup); itemIndex++; _bt_saveitem(so, itemIndex, offnum, itup); itemIndex++; The 'prevOffnum' is the offset number for the heap tid, and not the offset = number for the index offset, so it looks like just a random item is saved. = Furthermore, index offsets may change due to insertions and vacuums, so if = we, at any point, release the lock, these offsets are not necessarily valid= anymore. However, currently, the patch just reads the closest and then doe= sn't consider this page at all anymore, if the first tuple skipped to turns= out to be not visible. Consider the following sql to illustrate: create table a (a int, b int, c int); insert into a (select vs, ks, 10 from generate_series(1,5) vs, generate_ser= ies(1, 10000) ks); create index on a (a,b); analyze a; select distinct on (a) a,b from a order by a,b; a | b ---+--- 1 | 1 2 | 1 3 | 1 4 | 1 5 | 1 (5 rows) delete from a where a=3D2 and b=3D1; DELETE 1 select distinct on (a) a,b from a order by a,b; a | b ---+----- 1 | 1 2 | 249 ->> this should be b=3D2, because we deleted a=3D2 && b= =3D1. however, it doesn't consider any tuples from that page anymore and gi= ves us the first tuple from the next page. 3 | 1 4 | 1 5 | 1 (5 rows) ? -Floris [1] https://www.postgresql.org/message-id/flat/26641.1564778586%40sss.pgh.p= a.us#dd8f23e1704f45447185894e1c2a4f2a --_000_156499953920496859Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Thanks for the new patch. I've reviewed the skip scan patch, but haven't= taken a close look at the uniquekeys patch yet.


In my previous review I mentioned that queries of the form:

select distinct on(a) a,b from a where a=3D1;

do not lead to a skip scan with the patch, even though the skip scan wou= ld be much faster. It's about this piece of code in planner.c


/* Consider index skip scan as = well */
if (enable_indexskipscan &&= amp;
IsA(path, IndexPath) &&=
((IndexPath *) path)->indexi= nfo->amcanskip &&
root->distinct_pathk= eys !=3D NIL)

The root->distinct_pathkeys is already filtered for redundant keys,= so column 'a' is not in there anymore. Still, it'd be much faster to use t= he skip scan here, because a regular scan will scan all entries with a=3D1,= even though we're really only interested in the first one. In = previous versions, this would be fixed by changing the check in planner.c t= o use root->uniq_distinct_pathkeys instead of root->distinct_pathkeys, but things change a bit now that th= e patch is rebased on the unique-keys patch. Would it be valid to change th= is check to root->query_uniquekeys !=3D NIL to consider skip scans also = for this query?

Second is about the use of _bt_skip and _bt_read_closest in nbtsearch.= c. I don't think _bt_read_closest is correctly implemented, and I'm not sur= e if it can be used at all, due to concerns by Tom and Peter about such app= roach. I had a similar idea to only partially read items from a page for another use case, for which I submitt= ed a patch last Friday. However, both Tom and Peter find this idea quite sc= ary [1]. You could take a look at my patch on that thread to see the a= pproach taken to correctly partially read a page (well, correct as far as I can see so far...), but perhaps we = need to just use the regular _bt_readpage function which reads everything, = although this is unfortunate from a performance point of view, since most o= f the time we're indeed just interested in the first tuple.

Eg. it looks like there's some mixups between index offsets and heap t= id's in _bt_read_closest:
/*
* Save the current item and the= previous, even if the
* latter does not pass scan key= conditions
*/
ItemPointerData tid =3D prevItu= p->t_tid;
OffsetNumber prevOffnum =3D Ite= mPointerGetOffsetNumber(&tid);

_bt_saveitem(so, itemIndex, pre= vOffnum, prevItup);
itemIndex++;

_bt_saveitem(so, itemIndex, off= num, itup);
itemIndex++;

The 'prevOffnum' is the offset number for the heap tid, and not the offset = number for the index offset, so it looks like just a random item is saved. = Furthermore, index offsets may change due to insertions and vacuums, so if = we, at any point, release the lock, these offsets are not necessarily valid anymore. However, currently, = the patch just reads the closest and then doesn't consider this page at all= anymore, if the first tuple skipped to turns out to be not visible. Consid= er the following sql to illustrate:

create table a (a int, b int, c int);
insert into a (select vs, ks, 10 from generate_series(1,5) vs, generat= e_series(1, 10000) ks);
create index on a (a,b);
analyze a;
select distinct on (a) a,b from a order by a,b;

 a | b 
---+---
 1 | 1
 2 | 1
 3 | 1
 4 | 1
 5 | 1
(5 rows)

delete from a where a=3D2 and b=3D1;
DELETE 1

select distinct on (a) a,b from a order by a,b;

 a |  b  
---+-----
 1 |   1
 2 | 249           ->> this should= be b=3D2, because we deleted a=3D2 && b=3D1. however, it doesn't c= onsider any tuples from that page anymore and gives us the first tuple from= the next page.
 3 |   1
 4 |   1
 5 |   1
(5 rows)
​

-Floris


[1] https://www.postg= resql.org/message-id/flat/26641.1564778586%40sss.pgh.pa.us#dd8f23e1704f4544= 7185894e1c2a4f2a

--_000_156499953920496859Optivercom_--