Advanced partition matching for partition-wise join

Earlier I had written a blog about partition-wise join in PostgreSQL. In that blog I had talked about an advanced partition matching technique which will allow partition-wise join to be used in more cases. In this blog we will discuss this technique in detail. I will suggest to read my blog on basic partition-wise join again to get familiar with the technique.

Basic partition matching technique allows a join between two partitioned tables to be performed using partition-wise join technique if the two partitioned tables had exactly same partitions (more precisely exactly matching partition bounds). For example consider two partitioned tables prt1 and prt2

\d+ prt1
... [output clipped]
Partition key: RANGE (a)
Partitions: prt1_p1 FOR VALUES FROM (0) TO (5000),
            prt1_p2 FOR VALUES FROM (5000) TO (15000),
            prt1_p3 FOR VALUES FROM (15000) TO (30000)

and

\d+ prt2

... [ output clipped ]

Partition key: RANGE (b)

Partitions: prt2_p1 FOR VALUES FROM (0) TO (5000),

            prt2_p2 FOR VALUES FROM (5000) TO (15000),

            prt2_p3 FOR VALUES FROM (15000) TO (30000)

A join between prt1 and prt2 is executed as join between matching partitions i.e. prt1_p1 joins prt2_p1, prt1_p2 joins prt2_p2 and prt1_p3 joins prt2_p3. This has many advantages as discussed in my previous blog.

But basic partition matching can not join two partition tables with different partitions (more precisely different partition bounds). For example, in the above case if prt1 an extra partition prt1_p4 FOR VALUES FROM (30000) TO (50000), a join between prt1 and prt2 would not use partition-wise join. Many applications use partitions to segregate actively used and stale data, a technique I discussed in my another blog. The stale data is eventually removed by dropping partitions. New partitions are created to accommodate fresh data. Let's say the partition scheme of two such tables is such that they usually have matching partitions. But when an active partition gets added to one of these tables or a stale one gets deleted, they will have mismatched partitions for a small duration. We don't want a join hitting the database during this small duration to perform bad since it can not use partition-wise join. Advanced partition matching algorithm helps here.

Advanced partition matching algorithm

Advanced partition matching is very much similar to the merge join algorithm. It takes the sorted partition bounds and finds matching partitions by comparing the bounds from both the tables in their sorted order. Any two partitions, one from either partitioned table, whose bounds match exactly or overlap are considered to be joining partners since they may contain rows that join. Continuing with the above example:

\d+ prt1

... [output clipped]

Partition key: RANGE (a)

Partitions: prt1_p1 FOR VALUES FROM (0) TO (5000),

            prt1_p2 FOR VALUES FROM (5000) TO (15000),

            prt1_p3 FOR VALUES FROM (15000) TO (30000)

and

\d+ prt2

... [ output clipped ]

Partition key: RANGE (b)

Partitions: prt2_p1 FOR VALUES FROM (0) TO (5000),

            prt2_p2 FOR VALUES FROM (5000) TO (15000),

            prt2_p3 FOR VALUES FROM (15000) TO (30000),

            prt1_p4 FOR VALUES FROM (30000) TO (50000)

Similar to the basic partition matching algorithm this will join prt1_p1 and prt2_p1, prt1_p2 and prt2_p2, and prt1_p3 and prt2_p3. But unlike basic partition matching it will also know that prt1_p4 does not have any join partner in prt1. Thus if the join between prt1 and prt2 is INNER join or when prt2 is INNER relation of join, the join will contain only three joins leaving prt2_p4 aside. In PostgreSQL, a join where prt2 is OUTER relation, we won't be able to use partition-wise join even if We will come back to this again when we will discuss outer joins further.

This is simple right, but consider another example of listed partitioned tables

\d+ plt1_adv

Partition key: LIST (c)

Partitions: plt1_adv_p1 FOR VALUES IN ('0001', '0003'),

            plt1_adv_p2 FOR VALUES IN ('0004', '0006'),

            plt1_adv_p3 FOR VALUES IN ('0008', '0009')

and

\d+ plt2_adv

Partition key: LIST (c)

Partitions: plt2_adv_p1 FOR VALUES IN ('0002', '0003'),

            plt2_adv_p2 FOR VALUES IN ('0004', '0006'),

            plt2_adv_p3 FOR VALUES IN ('0007', '0009')

Observe that there are exactly three partitions in both the relations but lists corresponding plt1_adv_p2 match exactly that of plt2_adv_p2 but other two partitions do not have exactly matching lists. Advanced partition matching algorithm helps to determine that plt1_adv_p1 and plt2_adv_p1 have overlapping lists and their lists do not overlap with any other partition from the other relation. Similarly for plt1_adv_p3 and plt2_adv_p3. Thus it allows join between plt1_adv and plt2_adv to be executed as partition wise join by joining their matching partitions. The algorithm can find matching partitions in even more complex partition bound sets.

