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 1hWvDY-000260-Py for pgsql-hackers@arkaria.postgresql.org; Sat, 01 Jun 2019 04:02:05 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hWvDX-0001E1-Iy for pgsql-hackers@arkaria.postgresql.org; Sat, 01 Jun 2019 04:02:03 +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 1hWvDX-0001Du-8i for pgsql-hackers@lists.postgresql.org; Sat, 01 Jun 2019 04:02:03 +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 1hWvDU-00006m-Pl for pgsql-hackers@postgresql.org; Sat, 01 Jun 2019 04:02:02 +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 x5141dv7008131; Sat, 1 Jun 2019 06:01:39 +0200 Received: from opammb0562.comp.optiver.com (opammb0562.comp.optiver.com [10.131.160.2]) by smtp03.optiver.com with ESMTP id 2suey58149-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Sat, 01 Jun 2019 06:01:39 +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.1263.5; Sat, 1 Jun 2019 06:01:39 +0200 Received: from opammb0561.comp.optiver.com ([::1]) by opammb0561.comp.optiver.com ([fe80::d550:2c12:6cc:8457%17]) with mapi id 15.00.1263.000; Sat, 1 Jun 2019 06:01:39 +0200 From: Floris Van Nee To: Dmitry Dolgov <9erthalion6@gmail.com>, Kyotaro HORIGUCHI CC: Jeff Janes , Thomas Munro , Jesper Pedersen , Alexander Kuzmenkov , Peter Geoghegan , Tomas Vondra , Thomas Munro , Bhushan Uparkar , PostgreSQL-development , Alexander Korotkov , James Coleman Subject: Re: Index Skip Scan Thread-Topic: Index Skip Scan Thread-Index: AQHVGB0yxKHeWvA4q0SO7fDFkDcvLQ== Date: Sat, 1 Jun 2019 04:01:38 +0000 Message-ID: <1559361698401.22864@Optiver.com> References: <2685f020-f302-9bf6-1b5c-ebc2bcebc635@2ndquadrant.com> <20190315.125452.252656146.horiguchi.kyotaro@lab.ntt.co.jp> , 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-24650.004 x-tm-as-result: No--5.050800-0.000000-31 x-tm-as-user-approved-sender: Yes x-tm-as-user-blocked-sender: No Content-Type: multipart/alternative; boundary="_000_155936169840122864Optivercom_" MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-06-01_03:,, signatures=0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --_000_155936169840122864Optivercom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable After some talks with Jesper at PGCon about the Index Skip Scan, I started = testing this patch, because it seems to have great potential in speeding up= many of our queries (great conference by the way, really enjoyed my first = time being there!). I haven't looked in depth to the code itself, but I foc= used on some testing with real data that we have. Let me start by sketching our primary use case for this, as it is similar, = but slightly different than what was discussed earlier in this thread. I th= ink this use case is something a lot of people who handle timeseries data h= ave. Our database has many tables with timeseries data. We don't update row= s, but just insert new rows each time. One example of this would be a table= with prices for instruments. Instruments are identified by a column called= feedcode. Prices of instrument update with a certain frequency. Each time = it updates we insert a new row with the new value and the timestamp at that= time. So in the simplest form, you could see it as a table like this: create table prices (feedcode text, updated_at timestamptz, value float8); = -- there'll be some other columns as well, this is just an example create unique index on prices (feedcode, updated_at desc); This table perfectly fits the criteria for the index skip scan as there are= relatively few distinct feedcodes, but each of them has quite a lot of pri= ce inserts (imagine 1000 distinct feedcodes, each of them having one price = per second). We normally partition our data by a certain time interval, so = let's say we're just looking at one day of prices here. We have other cases= with higher update frequencies and/or more distinct values though. Typical queries on this table involve querying the price at a certain point= in time, or simply querying the latest update. If we know the feedcode, th= is is easy: select * from prices where feedcode=3D'A' and updated_at <=3D '2019-06-01 1= 2:00' order by feedcode, updated_at desc limit 1 Unfortunately, this gets hard if you want to know the price of everything a= t a certain point in time. The query then becomes: select distinct on (feedcode) * from prices where updated_at <=3D '2019-06-= 01 12:00' order by feedcode, updated_at desc Up until now (even with this patch) this uses a regular index scan + a uniq= ue node which scans the full index, which is terribly slow and is also not = constant - as the table grows it becomes slower and slower. Obviously there are currently already ways to speed this up using the recur= sive loose index scan, but I think everybody agrees that those are pretty u= nreadable. However, since they're also several orders of magnitude faster, = we actually use them everywhere. Eg. -- certain point in time -- first query *all* distinct feedcodes (disregarding time), then look do a= n index scan for every feedcode found to see if it has an update in the tim= e window we're interested in -- this essentially means we're doing 2*N index scans with recursive t as ( select feedcode from prices order by feedcode, updated_at desc limit 1 union all select n.feedcode from t cross join lateral (select feedcode from prices where feedcode > t.feedc= ode order by feedcode, updated_at desc limit 1) n ) select n.* from t cross join lateral (select * from prices where feedcode=3Dt.feedcode and = updated_at <=3D '2019-06-01 12:00' order by feedcode, updated_at desc limit= 1) n -- just latest value -- if we're interested in just the latest value, it can actually be optimiz= ed to just N index scans like this. -- to make it even more confusing - there's a tradeoff here.. if you're que= rying a timestamp close to the latest available timestamp, it is often fast= er to use this method anyway and just put the filter for updated_at inside = this query. this avoids the overhead of 2*N index scans, at the expense tha= t the LIMIT 1 may have to scan several tuples before finding one that match= es the timestamp criteria. With the 2*N method above we're guaranteed that = the first tuple it sees is the correct tuple, but we're doing many more sca= ns... with recursive t as ( select * from prices order by feedcode, updated_at desc limit 1 union all select n.* from t cross join lateral (select * from prices where feedcode > t.feedcode ord= er by feedcode, updated_at desc limit 1) _ ) select * from t I hope this makes our current situation clear. Please do ask if I need to e= laborate on something here. So what changes with this patch? The great thing is that the recursive CTE = is not required anymore! This is a big win for readability and it helps per= formance as well. It makes everything much better. I am really happy with t= hese results. If the index skip scan triggers, it is easily over 100x faste= r than the naive 'distinct on' query in earlier versions of Postgres. It is= also quite a bit faster than the recursive CTE version of the query. I have a few remarks though. I tested some of our queries with the patch an= d found that the following query would (with patch) work best now for arbit= rary timestamps: -- first query all distinct values using the index skip scan, then do an in= dex scan for each of these select r.* from ( select distinct feedcode from prices ) k cross join lateral ( select * from prices where feedcode=3Dk.feedcode and updated_at <=3D '2019-06-01 12:00' order by feedcode, updated_at desc limit 1 ) r? While certainly a big improvement over the recursive CTE, it would be nice = if the even simpler form with the 'distinct on' would work out of the box u= sing an index skip scan. select distinct on (feedcode) * from prices where updated_at <=3D '2019-06-= 01 12:00' order by feedcode, updated_at desc As far as I can see, there are two main problems with that at the moment. 1) Only support for Index-Only scan at the moment, not for regular index sc= ans. This was already mentioned upthread and I can understand that it was l= eft out until now to constrain the scope of this. However, if we were to su= pport 'distinct on' + selecting columns that are not part of the index we n= eed a regular index scan instead of the index only scan. 2) The complicating part that we're interested in the value 'at a specific = point in time'. This comparison with updated_at messes up all efficiency, a= s the index scan first looks at the *latest* updated_at for a certain feedc= ode and then walks the tree until it finds a tuple that matches the updated= _at criteria (which possibly never happens, in which case it will happily w= alk over the full index). I'm actually unsure if there is anything we can d= o about this (without adding a lot of complexity), aside from just rewritin= g the query itself in the way I did where we're doing the skip scan for all= distinct items followed by a second round of index scans for the specific = point in time. I'm struggling a bit to explain this part clearly - I hope i= t's clear though. Please let me know if I should elaborate. Perhaps it's ea= siest to see by the difference in speed between the following two queries: select distinct feedcode from prices -- approx 10ms select distinct feedcode from prices where updated_at <=3D '1999-01-01 00:0= 0' -- approx 200ms Both use the index skip scan, but the first one is very fast, because it ca= n skip large parts of the index. The second one scans the full index, becau= se it never finds any row that matches the where condition so it can never = skip anything. Thanks for this great patch. It is already very useful and ?fills a gap tha= t has existed for a long time. It is going to make our queries so much more= readable and performant if we won't have to resort to recursive CTEs anymo= re! -Floris --_000_155936169840122864Optivercom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

