[HACKERS] nested loop semijoin estimates

[Tomas Vondra]

Hi,

while looking at this post from pgsql-performance about plan changes

http://www.postgresql.org/message-id/flat/20150529095117.gb15...@hjp.at




    if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
    {
        double      outer_matched_rows;
        Selectivity inner_scan_frac;

        run_cost += inner_run_cost;

        outer_matched_rows
            = rint(outer_path_rows * semifactors->outer_match_frac);
        inner_scan_frac = 2.0 / (semifactors->match_count + 1.0);

        if (outer_matched_rows > 1)
            run_cost += (outer_matched_rows - 1)
                        * inner_rescan_run_cost * inner_scan_frac;

        ...
    }


I wonder whether the

        run_cost += inner_run_cost;



        run_cost += inner_run_cost * inner_scan_frac;









With the current code, the planner produces a plan like this:

                             QUERY PLAN
-----------------------------------------------------------------------
 Nested Loop  (cost=169627.96..169636.03 rows=1 width=74)
   Join Filter: ((t.term)::text = (f.berechnungsart)::text)
   ->  Index Scan using term_facttablename_columnname_idx on term t
       (cost=0.55..8.57 rows=1 width=74)
         Index Cond: (((facttablename)::text =
             'facttable_stat_fta4'::text) AND ((columnname)::text =
             'berechnungsart'::text))
   ->  HashAggregate  (cost=169627.41..169627.43 rows=2 width=2)
         Group Key: (f.berechnungsart)::text
         ->  Seq Scan on facttable_stat_fta4 f
             (cost=0.00..145274.93 rows=9740993 width=2)



With the run_cost change, I do get this plan:

                            QUERY PLAN
-----------------------------------------------------------------------
 Nested Loop Semi Join  (cost=111615.33..111623.42 rows=1 width=74)
   ->  Index Scan using term_facttablename_columnname_idx on term t
         (cost=0.55..8.57 rows=1 width=74)
         Index Cond: (((facttablename)::text =
              'facttable_stat_fta4'::text) AND ((columnname)::text =
               'berechnungsart'::text))
   ->  Bitmap Heap Scan on facttable_stat_fta4 f
         (cost=111614.78..220360.98 rows=4870496 width=2)
         Recheck Cond: ((berechnungsart)::text = (t.term)::text)
         ->  Bitmap Index Scan on facttable_stat_fta4_berechnungsart_idx
               (cost=0.00..110397.15 rows=4870496 width=0)
               Index Cond: ((berechnungsart)::text = (t.term)::text)





                             QUERY PLAN
------------------------------------------------------------------------
 Nested Loop Semi Join  (cost=0.99..9.20 rows=1 width=74)
   ->  Index Scan using term_facttablename_columnname_idx on term t
       (cost=0.55..8.57 rows=1 width=74)
         Index Cond: (((facttablename)::text =
                    'facttable_stat_fta4'::text) AND
                    ((columnname)::text = 'berechnungsart'::text))
   ->  Index Only Scan using facttable_stat_fta4_berechnungsart_idx
          on facttable_stat_fta4 f
         (cost=0.43..310525.02 rows=4870496 width=2)
         Index Cond: (berechnungsart = (t.term)::text)



regards

--
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

I noticed that initial_cost_nestloop() does this in (9.1, mentioned in the pgsql-performance post uses the same logic): is actually correct, because this pretty much means we assume scanning the whole inner relation (once). Wouldn't something like this be more appropriate? i.e. only counting the proportional part of the inner run cost, just like we do for the rescans (i.e. until the first match)? Imagine a simple EXISTS() query that gets turned into a semijoin, with an inner index scan. The current code pretty much means we'll scan the whole result, even though we only really need a single matching query (to confirm the EXISTS clause). For cheap index scans (e.g. using a PK) this does not make much difference, but the example posted to pgsql-performance results in index scans matching ~50% of the table, which makes the whole index scan quite expensive, and much higher than the rescan cost (multiplied by inner_scan_frac). While investigating the pgsql-performance report I've prepared the attached testcase, producing similar data set (attached). So let's see how the code change impacts plan choice. which seems slightly inefficient, as ~50% of the facttable_stat_fta4 matches the condition (so building the whole hash is a waste of time). Also notice this is a regular join, not a semijoin - that seems to confirm the planner does not realize the cost difference, believes both plans (regular and semijoin) are equally expensive and simply uses the first one. and this runs about ~3x faster than the original plan (700ms vs. 2000ms), at least when using the testcase dataset on my laptop. This however is not the whole story, because after disabling the bitmap index scan, I do get this plan, running in ~1ms (so ~700x faster than the bitmap index scan): Notice the cost - it's way lover than the previous plan (9.2 vs ~111k), yet this plan was not chosen. So either the change broke something (e.g. by violating some optimizer assumption), or maybe there's a bug somewhere else ...

testcase.sql
Description: application/sql

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers