title: Sequential Scan Used Over Index Scan on More Restrictive Predicate
body: <p><code>select version()</code>: <code>PostgreSQL 9.6.2 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.2 20140120 (Red Hat 4.8.2-16), 64-bit</code></p>
  
  <p>I have two tables:</p>
  
  <pre><code>create table if not exists cover.covering_s2_cell_ids (
    covering_id int references cover.coverings(id) on delete cascade,
    s2_cell_id bigint,
    s2_cell_min bigint,
    s2_cell_max bigint,
    primary key (covering_id, s2_cell_id)
  );
  
  
  create table if not exists tiles.tileset_segment_counts (
    tileset_id int references tiles.tilesets(id) on delete cascade,
    s2_cell_id bigint not null,
    segments jsonb not null,
    num int not null,
    primary key (tileset_id, s2_cell_id)
  );
  </code></pre>
  
  <p>Additionally, I have another index on <code>tiles.tileset_segment_counts(tileset_id, s2_cell_id, num)</code>. The query I would like to run is</p>
  
  <pre><code>SELECT tsc.s2_cell_id, tsc.segments
  from cover.covering_s2_cell_ids cs
  JOIN tiles.tileset_segment_counts tsc on tsc.s2_cell_id BETWEEN cs.s2_cell_min AND cs.s2_cell_max
  WHERE cs.covering_id = 2
    and tsc.tileset_id = 1
    and num &gt; 100
  </code></pre>
  
  <p>This runs relatively quickly and seems to be doing what I expect, leveraging the triple index to filter rows from <code>tiles.tileset_segment_counts</code>:</p>
  
  <pre><code>Nested Loop  (cost=0.71..1285012.81 rows=7919778 width=544) (actual time=0.039..20.139 rows=19305 loops=1)
    Output: tsc.s2_cell_id, tsc.segments
    Buffers: shared hit=5150
    -&gt;  Index Scan using covering_s2_cell_ids_covering_id_idx on cover.covering_s2_cell_ids cs  (cost=0.29..12.04 rows=157 width=16) (actual time=0.018..0.088 rows=157 loops=1)
          Output: cs.covering_id, cs.s2_cell_id, cs.s2_cell_min, cs.s2_cell_max
          Index Cond: (cs.covering_id = 2)
          Buffers: shared hit=4
    -&gt;  Index Scan using tileset_segment_counts_tileset_id_s2_cell_id_num_idx on tiles.tileset_segment_counts tsc  (cost=0.43..7680.28 rows=50444 width=544) (actual time=0.006..0.075 rows=123 loops=157)
          Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
          Index Cond: ((tsc.tileset_id = 1) AND (tsc.s2_cell_id &gt;= cs.s2_cell_min) AND (tsc.s2_cell_id &lt;= cs.s2_cell_max) AND (tsc.num &gt; 100))
          Buffers: shared hit=5146
  Planning time: 0.156 ms
  Execution time: 23.760 ms
  </code></pre>
  
  <p>The problem occurs if I increase <code>num</code> to be a larger value. Let's say I use greater than 1000, which is a more restrictive query on that table, the query planner opts to use a sequential scan and filter of the large <code>tiles.tileset_segment_counts</code> table instead:</p>
  
  <pre><code>Nested Loop  (cost=0.29..405447.61 rows=1624688 width=1111) (actual time=4656.731..6367.624 rows=6185 loops=1)
    Output: tsc.s2_cell_id, tsc.segments
    Join Filter: ((tsc.s2_cell_id &gt;= cs.s2_cell_min) AND (tsc.s2_cell_id &lt;= cs.s2_cell_max))
    Rows Removed by Join Filter: 14430122
    Buffers: shared hit=142735
    -&gt;  Seq Scan on tiles.tileset_segment_counts tsc  (cost=0.00..149546.77 rows=93135 width=1111) (actual time=0.119..214.902 rows=91951 loops=1)
          Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
          Filter: ((tsc.num &gt; 1000) AND (tsc.tileset_id = 1))
          Rows Removed by Filter: 362013
          Buffers: shared hit=142731
    -&gt;  Materialize  (cost=0.29..12.82 rows=157 width=16) (actual time=0.000..0.030 rows=157 loops=91951)
          Output: cs.s2_cell_min, cs.s2_cell_max
          Buffers: shared hit=4
          -&gt;  Index Scan using covering_s2_cell_ids_covering_id_idx on cover.covering_s2_cell_ids cs  (cost=0.29..12.04 rows=157 width=16) (actual time=0.015..0.052 rows=157 loops=1)
                Output: cs.s2_cell_min, cs.s2_cell_max
                Index Cond: (cs.covering_id = 2)
                Buffers: shared hit=4
  Planning time: 0.152 ms
  Execution time: 6368.822 ms
  </code></pre>
  
  <p>My thought is that the planner should be even more likely to want to use an index scan on tileset_segment_counts in this case, because it is returning even less rows. I've made sure I vacuum analyzed the table after creating the index. Any thoughts would be greatly appreciated. I don't understand why having this more restrictive predicate would push the planner towards using the Join Filter + sequential scan over the index condition.</p>
  
  <p>-- EDIT --
  With <code>enable_seqscan</code> and <code>enable_material</code> set to <code>OFF</code>, the query uses either an index scan or a bitmap heap scan and runs fast (below for num > 1000):</p>
  
  <pre><code>Nested Loop  (cost=1010.05..744541.04 rows=1624688 width=1111) (actual time=0.048..8.272 rows=6185 loops=1)
    Output: tsc.s2_cell_id, tsc.segments
    Buffers: shared hit=2353
    -&gt;  Index Scan using covering_s2_cell_ids_covering_id_idx on cover.covering_s2_cell_ids cs  (cost=0.29..12.04 rows=157 width=16) (actual time=0.018..0.076 rows=157 loops=1)
          Output: cs.covering_id, cs.s2_cell_id, cs.s2_cell_min, cs.s2_cell_max
          Index Cond: (cs.covering_id = 2)
          Buffers: shared hit=4
    -&gt;  Bitmap Heap Scan on tiles.tileset_segment_counts tsc  (cost=1009.77..4638.74 rows=10348 width=1111) (actual time=0.013..0.035 rows=39 loops=157)
          Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
          Recheck Cond: ((tsc.tileset_id = 1) AND (tsc.s2_cell_id &gt;= cs.s2_cell_min) AND (tsc.s2_cell_id &lt;= cs.s2_cell_max) AND (tsc.num &gt; 1000))
          Heap Blocks: exact=1688
          Buffers: shared hit=2349
          -&gt;  Bitmap Index Scan on tileset_segment_counts_tileset_id_s2_cell_id_num_idx  (cost=0.00..1007.18 rows=10348 width=0) (actual time=0.011..0.011 rows=39 loops=157)
                Index Cond: ((tsc.tileset_id = 1) AND (tsc.s2_cell_id &gt;= cs.s2_cell_min) AND (tsc.s2_cell_id &lt;= cs.s2_cell_max) AND (tsc.num &gt; 1000))
                Buffers: shared hit=661
  Planning time: 0.156 ms
  Execution time: 9.492 ms
  </code></pre>
  
  <p>The same is true if I only set <code>enable_material</code> to off and leave seq scans on. However, setting only <code>enable_seqscan = OFF</code> runs slowly and looks exactly like the slow query above (2nd plan), but instead of a sequential scan it uses an index or bitmap heap scan:</p>
  
  <pre><code>-&gt;  Bitmap Heap Scan on tiles.tileset_segment_counts tsc  (cost=43731.56..178253.16 rows=93135 width=1111) (actual time=41.738..105.038 rows=91951 loops=1)
        Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
        Recheck Cond: ((tsc.tileset_id = 1) AND (tsc.num &gt; 1000))
        Heap Blocks: exact=28833
        Buffers: shared hit=38069
        -&gt;  Bitmap Index Scan on tileset_segment_counts_tileset_id_s2_cell_id_num_idx  (cost=0.00..43708.27 rows=93135 width=0) (actual time=36.765..36.765 rows=91951 loops=1)
              Index Cond: ((tsc.tileset_id = 1) AND (tsc.num &gt; 1000))
              Buffers: shared hit=9236
  </code></pre>
  
  <p>I understand this is a temporary solution; how do I go about making the planner realize this on its own? Is this a matter of costs being way off?</p>
  
  <p>-- EDIT #2 --</p>
  
  <p>Updated the first query plan in the first edit to use <code>num &gt; 1000</code> to be consistent.</p>
  
  <p>Additionally, I tried setting the global default_statistics_target to the max value (<code>10000</code>), vacuum analyzing everything, and rerunning. The query planner still uses the slower method of doing a sequential scan with a join filter that takes roughly 6 seconds.</p>
  
  <p>What's even more baffling is if I introduce another table in the join, it coaxes the planner to use the faster method, regardless of the stats target or <code>enable_material</code> setting:</p>
  
  <pre><code>EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
  SELECT tsc.s2_cell_id, tsc.segments
  from public.markets d 
  join cover.covering_s2_cell_ids cs on d.default_covering_id = cs.covering_id
  JOIN tiles.tileset_segment_counts tsc on tsc.s2_cell_id BETWEEN cs.s2_cell_min AND cs.s2_cell_max
  WHERE d.id = 2 
    and tsc.tileset_id = 1
    and num &gt; 1000
  
  Nested Loop  (cost=0.71..99387.70 rows=1021667 width=1108) (actual time=0.033..7.860 rows=6185 loops=1)
    Output: tsc.s2_cell_id, tsc.segments
    Buffers: shared hit=2524
    -&gt;  Nested Loop  (cost=0.29..147.85 rows=100 width=16) (actual time=0.017..0.162 rows=157 loops=1)
          Output: cs.s2_cell_min, cs.s2_cell_max
          Buffers: shared hit=8
          -&gt;  Seq Scan on public.markets d  (cost=0.00..5.56 rows=1 width=4) (actual time=0.008..0.029 rows=1 loops=1)
                Output: d.id, d.name, d.neilsen_id, d.market_key, d.default_covering_id, d.enabled
                Filter: (d.id = 2)
                Rows Removed by Filter: 204
                Buffers: shared hit=3
          -&gt;  Index Scan using covering_s2_cell_ids_pkey on cover.covering_s2_cell_ids cs  (cost=0.29..141.29 rows=100 width=20) (actual time=0.006..0.072 rows=157 loops=1)
                Output: cs.covering_id, cs.s2_cell_id, cs.s2_cell_min, cs.s2_cell_max
                Index Cond: (cs.covering_id = d.default_covering_id)
                Buffers: shared hit=5
    -&gt;  Index Scan using tileset_segment_counts_tileset_id_s2_cell_id_num_idx on tiles.tileset_segment_counts tsc  (cost=0.42..890.23 rows=10217 width=1108) (actual time=0.004..0.031 rows=39 loops=157)
          Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
          Index Cond: ((tsc.tileset_id = 1) AND (tsc.s2_cell_id &gt;= cs.s2_cell_min) AND (tsc.s2_cell_id &lt;= cs.s2_cell_max) AND (tsc.num &gt; 1000))
          Buffers: shared hit=2516
  Planning time: 0.416 ms
  Execution time: 9.010 ms
  </code></pre>
  
  <p>Truly at a loss</p>
  
  <p>-- EDIT #3 --</p>
  
  <p>Adding an index on <code>cover.covering_s2_cell_ids(covering_id, s2_cell_min, s2_cell_max)</code> does make the query run faster, but is still much slower than expected:</p>
  
  <pre><code>Nested Loop  (cost=0.29..267283.27 rows=1602272 width=1107) (actual time=68.918..411.856 rows=6185 loops=1)
    Output: tsc.s2_cell_id, tsc.segments
    Buffers: shared hit=340825 read=3810
    -&gt;  Seq Scan on tiles.tileset_segment_counts tsc  (cost=0.00..149528.89 rows=91850 width=1107) (actual time=0.010..213.931 rows=91951 loops=1)
          Output: tsc.tileset_id, tsc.s2_cell_id, tsc.segments, tsc.num
          Filter: ((tsc.num &gt; 1000) AND (tsc.tileset_id = 1))
          Rows Removed by Filter: 362013
          Buffers: shared hit=138924 read=3807
    -&gt;  Index Only Scan using covering_s2_cell_ids_covering_id_s2_cell_min_s2_cell_max_idx on cover.covering_s2_cell_ids cs  (cost=0.29..1.11 rows=17 width=16) (actual time=0.002..0.002 rows=0 loops=91951)
          Output: cs.covering_id, cs.s2_cell_min, cs.s2_cell_max
          Index Cond: ((cs.covering_id = 2) AND (cs.s2_cell_min &lt;= tsc.s2_cell_id) AND (cs.s2_cell_max &gt;= tsc.s2_cell_id))
          Heap Fetches: 0
          Buffers: shared hit=201901 read=3
  Planning time: 0.372 ms
  Execution time: 413.054 ms
  </code></pre>
  
  <p>Adding an index for tsc(tileset_id, num) improves it slightly, but is still slow. I should note that the subquery on the covering table will only match around 157 rows. It seems the difference between the fast (~10ms) and the slow/medium queries is the order in which the loops are occurring. Notice that in this latest query, we have to perform 91951 loops of the index scan on the covering table. In the fast queries, we first find the rows that match the covering (157 rows), and then only have to perform 157 index scans on the tileset table. I'm going to try tweaking cost estimates because the planning is clearly over-estimating the cost of the fast query.</p>