When can postgresql use a partial (NOT NULL) index? Seems to depend on size of IN clause (even with enable seqscan = off)

Hi all,

I'm debugging a performance issue that looks like it might actually be an issue/limitation/parameter/bug in the query planner, but since I couldn't find anything authoritative on when exactly postgresql is able to use partial not null indexes I'm not sure that that's the case and I was hopping someone could give some clarity around that or point to an option I could tweak that would change this behavior.  Anyways the table in question (with names changed) is below.  I'm running postgres 8.4.1

\d
          Column          |   Type   | Modifiers
--------------------------+----------+-----------
 id                       | integer  | not null
 sid                      | integer  |
 bid                      | integer  |
 m                        | date     | not null
 k                        | integer  |
 cc                       | text     |
 f                        | integer  |
 d                        | smallint |
 u                        | smallint |
 f2                       | integer  |
 cm                       | text     |
Indexes:
    "scm_pkey" PRIMARY KEY, btree (id) WITH (fillfactor=100)
    "index_scm_on_bid" btree (bid) WITH (fillfactor=100) WHERE bid IS NOT NULL

~35 million rows (about 15 million of which have null bid).  There are about 1 million distinct bids (with selectivity ranging from 1 to ~100,000 rows).

The end user selects an arbitrary number of bid's then we run several queries one of which I include explain analyze output below.  For <= 100 bids the planner uses the index and completes in ~35ms, for 101+ bid's the planner uses a sequence scan and completes in ~45 seconds (3 orders of magnitude slower).  My first thought was that there was a problem with the statistics/estimation in the planner, but using "set enable seq_scan=off;" still does not use the index when there's over 100 bid's in the IN clause.  Breaking the IN clause into 2 < 100 element groups does however rescue the use of the index and the fast performance as does creating a new non-partial index on bid (i.e. an index "index_scm_on_bid2" btree (bid) WITH (fillfactor=100) will be used with over 100 bid's).  My best guess is that this is do to some limit on the number of in clause elements the query planner will check to see if match a partial index before giving up and assuming it doesn't (if there is such a limit I'd definitely like to make it larger, at least for this big of a table...). Is this 100 limit documented anywhere?

Anyways my workarounds are to either split the IN clause into multiple < 100 element groups or switch the index to be across all values rather then not null.  The reason I tend to use not null partial indexes is that I have another similarly sized table with 20 separately indexed columns each of which only has about 10000 non-null rows and the disk space savings from the not null partial index there are huge.

# <= 100 bids
=>explain analyze SELECT * FROM "scm" WHERE ((bid in (1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044))) order by m desc limit 100;
 Limit  (cost=66518.18..66518.43 rows=100 width=229) (actual time=24.665..24.821 rows=100 loops=1)
   ->  Sort  (cost=66518.18..66563.14 rows=17987 width=229) (actual time=24.658..24.698 rows=100 loops=1)
         Sort Key: m
         Sort Method:  top-N heapsort  Memory: 85kB
         ->  Bitmap Heap Scan on scm  (cost=566.83..65830.73 rows=17987 width=229) (actual time=1.863..12.850 rows=16430 loops=1)
               Recheck Cond: (bid = ANY ('{1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044}'::integer[]))
               ->  Bitmap Index Scan on index_scm_on_bid  (cost=0.00..562.33 rows=17987 width=0) (actual time=1.719..1.719 rows=16430 loops=1)
                     Index Cond: (bid = ANY ('{1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044}'::integer[]))
 Total runtime: 24.908 ms

# > 100 bids
# NOTE - this is the same even after running
# set enable_seqscan = off;
# HOWEVER - this will use an index scan and run fast if we create a non partial index on bid
=>explain analyze SELECT * FROM "scm" WHERE ((bid in (1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044,1208045))) order by m desc limit 100;
 Limit  (cost=3783824.03..3783824.28 rows=100 width=229) (actual time=31229.140..31229.284 rows=100 loops=1)
   ->  Sort  (cost=3783824.03..3783869.06 rows=18014 width=229) (actual time=31229.137..31229.193 rows=100 loops=1)
         Sort Key: m
         Sort Method:  top-N heapsort  Memory: 82kB
         ->  Seq Scan on scm  (cost=0.00..3783135.55 rows=18014 width=229) (actual time=97.582..31217.270 rows=16433 loops=1)
               Filter: (bid = ANY ('{1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044,1208045}'::integer[]))
 Total runtime: 31229.377 ms

# Splitting the IN into <= 100 element pieces works
=>explain analyze SELECT * FROM "scm" WHERE ((bid in (1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044))) OR ((bid IN (1208045))) order by m desc limit 100;
 Limit  (cost=66664.94..66665.19 rows=100 width=229) (actual time=24.749..24.902 rows=100 loops=1)
   ->  Sort  (cost=66664.94..66709.98 rows=18014 width=229) (actual time=24.747..24.795 rows=100 loops=1)
         Sort Key: m
         Sort Method:  top-N heapsort  Memory: 85kB
         ->  Bitmap Heap Scan on scm  (cost=577.99..65976.46 rows=18014 width=229) (actual time=1.867..12.888 rows=16433 loops=1)
               Recheck Cond: ((bid = ANY ('{1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044}'::integer[])) OR (bid = 1208045))
               ->  BitmapOr  (cost=577.99..577.99 rows=18014 width=0) (actual time=1.720..1.720 rows=0 loops=1)
                     ->  Bitmap Index Scan on index_scm_on_bid  (cost=0.00..562.33 rows=17987 width=0) (actual time=1.715..1.715 rows=16430 loops=1)
                           Index Cond: (bid = ANY ('{1000071082,1558141,1261493,1558137,1558166,1622957,1261535,1558191,1885437,2025548,1558144,1261485,1261536,1261539,1261541,1000067964,1558183,1789348,1000090512,1558150,1000096731,1261533,2056107,1875527,1177541,1535923,1558184,1558155,1261538,1261537,1558140,1159311,1558188,1558185,1261529,1558158,1000021460,1558517,1000090515,1558194,1558143,1558153,1261484,1261542,1558156,1201225,1261481,1558157,1891458,1200735,1285621,1702779,1558135,1261540,1579615,1558189,1558154,2053227,1261531,1261488,1558139,1261527,1558192,1261530,1261528,1159310,1558136,1558138,1558164,1261543,1000015605,2053214,1558187,1183258,1184576,1558145,1558159,1208646,1622955,1558161,1558160,1208046,1000060938,1000067963,1000067965,1261487,1828875,1541699,1261491,1210589,1558162,1558151,1558152,1558163,1181201,1186001,1197776,1200734,1208043,1208044}'::integer[]))
                     ->  Bitmap Index Scan on index_scm_on_bid  (cost=0.00..6.66 rows=27 width=0) (actual time=0.003..0.003 rows=3 loops=1)
                           Index Cond: (bid = 1208045)
 Total runtime: 24.998 ms


Thanks!
Tim