[PATCH] Add support for IS NULL to btree indexes

Here is a patch that enables IS NULL to use a btree index. After
mentioning it was really hard, I had a brainwave and here are the 80
lines of code necessary to make it work. What surprised me is that in
various important parts most of the work had actually been done already.

Actually, it's two changes:
- In the btree index code, if SK_ISNULL is set, do the right thing
- If the query has col IS NULL, expand that to col = NULL in the index
quals

The bit to convert col = NULL to an appropriate scan key and everything
else was already in place. It's not overhauling the index am code, just
using the facilities already there.

The only possibly controversial addition of a new scankey flag
SK_INDEXFINDNULL which needs to be set for the index to consider the
scankey. This is to distinguish the cases where (a = NULL) has been
derived from (a IS NULL) and (a = col) where col happens to be NULL
this time round.

It's not entirely perfect, if you look at the explain output, it's
still in the filter list. I couldn't work out how to remove it. Before
you ask, it is working, I traced gdb all the way through the btree
index code and it is doing what it's supposed to. It's the same issue
affecting the IS TRUE/FALSE predicates, they're still in the filter
lists too.

Basically, could some people look over the logic. I think I got it
right but this is the first time I've played with the index code so
maybe I've missed something. If it is agreed to be the way to go, I'll
go back and work out the documentation changes.

Download: http://svana.org/kleptog/pgsql/indexnulls.diff

Have a nice day,

test=# explain analyze select * from z order by t;
                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------
 Index Scan using zt on z  (cost=0.00..65.58 rows=1144 width=44) (actual time=0.034..4.624 rows=1000 loops=1)
 Total runtime: 7.684 ms
(2 rows)

test=# explain analyze select * from z where t is null order by t;
                                               QUERY PLAN
---------------------------------------------------------------------------------------------------------
 Index Scan using zt on z  (cost=0.00..5.84 rows=6 width=44) (actual time=0.044..1.442 rows=250 loops=1)
   Index Cond: (t = NULL::text)
   Filter: (t IS NULL)
 Total runtime: 2.279 ms
(4 rows)

--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.