The problem with outer joins

Outer joins pose a particular problem in PostgreSQL world. Consider again the example of join between prt2 LEFT JOIN prt1. prt2_p4 does not have a joining partner in prt1 and yet the rows in that partition will be part of the join since it is an outer relation, albeit with the columns from prt1 all "null"ed. Usually in PostgreSQL when the INNER side is empty, it's represented by a "dummy" relation which emits no rows but still knows the schema of that relation. Without partition-wise join a "concrete" relation which has some presence in the original query turns dummy and thus planner has "something" to join the outer relation with. So PostgreSQL's planner doesn't have to do anything extra when such outer joins occur. But when there is no matching inner partition for an outer partition e.g. prt2_p4, there is "no entity" which can represent the "dummy" inner side of that outer join. PostgreSQL does not have a way right now to induce such "dummy" relations during planning right now. But that's not required. Ideally such a join with empty inner only requires schema of the inner relation and not an entire relation itself. Once we build support to execute such a join with a solid outer relation and schema of inner relation, we will be able to tackle partition-wise join where there are no matching partitions on inner side. Hopefully we will solve that problem some time soon.

When there is no matching partition on the outer side of the join, the inner partition does not contribute to the result of join and can be just ignored. So partition-wise joins where there are no matching partitions on the inner side are not a problem at all.

Multiple matching partitions

When the partitioned tables are such that multiple partitions from one side match one partition or more partitions on the other side, partition-wise join simply bails out since there is no way to induce an "Append" relation during planning time which represents two or more partitions together. Hopefully we will remove that limitation as well sometime.

Curious case of hash partitioned tables

It doesn't make much sense to use it for a hash partitioned table since usually partitions of two hash partitioned table using same modulo always match. When the modulo is different, the data from one a given partition of one table can find its join partners in all the partitions of the other, thus rendering partition-wise join ineffective.

Even with all these limitation, what we have today is a very useful solution which serves most of the practical cases. Needless to say that this feature works seemlessly with FDW join push down to adding to sharding capabilities that PostgreSQL already has!

Containing bloat with partitions

PGConf India 2018 attracted a large number of PostgreSQL users and developers. I talked about "Query optimization techniques for partitioned tables" (slides). Last year, I had held an introductory talk about PostgreSQL's declarative partitioning support (slides). Many conference participants shared their perspective on partitioning with me. One particular query got me experimenting a bit.

The user had a huge table, almost 1TB in size, with one of the columns recording the data-creation time. Applications added MBs of new data daily and updated only the recent data. The old data was retained in the table for reporting and compliance purposes. The updates bloated the table, autovacuum wasn't clearing the bloat efficiently. Manual vacuum was out of scope as that would have locked the table for much longer. As a result queries were slow, and performance degraded day by day. (Read more about bloats and vacuum here and here.) The user was interested in knowing if partitioning would help.

Hot and Cold partitioning

The concept of hot and cold partitioning isn't new. The idea is to separate data being accessed and modified frequently (Hot data) from the data which is accessed and modified rarely (Cold data). In the above case, that can be achieved by partitioning the data by the creation timestamp. The partitions should be sized such that the updates and inserts access only a handful Hot partitions (ideally at most two). The Cold partitions containing the stale data would remain almost unchanged. Since the updates are taking place in the Hot partitions, those get bloated, but their sizes are much smaller than the whole table. Vacuuming those doesn't take as much time as the whole table. Once they become Cold, they hardly need any Vacuuming. Thus containing the bloat effectively.

In PostgreSQL autovacuum, if enabled on the given table, runs its job when the number of inserted, deleted or updated rows are above certain thresholds (See details). Since all the action happens in the Hot partitions, only those partitions can have their counts rise beyond the threshold. Those counts are hardly expected to change for Cold partitions (or once they become cold, if they were hot in the past). Thus autovacuum too automatically starts working on only the Hot partitions instead of entire table. This isn't the case with an unpartitioned table, for which autovacuum always runs on the entire table; it possibly never completes its job because of sheer size of the table and not necessarily because of the rate at which bloat is created.

Experiment

That's all theory, but I ventured to see how effective this could be. I created a table with two partitions, one Hot partition, representing Hot data and one Cold partition, representing Cold data. (Note: all the code below serves only as example and should be used with necessary caution.).

create table part (a int, b int, c varchar, d varchar, e varchar) partition by range(a);

