performance of bitmap scans in nested loop joins - Mailing list pgsql-hackers

Hello All,

I'd like to report about suprising (for me) results of performance testing of
bitmap  indexes in nested loop join plans. 

I have the table q3c

test=# \d q3c    Table "public.q3c"Column |  Type  | Modifiers 
--------+--------+-----------ipix   | bigint | errbox | box    | ra     | real   | dec    | real   | 
Indexes:   "ipix_idx" UNIQUE, btree (ipix)

####################

test=# SELECT count(*) from q3c; count  
---------3000000
(1 row)


First, two join plans with just simple index scan: 

############# 1) 

test=# EXPLAIN ANALYZE SELECT * FROM q3c,q3c AS q3cs WHERE 
q3c.ipix>=q3cs.ipix-3 AND q3c.ipix<=q3cs.ipix+3;                                                           QUERY PLAN
                                                         
 

-----------------------------------------------------------------------------------------------------------------------------------Nested
Loop (cost=0.01..49059519577.21 rows=1000010666695 width=96) (actual time=0.137..39385.725 rows=3000000 loops=1)  ->
SeqScan on q3c q3cs  (cost=0.00..60928.16 rows=3000016 width=48) (actual time=0.007..3659.171 rows=3000000 loops=1)  ->
Index Scan using ipix_idx on q3c  (cost=0.01..9686.37 rows=333335 width=48) (actual time=0.007..0.009 rows=1
loops=3000000)       Index Cond: ((q3c.ipix >= ("outer".ipix - 3)) AND (q3c.ipix <= ("outer".ipix + 3)))Total runtime:
40755.390ms
 
(5 rows)


############# 2)

test=# EXPLAIN ANALYZE SELECT * FROM q3c,q3c as q3cs WHERE 
(q3c.ipix>=q3cs.ipix-1000 AND q3c.ipix<=q3cs.ipix-993);                                                           QUERY
PLAN                                                            
 

-----------------------------------------------------------------------------------------------------------------------------------Nested
Loop (cost=0.01..49059519577.21 rows=1000010666695 width=96) (actual time=28058.983..28058.983 rows=0 loops=1)  ->  Seq
Scanon q3c q3cs  (cost=0.00..60928.16 rows=3000016 width=48) (actual time=0.061..3803.598 rows=3000000 loops=1)  ->
IndexScan using ipix_idx on q3c  (cost=0.01..9686.37 rows=333335 width=48) (actual time=0.006..0.006 rows=0
loops=3000000)       Index Cond: ((q3c.ipix >= ("outer".ipix - 1000)) AND (q3c.ipix <= ("outer".ipix - 993)))Total
runtime:28059.066 ms
 
(5 rows)

#############

And now I combine them in one:


test=# EXPLAIN ANALYZE SELECT * FROM q3c,q3c AS q3cs WHERE 
(q3c.ipix>=q3cs.ipix-3 AND q3c.ipix<=q3cs.ipix+3) OR 
(q3c.ipix>=q3cs.ipix-1000 AND q3c.ipix<=q3cs.ipix-993);
                QUERY PLAN                                                                                    
 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Nested
Loop (cost=5832.03..190281569757.46 rows=1888909037091 width=96) (actual time=0.180..122444.610 rows=3000000 loops=1)
-> Seq Scan on q3c q3cs  (cost=0.00..60928.16 rows=3000016 width=48) (actual time=0.063..3871.731 rows=3000000 loops=1)
->  Bitmap Heap Scan on q3c  (cost=5832.03..43426.73 rows=666670 width=48) (actual time=0.033..0.034 rows=1
loops=3000000)       Recheck Cond: (((q3c.ipix >= ("outer".ipix - 3)) AND (q3c.ipix <= ("outer".ipix + 3))) OR
((q3c.ipix>= ("outer".ipix - 1000)) AND (q3c.ipix <= ("outer".ipix - 993))))        ->  BitmapOr
(cost=5832.03..5832.03rows=666670 width=0) (actual time=0.029..0.029 rows=0 loops=3000000)              ->  Bitmap
IndexScan on ipix_idx  (cost=0.00..2916.02 rows=333335 width=0) (actual time=0.014..0.014 rows=1 loops=3000000)
          Index Cond: ((q3c.ipix >= ("outer".ipix - 3)) AND (q3c.ipix <= ("outer".ipix + 3)))              ->  Bitmap
