PostgreSQL: Materialize as inner node of Merge Join in query plan

Question

I'm learning PostgreSQL EXPLAIN plan nodes. Currently, I investigate Materialize node. Here is a query I found in the blog post (https://www.depesz.com/2013/05/09/explaining-the-unexplainable-part-3/) and a plan I obtained by myself (structurally it is the same as in the blog post):

set work_mem= '1GB';
explain analyze select * from
(select * from pg_class order by oid) as c
join
(select * from pg_attribute a order by attrelid) as a
on c.oid = a.attrelid;
                                                                              QUERY PLAN                                                                              
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=34.27..333.37 rows=2913 width=504) (actual time=0.823..28.413 rows=2913 loops=1)
   Merge Cond: (pg_class.oid = a.attrelid)
   ->  Sort  (cost=33.99..34.97 rows=395 width=265) (actual time=0.739..1.084 rows=395 loops=1)
         Sort Key: pg_class.oid
         Sort Method: quicksort  Memory: 130kB
         ->  Seq Scan on pg_class  (cost=0.00..16.95 rows=395 width=265) (actual time=0.038..0.285 rows=395 loops=1)
   ->  Materialize  (cost=0.28..257.05 rows=2913 width=239) (actual time=0.060..11.702 rows=2913 loops=1)
         ->  Index Scan using pg_attribute_relid_attnum_index on pg_attribute a  (cost=0.28..220.63 rows=2913 width=239) (actual time=0.050..6.827 rows=2913 loops=1)
 Planning Time: 1.472 ms
 Execution Time: 29.617 ms
(10 rows)

I can't understand the argumentation of the blog author about why Postgres is using Materialize here.

... Merge Join has to match several criteria. Some are obvious (data has to be sorted) and some are not so obvious as are more technical (data has to be scrollable back and forth).

Because of this (these not so obvious criteria) sometimes Pg will have to Materialize the data coming from source (Index Scan in our case) so that it will have all the necessary features when using it.

Why Merge Join needs data to be scrollable back and forth? According to my understanding of Merge Join it iterates forward both data sets simultaneously with two pointers. There is no case in Merge Join algorithm when it goes backward. Anyway, as I understand, Index Scan actually is "scrollable back and forth". I saw "Index Scan Backward" many times. So why Postgres has to materialize it?

I found the confirmation of the blog author opinion in other source, the old book "PostgreSQL: The comprehensive guide to building, programming, and administering PostgreSQL databases", 2nd Edition by Korry Douglas and Susan Douglas:

Materialize will also be used for some merge-join operations. In particular, if the inner input set of a Merge Join operator is not produced by a Seq Scan, an Index Scan, a Sort, or a Materialize operator, the planner/optimizer will insert a Materialize operator into the plan. The reasoning behind this rule is not obviousit has more to do with the capabilities of the other operators than with the performance or the structure of your data. The Merge Join operator is complex; one requirement of Merge Join is that the input sets must be ordered by the join columns. A second requirement is that the inner input set must be repositionable; that is, Merge Join needs to move backward and forward through the input set. Not all ordered operators can move backward and forward. If the inner input set is produced by an operator that is not repositionable, the planner/optimizer will insert a Materialize.

In my case the inner input set is produced by Index Scan, so according to the book, there should be no Materialize node in this plan.

Then I decided to modify the query in such way that planner will not use Materialize, but Merge Join will be still present. This is what I came up with:

set enable_hashjoin = off;
set work_mem= '1GB';
explain analyze select * from
(select * from pg_class order by oid) as c
join
(select * from pg_attribute a) as a
on c.oid = a.attrelid;
                                                                           QUERY PLAN                                                                           
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=34.27..296.96 rows=2913 width=504) (actual time=0.554..10.103 rows=2913 loops=1)
   Merge Cond: (pg_class.oid = a.attrelid)
   ->  Sort  (cost=33.99..34.97 rows=395 width=265) (actual time=0.491..0.645 rows=395 loops=1)
         Sort Key: pg_class.oid
         Sort Method: quicksort  Memory: 130kB
         ->  Seq Scan on pg_class  (cost=0.00..16.95 rows=395 width=265) (actual time=0.021..0.177 rows=395 loops=1)
   ->  Index Scan using pg_attribute_relid_attnum_index on pg_attribute a  (cost=0.28..220.63 rows=2913 width=239) (actual time=0.041..2.296 rows=2913 loops=1)
 Planning Time: 1.188 ms
 Execution Time: 10.731 ms