create table part_active partition of part for values from (990000) to (1000001);

create table part_default partition of part default;

I then inserted one million rows in this table, each row with distinct value for column a from 1 to 1000000. This means that the partition "part_active" which represents the Hot data (or latest data, if a is interpreted as some kind of timestamp) contains 1% of the total data in table "part".

For comparison, I also created an unpartitioned table "upart" with similar schema and populated it with the same data.

create table upart (a int, b int, c varchar, d varchar, e varchar);

I disabled autovacuum on these tables to create bloat using "with (autovacuum_enabled = 'false')", but that's only for the experimentation. In production or test environment, one should set this option as per the requirements of the setup.

Then I ran commands to update each of the rows with a between 990000 and 1000000 thrice. In the partitioned table this updated the rows in partition part_active, the Hot partition. Since autovacuum is disabled, it would not remove the old versions of the tuples. So, we see the statistics as

select n_tup_upd, n_tup_hot_upd, n_dead_tup, n_live_tup from pg_stat_user_tables where relid = 'upart'::regclass;
 n_tup_upd | n_tup_hot_upd | n_dead_tup | n_live_tup 
-----------+---------------+------------+------------
     30003 |            23 |      30003 |    1000000
(1 row)

select n_tup_upd, n_tup_hot_upd, n_dead_tup, n_live_tup from pg_stat_user_tables where relid = 'part_active'::regclass;
 n_tup_upd | n_tup_hot_upd | n_dead_tup | n_live_tup 
-----------+---------------+------------+------------
     30003 |            23 |      30003 |      10001
(1 row)

select n_tup_upd, n_tup_hot_upd, n_dead_tup, n_live_tup from pg_stat_user_tables where relid = 'part_default'::regclass;
 n_tup_upd | n_tup_hot_upd | n_dead_tup | n_live_tup 
-----------+---------------+------------+------------
         0 |             0 |          0 |     989999

(1 row)

As you will see that the unpartitioned table and the Hot partition both have same number of dead tuples. The Cold partition doesn't have any dead tuples since no row in that partition was updated. At this point the sizes of unpartitioned table and the Hot partition are.

select pg_size_pretty(pg_relation_size('upart'::regclass));
 pg_size_pretty 
----------------
 326 MB

(1 row)

select pg_size_pretty(pg_relation_size('part_active'::regclass));

 pg_size_pretty 

----------------

 13 MB

(1 row)

The Hot partition which contains only 1% of the rows of the unpartitioned table has its size much larger than that proportion. That's because all the bloat in partitioned table is concentrated in that partition.

Now, let's try to run VACUUM ANALYZE on these tables to remove the bloat and update statistics.

\timing on

vacuum full analyze upart;

Time: 4663.576 ms (00:04.664)

\timing off

\timing on

vacuum full analyze part_active;

Time: 53.314 ms

\timing off

After vacuuming the sizes of the unpartitioned table and the Hot partition are

select pg_size_pretty(pg_relation_size('upart'::regclass));

 pg_size_pretty 

----------------

 326 MB

(1 row)

select pg_size_pretty(pg_relation_size('part_active'::regclass));

 pg_size_pretty 

----------------

 3336 kB

(1 row)

Now the sizes of the table are in expected proportion with the bloat removed.

Notice that the time required for vacuuming Hot partition is 80 times lesser than the time required for vacuuming the unpartitioned table. Effectively, the bloat in entire partitioned table is cleared since partitioning has restricted the bloat only to the Hot partition. Since vacuum is now taking much lesser time it's possible to schedule it within the down-time and the time for which the table remains locked is also within the reasonable limits. This isn't magic (neither is partitioning a spell simple to cast). Observe that the reduction in time is inline with the proportion of Hot data in the total data. When vacuum is run on the unpartitioned table, it has to scan the whole unpartitioned table. But in case of a partitioned table, it needs to scan only the Hot partition which is much smaller than the unpartitioned table and thus takes much lesser time.

The customer had 1TB of data and the experiment above runs with only MBs of data. But that's all my laptop could afford and that's all time permitted me. But you got the idea. EnterpriseDB is implementing zero bloat heap which avoids bloat to start with, but it's going to take some time. Meanwhile you may try this option, but experiment with real-sized data.

Word of caution

Declarative partitioning is a new feature in PostgreSQL 10. Not all the functionalities like, foreign key, unique constraints, primary key that work with a regular table work with a partitioned table. Many of them will be part of PostgreSQL 11, but it may take few more releases to cover all the ground. It's always advisable to use the latest version of PostgreSQL and test the applications, for performance and correctness, before deploying in production.