Re: BUG #18042: Query planner favor index corresponding to a order by with a limit even when there is a where

Sorry I've replied only to Jeff by mistake, Jeff you could discard that precedent mail, I've added things here.

I have tested it with 13.11, 14.8 and they all do the same.

Sorry about the newline the email added in the one-liner json, otherwise it could have been pasted in explain.depesz.com even in json.

I know I can make an (event_type_id, date) index, this is the first thing I did, but it's still far from optimal. Even a covering index including all needed columns is far from optimal.

https://explain.depesz.com/s/8NEk slow using event_date_idx. 3 seconds
https://explain.depesz.com/s/lE8R with an index on (event_type_id, date). 1 seconds.
https://explain.depesz.com/s/99nK with a covering index. 500ms.
https://explain.depesz.com/s/l9da fast even if it seq scan on unit table (real table is larger and an index is used). 26 milliseconds.

Without changing the indexes, I already figured I could use a function like coalesce in the order by that won't change anything since the columns aren't nullable and it would prevent the planner from considering the index.
The nulls first seem a bit better solution, not involving a function. But it's a bit hacky, a newbie could decide to remove that and reintroduce the performance problem.

From the documentation :
An important special case is ORDER BY in combination with LIMIT n: an explicit sort will have to process all the data to identify the first n rows, but if there is an index matching the ORDER BY, the first n rows can be retrieved directly, without scanning the remainder at all.

This is my case, but this optimization pushes the table first (by necessity) and this hurt performance a lot when that table is large and not every column used are included in the index.
Even when they are included, it still pushes that table first and hurt performance, reading more data than necessary, and being discarded in the next step.

I totally understand that it's tricky, depends on statistic and all.

After thinking about that I decided to try with the event table first without the limit and indeed the query planner pushed the unit table first, so without limit the query planner knows how to optimize.
In my humble opinion the "order, limit, index" optimization should not reorder the table, the reorder should be the same as without limit and if the first table is the one with the order by then use the index.
And even then, I'm not convinced about it being optimal, if there is where condition not included in the index, using an index for that where condition would probably be better, because ordering is not that much costly over fetching data from disk. Again, in my humble opinion, I believe that optimization is good only when there is a single table, and everything is included in the index.

I filled in a bug report because I tough that maybe this optimization was just a bit too abrupt and more refinement could be added, like considering the presence of where condition and/or statistics of joined tables, to prevent it.
I tried reading the source to find where that special case might be, but I guess it'll take me more than an afternoon to figure!

If you guys still believe I'm wrong, I have no idea how hard that would be to implement, but if we could opt-out that optimization with an enable_ parameter, that would be a perfect work around.

Christian Vallières<mailto:christian(dot)vallieres(at)evimbec(dot)ca>

Programmeur Analyste

[cid:55cd0c4d-eb6c-4f58-a11c-ff8650f1b87d]<http://www.norda.com/signatures/UGEcz>

t.

(819) 569-1009 p. 25241

[cid:d254a128-49c1-4dc6-ae79-e25babeef0f5]

MISE EN GARDE CONCERNANT LA CONFIDENTIALITÉ

L'information contenue dans ce courriel est réservée exclusivement à l'usage personnel et confidentiel du destinataire indiqué ci-dessus. Si ce message ne vous est pas adressé et que vous n'êtes ni un employé ni un mandataire chargé de le remettre au destinataire, nous vous avisons par les présentes que vous avez reçu ce document par erreur et qu'il est strictement interdit de le réviser, de le diffuser, de le distribuer ou d'en faire une copie puisque confidentiel. Si vous avez reçu cette communication par erreur, veuillez nous en aviser immédiatement par courriel et supprimer le message original.

CONFIDENTIALITY CAUTION
The information contained in this e-mail is intended only for the personal and confidential use of the recipient(s) named above. If the reader of this message is not the intended recipient or an employee or agent responsible for delivering it to the intended recipient, you are hereby notified that you have received this document in error and that any review, dissemination, distribution, or copying of this message is strictly prohibited. If you have received this communication in error, please notify us immediately by e-mail, and delete the original message.

