Merge join doesn't seem to break early when I (and planner) think itshould - 10.4 - Mailing list pgsql-performance

Query plan quick link: https://explain.depesz.com/s/JVxn

Version: PostgreSQL 10.4 on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609, 64-bit

tbl: ~780 million rows, bigint primary key (keytbl), col1 is smallint and there is an index on (col1, col2)

tmp_tbl: ~10 million rows; columns are identical to tbl, no indices or primary key

Both tables are analyzed.

I'm doing an update of tbl from tmp_tbl joining on the primary key column of tbl.  The planner picks a merge join which takes about 4 hours. If I force it to use a hash join instead (set local enable_mergejoin=false) it takes about 2.5 minutes (see https://explain.depesz.com/s/vtLe for resulting plan, it's my current workaround).  The index scan done for the merge join below [*] is what eats  up the time and planner knows it's expensive [*], but I think it expects it to stop early [**], however it appears to index scan the entire table based on the rows removed by the filter [***] and the time taken.  I don't think the planner's wrong here, the merge join should break early, the max value of keytbl in tmp_tbl is less than all but a small portion of tbl (see **** below). So I think it should have to only go ~12.5 million rows into the index scan before stopping. Continued below...

explain analyze:

  max         3940649685073901
select count(*) from tbl where keytbl <= 3940649685073901;
  count       12454354 [****]

So far I've been unable to create a smaller / toy example that exhibits the same behavior. Some things that may be unusual about the situation: keytbl is bigint and the values are large (all are > 2^48) and sparse/dense (big chunks where the id advances by 1 separated by large (> 2^48) regions with no rows), the top 200k or so rows of tmp_table by keytbl don't have a corresponding row in tbl, and this is a bit of an older dot release (10.4).  I have a workaround (disabling merge join for the query) so I'm mostly trying to figure out what's going on and if I'm understanding the situation correctly.

It's interesting that even if it worked as expected, the merge join plan seems a lot riskier in that if the analyze didn't catch a single large outlier value of keytbl in tmp_tbl or a row with a large value for keytbl was inserted into tmp_tbl since the last analyze it could be forced to walk the entire index of the tbl (which based on the filter count looks like it involves touching each row of this large table for the filter even if it doesn't have a corresponding row to merge to).

Additional info:

Table schema (for tbl and tmp_tbl)

 explain analyze verbose 

      UPDATE "tbl" t
         SET xxxxx
        FROM "tmp_tbl" tt
       WHERE t."keytbl" = tt."keytbl" AND t.col1 IN (13,14) AND (xxx)