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 1huuz6-0000gL-4L for pgsql-hackers@arkaria.postgresql.org; Tue, 06 Aug 2019 08:38:20 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1huuz4-0001t5-PI for pgsql-hackers@arkaria.postgresql.org; Tue, 06 Aug 2019 08:38:18 +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 1huuz4-0001oj-8d for pgsql-hackers@lists.postgresql.org; Tue, 06 Aug 2019 08:38:18 +0000 Received: from smtp03.optiver.com ([195.246.114.70]) by makus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.92) (envelope-from ) id 1huuz1-00085f-CA for pgsql-hackers@postgresql.org; Tue, 06 Aug 2019 08:38:17 +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 x768V83a015121; Tue, 6 Aug 2019 10:37:56 +0200 Received: from opammb0561.comp.optiver.com (opammb0561.comp.optiver.com [10.131.160.1]) by smtp03.optiver.com with ESMTP id 2u4yv4s28r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Tue, 06 Aug 2019 10:37:56 +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; Tue, 6 Aug 2019 10:37:56 +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; Tue, 6 Aug 2019 10:37:56 +0200 From: Floris Van Nee To: Dmitry Dolgov <9erthalion6@gmail.com> CC: Kyotaro Horiguchi , "jesper.pedersen@redhat.com" , David Rowley , Thomas Munro , James Coleman , Rafia Sabih , Jeff Janes , Peter Geoghegan , Tomas Vondra , Thomas Munro , Bhushan Uparkar , PostgreSQL-development , Alexander Korotkov Thread-Topic: Index Skip Scan [External] Thread-Index: AQHVS82/8I7Hp/xhKE24R/iLI4xfdKbtr/D2 Date: Tue, 6 Aug 2019 08:37:55 +0000 Message-ID: <1565080675672.86115@Optiver.com> References: <1d917274-73c1-24de-9faf-c1d2c542cb23@redhat.com> <20190725.201737.192223037.horikyota.ntt@gmail.com> <20190725.202950.257050501.horikyota.ntt@gmail.com> <1564999539204.96859@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-24824.005 x-tm-as-result: No--10.616400-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_156508067567286115Optivercom_" MIME-Version: 1.0 Subject: Re: Index Skip Scan X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-08-06_05:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_156508067567286115Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable > Yes, the check should be for that. However, the query in question > doesn't have any query_pathkeys, and hence query_uniquekeys in > standard_qp_callback(), so therefore it isn't supported > Your scenario is covered by one of the test cases in case the > functionality is supported. But, I think that is outside the scope of > the current patch. Ah alright, thanks. That makes it clear why it doesn't work. From a user point of view I think it's rather strange that SELECT DISTINCT ON (a) a,b FROM a WHERE a BETWEEN 2 AND 2 would give a fast skip scan, even though the more likely query that someone= would write SELECT DISTINCT ON (a) a,b FROM a WHERE a=3D2 would not. It is something we could be leave up to the next patch though. Something else I just noticed which I'm just writing here for awareness; I = don't think it's that pressing at the moment and can be left to another pat= ch. When there are multiple indices on a table the planner gets confused an= d doesn't select an index-only skip scan even though it could. I'm guessing= it just takes the first available index based on the DISTINCT clause and t= hen doesn't look further, eg. With an index on (a,b) and (a,c,b): postgres=3D# explain select distinct on (a) a,c,b FROM a; QUERY PLAN -------------------------------------------------------------------- Index Scan using a_a_b_idx on a (cost=3D0.29..1.45 rows=3D5 width=3D12) Skip scan mode: true (2 rows) -> This could be an index only scan with the (a,b,c) index. > For the records, the purpose of `_bt_read_closest` is not so much to redu= ce > amount of data we read from a page, but more to correctly handle those > situations we were discussing before with reading forward/backward in cur= sors, > since for that in some cases we need to remember previous values for step= ping > to the next. I've limited number of items, fetched in this function just > because I was misled by having a check for dead tuples in `_bt_skip`. Of = course > we can modify it to read a whole page and leave visibility check for the = code > after `index_getnext_tid` (although in case if we know that all tuples on= this > page are visilbe I guess it's not strictly necessary, but we still get > improvement from skipping itself). I understand and I agree - primary purpose why we chose this function was t= o make it work correctly. I don't think it would be something for this patc= h to use the optimization of partially reading a page. My point was however= , if this optimization was allowed in a future patch, it would have great p= erformance benefits. To fix the current patch, we'd indeed need to read the full page. It'd be g= ood to take a close look at the implementation of this function then, becau= se messing around with the previous/next is also not trivial. I think the c= urrent implementation also has a problem when the item that is skipped to, = is the first item on the page. Eg. (this depends on page size) postgres=3D# drop table if exists b; create table b as select a,b from gene= rate_series(1,5) a, generate_series(1,366) b; create index on b (a,b); anal= yze b; DROP TABLE SELECT 1830 CREATE INDEX ANALYZE postgres=3D# select distinct on(a) a,b from b; a | b ---+--- 1 | 1 2 | 2 <-- (2,1) is the first item on the page and doesn't get selected b= y read_closest function. it returns the second item on page which is (2,2) 3 | 2 4 | 2 5 | 2 (5 rows) -Floris --_000_156508067567286115Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
> Yes, the check should be for that. However, the query in question
> doesn't have any query_pathkeys,= and hence query_uniquekeys in
> standard_qp_callback(), so there= fore it isn't supported

