Обсуждение: NULLS LAST performance
Hi all,
Running PostgreSQL 8.4.7 (backport package from Debian Lenny).
I have some queries that are based on views, and an engine adds a few clauses (like NULLS LAST). One of these queries has a performance problem.
The simplified form is this:
shs=# explain analyze select * from performance e JOIN part v ON v.performance_id = e.id order by e.creation_date desc limit 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..4.25 rows=10 width=312) (actual time=0.078..0.147 rows=10 loops=1)
-> Nested Loop (cost=0.00..62180.28 rows=146294 width=312) (actual time=0.078..0.145 rows=10 loops=1)
-> Index Scan Backward using performance_create_idx on performance e (cost=0.00..12049.21 rows=145379 width=247) (actual time=0.051..0.087 rows=10 loops=1)
-> Index Scan using part_performance_idx on part v (cost=0.00..0.33 rows=1 width=65) (actual time=0.005..0.005 rows=1 loops=10)
Index Cond: (v.performance_id = e.id)
Total runtime: 0.205 ms
creation_date is declared as NOT NULL, and since it's a inner join, creation_date can never be null in this query. I'd think that if I add NULLS LAST, it wouldn't have any effect.
However, the query with NULLS LAST (as generated by the engine):
shs=# explain analyze select * from performance e JOIN part v ON v.performance_id = e.id order by e.creation_date desc nulls last limit 10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=25773.76..25773.79 rows=10 width=312) (actual time=492.959..492.963 rows=10 loops=1)
-> Sort (cost=25773.76..26139.50 rows=146294 width=312) (actual time=492.958..492.962 rows=10 loops=1)
Sort Key: e.creation_date
Sort Method: top-N heapsort Memory: 27kB
-> Merge Join (cost=1.27..22612.40 rows=146294 width=312) (actual time=0.064..367.160 rows=146294 loops=1)
Merge Cond: (e.id = v.performance_id)
-> Index Scan using performance_pkey on performance e (cost=0.00..11989.20 rows=145379 width=247) (actual time=0.035..160.838 rows=145379 loops=1)
-> Index Scan using part_performance_idx on part v (cost=0.00..8432.35 rows=146294 width=65) (actual time=0.025..91.084 rows=146294 loops=1)
Total runtime: 493.062 ms
Both tables have around 150k rows as you can read from the last plan.
Table performance:
Table "public.performance"
Column | Type | Modifiers
-----------------+--------------------------+----------------------------------------------------------
created_by | integer | not null
creation_date | timestamp with time zone | not null
comments | text |
owned_by | integer | not null
id | integer | not null default nextval('performance_id_seq'::regclass)
title | text |
title_ | text |
performer_id | integer |
first_medium_id | integer |
vperf_id | integer |
perf_date | partial_date |
bonustrack | boolean | not null default false
type_id | integer | not null
instrumental | boolean | not null default false
init_rev_level | smallint | not null default 1
curr_rev_level | smallint | not null default 1
revision_date | timestamp with time zone |
revised_by | integer |
object_type | text | not null default 'performance'::text
editor_note | text |
active | boolean | not null default true
Indexes:
"performance_pkey" PRIMARY KEY, btree (id)
"performance_create_idx" btree (creation_date)
"performance_medium_idx" btree (first_medium_id)
"performance_own_idx" btree (owned_by)
"performance_performer_idx" btree (performer_id)
Table part:
Table "public.part"
Column | Type | Modifiers
----------------+--------------------------+---------------------------------------------------
created_by | integer | not null
creation_date | timestamp with time zone |
comments | text |
owned_by | integer | not null
id | integer | not null default nextval('part_id_seq'::regclass)
work_id | integer | not null
performance_id | integer | not null
Indexes:
"part_pkey" PRIMARY KEY, btree (id)
"part_own_idx" btree (owned_by)
"part_performance_idx" btree (performance_id)
"part_work_idx" btree (work_id)
Please advise!
Thanks.
Kind regards,
Mathieu
On Wed, Feb 23, 2011 at 1:27 PM, Mathieu De Zutter <mathieu@dezutter.org> wrote: > Hi all, > Running PostgreSQL 8.4.7 (backport package from Debian Lenny). > I have some queries that are based on views, and an engine adds a few > clauses (like NULLS LAST). One of these queries has a performance problem. > The simplified form is this: > shs=# explain analyze select * from performance e JOIN part v ON > v.performance_id = e.id order by e.creation_date desc limit 10; > > QUERY PLAN > > ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- > Limit (cost=0.00..4.25 rows=10 width=312) (actual time=0.078..0.147 > rows=10 loops=1) > -> Nested Loop (cost=0.00..62180.28 rows=146294 width=312) (actual > time=0.078..0.145 rows=10 loops=1) > -> Index Scan Backward using performance_create_idx on performance > e (cost=0.00..12049.21 rows=145379 width=247) (actual time=0.051..0.087 > rows=10 loops=1) > -> Index Scan using part_performance_idx on part v > (cost=0.00..0.33 rows=1 width=65) (actual time=0.005..0.005 rows=1 > loops=10) > Index Cond: (v.performance_id = e.id) > Total runtime: 0.205 ms > creation_date is declared as NOT NULL, and since it's a inner join, > creation_date can never be null in this query. I'd think that if I add NULLS > LAST, it wouldn't have any effect. > However, the query with NULLS LAST (as generated by the engine): > shs=# explain analyze select * from performance e JOIN part v ON > v.performance_id = e.id order by e.creation_date desc nulls last limit 10; hm, creation date being NOT NULL is not applied in that sense. maybe it could be logically (I'm not sure). Your best bet is to probably to get the engine to knock off the nulls last stuff, but if you can't, you can always do this: create index performance_creation_date_desc_idx on performance(creation_date desc nulls last); which will index optimize your sql. Interesting that 'null last' fools disallows index usage even when the index was created with nullls last as the default. merlin
Merlin Moncure <mmoncure@gmail.com> writes: > you can always do this: > create index performance_creation_date_desc_idx on > performance(creation_date desc nulls last); > which will index optimize your sql. Interesting that 'null last' > fools disallows index usage even when the index was created with > nullls last as the default. The problem is that his query needs to scan the index in DESC order, which means it's effectively NULLS FIRST, which doesn't match the requested sort order. regards, tom lane
On Wed, Feb 23, 2011 at 10:37 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Merlin Moncure <mmoncure@gmail.com> writes:The problem is that his query needs to scan the index in DESC order,
> you can always do this:
> create index performance_creation_date_desc_idx on
> performance(creation_date desc nulls last);
> which will index optimize your sql. Interesting that 'null last'
> fools disallows index usage even when the index was created with
> nullls last as the default.
which means it's effectively NULLS FIRST, which doesn't match the
requested sort order.
Merlin, Tom,
Thanks for explaining the behavior!
Any chance that the planner could get smarter about this? In my naive view, it would just be telling the planner that it can disregard "NULLS" when searching for an index, in case the column is known to be NOT NULL.
Kind regards,
Mathieu
On Feb 24, 2011, at 3:47 AM, Mathieu De Zutter wrote: > > which will index optimize your sql. Interesting that 'null last' > > fools disallows index usage even when the index was created with > > nullls last as the default. > > The problem is that his query needs to scan the index in DESC order, > which means it's effectively NULLS FIRST, which doesn't match the > requested sort order. > > Merlin, Tom, > > Thanks for explaining the behavior! > > Any chance that the planner could get smarter about this? In my naive view, it would just be telling the planner that itcan disregard "NULLS" when searching for an index, in case the column is known to be NOT NULL. Unfortunately, I don't think the planner actually has that level of knowledge. A more reasonable fix might be to teach the executor that it can do 2 scans of the index: one to get non-null data and asecond to get null data. I don't know if the use case is prevalent enough to warrant the extra code though. -- Jim C. Nasby, Database Architect jim@nasby.net 512.569.9461 (cell) http://jim.nasby.net
On Wed, Mar 9, 2011 at 6:01 PM, Jim Nasby <jim@nasby.net> wrote: > Unfortunately, I don't think the planner actually has that level of knowledge. Actually, I don't think it would be that hard to teach the planner about that special case... > A more reasonable fix might be to teach the executor that it can do 2 scans of the index: one to get non-null data anda second to get null data. I don't know if the use case is prevalent enough to warrant the extra code though. That would probably be harder, but useful. I thought about working on it before but got sidetracked onto other things. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Thu, Mar 10, 2011 at 9:55 AM, Robert Haas <robertmhaas@gmail.com> wrote: > On Wed, Mar 9, 2011 at 6:01 PM, Jim Nasby <jim@nasby.net> wrote: >> Unfortunately, I don't think the planner actually has that level of knowledge. > > Actually, I don't think it would be that hard to teach the planner > about that special case... > >> A more reasonable fix might be to teach the executor that it can do 2 scans of the index: one to get non-null data anda second to get null data. I don't know if the use case is prevalent enough to warrant the extra code though. > > That would probably be harder, but useful. I thought about working on > it before but got sidetracked onto other things. ISTM this isn't all that different from the case of composite indexes where you are missing the left most term, or you have an index on a,b,c (which the server already handles) but user asks for a,b desc, c. If cardinality on b is low it might pay to loop and break up the scan. merlin
On Thu, Mar 10, 2011 at 11:32 AM, Merlin Moncure <mmoncure@gmail.com> wrote: > On Thu, Mar 10, 2011 at 9:55 AM, Robert Haas <robertmhaas@gmail.com> wrote: >> On Wed, Mar 9, 2011 at 6:01 PM, Jim Nasby <jim@nasby.net> wrote: >>> Unfortunately, I don't think the planner actually has that level of knowledge. >> >> Actually, I don't think it would be that hard to teach the planner >> about that special case... >> >>> A more reasonable fix might be to teach the executor that it can do 2 scans of the index: one to get non-null data anda second to get null data. I don't know if the use case is prevalent enough to warrant the extra code though. >> >> That would probably be harder, but useful. I thought about working on >> it before but got sidetracked onto other things. > > ISTM this isn't all that different from the case of composite indexes > where you are missing the left most term, or you have an index on > a,b,c (which the server already handles) but user asks for a,b desc, > c. If cardinality on b is low it might pay to loop and break up the > scan. Yeah, there are a couple of refinements possible here. One possibility is that you might ask for ORDER BY a, b and the only relevant index is on a. In that case, it'd be a good idea to consider scanning the index and sorting each equal group on b. I've seen quite a few queries that would benefit from this. A second possibility is that you might ask for ORDER BY a, b and the only relevant index is on a, b DESC. In that case, you could do three things: - Scan the index and sort each group that's equal on a by b desc, just as if the index were only on a. - Scan the index and reverse each group. - Scan the index in a funny order - for each value of a, find the highest value of b and scan backwards until the a value changes; then repeat for the next a-value. And similarly with the case where you have ORDER BY a NULLS FIRST and an index on a NULLS LAST, you could either: - Detect when the column is NOT NULL and ignore the NULLS FIRST/LAST property for purposes of matching the index in such cases, or - Scan the index in a funny order - traverse the index to find the first non-NULL entry at whichever end of the index has the nulls, go from there to the end, and then "wrap around" to pick up the null entries The tricky part, at least IMO, is that you've got to not only teach the planner to recognize these conditions when they occur, but also find some way of passing it down to the index AM, which you also have to modify to know how to do all this stuff. The worst part about making modifications of this type is that it's really hard to unit test them - the planner, executor, and index AM all have to cooperate before you can get off the ground. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company