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.
Index: src/backend/access/nbtree/nbtsearch.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v
retrieving revision 1.93
diff -u -r1.93 nbtsearch.c
--- src/backend/access/nbtree/nbtsearch.c       19 Jun 2005 22:41:00 -0000      
1.93
+++ src/backend/access/nbtree/nbtsearch.c       19 Sep 2005 17:37:51 -0000
@@ -647,13 +647,6 @@
                ScanKey         cur = startKeys[i];
 
                /*
-                * _bt_preprocess_keys disallows it, but it's place to add some
-                * code later
-                */
-               if (cur->sk_flags & SK_ISNULL)
-                       elog(ERROR, "btree doesn't support is(not)null, yet");
-
-               /*
                 * If scankey operator is of default subtype, we can use the
                 * cached comparison procedure; otherwise gotta look it up in 
the
                 * catalogs.
Index: src/backend/access/nbtree/nbtutils.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v
retrieving revision 1.63
diff -u -r1.63 nbtutils.c
--- src/backend/access/nbtree/nbtutils.c        13 Jun 2005 23:14:48 -0000      
1.63
+++ src/backend/access/nbtree/nbtutils.c        19 Sep 2005 17:37:52 -0000
@@ -257,12 +257,26 @@
        if (numberOfKeys == 1)
        {
                /*
-                * We don't use indices for 'A is null' and 'A is not null'
-                * currently and 'A < = > <> NULL' will always fail - so qual is
-                * not OK if comparison value is NULL.          - vadim 03/21/97
+                * A IS NULL is transformed to A = NULL for index scans. 
+                * NULL is only OK for BTEqualStrategyNumber, nothing else.
+                * This shouldn't ever happen though, since the optimizer
+                * should optimise away (anything op NULL). We only get here
+                * because expand_index_quals creates it and the optimizer
+                * doesn't touch that.
+                *
+                * Note the use of SK_INDEXFINDNULL. This flag needs to be
+                * set for the index to find NULLs. This is to distinguish
+                * the static predicate (a = NULL) which was transformed
+                * from (a IS NULL) and the runtime predicate (a = col)
+                * where col happend to be NULL this iteration.
                 */
                if (cur->sk_flags & SK_ISNULL)
