Performance degradation in Bitmapscan (commit 75ae538bc3168bf44475240d4e0487ee2f3bb376)

While testing bitmap performance, I have observed that some of the
TPCH queries taking huge time in BitmapIndexScan node, when there are
lossy pages.

I suspected 75ae538bc3168bf44475240d4e0487ee2f3bb376 commit, because
prior to that it used to take very less time. So I tested by reverting
suspected commit and problem is solved.

Here is explained analyze result for TPCH query 6 (scale factor 10)

work_mem=10M
shared_buffers=20GB
machine under test: POWER, 4 socket machine

->On Head:

postgres=# \i 6.explain.sql
                                  QUERY PLAN


--------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------Limit  (cost=1585507.74..1585507.75 rows=1 width=32)
(actual
time=21626.467..21626.467 rows=1 loops=1)  ->  Aggregate  (cost=1585507.74..1585507.75 rows=1 width=32)
(actual time=21626.466..21626.466 rows=1 loops=1)        ->  Bitmap Heap Scan on lineitem  (cost=299632.60..1579529.48
rows=1195652 width=12) (actual time=9204.770..20910.089 rows=1190658
loops=1)              Recheck Cond: ((l_shipdate >= '1995-01-01'::date) AND
(l_shipdate < '1996-01-01 00:00:00'::timestamp without time zone) AND
(l_discount >= 0.07
) AND (l_discount <= 0.09) AND (l_quantity < '25'::numeric))              Rows Removed by Index Recheck: 27584798
      Heap Blocks: exact=101349 lossy=580141              ->  Bitmap Index Scan on idx_lineitem_shipdate
 
(cost=0.00..299333.68 rows=1195652 width=0) (actual
time=9185.490..9185.490 rows=1190658 loops=
1)                    Index Cond: ((l_shipdate >= '1995-01-01'::date)
AND (l_shipdate < '1996-01-01 00:00:00'::timestamp without time zone)
AND (l_discount >=
0.07) AND (l_discount <= 0.09) AND (l_quantity < '25'::numeric))Planning time: 0.675 msExecution time: 21626.838 ms
(10 rows)


->After reverting Commit: 75ae538bc3168bf44475240d4e0487ee2f3bb376
postgres=# \i 6.explain.sql
                                  QUERY PLAN


--------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------Limit  (cost=1585507.74..1585507.75 rows=1 width=32)
(actual
time=12807.293..12807.294 rows=1 loops=1)  ->  Aggregate  (cost=1585507.74..1585507.75 rows=1 width=32)
(actual time=12807.291..12807.291 rows=1 loops=1)        ->  Bitmap Heap Scan on lineitem  (cost=299632.60..1579529.48
rows=1195652 width=12) (actual time=1632.351..12131.552 rows=1190658
loops=1)              Recheck Cond: ((l_shipdate >= '1995-01-01'::date) AND
(l_shipdate < '1996-01-01 00:00:00'::timestamp without time zone) AND
(l_discount >= 0.07
) AND (l_discount <= 0.09) AND (l_quantity < '25'::numeric))              Rows Removed by Index Recheck: 28401743
      Heap Blocks: exact=84860 lossy=596630              ->  Bitmap Index Scan on idx_lineitem_shipdate
 
(cost=0.00..299333.68 rows=1195652 width=0) (actual
time=1613.166..1613.166 rows=1190658 loops=
1)                    Index Cond: ((l_shipdate >= '1995-01-01'::date)
AND (l_shipdate < '1996-01-01 00:00:00'::timestamp without time zone)
AND (l_discount >=
0.07) AND (l_discount <= 0.09) AND (l_quantity < '25'::numeric))Planning time: 0.173 msExecution time: 12807.380 ms
(10 rows)


From above explain analyze result we can see that with commit
75ae538bc3168bf44475240d4e0487ee2f3bb376, Bitmap Index Scan node is
way slower than without this commit.

Perf result:
Head
+   13.12%     0.01%  postgres  postgres            [.] tbm_lossify
+   13.10%    13.10%  postgres  postgres            [.]
tbm_mark_page_lossy
+   12.84%    12.82%  postgres  postgres            [.]
slot_deform_tuple
+    6.94%     0.00%  postgres  postgres            [.] _bt_next
+    6.94%     0.02%  postgres  postgres            [.] _bt_steppage
+    6.55%     0.05%  postgres  postgres            [.] _bt_readpage
+    6.41%     1.00%  postgres  postgres            [.] _bt_checkkeys

After Reverting 75ae538bc3168bf44475240d4e0487ee2f3bb376:
+    0.71%     0.71%  postgres  postgres            [.] cmp_var_common
+    0.62%     0.02%  postgres  postgres            [.] tbm_lossify
+    0.62%     0.62%  postgres  postgres            [.] AllocSetReset
+    0.60%     0.11%  postgres  [kernel.kallsyms]   [k] sys_read
+    0.59%     0.10%  postgres  postgres            [.]
advance_transition_function

I think in new hash implementation, delete from pagetable have severe
performance issue.

Note: If I set work_mem=100MB (no lossy page) then performance is fine.


-- 
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com