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 1hlTjQ-0001Yi-RE for pgsql-hackers@arkaria.postgresql.org; Thu, 11 Jul 2019 07:43:09 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hlTjP-0004pe-Ma for pgsql-hackers@arkaria.postgresql.org; Thu, 11 Jul 2019 07:43:07 +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 1hlTjP-0004pI-6j for pgsql-hackers@lists.postgresql.org; Thu, 11 Jul 2019 07:43:07 +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.89) (envelope-from ) id 1hlTjM-0004fQ-Pw for pgsql-hackers@postgresql.org; Thu, 11 Jul 2019 07:43:06 +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 x6B7Us0Y008651; Thu, 11 Jul 2019 09:41:31 +0200 Received: from opammb0561.comp.optiver.com (opammb0561.comp.optiver.com [10.131.160.1]) by smtp03.optiver.com with ESMTP id 2tjh85tj6q-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Thu, 11 Jul 2019 09:41: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; Thu, 11 Jul 2019 09:41: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; Thu, 11 Jul 2019 09:41:31 +0200 From: Floris Van Nee To: David Rowley , Thomas Munro CC: Dmitry Dolgov <9erthalion6@gmail.com>, Jesper Pedersen , 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: AQHVN7wOPs66PIRMSEm48CCX9Bu/Hg== Date: Thu, 11 Jul 2019 07:41:31 +0000 Message-ID: <1562830890974.32121@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> <1562769595280.16860@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-24752.005 x-tm-as-result: No--0.893900-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_156283089097432121Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-07-11_01:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_156283089097432121Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable > For the general forward direction but for a backwards cursor scroll, > we'd return the lowest value for each distinct prefix, but for the > general backwards direction (DESC case) we'd return the highest value > for each distinct prefix. Looking at IndexNext() the cursor direction > seems to be estate->es_direction and the general scan direction is > indicated by the plan's indexorderdir. Can't we just pass both of > those to index_skip() to have it decide what to do? If we also pass in > indexorderdir then index_skip() should know if it's to return the > highest or lowest value, right? Correct, with these two values correct behavior can be deduced. The impleme= ntation of this is a bit cumbersome though. Consider a case like: SELECT DISTINCT ON (a) a,b,c FROM a WHERE c =3D 2 (with an index on a,b,c) Data (imagine every tuple here actually occurs 10.000 times in the index to= see the benefit of skipping): 1,1,1 1,1,2 1,2,2 1,2,3 2,2,1 2,2,3 3,1,1 3,1,2 3,2,2 3,2,3 Creating a cursor on this query and then moving forward, you should get (1,= 1,2), (3,1,2). In the current implementation of the patch, after bt_first, = it skips over (1,1,2) to (2,2,1). It checks quals and moves forward one-by-= one until it finds a match. This match only comes at (3,1,2) however. Then = it skips to the end. If you move the cursor backwards from the end of the cursor, you should sti= ll get (3,1,2) (1,1,2). A possible implementation would start at the end an= d do a skip to the beginning of the prefix: (3,1,1). Then it needs to move = forward one-by-one in order to find the first matching (minimum) item (3,1,= 2). When it finds it, it needs to skip backwards to the beginning of prefix= 2 (2,2,1). It needs to move forwards to find the minimum element, but shou= ld stop as soon as it detects that the prefix doesn't match anymore (becaus= e there is no match for prefix 2, it will move all the way from (2,2,1) to = (3,1,1)). It then needs to skip backwards again to the start of prefix 1: (= 1,1,1) and scan forward to find (1,1,2). Perhaps anyone can think of an easier way to implement it? I do think being able to use DISTINCT ON is very useful and it's worth the = extra complications. In the future we can add even more useful skipping fea= tures to it, for example: SELECT DISTINCT ON (a) * FROM a WHERE b =3D2 After skipping to the next prefix of column a, we can start a new search fo= r (a,b)=3D(prefix,2) to avoid having to move one-by-one from the start of t= he prefix to the first matching element. There are many other useful optimi= zations possible. That won't have to be for this patch though :-) -Floris --_000_156283089097432121Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

> For the ge= neral forward direction but for a backwards cursor scroll,

> we'd return the lowest value for each disti= nct prefix, but for the
> = general backwards direction (DESC case) we'd return the highest valu= e
> = for each distinct prefix. Looking at IndexNext() the cursor directio= n
> = seems to be estate->es_direction and the general scan direction i= s
> = indicated by the plan's indexorderdir. Can't we just pass both of > = those to index_skip() to have it decide what to do? If we also pass = in
> = indexorderdir then index_skip() should know if it's to return the > = highest or lowest value, right?

Correct, with these two values correct behavior ca= n be deduced. The implementation of this is a bit cumbersome though. Consid= er a case like:

SELECT DISTINCT ON (a) a,b,c FROM a WHERE c = =3D 2 (with an index on a,b,c)
Data (imagine every tuple here actually occurs 10.= 000 times in the index to see the benefit of skipping):
1,1,1
1,1,2
1,2,2
1,2,3
2,2,1
2,2,3
3,1,1
3,1,2
3,2,2
3,2,3

Creating a cursor on this query and then moving fo= rward, you should get (1,1,2), (3,1,2). In the current implementation = of the patch, after bt_first, it skips over (1,1,2) to (2,2,1). It checks q= uals and moves forward one-by-one until it finds a match. This match only comes at (3,1,2) however. Then it skips = to the end.

If you move the cursor backwards from the end of t= he cursor, you should still get (3,1,2) (1,1,2). A possible implementation = would start at the end and do a skip to the beginning of the prefix: (3,1,1= ). Then it needs to move forward one-by-one in order to find the first matching (minimum) item (3,1,2). When it finds it,= it needs to skip backwards to the beginning of prefix 2 (2,2,1). It needs = to move forwards to find the minimum element, but should stop as soon as it= detects that the prefix doesn't match anymore (because there is no match for prefix 2, it will move all th= e way from (2,2,1) to (3,1,1)). It then needs to skip backwards a= gain to the start of prefix 1: (1,1,1) and scan forward to find (1,1,2= ).
Perhaps anyone ca= n think of an easier way to implement it?

I do think being able to use DISTINCT ON is very u= seful and it's worth the extra complications. In the future we can add even= more useful skipping features to it, for example:
SELECT DISTINCT ON (a) * FROM a WHERE b =3D2
After skipping to the next prefix of column a, we = can start a new search for (a,b)=3D(prefix,2) to avoid having to move one-b= y-one from the start of the prefix to the first matching element. There are= many other useful optimizations possible. That won't have to be for this patch though :-)

-Floris

--_000_156283089097432121Optivercom_--