diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c new file mode 100644 index a452fea..8f92dfc *** a/src/backend/access/nbtree/nbtinsert.c --- b/src/backend/access/nbtree/nbtinsert.c *************** top: *** 157,163 **** { TransactionId xwait; ! offset = _bt_binsrch(rel, buf, natts, itup_scankey, false); xwait = _bt_check_unique(rel, itup, heapRel, buf, offset, itup_scankey, checkUnique, &is_unique); --- 157,163 ---- { TransactionId xwait; ! offset = _bt_page_srch(rel, buf, natts, itup_scankey, false); xwait = _bt_check_unique(rel, itup, heapRel, buf, offset, itup_scankey, checkUnique, &is_unique); *************** _bt_findinsertloc(Relation rel, *** 639,645 **** else if (firstlegaloff != InvalidOffsetNumber && !vacuumed) newitemoff = firstlegaloff; else ! newitemoff = _bt_binsrch(rel, buf, keysz, scankey, false); *bufptr = buf; *offsetptr = newitemoff; --- 639,645 ---- else if (firstlegaloff != InvalidOffsetNumber && !vacuumed) newitemoff = firstlegaloff; else ! newitemoff = _bt_page_srch(rel, buf, keysz, scankey, false); *bufptr = buf; *offsetptr = newitemoff; diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c new file mode 100644 index ac98589..391b055 *** a/src/backend/access/nbtree/nbtsearch.c --- b/src/backend/access/nbtree/nbtsearch.c *************** *** 24,29 **** --- 24,32 ---- #include "utils/rel.h" + static int _bt_getfibnumber(OffsetNumber pagehigh); + static int _bt_fib_srch(Relation rel, int keysz, ScanKey scankey, Page page, + int low, int high); static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum); static void _bt_saveitem(BTScanOpaque so, int itemIndex, *************** static bool _bt_endpoint(IndexScanDesc s *** 34,39 **** --- 37,53 ---- /* + * Precomputed table of Fibonacci numbers, used as search pivot offsets. + * + * There are enough constants here to cover all possible values of BLCKSZ. + */ + static const OffsetNumber fibonacci[] = { + 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, + 233, 377, 610, 987, 1597, 2584, 4181, 6765, + 10946, 17711, 28657, 46368, USHRT_MAX + }; + + /* * _bt_search() -- Search the tree for a particular scankey, * or more precisely for the first leaf page it could be on. * *************** _bt_search(Relation rel, int keysz, Scan *** 95,101 **** * Find the appropriate item on the internal page, and get the child * page that it points to. */ ! offnum = _bt_binsrch(rel, *bufP, keysz, scankey, nextkey); itemid = PageGetItemId(page, offnum); itup = (IndexTuple) PageGetItem(page, itemid); blkno = ItemPointerGetBlockNumber(&(itup->t_tid)); --- 109,115 ---- * Find the appropriate item on the internal page, and get the child * page that it points to. */ ! offnum = _bt_page_srch(rel, *bufP, keysz, scankey, nextkey); itemid = PageGetItemId(page, offnum); itup = (IndexTuple) PageGetItem(page, itemid); blkno = ItemPointerGetBlockNumber(&(itup->t_tid)); *************** _bt_moveright(Relation rel, *** 204,210 **** } /* ! * _bt_binsrch() -- Do a binary search for a key on a particular page. * * The passed scankey must be an insertion-type scankey (see nbtree/README), * but it can omit the rightmost column(s) of the index. --- 218,224 ---- } /* ! * _bt_page_srch() -- Do a search for a key on a particular page. * * The passed scankey must be an insertion-type scankey (see nbtree/README), * but it can omit the rightmost column(s) of the index. *************** _bt_moveright(Relation rel, *** 213,224 **** * item >= scankey. When nextkey is true, we are looking for the first * item strictly greater than scankey. * ! * On a leaf page, _bt_binsrch() returns the OffsetNumber of the first * key >= given scankey, or > scankey if nextkey is true. (NOTE: in * particular, this means it is possible to return a value 1 greater than the * number of keys on the page, if the scankey is > all keys on the page.) * ! * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber * of the last key < given scankey, or last key <= given scankey if nextkey * is true. (Since _bt_compare treats the first data key of such a page as * minus infinity, there will be at least one key < scankey, so the result --- 227,238 ---- * item >= scankey. When nextkey is true, we are looking for the first * item strictly greater than scankey. * ! * On a leaf page, _bt_page_srch() returns the OffsetNumber of the first * key >= given scankey, or > scankey if nextkey is true. (NOTE: in * particular, this means it is possible to return a value 1 greater than the * number of keys on the page, if the scankey is > all keys on the page.) * ! * On an internal (non-leaf) page, _bt_page_srch() returns the OffsetNumber * of the last key < given scankey, or last key <= given scankey if nextkey * is true. (Since _bt_compare treats the first data key of such a page as * minus infinity, there will be at least one key < scankey, so the result *************** _bt_moveright(Relation rel, *** 227,237 **** * (or leaf keys > given scankey when nextkey is true). * * This procedure is not responsible for walking right, it just examines ! * the given page. _bt_binsrch() has no lock or refcount side effects * on the buffer. */ OffsetNumber ! _bt_binsrch(Relation rel, Buffer buf, int keysz, ScanKey scankey, --- 241,251 ---- * (or leaf keys > given scankey when nextkey is true). * * This procedure is not responsible for walking right, it just examines ! * the given page. _bt_page_srch() has no lock or refcount side effects * on the buffer. */ OffsetNumber ! _bt_page_srch(Relation rel, Buffer buf, int keysz, ScanKey scankey, *************** _bt_binsrch(Relation rel, *** 274,293 **** */ high++; /* establish the loop invariant for high */ ! cmpval = nextkey ? 0 : 1; /* select comparison value */ ! ! while (high > low) { ! OffsetNumber mid = low + ((high - low) / 2); ! /* We have low <= mid < high, so mid points at a real slot */ ! result = _bt_compare(rel, keysz, scankey, page, mid); ! if (result >= cmpval) ! low = mid + 1; ! else ! high = mid; } /* --- 288,314 ---- */ high++; /* establish the loop invariant for high */ ! if (nextkey) { ! cmpval = nextkey ? 0 : 1; /* select comparison value */ ! while (high > low) ! { ! OffsetNumber mid = low + ((high - low) / 2); ! /* We have low <= mid < high, so mid points at a real slot */ ! result = _bt_compare(rel, keysz, scankey, page, mid); ! ! if (result >= cmpval) /* for !nextKey, if result > 0 */ ! low = mid + 1; ! else ! high = mid; ! } ! } ! else ! { ! low = _bt_fib_srch(rel, keysz, scankey, page, low, high); } /* *************** _bt_compare(Relation rel, *** 395,412 **** } else { ! /* ! * The sk_func needs to be passed the index value as left arg and ! * the sk_argument as right arg (they might be of different ! * types). Since it is convenient for callers to think of ! * _bt_compare as comparing the scankey to the index item, we have ! * to flip the sign of the comparison result. (Unless it's a DESC ! * column, in which case we *don't* flip the sign.) ! */ ! result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func, ! scankey->sk_collation, ! datum, ! scankey->sk_argument)); if (!(scankey->sk_flags & SK_BT_DESC)) result = -result; --- 416,448 ---- } else { ! if (scankey->sk_func.fn_oid == 351) ! { ! int32 a = DatumGetInt32(datum); ! int32 b = DatumGetInt32(scankey->sk_argument); ! ! if (a > b) ! result = Int32GetDatum(1); ! else if (a == b) ! result = Int32GetDatum(0); ! else ! result = Int32GetDatum(-1); ! } ! else ! { ! /* ! * The sk_func needs to be passed the index value as left arg and ! * the sk_argument as right arg (they might be of different ! * types). Since it is convenient for callers to think of ! * _bt_compare as comparing the scankey to the index item, we have ! * to flip the sign of the comparison result. (Unless it's a DESC ! * column, in which case we *don't* flip the sign.) ! */ ! result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func, ! scankey->sk_collation, ! datum, ! scankey->sk_argument)); ! } if (!(scankey->sk_flags & SK_BT_DESC)) result = -result; *************** _bt_first(IndexScanDesc scan, ScanDirect *** 803,809 **** * where we need to start the scan, and set flag variables to control the * code below. * ! * If nextkey = false, _bt_search and _bt_binsrch will locate the first * item >= scan key. If nextkey = true, they will locate the first * item > scan key. * --- 839,845 ---- * where we need to start the scan, and set flag variables to control the * code below. * ! * If nextkey = false, _bt_search and _bt_page_srch will locate the first * item >= scan key. If nextkey = true, they will locate the first * item > scan key. * *************** _bt_first(IndexScanDesc scan, ScanDirect *** 929,935 **** so->markItemIndex = -1; /* ditto */ /* position to the precise item on the page */ ! offnum = _bt_binsrch(rel, buf, keysCount, scankeys, nextkey); /* * If nextkey = false, we are positioned at the first item >= scan key, or --- 965,971 ---- so->markItemIndex = -1; /* ditto */ /* position to the precise item on the page */ ! offnum = _bt_page_srch(rel, buf, keysCount, scankeys, nextkey); /* * If nextkey = false, we are positioned at the first item >= scan key, or *************** _bt_next(IndexScanDesc scan, ScanDirecti *** 1038,1043 **** --- 1074,1207 ---- } /* + * Returns offset to smallest Fibonacci number greater than or equal to a max + * offset value. (e.g. if 12 is passed, 7 is returned, which can be subscripted + * to obtain the 8th number in the sequence, 13). + */ + static int + _bt_getfibnumber(OffsetNumber pagehigh) + { + static const int nfibs = sizeof(fibonacci) / sizeof(OffsetNumber); + + int low, mid, high, geq; + + low = 0; + high = nfibs - 1; + geq = -1; + + if (pagehigh <= 1) + return 1; + + /* Perform simple binary search */ + while (low <= high) + { + mid = (low + high) / 2; + + if (pagehigh < fibonacci[mid]) + { + high = mid - 1; + geq = mid; + } + else if (pagehigh > fibonacci[mid]) + low = mid + 1; + else + return mid; + } + + if (geq == -1) + elog(ERROR, "could not find fibonacci number for offset %d", pagehigh); + + /* Return smallest index greater than or equal to pagehigh */ + return geq; + } + + /* + * Fibonacci search for a key on a particular page. + * + * This is often preferred over the binary search otherwise performed by + * _bt_page_srch, because it is thought to take advantage of CPU cache + * characteristics. However, it is only safe to call this function for the + * nextkey case (i.e. when searching for the first item >= scankey). + */ + static int + _bt_fib_srch(Relation rel, int keysz, ScanKey scankey, Page page, + int low, int high) + { + int32 result; + int k; /* Kth fib number < high */ + static int prevk = -1; /* Previous k, cached */ + static int prevhigh = -1; /* Previous val, cached for re-use */ + int idx = 0, offs = 0, last; + + /* + * Find value cached in static memory, or search for value and cache it + * there for his high. + */ + if (high != prevhigh) + { + prevk = k = _bt_getfibnumber(high); + prevhigh = high; + } + else + { + high = prevhigh; + k = prevk; + Assert(k >= 1); + } + + do + { + /* Lose the greater than "high" value in first iteration */ + idx = offs + fibonacci[--k]; + + Assert(fibonacci[k] < high); + Assert(low < high); + + if (idx < low) + { + /* val in 2nd part */ + offs = low; + --k; + continue; + } + else if (idx >= high) /* Went too far */ + continue; + + result = _bt_compare(rel, keysz, scankey, page, idx); + + /* Note that at this point k has already been decremented once */ + if (result < 0) + { + continue; + } + else if (result > 0) + { + /* val in 2nd part */ + offs = idx; + --k; + } + else + { + /* Found, but may not be the first such key */ + while (result == 0) + { + /* TODO: Think harder about many duplicates case */ + last = idx; + if (idx <= low) + return low; + result = _bt_compare(rel, keysz, scankey, page, --idx); + } + + return last; + } + } + while (k > 0); + + /* Not found */ + return idx + 1; + } + + /* * _bt_readpage() -- Load data from current index page into so->currPos * * Caller must have pinned and read-locked so->currPos.buf; the buffer's state diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h new file mode 100644 index 3997f94..dc36346 *** a/src/include/access/nbtree.h --- b/src/include/access/nbtree.h *************** extern BTStack _bt_search(Relation rel, *** 649,655 **** Buffer *bufP, int access); extern Buffer _bt_moveright(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey, int access); ! extern OffsetNumber _bt_binsrch(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey); extern int32 _bt_compare(Relation rel, int keysz, ScanKey scankey, Page page, OffsetNumber offnum); --- 649,655 ---- Buffer *bufP, int access); extern Buffer _bt_moveright(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey, int access); ! extern OffsetNumber _bt_page_srch(Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey); extern int32 _bt_compare(Relation rel, int keysz, ScanKey scankey, Page page, OffsetNumber offnum);