IndexScan on ipix_idx  (cost=0.00..2916.02 rows=333335 width=0) (actual time=0.011..0.011 rows=0 loops=3000000)
          Index Cond: ((q3c.ipix >= ("outer".ipix - 1000)) AND (q3c.ipix <= ("outer".ipix - 993)))Total runtime:
124366.545ms
 
(10 rows)


So, we see that total time of the plan with bitmap scan is roughly two times
greater than the sum of times of individual index scans.  


I see that in my case even simple union is significantly faster than bitmap
indexes. 

test=# EXPLAIN ANALYZE SELECT * FROM q3c,q3c AS q3cs WHERE 
(q3c.ipix>=q3cs.ipix-3 AND q3c.ipix<=q3cs.ipix+3) 
UNION ALL
SELECT * FROM q3c,q3c AS q3cs WHERE 
(q3c.ipix>=q3cs.ipix-1000 AND q3c.ipix<=q3cs.ipix-993);
QUERYPLAN                                                                   
 

-----------------------------------------------------------------------------------------------------------------------------------------------Append
(cost=0.01..118119252488.32 rows=2000021333390 width=96) (actual time=0.139..75048.897 rows=3000000 loops=1)  ->
SubqueryScan "*SELECT* 1"  (cost=0.01..59059626244.16 rows=1000010666695 width=96) (actual time=0.139..44221.409
rows=3000000loops=1)        ->  Nested Loop  (cost=0.01..49059519577.21 rows=1000010666695 width=96) (actual
time=0.137..40735.906rows=3000000 loops=1)              ->  Seq Scan on q3c q3cs  (cost=0.00..60928.16 rows=3000016
width=48)(actual time=0.063..3719.637 rows=3000000 loops=1)              ->  Index Scan using ipix_idx on q3c
(cost=0.01..9686.37rows=333335 width=48) (actual time=0.007..0.009 rows=1 loops=3000000)                    Index Cond:
((q3c.ipix>= ("outer".ipix - 3)) AND (q3c.ipix <= ("outer".ipix + 3)))  ->  Subquery Scan "*SELECT* 2"
(cost=0.01..59059626244.16rows=1000010666695 width=96) (actual time=28120.449..28120.449 rows=0 loops=1)        ->
NestedLoop  (cost=0.01..49059519577.21 rows=1000010666695 width=96) (actual time=28120.447..28120.447 rows=0 loops=1)
          ->  Seq Scan on q3c q3cs  (cost=0.00..60928.16 rows=3000016 width=48) (actual time=0.023..3649.739
rows=3000000loops=1)              ->  Index Scan using ipix_idx on q3c  (cost=0.01..9686.37 rows=333335 width=48)
(actualtime=0.006..0.006 rows=0 loops=3000000)                    Index Cond: ((q3c.ipix >= ("outer".ipix - 1000)) AND
(q3c.ipix<= ("outer".ipix - 993)))Total runtime: 76413.737 ms
 
(12 rows)


Last note: all those queries were run in fully cached regime on P4 2.8Ghz. 
I used the yesterday's CVS snapshot.

Are those performance results expected for the bitmap index scans ?  

Thanks in advance for any comments.


With Best Regards,    Sergey Koposov

------------------------------------------------------------
Sergey E. Koposov
Sternberg Astronomical Institute, Moscow University (Russia)
Max-Planck Institute for Astronomy (Germany) 
Internet: math@sai.msu.ru, http://lnfm1.sai.msu.su/~math/