After some talks with Jesper at PGCon about the Index Skip Scan, I = started testing this patch, because it seems to have great potential i= n speeding up many of our queries (great conference by the way, really=  enjoyed my first time being there!). I haven't looked in depth to the code itself, but I focused on some testing with rea= l data that we have.

Let me start by sketching our primary use case for this, as it is simila= r, but slightly different than what was discussed earlier in this thread. I= think this use case is something a lot of people who handle timeseries dat= a have. Our database has many tables with timeseries data. We don't update rows, but just insert new rows each = time. One example of this would be a table with prices for instruments= . Instruments are identified by a column called feedcode. Prices of in= strument update with a certain frequency. Each time it updates we insert a new row with the new value and the timest= amp at that time. So in the simplest form, you could see it as a table= like this:


create table prices (feedcode text, updated_at timestamptz, value float8= ); -- there'll be some other columns as well, this is just an example

create unique index on prices (feedcode, updated_at desc);


This table perfectly fit= s the criteria for the index skip scan as there are relatively few dis= tinct feedcodes, but each of them has quite a lot of price inserts (imagine 1000 distinct feedcodes, each of them= having one price per second). We normally partition our data by a certain = time interval, so let's say we're just looking at one day of prices here. W= e have other cases with higher update frequencies and/or more distinct values though.


Typical queries on this = table involve querying the price at a certain point in time, or simply quer= ying the latest update. If we know the feedcode, this is easy:

