Re: BUG #6278: Index scans on '>' condition on field with many NULLS - Mailing list pgsql-bugs

Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Oct 31, 2011 at 12:43 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> A patch along these lines should be pretty localized.  Has anyone
>> got an opinion on whether to back-patch or not?  This seems like a
>> performance bug, but given the lack of prior complaints, maybe we
>> shouldn't take any risks for it.

> I think my vote would be to just fix it in master.

After researching the issue, my patch looks like the attached.  This
seems to apply cleanly back to about 8.3, so I'm inclined to back-patch
that far.  It's pretty simple, and I think the reason we (I) got it
wrong to begin with is just lack of thought about the NULLs case.

            regards, tom lane

diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 134abe6d596413a1ad54c0c7f378248251295d4a..c00255567116e3b6f7bd8426eb32b2398c8d95d5 100644
*** a/src/backend/access/nbtree/nbtutils.c
--- b/src/backend/access/nbtree/nbtutils.c
*************** _bt_checkkeys(IndexScanDesc scan,
*** 1384,1398 ****
              }

              /*
!              * Tuple fails this qual.  If it's a required qual for the current
!              * scan direction, then we can conclude no further tuples will
!              * pass, either.
               */
!             if ((key->sk_flags & SK_BT_REQFWD) &&
!                 ScanDirectionIsForward(dir))
!                 *continuescan = false;
!             else if ((key->sk_flags & SK_BT_REQBKWD) &&
!                      ScanDirectionIsBackward(dir))
                  *continuescan = false;

              /*
--- 1394,1409 ----
              }

              /*
!              * Tuple fails this qual.  If it's a required qual, then we can
!              * conclude no further tuples will pass, either.  We can stop
!              * regardless of the scan direction, because we know that NULLs
!              * sort to one end or the other of the range of values.  If this
!              * tuple doesn't pass, then no future ones will either, until we
!              * reach the next set of values of the higher-order index attrs
!              * (if any) ... and those attrs must have equality quals, else
!              * this one wouldn't be marked required.
               */
!             if (key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
                  *continuescan = false;

              /*
*************** _bt_checkkeys(IndexScanDesc scan,
*** 1403,1434 ****

          if (isNull)
          {
!             if (key->sk_flags & SK_BT_NULLS_FIRST)
!             {
!                 /*
!                  * Since NULLs are sorted before non-NULLs, we know we have
!                  * reached the lower limit of the range of values for this
!                  * index attr.    On a backward scan, we can stop if this qual
!                  * is one of the "must match" subset.  On a forward scan,
!                  * however, we should keep going.
!                  */
!                 if ((key->sk_flags & SK_BT_REQBKWD) &&
!                     ScanDirectionIsBackward(dir))
!                     *continuescan = false;
!             }
!             else
!             {
!                 /*
!                  * Since NULLs are sorted after non-NULLs, we know we have
!                  * reached the upper limit of the range of values for this
!                  * index attr.    On a forward scan, we can stop if this qual is
!                  * one of the "must match" subset.    On a backward scan,
!                  * however, we should keep going.
!                  */
!                 if ((key->sk_flags & SK_BT_REQFWD) &&
!                     ScanDirectionIsForward(dir))
!                     *continuescan = false;
!             }

              /*
               * In any case, this indextuple doesn't match the qual.
--- 1414,1428 ----

          if (isNull)
          {
!             /*
!              * The index entry is NULL, so it must fail this qual (we assume
!              * all btree operators are strict).  Furthermore, we know that
!              * all remaining entries with the same higher-order index attr
!              * values must be NULLs too.  So, just as above, we can stop the
!              * scan regardless of direction, if the qual is required.
!              */
!             if (key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
!                 *continuescan = false;

              /*
               * In any case, this indextuple doesn't match the qual.
*************** _bt_check_rowcompare(ScanKey skey, Index
*** 1508,1539 ****

          if (isNull)
          {
!             if (subkey->sk_flags & SK_BT_NULLS_FIRST)
!             {
!                 /*
!                  * Since NULLs are sorted before non-NULLs, we know we have
!                  * reached the lower limit of the range of values for this
!                  * index attr. On a backward scan, we can stop if this qual is
!                  * one of the "must match" subset.    On a forward scan,
!                  * however, we should keep going.
!                  */
!                 if ((subkey->sk_flags & SK_BT_REQBKWD) &&
!                     ScanDirectionIsBackward(dir))
!                     *continuescan = false;
!             }
!             else
!             {
!                 /*
!                  * Since NULLs are sorted after non-NULLs, we know we have
!                  * reached the upper limit of the range of values for this
!                  * index attr. On a forward scan, we can stop if this qual is
!                  * one of the "must match" subset.    On a backward scan,
!                  * however, we should keep going.
!                  */
!                 if ((subkey->sk_flags & SK_BT_REQFWD) &&
!                     ScanDirectionIsForward(dir))
!                     *continuescan = false;
!             }

              /*
               * In any case, this indextuple doesn't match the qual.
--- 1502,1516 ----

          if (isNull)
          {
!             /*
!              * The index entry is NULL, so it must fail this qual (we assume
!              * all btree operators are strict).  Furthermore, we know that
!              * all remaining entries with the same higher-order index attr
!              * values must be NULLs too.  So, just as above, we can stop the
!              * scan regardless of direction, if the qual is required.
!              */
!             if (subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
!                 *continuescan = false;

              /*
               * In any case, this indextuple doesn't match the qual.