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 ms
Execution 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 ms
Execution 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