select * from prices whe= re feedcode=3D'A' and updated_at <=3D '2019-06-01 12:00' order by f= eedcode, updated_at desc limit 1


Unfortunately, this gets= hard if you want to know the price of everything at a certain point in tim= e. The query then becomes:

select distinct on (feed= code) * from prices where updated_at <=3D '2019-06-01 12:00' order by fe= edcode, updated_at desc

Up until now (even with = this patch) this uses a regular index scan + a unique node which scans = the full index, which is terribly slow and is also not constant - as the table grows it becomes slower and slower= .


Obviously there are curr= ently already ways to speed this up using the recursive loose index scan, b= ut I think everybody agrees that those are pretty unreadable. However, since they're also several orders of = magnitude faster, we actually use them everywhere. Eg.

-- certain point in time=

-- first query *all* dis= tinct feedcodes (disregarding time), then look do an index scan for every f= eedcode found to see if it has an update in the time window we're interested in

-- this essentially mean= s we're doing 2*N index scans

with recursive t as (
   select feedcode from prices order by feedcode, updated_at= desc limit 1
   union all 
   select n.feedcode from t
   cross join lateral (select feedcode from prices where fee= dcode > t.feedcode order by feedcode, updated_at desc limit 1) n
) select n.* from t
  cross join lateral (select * from prices where feedcode=3Dt.fee= dcode and updated_at <=3D '2019-06-01 12:00' order by feedcode, updated_= at desc limit 1) n

-- just latest value
-- if we're interested in just the latest value, it can actually be op= timized to just N index scans like this.
-- to make it even more confusing - there's a tradeoff here.. if you'r= e querying a timestamp close to the latest available timestamp, it is often= faster to use this method anyway and just put the filter for updated_at in= side this query. this avoids the overhead of 2*N index scans, at the expense that the LIMIT 1 may have to s= can several tuples before finding one that matches the timestamp criteria. = With the 2*N method above we're guaranteed that the first tuple it sees&nbs= p;is the correct tuple, but we're doing many more scans...
with recursive t as (
   select * from prices order by feedcode, updated_at desc l= imit 1
   union all 
   select n.* from t
   cross join lateral (select * from prices where feedcode &= gt; t.feedcode order by feedcode, updated_at desc limit 1) _
) select * from t


I hope this makes our current situation clear. Please do ask if I need t= o elaborate on something here.


So what changes with this patch? The great thing is that the recurs= ive CTE is not required anymore! This is a big win for readability and it h= elps performance as well. It makes everything much better. I am really happ= y with these results. If the index skip scan triggers, it is easily over 100x faster than the naive 'distinct on' = query in earlier versions of Postgres. It is also quite a bit faster than t= he recursive CTE version of the query.


I have a few remarks though. I tested some of our queries with the patch= and found that the following query would (with patch) work best now for ar= bitrary timestamps:

-- first query all distinct values using the index skip scan, then do an= index scan for each of these

select r.* from (
   select distinct feedcode from prices
) k
cross join lateral (
   select *
   from prices
   where feedcode=3Dk.feedcode and updated_at <=3D '2019-= 06-01 12:00'
   order by feedcode, updated_at desc
   limit 1
) r​


While certainly a b= ig improvement over the recursive CTE, it would be nice if the even simpler= form with the 'distinct on' would work out of the box using an index skip scan.

select distinct on (feedcode) * fro= m prices where updated_at <=3D '2019-06-01 12:00' order by feedcode, upd= ated_at desc


As far as I can see= , there are two main problems with that at the moment.

1) Only support for Inde= x-Only scan at the moment, not for regular index scans. This was alrea= dy mentioned upthread and I can understand that it was left out until now to constrain the scope of this. However, if= we were to support 'distinct on' + selecting columns that are not part= of the index we need a regular index scan instead of the index only s= can.

2) The complicating part= that we're interested in the value 'at a specific point in time'. This com= parison with updated_at messes up all efficiency, as the index scan first looks at the *latest* updated_at f= or a certain feedcode and then walks the tree until it finds a tu= ple that matches the updated_at criteria (which possibly never happens, in = which case it will happily walk over the full index). I'm actually unsure if there is anything we can do about this (wit= hout adding a lot of complexity), aside from just rewriting the query itsel= f in the way I did where we're doing the skip scan for all distinct items f= ollowed by a second round of index scans for the specific point in time. I'm struggling a bit&= nbsp;to explain this part clearly - I hope it's clear though. Please l= et me know if I should elaborate. Perhaps it's easiest to see by the d= ifference in speed between the following two queries:

select distinct feedcode= from prices -- approx 10ms

select distinct feedcode= from prices where updated_at <=3D '1999-01-01 00:00' -- approx 200= ms

Both use the index skip = scan, but the first one is very fast, because it can skip large parts of th= e index. The second one scans the full index, because it never finds any row that matches the where conditio= n so it can never skip anything.


Thanks for this great patch. It is already very useful and ​fill= s a gap that has existed for a long time. It is going to make our queries s= o much more readable and performant if we won't have to resort to recursive= CTEs anymore!


-Floris


--_000_155936169840122864Optivercom_--