Re: [PoC] Reducing planning time when tables have many partitions

Hello,

On Thu, Jul 28, 2022 at 6:35 AM David Rowley <dgrowleyml@gmail.com> wrote:
> I've attached a very half-done patch that might help you get started
> on this.

Thank you so much for creating the patch. I have implemented your
approach and attached a new version of the patch to this email.

If you have already applied David's patch, please start the 'git am'
command from 0002-Fix-bugs.patch. All regression tests passed with
this patch on my environment.

1. Optimizations

The new optimization techniques utilizing Bitmapsets are implemented
as the following functions in src/include/optimizer/paths.h.

* get_eclass_members_indexes_for_relids()
* get_eclass_members_indexes_for_not_children()
* get_eclass_members_indexes_for_relids_or_not_children()
* get_eclass_members_indexes_for_subsets_of_relids()
* get_eclass_members_indexes_for_subsets_of_relids_or_not_children()
// I think the names of these functions need to be reconsidered.

These functions intersect ec->ec_member_indexes and some Bitmapset and
return indexes of EquivalenceMembers that we want to get.

The implementation of the first three functions listed above is
simple. However, the rest functions regarding the bms_is_subset()
condition are a bit more complicated. I have optimized this case based
on Tom's idea. The detailed steps are as follows.

I.  Intersect ec->ec_member_indexes and the Bitmapset in RelOptInfo.
This intersection set is a candidate for the EquivalenceMembers to be
retrieved.
II. Remove from the candidate set the members that do not satisfy the
bms_is_subset().

Optimization for EquivalenceMembers with a constant value is one of
the future works.

2. Experimental Results

I conducted an experiment by using the original query, which is
attached to this email. You can reproduce this experiment by the
following commands.

=====
psql -f create-tables.sql
psql -f query.sql
=====

The following table and the attached figure describe the experimental result.

Planning time of "query.sql" (n = the number of partitions)
----------------------------------------------------------------
    n | Master (ms) | Patched (ms) | Speedup (%) | Speedup (ms)
----------------------------------------------------------------
    1 |       0.809 |        0.760 |       6.09% |        0.049
    2 |       0.799 |        0.811 |      -1.53% |       -0.012
    4 |       1.022 |        0.989 |       3.20% |        0.033
    8 |       1.357 |        1.325 |       2.32% |        0.032
   16 |       2.149 |        2.026 |       5.69% |        0.122
   32 |       4.357 |        3.925 |       9.91% |        0.432
   64 |       9.543 |        7.543 |      20.96% |        2.000
  128 |      27.195 |       15.823 |      41.82% |       11.372
  256 |     130.207 |       52.664 |      59.55% |       77.542
  384 |     330.642 |      112.324 |      66.03% |      218.318
  512 |     632.009 |      197.957 |      68.68% |      434.052
  640 |    1057.193 |      306.861 |      70.97% |      750.333
  768 |    1709.914 |      463.628 |      72.89% |     1246.287
  896 |    2531.685 |      738.827 |      70.82% |     1792.858
 1024 |    3516.592 |      858.211 |      75.60% |     2658.381
----------------------------------------------------------------

-------------------------------------------------------
    n | Stddev of Master (ms) | Stddev of Patched (ms)
-------------------------------------------------------
    1 |                 0.085 |                  0.091
    2 |                 0.061 |                  0.091
    4 |                 0.153 |                  0.118
    8 |                 0.203 |                  0.107
   16 |                 0.150 |                  0.153
   32 |                 0.313 |                  0.242
   64 |                 0.411 |                  0.531
  128 |                 1.263 |                  1.109
  256 |                 5.592 |                  4.714
  384 |                17.423 |                  6.625
  512 |                20.172 |                  7.188
  640 |                40.964 |                 26.246
  768 |                61.924 |                 31.741
  896 |                66.481 |                 27.819
 1024 |                80.950 |                 49.162
-------------------------------------------------------

The speed up with the new patch was up to 75.6% and 2.7 seconds. The
patch achieved a 21.0% improvement even with 64 partitions, which is a
realistic size. We can conclude that this optimization is very
effective in workloads with highly partitioned tables.

Performance degradation occurred only when the number of partitions
was 2, and its degree was 1.53% or 12 microseconds. This degradation
is the difference between the average planning times of 10000 runs.
Their standard deviations far exceed the difference in averages. It is
unclear whether this degradation is an error.

=====

I'm looking forward to your comments.

-- 
Best regards,
Yuya Watari