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

Hello Alvaro and all,

Thank you for the quick reply and I apologize for the delay in responding.

On Fri, Dec 13, 2024 at 7:53 PM Alvaro Herrera <alvherre(at)alvh(dot)no-ip(dot)org> wrote:
>
> BTW I forgot to mention it yesterday, but I was surprised that you
> attached Ashutosh's old patch for planner memory usage reporting.
> This feature is already in EXPLAIN (MEMORY), so you don't need any patch
> to measure memory consumption ... or does your patch add some detail
> that isn't already in the code?

Thank you for pointing this out. I did not add anything beyond the
rebase. I apologize for not noticing this. I have now re-run the same
experiments as in [1] using EXPLAIN (MEMORY).

> > As you said, we have another big problem, which is memory usage. I
> > will focus on the memory usage problem first, as you suggested.
>
> That's great, thanks.

In v29-0008, which is attached to this email, I introduced a new
approach to reduce memory usage during planning. Patch 0002 added
Bitmapset indexes over RestrictInfos. Previously, when retrieving
RestrictInfos, we had to perform intersections or unions of these
Bitmapset indexes, resulting in frequent allocations and copies of
temporary Bitmapsets. This was a significant source of memory
consumption.

The v29-0008 patch adds an iterator mechanism that emulates
bms_next_member(), bms_intersect() and bms_union() operations without
allocating additional Bitmapsets. Instead of constructing new
temporary Bitmapsets for each operation, the iterator performs these
operations on the fly. This approach eliminates the need for temporary
Bitmapsets and reduces memory usage.

I have attached updated experimental results below (tables and figure)
showing the effect of this iterator mechanism on memory usage and
planning time. In summary, the main results are as follows:

* Memory Usage: The v29-0008 change significantly reduces memory
consumption, especially in query B (44.4% reduction).
* Planning Time: While we still see a significant overall improvement
in planning time compared to master, there is some regression observed
in cases with a very large number of tables compared to v28. Notably,
this regression does not occur in smaller size cases such as
'installcheck'.

Table 1: Memory usage (MB)
(n: the number of partitions of each table; PWJ: partition-wise join)
-----------------------------------------------------
Query | n | PWJ | Master | v28 | v29
-----------------------------------------------------
A | 1024 | OFF | 47.818 | 69.000 | 59.156
A | 1024 | ON | 119.969 | 141.150 | 131.307
B | 256 | OFF | 89.429 | 196.217 | 109.088
B | 256 | ON | 4945.597 | 5052.386 | 4965.257
-----------------------------------------------------

---------------------------------------------------------------
Query | n | PWJ | v28 - v29 | 1 - v29 / v28 | v29 - Master
---------------------------------------------------------------
A | 1024 | OFF | 9.844 | 14.3% | 11.338
A | 1024 | ON | 9.844 | 7.0% | 11.338
B | 256 | OFF | 87.129 | 44.4% | 19.659
B | 256 | ON | 87.129 | 1.7% | 19.660
---------------------------------------------------------------

Table 2: Total planning time for installcheck (seconds)
------------------------------------------
Version | Mean | Median | Stddev
------------------------------------------
Master | 0.898575 | 0.897965 | 0.005739
v28 | 0.909598 | 0.906713 | 0.010797
v29 | 0.907552 | 0.906640 | 0.008023
------------------------------------------

Table 3: Speedup for installcheck (higher is better)
--------------------------
Version | Mean | Median
--------------------------
v28 | 98.8% | 99.0%
v29 | 99.0% | 99.0%
--------------------------

Table 4: Planning time for query A (ms)
----------------------------------
n | Master | v28 | v29
----------------------------------
1 | 0.243 | 0.247 | 0.246
2 | 0.263 | 0.269 | 0.269
4 | 0.327 | 0.349 | 0.338
8 | 0.433 | 0.435 | 0.438
16 | 0.617 | 0.615 | 0.608
32 | 1.061 | 1.000 | 0.982
64 | 2.083 | 1.955 | 1.938
128 | 5.774 | 4.225 | 4.209
256 | 17.521 | 10.446 | 10.682
384 | 32.913 | 16.196 | 16.669
512 | 57.379 | 22.274 | 23.392
640 | 92.402 | 28.751 | 30.526
768 | 148.043 | 34.923 | 38.501
896 | 257.313 | 50.124 | 54.165
1024 | 335.586 | 49.742 | 56.389
----------------------------------

Table 5: Speedup of query A (higher is better)
------------------------
n | v28 | v29
------------------------
1 | 98.3% | 98.9%
2 | 98.0% | 98.0%
4 | 93.6% | 96.6%
8 | 99.5% | 98.9%
16 | 100.3% | 101.4%
32 | 106.2% | 108.0%
64 | 106.6% | 107.5%
128 | 136.7% | 137.2%
256 | 167.7% | 164.0%
384 | 203.2% | 197.5%
512 | 257.6% | 245.3%
640 | 321.4% | 302.7%
768 | 423.9% | 384.5%
896 | 513.3% | 475.1%
1024 | 674.6% | 595.1%
------------------------

Table 6: Planning time for query B (ms)
-----------------------------------
n | Master | v28 | v29
-----------------------------------
1 | 11.675 | 11.755 | 11.651
2 | 11.210 | 11.282 | 11.169
4 | 11.745 | 11.677 | 11.556
8 | 12.896 | 12.545 | 12.324
16 | 15.455 | 14.112 | 14.024
32 | 21.642 | 17.531 | 17.585
64 | 44.220 | 26.481 | 26.910
128 | 129.947 | 47.559 | 51.107
256 | 772.431 | 105.115 | 131.829
-----------------------------------

Table 7: Speedup of query B (higher is better)
-----------------------
n | v28 | v29
-----------------------
1 | 99.3% | 100.2%
2 | 99.4% | 100.4%
4 | 100.6% | 101.6%
8 | 102.8% | 104.6%
16 | 109.5% | 110.2%
32 | 123.5% | 123.1%
64 | 167.0% | 164.3%
128 | 273.2% | 254.3%
256 | 734.8% | 585.9%
-----------------------

As shown in the above tables and the attached figure, the iterator
mechanism reduces memory usage (especially for query B, where we
observed a 44.4% reduction). Partition-wise join has no impact on
memory usage in either query A or B.

For planning time, v29 maintains the improvements seen in previous
versions, although there is some regression at large sizes (for
example, about 25.4% slower or 26.7ms more in query B with 256
partitions). For small sizes (a few partitions in the queries A and B,
and 'installcheck'), there is not much difference in planning time
between v28 and v29.

Overall, v29 demonstrates a better balance between planning time and
memory usage. There may still be room for further optimization of the
iterator mechanism, but I believe this is a good step towards
addressing previous concerns. I would appreciate any feedback or
suggestions.

[1] https://www.postgresql.org/message-id/CAJ2pMkZMKwdjYRUGA0%3Dza4SUrgpBJ5_JDYuVeG%3DEsbv1dKSouQ%40mail.gmail.com

--
Best regards,
Yuya Watari