Thread: Some question about lazy subquery/procedures execution in SELECT ... ORDER BY... LIMIT N queries

Is here any reason why Postgresql calculates subqueries/storable procedures in select list before applying ORDER BY / LIMIT?

I talking about cases like:

SELECT *,
(some very slow subquery or slow storable stable/immutable procedure like xml processing)
FROM
some_table
ORDER BY
some_field (unrelated to subquery results)
LIMIT N
?

I seen cases where that lead to 3-6 orders of slowdown.

Simpliest test case:

CREATE TABLE test (id integer);
INSERT INTO test SELECT * FROM generate_series(1,1000);

Slow query (note LOOPS=1000 around subplan):
 EXPLAIN ANALYZE select id,(select count(*) from test t1 where t1.id=t.id) from test t order by id limit 10;
                                                          QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=13044.61..13044.63 rows=10 width=4) (actual time=158.636..158.641 rows=10 loops=1)
   ->  Sort  (cost=13044.61..13047.11 rows=1000 width=4) (actual time=158.636..158.639 rows=10 loops=1)
         Sort Key: t.id
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Seq Scan on test t  (cost=0.00..13023.00 rows=1000 width=4) (actual time=0.188..158.242 rows=1000 loops=1)
               SubPlan 1
                 ->  Aggregate  (cost=13.00..13.01 rows=1 width=0) (actual time=0.157..0.157 rows=1 loops=1000)
                       ->  Seq Scan on test t1  (cost=0.00..13.00 rows=1 width=0) (actual time=0.081..0.156 rows=1 loops=1000)
                             Filter: (id = t.id)
 Total runtime: 158.676 ms

Fast query:
EXPLAIN ANALYZE select id,(select count(*) from test t1 where t1.id=t.id) from (select id from test order by id limit 10) as t order by id;
                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Subquery Scan on t  (cost=32.11..162.36 rows=10 width=4) (actual time=1.366..4.770 rows=10 loops=1)
   ->  Limit  (cost=32.11..32.13 rows=10 width=4) (actual time=0.971..0.983 rows=10 loops=1)
         ->  Sort  (cost=32.11..34.61 rows=1000 width=4) (actual time=0.970..0.975 rows=10 loops=1)
               Sort Key: test.id
               Sort Method: top-N heapsort  Memory: 25kB
               ->  Seq Scan on test  (cost=0.00..10.50 rows=1000 width=4) (actual time=0.027..0.455 rows=1000 loops=1)
   SubPlan 1
     ->  Aggregate  (cost=13.00..13.01 rows=1 width=0) (actual time=0.375..0.375 rows=1 loops=10)
           ->  Seq Scan on test t1  (cost=0.00..13.00 rows=1 width=0) (actual time=0.017..0.371 rows=1 loops=10)
                 Filter: (id = t.id)
 Total runtime: 4.845 ms

Using second way is reasonable workaround for sure, but half year ago I happen to meet project where I was forced ask developers to rewrite huge pile of analitical queries on that way
to get reasonable performance (and there was a lot outcry and complaints in the process).

And ofcourse there is not always possible to create additional indexes so query will be go through index scan/backward indexscan instead of sort/limit in the top level.

Regards,
Maksym

--
Maxim Boguk
Senior Postgresql DBA.

Phone RU: +7 910 405 4718
Phone AU: +61 45 218 5678

Skype: maxim.boguk
Jabber: maxim.boguk@gmail.com

LinkedIn profile: http://nz.linkedin.com/in/maximboguk
If they can send one man to the moon... why can't they send them all?

МойКруг: http://mboguk.moikrug.ru/
Сила солому ломит, но не все в нашей жизни - солома, да и сила далеко не все.

Maxim Boguk <maxim.boguk@gmail.com> writes:
> Is here any reason why Postgresql calculates subqueries/storable procedures
> in select list before applying ORDER BY / LIMIT?

Well, that's the definition of ORDER BY --- it happens after computing
the select list, according to the SQL standard.  We try to optimize this
in some cases but you can't really complain when we don't.  Consider
putting the expensive function outside the ORDER BY/LIMIT, ie

select ..., expensive_fn() from (select ... order by ... limit ...) ss;

            regards, tom lane

I understand that position.
However if assumption: " the definition of ORDER BY --- it happens after computing the select list, according to the SQL standard"
is correct,
then plans like:

postgres=# EXPLAIN ANALYZE SELECT * from test order by _data limit 10 offset 1000;
                                                              QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2884.19..2913.03 rows=10 width=8) (actual time=3.584..3.620 rows=10 loops=1)
   ->  Index Scan using random_key on test  (cost=0.00..2884190.16 rows=1000000 width=8) (actual time=0.103..3.354 rows=1010 loops=1)
 Total runtime: 3.663 ms
(3 rows)
should not be used at all.


In realty I was bite by next scenario (that is simplified case):

postgres=# CREATE TABLE test as (select random() as _data from (select * from generate_series(1,1000000)) as t);
SELECT 1000000
postgres=# CREATE INDEX random_key on test(_data);
CREATE INDEX
postgres=# analyze test;
ANALYZE
postgres=# set seq_page_cost to 1;
SET
postgres=# set random_page_cost to 4;
SET
postgres=# set effective_cache_size to '16MB';
SET