-                       so->qual_ok = false;
+               {
+                       if( cur->sk_strategy != BTEqualStrategyNumber )
+                               so->qual_ok = false;
+                       else if( !(cur->sk_flags & SK_INDEXFINDNULL) )
+                               so->qual_ok = false;
+               }
                else if (relation->rd_index->indisunique &&
                                 relation->rd_rel->relnatts == 1)
                {
@@ -306,7 +320,8 @@
                if (i < numberOfKeys)
                {
                        /* See comments above: any NULL implies cannot match 
qual */
-                       if (cur->sk_flags & SK_ISNULL)
+                       if (cur->sk_flags & SK_ISNULL &&
+                               (cur->sk_strategy != BTEqualStrategyNumber || 
!(cur->sk_flags & SK_INDEXFINDNULL) ) )
                        {
                                so->qual_ok = false;
 
@@ -345,6 +360,13 @@
 
                                        if (!chk || j == (BTEqualStrategyNumber 
- 1))
                                                continue;
+                                       
+                                       /* If = NULL, cannot accept any other 
predicates */
+                                       if ( eq->sk_flags & SK_ISNULL)
+                                       {
+                                               so->qual_ok = false;
+                                               break;
+                                       }
                                        test = FunctionCall2(&chk->sk_func,
                                                                                
 eq->sk_argument,
                                                                                
 chk->sk_argument);
@@ -445,6 +467,17 @@
                /* have we seen one of these before? */
                if (xform[j])
                {
+                       /* If matching NULL, we can *only* match null */
+                       if ( (cur->sk_flags ^ xform[j]->sk_flags) & SK_ISNULL)
+                       {
+                               so->qual_ok = false;
+                               continue;
+                       }
+                       /* If both = NULL, goto next attr */
+                       if( cur->sk_flags & SK_ISNULL )
+                       {
+                               continue;
+                       }
                        /* yup, keep the more restrictive key */
                        test = FunctionCall2(&cur->sk_func,
                                                                 
cur->sk_argument,
@@ -515,12 +548,18 @@
                                                          tupdesc,
                                                          &isNull);
 
-               /* btree doesn't support 'A is null' clauses, yet */
                if (key->sk_flags & SK_ISNULL)
                {
-                       /* we shouldn't get here, really; see 
_bt_preprocess_keys() */
-                       *continuescan = false;
-                       return false;
+                       /* If the scankey is null, it must be
+                        * BTEqualStrategyNumber. The comment below applies
+                        * here too: if we're at a not null value on a
+                        * required key, we must be at a point where it is
+                        * no longer useful to proceed. */
+                       
+                       if( !isNull && ikey < so->numberOfRequiredKeys )
+                               *continuescan = false;
+
+                       return isNull;
                }
 
                if (isNull)
Index: src/backend/executor/nodeIndexscan.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/executor/nodeIndexscan.c,v
retrieving revision 1.103
diff -u -r1.103 nodeIndexscan.c
--- src/backend/executor/nodeIndexscan.c        6 May 2005 17:24:54 -0000       
1.103
+++ src/backend/executor/nodeIndexscan.c        19 Sep 2005 17:37:53 -0000
@@ -624,10 +624,14 @@
                        /*
                         * if the rightop is a const node then it means it
                         * identifies the value to place in our scan key.
+                        *
+                        * We need SK_INDEXFINDNULL for IS NULL to work, for
+                        * runtime keys a NULL is special and shouldn't
+                        * match anything.
                         */
                        scanvalue = ((Const *) rightop)->constvalue;
                        if (((Const *) rightop)->constisnull)
-                               flags |= SK_ISNULL;
+                               flags |= SK_ISNULL | SK_INDEXFINDNULL;
                }
                else
                {
Index: src/backend/optimizer/path/indxpath.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v
retrieving revision 1.188
diff -u -r1.188 indxpath.c
--- src/backend/optimizer/path/indxpath.c       28 Aug 2005 22:47:20 -0000      
1.188
+++ src/backend/optimizer/path/indxpath.c       19 Sep 2005 17:37:53 -0000
@@ -816,6 +816,13 @@
                if (match_boolean_index_clause((Node *) clause, indexcol, 
index))
                        return true;
        }
+       
+       if( IsA( clause, NullTest ) && ((NullTest*)clause)->nulltesttype == 
IS_NULL )
+       {
+               leftop = (Node*) ((NullTest*)clause)->arg;
+               if (match_index_to_operand(leftop, indexcol, index))
+                       return true;
+       }
 
        /* Else clause must be a binary opclause. */
        if (!is_opclause(clause))
@@ -1928,6 +1935,18 @@
                                        continue;
                                }
                        }
+                       
+                       /* IS NULL case */
+                       if( IsA( rinfo->clause, NullTest ) )
+                       {
+                               Oid     eqop = get_opclass_member(curClass, 
InvalidOid, BTEqualStrategyNumber);
+                               Expr *arg = ((NullTest*)(rinfo->clause))->arg;
+                               Expr *opclause = make_opclause(eqop, BOOLOID, 
false, arg, (Expr *) makeNullConst(exprType(arg)) );
+
+                               resultquals = lappend(resultquals, 
make_restrictinfo( opclause, true, NULL ) );
+                               
+                               continue;
+                       }
 
                        resultquals = list_concat(resultquals,
                                                                          
expand_indexqual_condition(rinfo,
Index: src/include/access/skey.h
===================================================================
RCS file: /projects/cvsroot/pgsql/src/include/access/skey.h,v
retrieving revision 1.29
diff -u -r1.29 skey.h
--- src/include/access/skey.h   24 Jun 2005 00:18:52 -0000      1.29
+++ src/include/access/skey.h   19 Sep 2005 17:37:55 -0000
@@ -73,7 +73,7 @@
 #define SK_ISNULL              0x0001  /* sk_argument is NULL */
 #define SK_UNARY               0x0002  /* unary operator (currently 
unsupported) */
 #define SK_NEGATE              0x0004  /* must negate the function result */
-
+#define SK_INDEXFINDNULL       0x0008  /* index can find NULL with SK_ISNULL 
here */
 
 /*
  * prototypes for functions in access/common/scankey.c

Attachment: pgpBMc51fRiR5.pgp
Description: PGP signature

Reply via email to