Explain analyze gist index slowing down query

explain_analyze_gist_index.sql

WITH my_polygon as (
  SELECT ST_GeomFromEWKT('<EWKT polygon>') as geom
)
SELECT count(*)
FROM points as a
,    my_polygon as p
WHERE ST_Within(points.geom, my_polygon.geom);


Small table, no index
=================================================================================================

Aggregate  (cost=167810.85..167810.86 rows=1 width=8) (actual time=483.508..483.508 rows=1 loops=1)
  CTE my_polygon
    ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.000..0.001 rows=1 loops=1)
  ->  Nested Loop  (cost=0.00..167810.42 rows=165 width=0) (actual time=97.338..483.502 rows=3 loops=1)
        Join Filter: ((my_polygon.geom ~ points.geom) AND _st_contains(my_polygon.geom, points.geom))
        Rows Removed by Join Filter: 495026
        ->  CTE Scan on my_polygon p  (cost=0.00..0.02 rows=1 width=32) (actual time=0.002..0.003 rows=1 loops=1)
        ->  Seq Scan on points a  (cost=0.00..37865.29 rows=495029 width=32) (actual time=0.871..341.999 rows=495029 loops=1)
Planning time: 0.290 ms
Execution time: 483.544 ms
-------------------------------------------------------------------------------------------------


Small table, with gist index
=================================================================================================

Aggregate  (cost=1939.61..1939.62 rows=1 width=8) (actual time=0.081..0.081 rows=1 loops=1)
  CTE my_polygon
    ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.001..0.001 rows=1 loops=1)
  ->  Nested Loop  (cost=20.04..1939.19 rows=165 width=0) (actual time=0.069..0.078 rows=3 loops=1)
        ->  CTE Scan on my_polygon p  (cost=0.00..0.02 rows=1 width=32) (actual time=0.003..0.004 rows=1 loops=1)
        ->  Bitmap Heap Scan on points a  (cost=20.04..1937.52 rows=165 width=32) (actual time=0.060..0.067 rows=3 loops=1)
              Recheck Cond: (my_polygon.geom ~ geom)
              Filter: _st_contains(my_polygon.geom, geom)
              Heap Blocks: exact=3
              ->  Bitmap Index Scan on idx_points_geom  (cost=0.00..20.00 rows=495 width=0) (actual time=0.049..0.049 rows=3 loops=1)
                    Index Cond: (my_polygon.geom ~ geom)


Planning time: 0.441 ms
Execution time: 0.142 ms

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



Big table, no index
=================================================================================================
Aggregate  (cost=121550372.01..121550372.02 rows=1 width=8) (actual time=195307.120..195307.120 rows=1 loops=1)
  CTE my_polygon
    ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.001..0.001 rows=1 loops=1)
  ->  Nested Loop  (cost=0.00..121550091.90 rows=112040 width=0) (actual time=9928.108..194494.866 rows=13724493 loops=1)
        Join Filter: ((my_polygon.geom ~ points.geom) AND _st_contains(my_polygon.geom, points.geom))
        Rows Removed by Join Filter: 322396436
        ->  CTE Scan on my_polygon p  (cost=0.00..0.02 rows=1 width=32) (actual time=0.001..0.002 rows=1 loops=1)
        ->  Seq Scan on points a  (cost=0.00..33318348.28 rows=336120928 width=32) (actual time=9926.982..117809.409 rows=336120929 loops=1)
Planning time: 0.863 ms
Execution time: 195307.138 ms
-------------------------------------------------------------------------------------------------


Big table, with gist index
=================================================================================================

Aggregate  (cost=1012144.51..1012144.52 rows=1 width=8) (actual time=234495.198..234495.198 rows=1 loops=1)
  CTE my_polygon
    ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.002..0.003 rows=1 loops=1)
  ->  Nested Loop  (cost=10869.96..1011934.68 rows=83930 width=0) (actual time=12663.335..233563.128 rows=13724493 loops=1)
        ->  CTE Scan on my_polygon p  (cost=0.00..0.02 rows=1 width=32) (actual time=0.005..0.007 rows=1 loops=1)
        ->  Bitmap Heap Scan on points a  (cost=10869.96..1011095.36 rows=83930 width=32) (actual time=12663.321..232441.120 rows=13724493 loops=1)
              Recheck Cond: (my_polygon.geom ~ geom)
              Rows Removed by Index Recheck: 141788471
              Filter: _st_contains(my_polygon.geom, geom)
              Rows Removed by Filter: 1224016
              Heap Blocks: exact=39822 lossy=10462883
              ->  Bitmap Index Scan on idx_points_geom  (cost=0.00..10848.97 rows=251790 width=0) (actual time=12639.934..12639.934 rows=14948509 loops=1)
                    Index Cond: (my_polygon.geom ~ geom)
Planning time: 0.426 ms
Execution time: 234495.684 ms

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



Within, gist index   SET work_mem = '1GB';
=================================================================================================

Aggregate  (cost=1012144.51..1012144.52 rows=1 width=8) (actual time=244212.718..244212.718 rows=1 loops=1)
  CTE polygon
    ->  Result  (cost=0.00..0.01 rows=1 width=32) (actual time=0.001..0.001 rows=1 loops=1)
  ->  Nested Loop  (cost=10869.96..1011934.68 rows=83930 width=0) (actual time=15519.622..243241.593 rows=13724493 loops=1)
        ->  CTE Scan on polygon p  (cost=0.00..0.02 rows=1 width=32) (actual time=0.003..0.004 rows=1 loops=1)
        ->  Bitmap Heap Scan on ais_position a  (cost=10869.96..1011095.36 rows=83930 width=32) (actual time=15519.616..241975.226 rows=13724493 loops=1)
              Recheck Cond: (p.geom ~ geom)
              Filter: _st_contains(p.geom, geom)
              Rows Removed by Filter: 1224016
              Heap Blocks: exact=10502705
              ->  Bitmap Index Scan on idx_ais_position_geom  (cost=0.00..10848.97 rows=251790 width=0) (actual time=11751.134..11751.134 rows=14948509 loops=1)
                    Index Cond: (p.geom ~ geom)
Planning time: 7.241 ms
Execution time: 244236.237 ms