Now:
postgres=# EXPLAIN analyze SELECT *,(select pg_sleep(10)) from test order by _data limit 10;
                                                                 QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.01..28.85 rows=10 width=8) (actual time=10001.132..10001.198 rows=10 loops=1)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=10001.076..10001.078 rows=1 loops=1)
   ->  Index Scan using random_key on test  (cost=0.00..2884190.16 rows=1000000 width=8) (actual time=10001.129..10001.188 rows=10 loops=1)
 Total runtime: 10001.252 ms
(5 rows)

Is ok.

postgres=# EXPLAIN analyze SELECT *,(select pg_sleep(10)) from test order by _data limit 10 offset 10000;
                                                                  QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=28841.91..28870.76 rows=10 width=8) (actual time=10037.850..10037.871 rows=10 loops=1)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=10001.040..10001.041 rows=1 loops=1)
   ->  Index Scan using random_key on test  (cost=0.00..2884190.16 rows=1000000 width=8) (actual time=10001.094..10036.022 rows=10010 loops=1)
 Total runtime: 10037.919 ms
(5 rows)

Is still ok.


postgres=# EXPLAIN SELECT *,(select pg_sleep(10)) from test order by _data limit 10 offset 100000;
                                QUERY PLAN
--------------------------------------------------------------------------
 Limit  (cost=102723.94..102723.96 rows=10 width=8)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=0)
   ->  Sort  (cost=102473.92..104973.92 rows=1000000 width=8)
         Sort Key: _data
         ->  Seq Scan on test  (cost=0.00..14425.00 rows=1000000 width=8)
(6 rows)

Ooops, there project screwed.

And it is not possible to predict in advance where and when you get hit by that problem.
E.g. all usually fast statements with some arguments become slow as a snail once DB switch from index scan to top node sort.

Only way prevent that is always write all queries way you suggested.

Kind Regards,
Maksym




--
Maxim Boguk
Senior Postgresql DBA.

Phone RU: +7 910 405 4718
Phone AU: +61 45 218 5678

Skype: maxim.boguk
Jabber: maxim.boguk@gmail.com

LinkedIn profile: http://nz.linkedin.com/in/maximboguk
If they can send one man to the moon... why can't they send them all?

МойКруг: http://mboguk.moikrug.ru/
Сила солому ломит, но не все в нашей жизни - солома, да и сила далеко не все.

On 11/25/2011 06:53 AM, Maxim Boguk wrote:
> I understand that position.
> However if assumption: " the definition of ORDER BY --- it happens after
> computing the select list, according to the SQL standard"
> is correct,
> then plans like:
>
> postgres=# EXPLAIN ANALYZE SELECT * from test order by _data limit 10
> offset 1000;
>                                                                QUERY PLAN
>
--------------------------------------------------------------------------------------------------------------------------------------
>   Limit  (cost=2884.19..2913.03 rows=10 width=8) (actual
> time=3.584..3.620 rows=10 loops=1)
>     ->  Index Scan using random_key on test  (cost=0.00..2884190.16
> rows=1000000 width=8) (actual time=0.103..3.354 rows=1010 loops=1)
>   Total runtime: 3.663 ms
> (3 rows)
> should not be used at all.


`LIMIT' and `OFFSET' are explicitly defined to compute only that part of
the SELECT list that is required. If they weren't specifically defined
with that exception then you'd be right.

LIMIT and OFFSET aren't standard anyway, so Pg can define them to mean
whatever is most appropriate. The SQL standard is adding new and (as
usual) painfully clumsily worded features that work like LIMIT and
OFFSET, but I don't know whether they have the same rules about whether
execution of functions can be skipped or not.

> And it is not possible to predict in advance where and when you get hit
> by that problem.

That's the biggest problem with statistics- and heuristics-based query
planners in general, but this does seem to be a particularly difficult case.

Setting a cost on the function call that more accurately reflects how
expensive it is so PostgreSQL will work harder to avoid calling it might
help. See
http://www.postgresql.org/docs/current/static/sql-createfunction.html .

--
Craig Ringer

Change cost for the functions in that case simple ignored by planner/executor.

I think it should be possible always delay execution functions/subqueries unrelated to order by list untill limit/offset were applied (even in the worst case that will provide same performance as today), and no heuristics need at all.


Hm, one more idea:  lets say I call the next sql query -
'SELECT ...,very_log_sure_toasted_field  FROM ... ORDER BY (something but not very_log_toasted_field) LIMIT N'
which will use sort as top node.

Is detoasting of very_log_sure_toasted_field will be performed after applying ORDER BY... LIMIT N or before it?

If  detoasting performed before applying order by/limit, than there exists large class of queries where delayed/lazy detoasting can be huge performance win.
If detoasting performed after applying order by/limit, than the same mechanics can be used to delay subquery/function execution.


PS: Yes I know good response to my complaints: 'patch welcome', but I only started study of postgresql source code and recovering my C coding skills.
Unfortunately, I don't think I will be ready to start hacking planner/executor code in short future (planner/executor is most complicated and easiest to break part of the postgresql code, that  is definitely not newbie task).

--
Maxim Boguk