________________________________
De : PG Bug reporting form <noreply(at)postgresql(dot)org>
Envoyé : 28 juillet 2023 14:40
À : pgsql-bugs(at)lists(dot)postgresql(dot)org <pgsql-bugs(at)lists(dot)postgresql(dot)org>
Cc : Christian Vallières <christian(dot)vallieres(at)evimbec(dot)ca>
Objet : BUG #18042: Query planner favor index corresponding to a order by with a limit even when there is a where

ATTENTION: Ce courriel vient d'une organisation externe. Ne cliquez pas sur les liens ou les pièces-jointes si vous ne reconnaissez pas l'expéditeur ou si le message vous semble suspect.

The following bug has been logged on the website:

Bug reference: 18042
Logged by: Christian Vallières
Email address: christian(dot)vallieres(at)evimbec(dot)ca
PostgreSQL version: 15.3
Operating system: Windows 10 x86_64
Description:

Query planner favor starting with the event table and use the 102MB
event_date_idx corresponding to a order by with a limit,
instead of the 94MB event_event_type_id_idx corresponding to the where
condition.

My understanding is that the engine would need to read the event_date_idx
index entirely to find rows matching the where condition.
Using event_event_type_id_idx the engine would only need to find rows
matching the where condition, less rows from a smaller index.

Dropping event_date_idx lead to a plan where it start with unit table then
use event_unit_id_idx on event table which is much better!

I've made the following simplified schema, but can't provide data here since
it weight around 1.3G
I've been able to reproduce the problem with random data, but I need to
remove event_unit_id_idx to get a similar plan.
Ask me if you actually need data.

CREATE TABLE public.unit (
id int4 PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
city_id int4 NOT NULL
);

CREATE INDEX unit_city_id ON public.unit (city_id);

CREATE TABLE public."event" (
id int4 PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
event_type_id int4 NOT NULL,
unit_id int4 NOT NULL,
date timestamp NOT NULL
);

CREATE INDEX event_event_type_id_idx ON public."event" (event_type_id);
CREATE INDEX event_unit_id_idx ON public."event" (unit_id);
CREATE INDEX event_date_idx ON public."event" (date);

EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS, FORMAT JSON)
SELECT *
FROM public.unit
INNER JOIN public."event" ON unit.id = "event".unit_id
WHERE unit.city_id=40005
AND event_type_id=1
ORDER BY date
LIMIT 25;
--Bad plan
[{"Plan":{"Node Type":"Limit","Parallel Aware":false,"Startup
Cost":1000.88,"Total Cost":7653.98,"Plan Rows":25,"Plan Width":28,"Actual
Startup Time":3282.866,"Actual Total Time":3283.948,"Actual Rows":0,"Actual
Loops":1,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Shared
Hit Blocks":9382915,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Gather
Merge","Parent Relationship":"Outer","Parallel Aware":false,"Startup
Cost":1000.88,"Total Cost":497587.81,"Plan Rows":1866,"Plan
Width":28,"Actual Startup Time":3282.864,"Actual Total
Time":3283.947,"Actual Rows":0,"Actual
Loops":1,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Workers
Planned":2,"Workers Launched":2,"Shared Hit Blocks":9382915,"Shared Read
Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit
Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Nested Loop","Parent
Relationship":"Outer","Parallel Aware":false,"Join Type":"Inner","Startup
Cost":0.86,"Total Cost":496372.4,"Plan Rows":778,"Plan Width":28,"Actual
Startup Time":3273.523,"Actual Total Time":3273.524,"Actual Rows":0,"Actual
Loops":3,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Inner
Unique":true,"Shared Hit Blocks":9382915,"Shared Read Blocks":0,"Shared
Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0,"Workers":[{"Worker Number":0,"Actual Startup Time":3277.105,"Actual
Total Time":3277.105,"Actual Rows":0,"Actual Loops":1,"Shared Hit
Blocks":3106786,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0},{"Worker Number":1,"Actual
Startup Time":3260.872,"Actual Total Time":3260.874,"Actual Rows":0,"Actual
Loops":1,"Shared Hit Blocks":3126968,"Shared Read Blocks":0,"Shared Dirtied
Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0}],"Plans":[{"Node Type":"Index Scan","Parent
Relationship":"Outer","Parallel Aware":true,"Scan
Direction":"Forward","Index Name":"event_date_idx","Relation
Name":"event","Schema":"public","Alias":"event","Startup Cost":0.43,"Total
Cost":273080.27,"Plan Rows":497488,"Plan Width":20,"Actual Startup
Time":2.311,"Actual Total Time":2445.49,"Actual Rows":378663,"Actual
Loops":3,"Output":["event.id","event.event_type_id","event.unit_id","event.date"],"Filter":"(event.event_type_id
= 1)","Rows Removed by Filter":4697889,"Shared Hit Blocks":5554775,"Shared
Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local
Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0,"Workers":[{"Worker Number":0,"Actual Startup
Time":0.041,"Actual Total Time":2444.879,"Actual Rows":374983,"Actual
Loops":1,"Shared Hit Blocks":1841396,"Shared Read Blocks":0,"Shared Dirtied
Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0},{"Worker Number":1,"Actual Startup Time":6.862,"Actual Total
Time":2433.461,"Actual Rows":380614,"Actual Loops":1,"Shared Hit
Blocks":1844508,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0}]},{"Node Type":"Index
Scan","Parent Relationship":"Inner","Parallel Aware":false,"Scan
Direction":"Forward","Index Name":"unit_pkey","Relation
Name":"unit","Schema":"public","Alias":"unit","Startup Cost":0.42,"Total
Cost":0.45,"Plan Rows":1,"Plan Width":8,"Actual Startup Time":0.002,"Actual
Total Time":0.002,"Actual Rows":0,"Actual
Loops":1135989,"Output":["unit.id","unit.city_id"],"Index Cond":"(unit.id =
event.unit_id)","Rows Removed by Index Recheck":0,"Filter":"(unit.city_id =
40005)","Rows Removed by Filter":0,"Shared Hit Blocks":3828140,"Shared Read
Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit
Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0,"Workers":[{"Worker Number":0,"Actual Startup
Time":0.002,"Actual Total Time":0.002,"Actual Rows":0,"Actual
Loops":374983,"Shared Hit Blocks":1265390,"Shared Read Blocks":0,"Shared
Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0},{"Worker Number":1,"Actual Startup Time":0.002,"Actual Total
Time":0.002,"Actual Rows":0,"Actual Loops":380614,"Shared Hit
Blocks":1282460,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0}]}]}]}]},"Planning":{"Shared
Hit Blocks":12,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0},"Planning
Time":0.244,"Triggers":[],"Execution Time":3283.98}]

DROP INDEX event_date_idx;
EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS, FORMAT JSON)
SELECT *
FROM public.unit
INNER JOIN public."event" ON unit.id = "event".unit_id
WHERE unit.city_id=40005
AND event_type_id=1
ORDER BY date
LIMIT 25;
--Good plan
[{"Plan":{"Node Type":"Limit","Parallel Aware":false,"Startup
Cost":44726.83,"Total Cost":44729.71,"Plan Rows":25,"Plan Width":28,"Actual
Startup Time":24.786,"Actual Total Time":26.094,"Actual Rows":0,"Actual
Loops":1,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Shared
Hit Blocks":4375,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Gather
Merge","Parent Relationship":"Outer","Parallel Aware":false,"Startup
Cost":44726.83,"Total Cost":44853.1,"Plan Rows":1098,"Plan Width":28,"Actual
Startup Time":24.785,"Actual Total Time":26.092,"Actual Rows":0,"Actual
Loops":1,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Workers
Planned":1,"Workers Launched":1,"Shared Hit Blocks":4375,"Shared Read
Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit
Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0,"Plans":[{"Node Type":"Sort","Parent
Relationship":"Outer","Parallel Aware":false,"Startup Cost":43726.82,"Total
Cost":43729.57,"Plan Rows":1098,"Plan Width":28,"Actual Startup
Time":22.331,"Actual Total Time":22.332,"Actual Rows":0,"Actual
Loops":2,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Sort
Key":["event.date"],"Sort Method":"quicksort","Sort Space Used":25,"Sort
Space Type":"Memory","Shared Hit Blocks":4375,"Shared Read Blocks":0,"Shared
Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0,"Workers":[{"Worker Number":0,"Actual Startup Time":20.152,"Actual
Total Time":20.153,"Actual Rows":0,"Actual Loops":1,"Sort
Method":"quicksort","Sort Space Used":25,"Sort Space Type":"Memory","Shared
Hit Blocks":2141,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0}],"Plans":[{"Node
Type":"Nested Loop","Parent Relationship":"Outer","Parallel
Aware":false,"Join Type":"Inner","Startup Cost":0.43,"Total
Cost":43695.84,"Plan Rows":1098,"Plan Width":28,"Actual Startup
Time":22.313,"Actual Total Time":22.314,"Actual Rows":0,"Actual
Loops":2,"Output":["unit.id","unit.city_id","event.id","event.event_type_id","event.unit_id","event.date"],"Inner
Unique":false,"Shared Hit Blocks":4366,"Shared Read Blocks":0,"Shared
Dirtied Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0,"Workers":[{"Worker Number":0,"Actual Startup Time":20.121,"Actual
Total Time":20.121,"Actual Rows":0,"Actual Loops":1,"Shared Hit
Blocks":2132,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared
Written Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write Time":0}],"Plans":[{"Node Type":"Seq
Scan","Parent Relationship":"Outer","Parallel Aware":true,"Relation
Name":"unit","Schema":"public","Alias":"unit","Startup Cost":0,"Total
Cost":16581.3,"Plan Rows":588,"Plan Width":8,"Actual Startup
Time":7.566,"Actual Total Time":21.818,"Actual Rows":256,"Actual
Loops":2,"Output":["unit.id","unit.city_id"],"Filter":"(unit.city_id =
40005)","Rows Removed by Filter":319366,"Shared Hit Blocks":2829,"Shared
Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written Blocks":0,"Local
Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0,"Workers":[{"Worker Number":0,"Actual Startup
Time":5.368,"Actual Total Time":19.58,"Actual Rows":286,"Actual
Loops":1,"Shared Hit Blocks":1273,"Shared Read Blocks":0,"Shared Dirtied
Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0}]},{"Node Type":"Index Scan","Parent Relationship":"Inner","Parallel
Aware":false,"Scan Direction":"Forward","Index
Name":"event_unit_id_idx","Relation
Name":"event","Schema":"public","Alias":"event","Startup Cost":0.43,"Total
Cost":46.06,"Plan Rows":5,"Plan Width":20,"Actual Startup
Time":0.002,"Actual Total Time":0.002,"Actual Rows":0,"Actual
Loops":512,"Output":["event.id","event.event_type_id","event.unit_id","event.date"],"Index
Cond":"(event.unit_id = unit.id)","Rows Removed by Index
Recheck":0,"Filter":"(event.event_type_id = 1)","Rows Removed by
Filter":0,"Shared Hit Blocks":1537,"Shared Read Blocks":0,"Shared Dirtied
Blocks":0,"Shared Written Blocks":0,"Local Hit Blocks":0,"Local Read
Blocks":0,"Local Dirtied Blocks":0,"Local Written Blocks":0,"Temp Read
Blocks":0,"Temp Written Blocks":0,"I/O Read Time":0,"I/O Write
Time":0,"Workers":[{"Worker Number":0,"Actual Startup Time":0.002,"Actual
Total Time":0.002,"Actual Rows":0,"Actual Loops":286,"Shared Hit
Blocks":859,"Shared Read Blocks":0,"Shared Dirtied Blocks":0,"Shared Written
Blocks":0,"Local Hit Blocks":0,"Local Read Blocks":0,"Local Dirtied
Blocks":0,"Local Written Blocks":0,"Temp Read Blocks":0,"Temp Written
Blocks":0,"I/O Read Time":0,"I/O Write
Time":0}]}]}]}]}]},"Planning":{"Shared Hit Blocks":18,"Shared Read
Blocks":0,"Shared Dirtied Blocks":1,"Shared Written Blocks":0,"Local Hit
Blocks":0,"Local Read Blocks":0,"Local Dirtied Blocks":0,"Local Written
Blocks":0,"Temp Read Blocks":0,"Temp Written Blocks":0,"I/O Read
Time":0,"I/O Write Time":0},"Planning Time":0.336,"Triggers":[],"Execution
Time":26.126}]