Обсуждение: NULLS LAST performance

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 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