> Your scenario is covered by one = of the test cases in case the
> functionality is supported. But,= I think that is outside the scope of
> the current patch.

Ah alright, thanks. That makes it cle= ar why it doesn't work.
From a user point of view I think it'= s rather strange that
SELECT DISTINCT ON (a) a,b FROM a WHE= RE a BETWEEN 2 AND 2
would give a fast skip scan, even tho= ugh the more likely query that someone would write
SELECT DISTINCT ON (a) a,b FROM a WHE= RE a=3D2
would not.
It is something we could be leave up = to the next patch though.

Something else I just noticed which I= 'm just writing here for awareness; I don't think it's that pressing at the moment and can be left to another patch. When there are multiple in= dices on a table the planner gets confused and doesn't select an index-only= skip scan even though it could. I'm guessing it just takes the first avail= able index based on the DISTINCT clause and then doesn't look further, eg.
With an index on (a,b) and (a,c,b):
postgres=3D# explain select distinct = on (a) a,c,b FROM a;
          &n= bsp;                  QUERY PL= AN                     &n= bsp;       
-------------------------------------= -------------------------------
 Index Scan using a_a_b_idx on a=  (cost=3D0.29..1.45 rows=3D5 width=3D12)
   Skip scan mode: true
(2 rows)
-> This could be an index only sca= n with the (a,b,c) index.

> For the records, the purpose of = `_bt_read_closest` is not so much to reduce
> amount of data we read from a pa= ge, but more to correctly handle those
> situations we were discussing be= fore with reading forward/backward in cursors,
> since for that in some cases we = need to remember previous values for stepping
> to the next. I've limited number= of items, fetched in this function just
> because I was misled by having a= check for dead tuples in `_bt_skip`. Of course
> we can modify it to read a whole= page and leave visibility check for the code
> after `index_getnext_tid` (altho= ugh in case if we know that all tuples on this
> page are visilbe I guess it's no= t strictly necessary, but we still get
> improvement from skipping itself= ).

I understand and I agree - primary pu= rpose why we chose this function was to make it work correctly. I don't think it would be something for this patch to use the optimization= of partially reading a page. My point was however, if this optimization wa= s allowed in a future patch, it would have great performance benefits.
To fix the current patch, we'd indeed= need to read the full page. It'd be good to take a close look at the implementation of this function then, because messing around with the = previous/next is also not trivial. I think the current implementation also = has a problem when the item that is skipped to, is the first item on the pa= ge. Eg. (this depends on page size)

postgres=3D# drop table if exists b; create table b as select a,b from= generate_series(1,5) a, generate_series(1,366) b; create index on b (a,b);= analyze b;
DROP TABLE
SELECT 1830
CREATE INDEX
ANALYZE
postgres=3D# select distinct on(a) a,b from b;
 a | b 
---+---
 1 | 1
 2 | 2   <-- (2,1) is the first item on the page and= doesn't get selected by read_closest function. it returns the second item = on page which is (2,2)
 3 | 2
 4 | 2
 5 | 2
(5 rows)


-Floris

--_000_156508067567286115Optivercom_--