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 1hlDlY-00033U-6l for pgsql-hackers@arkaria.postgresql.org; Wed, 10 Jul 2019 14:40:16 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hlDlW-00077w-MI for pgsql-hackers@arkaria.postgresql.org; Wed, 10 Jul 2019 14:40:14 +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 1hlDlW-000731-A0 for pgsql-hackers@lists.postgresql.org; Wed, 10 Jul 2019 14:40:14 +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 1hlDlT-0003ou-Gk for pgsql-hackers@postgresql.org; Wed, 10 Jul 2019 14:40:13 +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 x6AEVmUp014036; Wed, 10 Jul 2019 16:39:56 +0200 Received: from opammb0561.comp.optiver.com (opammb0561.comp.optiver.com [10.131.160.1]) by smtp03.optiver.com with ESMTP id 2tjh85t758-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Wed, 10 Jul 2019 16:39: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; Wed, 10 Jul 2019 16:39:55 +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; Wed, 10 Jul 2019 16:39:55 +0200 From: Floris Van Nee To: Dmitry Dolgov <9erthalion6@gmail.com>, Thomas Munro CC: David Rowley , 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: AQHVNywUdATv0+5AHUO9P+ZQG4MLYA== Date: Wed, 10 Jul 2019 14:39:55 +0000 Message-ID: <1562769595280.16860@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> , 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-24750.007 x-tm-as-result: No--8.617100-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_156276959528016860Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-07-10_06:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_156276959528016860Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable > Here is finally a new version of the patch, where all the mentioned issue= s > seems to be fixed and the corresponding new tests should keep it like tha= t > (I've skipped all the pubs at PostgresLondon for that). Thanks for the new patch! Really appreciate the work you're putting into it= . I verified that the backwards index scan is indeed functioning now. However= , I'm afraid it's not that simple, as I think the cursor case is broken now= . I think having just the 'scan direction' in the btree code is not enough = to get this working properly, because we need to know whether we want the m= inimum or maximum element of a certain prefix. There are basically four cas= es: - Forward Index Scan + Forward cursor: we want the minimum element within a= prefix and we want to skip 'forward' to the next prefix - Forward Index Scan + Backward cursor: we want the minimum element within = a prefix and we want to skip 'backward' to the previous prefix - Backward Index Scan + Forward cursor: we want the maximum element within = a prefix and we want to skip 'backward' to the previous prefix - Backward Index Scan + Backward cursor: we want the maximum element within= a prefix and we want to skip 'forward' to the next prefix These cases make it rather complicated unfortunately. They do somewhat tie = in with the previous discussion on this thread about being able to skip to = the min or max value. If we ever want to support a sort of minmax scan, we'= ll encounter the same issues. Also, I think in planner.c, line 4831, we should actually be looking at whe= ther uniq_distinct_pathkeys is NIL, rather than the current check for disti= nct_pathkeys. That'll make the planner pick the skip scan even with queries= like "select distinct on (a) a,b where a=3D2". Currently, it doesn't pick = the skip scan here, beacuse distinct_pathkeys does not contain "a" anymore.= This leads to it scanning every item for a=3D2 even though it can stop aft= er the first one. I'll do some more tests with the patch. -Floris --_000_156276959528016860Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

> H= ere is finally a new version of the patch, where all the mentioned issues

> seems to be fixed and the corresponding = new tests should keep it like that
> (I've skipped all the pubs at PostgresLondon for that).


Thanks for the new patch! Really appreciate the work you're putting into= it.


I verified that the backwards index scan is indeed functioning now. Howe= ver, I'm afraid it's not that simple, as I think the cursor case is br= oken now. I think having just the 'scan direction' in the btree code i= s not enough to get this working properly, because we need to know whether we want the minimum or maximum element of = a certain prefix. There are basically four cases:

- Forward Index Scan + Forward cursor: we want the minimum element w= ithin a prefix and we want to skip 'forward' to the next prefix

- Forward Index Scan = 3; Backward cursor: we want the minimum element within a prefix a= nd we want to skip 'backward' to the previous prefix

- Backward Index Scan &#= 43; Forward cursor: we want the maximum element within a prefix a= nd we want to skip 'backward' to the previous prefix

- Backward Index Sc= an + Backward cursor: we want the maximum element within a pr= efix and we want to skip 'forward' to the next prefix

These cases make it rather complicated unfortunately. They do somewhat t= ie in with the previous discussion on this thread about being able to = skip to the min or max value. If we ever want to support a sort of minmax s= can, we'll encounter the same issues.


Also, I think in planner.c, line 4831, we should actually be looking at = whether uniq_distinct_pathkeys is NIL, rather than the current check for di= stinct_pathkeys. That'll make the planner pick the skip scan even with quer= ies like "select distinct on (a) a,b where a=3D2". Currently, it doesn't pick the skip scan here, beac= use distinct_pathkeys does not contain "a" anymore. This leads to= it scanning every item for a=3D2 even though it can stop after the first o= ne.


I'll do some more tests with the patch.


-Floris


--_000_156276959528016860Optivercom_--