(9 rows)

I deleted order by attrelid from 2nd subquery and disabled Hash Join forcibly. This plan is the same as previous one except Materialize node. So, I conclude that Merge Join is not the reason why planner use Materialize in previous one. This plan is less expensive, but I suppose the result to be the same.

I will be grateful if you help me to solve some of this puzzles:

1. Does Merge Join really need to be able to iterate inner dataset backward? In which cases? Is the result of Index Scan "backward iterable" in terms of Merge Join requirements?
2. Why Postgres planner uses Materialize in the first plan even though it costs more? What purpose it serves here? Why Postgres planner does not use Materialize in the second plan?

Answer 1

Your analysis is right; the decision to materialize for the inner relation of a merge join is made in final_cost_mergejoin.

PostgreSQL will consider materializing if it is cheaper or the sort for the inner path would spill to disk. This can be disabled by turning off enable_material, so that is a useful test. In our case, disabling that still materializes the index scan, so the materialization must be required.

This source comment describes when that is necessary:

/*
 * Even if materializing doesn't look cheaper, we *must* do it if the
 * inner path is to be used directly (without sorting) and it doesn't
 * support mark/restore.
 *
 * Since the inner side must be ordered, and only Sorts and IndexScans can
 * create order to begin with, and they both support mark/restore, you
 * might think there's no problem --- but you'd be wrong.  Nestloop and
 * merge joins can *preserve* the order of their inputs, so they can be
 * selected as the input of a mergejoin, and they don't support
 * mark/restore at present.
 *
 * We don't test the value of enable_material here, because
 * materialization is required for correctness in this case, and turning
 * it off does not entitle us to deliver an invalid plan.
 */
else if (innersortkeys == NIL &&
         !ExecSupportsMarkRestore(inner_path))
    path->materialize_inner = true;

ExecSupportsMarkRestore does this:

bool
ExecSupportsMarkRestore(Path *pathnode)
{
    /*
     * For consistency with the routines above, we do not examine the nodeTag
     * but rather the pathtype, which is the Plan node type the Path would
     * produce.
     */
    switch (pathnode->pathtype)
    {
        case T_IndexScan:
        case T_IndexOnlyScan:

            /*
             * Not all index types support mark/restore.
             */
            return castNode(IndexPath, pathnode)->indexinfo->amcanmarkpos;
    [...]
        default:
            break;
    }

    return false;
}

Now B-tree indexes do support mark/restore, so what is going on?

The problem is that you are not joining with pg_attribute directly, but with a subquery. Now this is not visible in the final execution plan, but at the stage where the paths are generated, the path type is not T_IndexScan, but T_SubqueryScan, so ExecSupportsMarkRestore concludes that we have to materialize.

You can test by omitting the ORDER BY and disabling hash joins:

SET enable_hashjoin = off;

explain (costs off) select * from
(select * from pg_class order by oid) as c
join
(select * from pg_attribute a) as a
on c.oid = a.attrelid;

                                QUERY PLAN                                
══════════════════════════════════════════════════════════════════════════
 Merge Join
   Merge Cond: (pg_class.oid = a.attrelid)
   ->  Sort
         Sort Key: pg_class.oid
         ->  Seq Scan on pg_class
   ->  Index Scan using pg_attribute_relid_attnum_index on pg_attribute a
(6 rows)

Voila – no Materialize.

This could be optimized, but I don't know the code well enough to say if it is feasible.

Answer 2

Why Merge Join needs data to be scrollable back and forth? According to my understanding of Merge Join it iterates forward both data sets simultaneously with two pointers. There is no case in Merge Join algorithm when it goes backward.

So the first node produces a 'cat'. The 2nd node scans (ignoring results) until it finds a 'cat' or greater, produces results until it sees a >'cat', then pauses. Now the first node produce another 'cat'. Now, what do you think the 2nd node should do?

In my case the inner input set is produced by Index Scan, so according to the book, there should be no Materialize node in this plan.

What if it just thinks using the materialize will be faster?(Well, that is not the case here as Laurenz pointed out)