Re: partitioning performance tests after recent patches - Mailing list pgsql-hackers

On Mon, 15 Apr 2019 at 19:33, Floris Van Nee <florisvannee@optiver.com> wrote:
> Here's the output of explain/analyze for HEAD. At run-time, technically all partitions could be pruned directly.
However,one partition remains in the output of explain/analyze because of other difficulties with removing all of them,
ifI remember correctly? Still, that partition is never executed.  The only difference I can see is the Limit node on
top,as well as apparently another  partition appearing in the analyze output (4096_4096, last partition, remains in the
firstplan. 4096_1, the first partition, remains the second plan). 
>
> -- select_now.sql
> explain(analyze, verbose, buffers on)
> select * from :tbl where a='abc' and updated_at between now() and now()+interval '1d';
>
> Append  (cost=0.16..8949.61 rows=4096 width=112) (actual time=0.000..0.000 rows=0 loops=1)
>   Subplans Removed: 4095
>   ->  Index Scan using p4096_4096_a_updated_at_idx on public.p4096_4096  (cost=0.16..2.18 rows=1 width=112) (never
executed)
>         Output: p4096_4096.a, p4096_4096.b, p4096_4096.c, p4096_4096.d, p4096_4096.updated_at
>         Index Cond: ((p4096_4096.a = 'abc'::text) AND (p4096_4096.updated_at >= now()) AND (p4096_4096.updated_at <=
(now()+ '1 day'::interval))) 
> Planning Time: 237.603 ms
> Execution Time: 0.475 ms
>
> -- select_now_limit.sql
> explain(analyze, verbose, buffers on)
> select * from :tbl where a='abc' and updated_at between now() and now()+interval '1d'
> order by a, updated_at desc limit 1;
>
> Limit  (cost=645.53..647.56 rows=1 width=112) (actual time=0.002..0.002 rows=0 loops=1)
>   Output: p4096_1.a, p4096_1.b, p4096_1.c, p4096_1.d, p4096_1.updated_at
>   ->  Append  (cost=645.53..8949.61 rows=4096 width=112) (actual time=0.000..0.000 rows=0 loops=1)
>         Subplans Removed: 4095
>         ->  Index Scan using p4096_1_a_updated_at_idx on public.p4096_1  (cost=0.57..2.03 rows=1 width=54) (never
executed)
>               Output: p4096_1.a, p4096_1.b, p4096_1.c, p4096_1.d, p4096_1.updated_at
>               Index Cond: ((p4096_1.a = 'abc'::text) AND (p4096_1.updated_at >= now()) AND (p4096_1.updated_at <=
(now()+ '1 day'::interval))) 
> Planning Time: 3897.687 ms
> Execution Time: 0.491 ms

I had a look at this and it's due to get_eclass_for_sort_expr() having
a hard time due to the EquivalenceClass having so many members. This
must be done for each partition, so search time is quadratic based on
the number of partitions. We only hit this in the 2nd plan due to
build_index_paths() finding that there are useful pathkeys from
query_pathkeys.  Of course, this does not happen for the first query
since it has no ORDER BY clause.

Tom and I were doing a bit of work in [1] to speed up cases when there
are many EquivalenceClasses by storing a Bitmapset for each RelOptInfo
to mark the indexes of each eq_classes they have members in.  This
does not really help this case since we're slow due to lots of members
rather than lots of classes, but perhaps something similar can be done
to allow members to be found more quickly.  I'm not sure exactly how
that can be done without having something like an array of Lists
indexed by relid in each EquivalenceClasses. That does not sound great
from a memory consumption point of view.  Maybe having
EquivalenceMember in some data structure that we don't have to perform
a linear search on would be a better fix.  Although, we don't
currently have any means to hash or binary search for note types
though. Perhaps its time we did.

[1] https://commitfest.postgresql.org/23/1984/

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services