PostgreSQL Source Code  git master
nbtutils.c File Reference
#include "postgres.h"
#include <time.h>
#include "access/nbtree.h"
#include "access/reloptions.h"
#include "access/relscan.h"
#include "catalog/catalog.h"
#include "commands/progress.h"
#include "lib/qunique.h"
#include "miscadmin.h"
#include "utils/array.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
Include dependency graph for nbtutils.c:

Go to the source code of this file.

Data Structures

struct  BTSortArrayContext
 
struct  BTOneVacInfo
 
struct  BTVacInfo
 

Typedefs

typedef struct BTSortArrayContext BTSortArrayContext
 
typedef struct BTOneVacInfo BTOneVacInfo
 
typedef struct BTVacInfo BTVacInfo
 

Functions

static Datum _bt_find_extreme_element (IndexScanDesc scan, ScanKey skey, StrategyNumber strat, Datum *elems, int nelems)
 
static int _bt_sort_array_elements (IndexScanDesc scan, ScanKey skey, bool reverse, Datum *elems, int nelems)
 
static int _bt_compare_array_elements (const void *a, const void *b, void *arg)
 
static bool _bt_compare_scankey_args (IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, bool *result)
 
static bool _bt_fix_scankey_strategy (ScanKey skey, int16 *indoption)
 
static void _bt_mark_scankey_required (ScanKey skey)
 
static bool _bt_check_rowcompare (ScanKey skey, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
 
static int _bt_keep_natts (Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
 
BTScanInsert _bt_mkscankey (Relation rel, IndexTuple itup)
 
void _bt_freestack (BTStack stack)
 
void _bt_preprocess_array_keys (IndexScanDesc scan)
 
void _bt_start_array_keys (IndexScanDesc scan, ScanDirection dir)
 
bool _bt_advance_array_keys (IndexScanDesc scan, ScanDirection dir)
 
void _bt_mark_array_keys (IndexScanDesc scan)
 
void _bt_restore_array_keys (IndexScanDesc scan)
 
void _bt_preprocess_keys (IndexScanDesc scan)
 
bool _bt_checkkeys (IndexScanDesc scan, IndexTuple tuple, int tupnatts, ScanDirection dir, bool *continuescan, bool requiredMatchedByPrecheck)
 
void _bt_killitems (IndexScanDesc scan)
 
BTCycleId _bt_vacuum_cycleid (Relation rel)
 
BTCycleId _bt_start_vacuum (Relation rel)
 
void _bt_end_vacuum (Relation rel)
 
void _bt_end_vacuum_callback (int code, Datum arg)
 
Size BTreeShmemSize (void)
 
void BTreeShmemInit (void)
 
byteabtoptions (Datum reloptions, bool validate)
 
bool btproperty (Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
 
char * btbuildphasename (int64 phasenum)
 
IndexTuple _bt_truncate (Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
 
int _bt_keep_natts_fast (Relation rel, IndexTuple lastleft, IndexTuple firstright)
 
bool _bt_check_natts (Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
 
void _bt_check_third_page (Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
 
bool _bt_allequalimage (Relation rel, bool debugmessage)
 

Variables

static BTVacInfobtvacinfo
 

Typedef Documentation

◆ BTOneVacInfo

typedef struct BTOneVacInfo BTOneVacInfo

◆ BTSortArrayContext

◆ BTVacInfo

typedef struct BTVacInfo BTVacInfo

Function Documentation

◆ _bt_advance_array_keys()

bool _bt_advance_array_keys ( IndexScanDesc  scan,
ScanDirection  dir 
)

Definition at line 545 of file nbtutils.c.

546 {
547  BTScanOpaque so = (BTScanOpaque) scan->opaque;
548  bool found = false;
549  int i;
550 
551  /*
552  * We must advance the last array key most quickly, since it will
553  * correspond to the lowest-order index column among the available
554  * qualifications. This is necessary to ensure correct ordering of output
555  * when there are multiple array keys.
556  */
557  for (i = so->numArrayKeys - 1; i >= 0; i--)
558  {
559  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
560  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
561  int cur_elem = curArrayKey->cur_elem;
562  int num_elems = curArrayKey->num_elems;
563 
564  if (ScanDirectionIsBackward(dir))
565  {
566  if (--cur_elem < 0)
567  {
568  cur_elem = num_elems - 1;
569  found = false; /* need to advance next array key */
570  }
571  else
572  found = true;
573  }
574  else
575  {
576  if (++cur_elem >= num_elems)
577  {
578  cur_elem = 0;
579  found = false; /* need to advance next array key */
580  }
581  else
582  found = true;
583  }
584 
585  curArrayKey->cur_elem = cur_elem;
586  skey->sk_argument = curArrayKey->elem_values[cur_elem];
587  if (found)
588  break;
589  }
590 
591  /* advance parallel scan */
592  if (scan->parallel_scan != NULL)
594 
595  /*
596  * When no new array keys were found, the scan is "past the end" of the
597  * array keys. _bt_start_array_keys can still "restart" the array keys if
598  * a rescan is required.
599  */
600  if (!found)
601  so->arraysStarted = false;
602 
603  return found;
604 }
int i
Definition: isn.c:73
void _bt_parallel_advance_array_keys(IndexScanDesc scan)
Definition: nbtree.c:764
BTScanOpaqueData * BTScanOpaque
Definition: nbtree.h:1079
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
Datum * elem_values
Definition: nbtree.h:1029
BTArrayKeyInfo * arrayKeys
Definition: nbtree.h:1047
bool arraysStarted
Definition: nbtree.h:1041
ScanKey arrayKeyData
Definition: nbtree.h:1040
struct ParallelIndexScanDescData * parallel_scan
Definition: relscan.h:166
Datum sk_argument
Definition: skey.h:72

References _bt_parallel_advance_array_keys(), BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, BTScanOpaqueData::arraysStarted, BTArrayKeyInfo::cur_elem, BTArrayKeyInfo::elem_values, i, BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, BTArrayKeyInfo::scan_key, ScanDirectionIsBackward, and ScanKeyData::sk_argument.

Referenced by btgetbitmap(), and btgettuple().

◆ _bt_allequalimage()

bool _bt_allequalimage ( Relation  rel,
bool  debugmessage 
)

Definition at line 2729 of file nbtutils.c.

2730 {
2731  bool allequalimage = true;
2732 
2733  /* INCLUDE indexes can never support deduplication */
2736  return false;
2737 
2738  for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
2739  {
2740  Oid opfamily = rel->rd_opfamily[i];
2741  Oid opcintype = rel->rd_opcintype[i];
2742  Oid collation = rel->rd_indcollation[i];
2743  Oid equalimageproc;
2744 
2745  equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
2747 
2748  /*
2749  * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
2750  * be unsafe. Otherwise, actually call proc and see what it says.
2751  */
2752  if (!OidIsValid(equalimageproc) ||
2753  !DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
2754  ObjectIdGetDatum(opcintype))))
2755  {
2756  allequalimage = false;
2757  break;
2758  }
2759  }
2760 
2761  if (debugmessage)
2762  {
2763  if (allequalimage)
2764  elog(DEBUG1, "index \"%s\" can safely use deduplication",
2766  else
2767  elog(DEBUG1, "index \"%s\" cannot use deduplication",
2769  }
2770 
2771  return allequalimage;
2772 }
#define OidIsValid(objectId)
Definition: c.h:764
#define DEBUG1
Definition: elog.h:30
Datum OidFunctionCall1Coll(Oid functionId, Oid collation, Datum arg1)
Definition: fmgr.c:1411
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition: lsyscache.c:795
#define BTEQUALIMAGE_PROC
Definition: nbtree.h:710
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
static Datum ObjectIdGetDatum(Oid X)
Definition: postgres.h:252
unsigned int Oid
Definition: postgres_ext.h:31
#define RelationGetRelationName(relation)
Definition: rel.h:538
#define IndexRelationGetNumberOfAttributes(relation)
Definition: rel.h:516
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:523
Oid * rd_opcintype
Definition: rel.h:207
Oid * rd_opfamily
Definition: rel.h:206
Oid * rd_indcollation
Definition: rel.h:216

References BTEQUALIMAGE_PROC, DatumGetBool(), DEBUG1, elog(), get_opfamily_proc(), i, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, ObjectIdGetDatum(), OidFunctionCall1Coll(), OidIsValid, RelationData::rd_indcollation, RelationData::rd_opcintype, RelationData::rd_opfamily, and RelationGetRelationName.

Referenced by _bt_leafbuild(), bt_index_check_internal(), and btbuildempty().

◆ _bt_check_natts()

bool _bt_check_natts ( Relation  rel,
bool  heapkeyspace,
Page  page,
OffsetNumber  offnum 
)

Definition at line 2511 of file nbtutils.c.

2512 {
2515  BTPageOpaque opaque = BTPageGetOpaque(page);
2516  IndexTuple itup;
2517  int tupnatts;
2518 
2519  /*
2520  * We cannot reliably test a deleted or half-dead page, since they have
2521  * dummy high keys
2522  */
2523  if (P_IGNORE(opaque))
2524  return true;
2525 
2526  Assert(offnum >= FirstOffsetNumber &&
2527  offnum <= PageGetMaxOffsetNumber(page));
2528 
2529  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
2530  tupnatts = BTreeTupleGetNAtts(itup, rel);
2531 
2532  /* !heapkeyspace indexes do not support deduplication */
2533  if (!heapkeyspace && BTreeTupleIsPosting(itup))
2534  return false;
2535 
2536  /* Posting list tuples should never have "pivot heap TID" bit set */
2537  if (BTreeTupleIsPosting(itup) &&
2539  BT_PIVOT_HEAP_TID_ATTR) != 0)
2540  return false;
2541 
2542  /* INCLUDE indexes do not support deduplication */
2543  if (natts != nkeyatts && BTreeTupleIsPosting(itup))
2544  return false;
2545 
2546  if (P_ISLEAF(opaque))
2547  {
2548  if (offnum >= P_FIRSTDATAKEY(opaque))
2549  {
2550  /*
2551  * Non-pivot tuple should never be explicitly marked as a pivot
2552  * tuple
2553  */
2554  if (BTreeTupleIsPivot(itup))
2555  return false;
2556 
2557  /*
2558  * Leaf tuples that are not the page high key (non-pivot tuples)
2559  * should never be truncated. (Note that tupnatts must have been
2560  * inferred, even with a posting list tuple, because only pivot
2561  * tuples store tupnatts directly.)
2562  */
2563  return tupnatts == natts;
2564  }
2565  else
2566  {
2567  /*
2568  * Rightmost page doesn't contain a page high key, so tuple was
2569  * checked above as ordinary leaf tuple
2570  */
2571  Assert(!P_RIGHTMOST(opaque));
2572 
2573  /*
2574  * !heapkeyspace high key tuple contains only key attributes. Note
2575  * that tupnatts will only have been explicitly represented in
2576  * !heapkeyspace indexes that happen to have non-key attributes.
2577  */
2578  if (!heapkeyspace)
2579  return tupnatts == nkeyatts;
2580 
2581  /* Use generic heapkeyspace pivot tuple handling */
2582  }
2583  }
2584  else /* !P_ISLEAF(opaque) */
2585  {
2586  if (offnum == P_FIRSTDATAKEY(opaque))
2587  {
2588  /*
2589  * The first tuple on any internal page (possibly the first after
2590  * its high key) is its negative infinity tuple. Negative
2591  * infinity tuples are always truncated to zero attributes. They
2592  * are a particular kind of pivot tuple.
2593  */
2594  if (heapkeyspace)
2595  return tupnatts == 0;
2596 
2597  /*
2598  * The number of attributes won't be explicitly represented if the
2599  * negative infinity tuple was generated during a page split that
2600  * occurred with a version of Postgres before v11. There must be
2601  * a problem when there is an explicit representation that is
2602  * non-zero, or when there is no explicit representation and the
2603  * tuple is evidently not a pre-pg_upgrade tuple.
2604  *
2605  * Prior to v11, downlinks always had P_HIKEY as their offset.
2606  * Accept that as an alternative indication of a valid
2607  * !heapkeyspace negative infinity tuple.
2608  */
2609  return tupnatts == 0 ||
2611  }
2612  else
2613  {
2614  /*
2615  * !heapkeyspace downlink tuple with separator key contains only
2616  * key attributes. Note that tupnatts will only have been
2617  * explicitly represented in !heapkeyspace indexes that happen to
2618  * have non-key attributes.
2619  */
2620  if (!heapkeyspace)
2621  return tupnatts == nkeyatts;
2622 
2623  /* Use generic heapkeyspace pivot tuple handling */
2624  }
2625  }
2626 
2627  /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
2628  Assert(heapkeyspace);
2629 
2630  /*
2631  * Explicit representation of the number of attributes is mandatory with
2632  * heapkeyspace index pivot tuples, regardless of whether or not there are
2633  * non-key attributes.
2634  */
2635  if (!BTreeTupleIsPivot(itup))
2636  return false;
2637 
2638  /* Pivot tuple should not use posting list representation (redundant) */
2639  if (BTreeTupleIsPosting(itup))
2640  return false;
2641 
2642  /*
2643  * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
2644  * when any other key attribute is truncated
2645  */
2646  if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts)
2647  return false;
2648 
2649  /*
2650  * Pivot tuple must have at least one untruncated key attribute (minus
2651  * infinity pivot tuples are the only exception). Pivot tuples can never
2652  * represent that there is a value present for a key attribute that
2653  * exceeds pg_index.indnkeyatts for the index.
2654  */
2655  return tupnatts > 0 && tupnatts <= nkeyatts;
2656 }
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
signed short int16
Definition: c.h:482
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static OffsetNumber ItemPointerGetOffsetNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:114
IndexTupleData * IndexTuple
Definition: itup.h:53
Assert(fmt[strlen(fmt) - 1] !='\n')
#define BT_PIVOT_HEAP_TID_ATTR
Definition: nbtree.h:465
static bool BTreeTupleIsPivot(IndexTuple itup)
Definition: nbtree.h:480
#define P_ISLEAF(opaque)
Definition: nbtree.h:220
#define P_HIKEY
Definition: nbtree.h:367
#define BTPageGetOpaque(page)
Definition: nbtree.h:73
#define P_FIRSTDATAKEY(opaque)
Definition: nbtree.h:369
#define P_RIGHTMOST(opaque)
Definition: nbtree.h:219
#define P_IGNORE(opaque)
Definition: nbtree.h:225
static bool BTreeTupleIsPosting(IndexTuple itup)
Definition: nbtree.h:492
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:638
#define BTreeTupleGetNAtts(itup, rel)
Definition: nbtree.h:577
#define FirstOffsetNumber
Definition: off.h:27
ItemPointerData t_tid
Definition: itup.h:37

References Assert(), BT_PIVOT_HEAP_TID_ATTR, BTPageGetOpaque, BTreeTupleGetHeapTID(), BTreeTupleGetNAtts, BTreeTupleIsPivot(), BTreeTupleIsPosting(), FirstOffsetNumber, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, ItemPointerGetOffsetNumber(), ItemPointerGetOffsetNumberNoCheck(), P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and IndexTupleData::t_tid.

Referenced by _bt_compare(), and bt_target_page_check().

◆ _bt_check_rowcompare()

static bool _bt_check_rowcompare ( ScanKey  skey,
IndexTuple  tuple,
int  tupnatts,
TupleDesc  tupdesc,
ScanDirection  dir,
bool continuescan 
)
static

Definition at line 1569 of file nbtutils.c.

1571 {
1572  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1573  int32 cmpresult = 0;
1574  bool result;
1575 
1576  /* First subkey should be same as the header says */
1577  Assert(subkey->sk_attno == skey->sk_attno);
1578 
1579  /* Loop over columns of the row condition */
1580  for (;;)
1581  {
1582  Datum datum;
1583  bool isNull;
1584 
1585  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1586 
1587  if (subkey->sk_attno > tupnatts)
1588  {
1589  /*
1590  * This attribute is truncated (must be high key). The value for
1591  * this attribute in the first non-pivot tuple on the page to the
1592  * right could be any possible value. Assume that truncated
1593  * attribute passes the qual.
1594  */
1596  Assert(BTreeTupleIsPivot(tuple));
1597  cmpresult = 0;
1598  if (subkey->sk_flags & SK_ROW_END)
1599  break;
1600  subkey++;
1601  continue;
1602  }
1603 
1604  datum = index_getattr(tuple,
1605  subkey->sk_attno,
1606  tupdesc,
1607  &isNull);
1608 
1609  if (isNull)
1610  {
1611  if (subkey->sk_flags & SK_BT_NULLS_FIRST)
1612  {
1613  /*
1614  * Since NULLs are sorted before non-NULLs, we know we have
1615  * reached the lower limit of the range of values for this
1616  * index attr. On a backward scan, we can stop if this qual
1617  * is one of the "must match" subset. We can stop regardless
1618  * of whether the qual is > or <, so long as it's required,
1619  * because it's not possible for any future tuples to pass. On
1620  * a forward scan, however, we must keep going, because we may
1621  * have initially positioned to the start of the index.
1622  */
1623  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1625  *continuescan = false;
1626  }
1627  else
1628  {
1629  /*
1630  * Since NULLs are sorted after non-NULLs, we know we have
1631  * reached the upper limit of the range of values for this
1632  * index attr. On a forward scan, we can stop if this qual is
1633  * one of the "must match" subset. We can stop regardless of
1634  * whether the qual is > or <, so long as it's required,
1635  * because it's not possible for any future tuples to pass. On
1636  * a backward scan, however, we must keep going, because we
1637  * may have initially positioned to the end of the index.
1638  */
1639  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1641  *continuescan = false;
1642  }
1643 
1644  /*
1645  * In any case, this indextuple doesn't match the qual.
1646  */
1647  return false;
1648  }
1649 
1650  if (subkey->sk_flags & SK_ISNULL)
1651  {
1652  /*
1653  * Unlike the simple-scankey case, this isn't a disallowed case.
1654  * But it can never match. If all the earlier row comparison
1655  * columns are required for the scan direction, we can stop the
1656  * scan, because there can't be another tuple that will succeed.
1657  */
1658  if (subkey != (ScanKey) DatumGetPointer(skey->sk_argument))
1659  subkey--;
1660  if ((subkey->sk_flags & SK_BT_REQFWD) &&
1662  *continuescan = false;
1663  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
1665  *continuescan = false;
1666  return false;
1667  }
1668 
1669  /* Perform the test --- three-way comparison not bool operator */
1670  cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func,
1671  subkey->sk_collation,
1672  datum,
1673  subkey->sk_argument));
1674 
1675  if (subkey->sk_flags & SK_BT_DESC)
1676  INVERT_COMPARE_RESULT(cmpresult);
1677 
1678  /* Done comparing if unequal, else advance to next column */
1679  if (cmpresult != 0)
1680  break;
1681 
1682  if (subkey->sk_flags & SK_ROW_END)
1683  break;
1684  subkey++;
1685  }
1686 
1687  /*
1688  * At this point cmpresult indicates the overall result of the row
1689  * comparison, and subkey points to the deciding column (or the last
1690  * column if the result is "=").
1691  */
1692  switch (subkey->sk_strategy)
1693  {
1694  /* EQ and NE cases aren't allowed here */
1695  case BTLessStrategyNumber:
1696  result = (cmpresult < 0);
1697  break;
1699  result = (cmpresult <= 0);
1700  break;
1702  result = (cmpresult >= 0);
1703  break;
1705  result = (cmpresult > 0);
1706  break;
1707  default:
1708  elog(ERROR, "unrecognized RowCompareType: %d",
1709  (int) subkey->sk_strategy);
1710  result = 0; /* keep compiler quiet */
1711  break;
1712  }
1713 
1714  if (!result)
1715  {
1716  /*
1717  * Tuple fails this qual. If it's a required qual for the current
1718  * scan direction, then we can conclude no further tuples will pass,
1719  * either. Note we have to look at the deciding column, not
1720  * necessarily the first or last column of the row condition.
1721  */
1722  if ((subkey->sk_flags & SK_BT_REQFWD) &&
1724  *continuescan = false;
1725  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
1727  *continuescan = false;
1728  }
1729 
1730  return result;
1731 }
#define INVERT_COMPARE_RESULT(var)
Definition: c.h:1119
signed int int32
Definition: c.h:483
#define ERROR
Definition: elog.h:39
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1149
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:117
#define SK_BT_REQBKWD
Definition: nbtree.h:1087
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1090
#define SK_BT_REQFWD
Definition: nbtree.h:1086
#define SK_BT_DESC
Definition: nbtree.h:1089
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:202
#define ScanDirectionIsForward(direction)
Definition: sdir.h:64
#define SK_ROW_MEMBER
Definition: skey.h:118
#define SK_ROW_END
Definition: skey.h:119
ScanKeyData * ScanKey
Definition: skey.h:75
#define SK_ISNULL
Definition: skey.h:115
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
int sk_flags
Definition: skey.h:66
FmgrInfo sk_func
Definition: skey.h:71
Oid sk_collation
Definition: skey.h:70
StrategyNumber sk_strategy
Definition: skey.h:68
AttrNumber sk_attno
Definition: skey.h:67

References Assert(), BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTreeTupleIsPivot(), DatumGetInt32(), DatumGetPointer(), elog(), ERROR, FunctionCall2Coll(), index_getattr(), INVERT_COMPARE_RESULT, ScanDirectionIsBackward, ScanDirectionIsForward, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, SK_BT_REQBKWD, SK_BT_REQFWD, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, SK_ROW_END, SK_ROW_MEMBER, and ScanKeyData::sk_strategy.

Referenced by _bt_checkkeys().

◆ _bt_check_third_page()

void _bt_check_third_page ( Relation  rel,
Relation  heap,
bool  needheaptidspace,
Page  page,
IndexTuple  newtup 
)

Definition at line 2671 of file nbtutils.c.

2673 {
2674  Size itemsz;
2675  BTPageOpaque opaque;
2676 
2677  itemsz = MAXALIGN(IndexTupleSize(newtup));
2678 
2679  /* Double check item size against limit */
2680  if (itemsz <= BTMaxItemSize(page))
2681  return;
2682 
2683  /*
2684  * Tuple is probably too large to fit on page, but it's possible that the
2685  * index uses version 2 or version 3, or that page is an internal page, in
2686  * which case a slightly higher limit applies.
2687  */
2688  if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid(page))
2689  return;
2690 
2691  /*
2692  * Internal page insertions cannot fail here, because that would mean that
2693  * an earlier leaf level insertion that should have failed didn't
2694  */
2695  opaque = BTPageGetOpaque(page);
2696  if (!P_ISLEAF(opaque))
2697  elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"",
2698  itemsz, RelationGetRelationName(rel));
2699 
2700  ereport(ERROR,
2701  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2702  errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"",
2703  itemsz,
2704  needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION,
2705  needheaptidspace ? BTMaxItemSize(page) :
2706  BTMaxItemSizeNoHeapTid(page),
2708  errdetail("Index row references tuple (%u,%u) in relation \"%s\".",
2711  RelationGetRelationName(heap)),
2712  errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n"
2713  "Consider a function index of an MD5 hash of the value, "
2714  "or use full text indexing."),
2716 }
#define MAXALIGN(LEN)
Definition: c.h:800
size_t Size
Definition: c.h:594
int errdetail(const char *fmt,...)
Definition: elog.c:1202
int errhint(const char *fmt,...)
Definition: elog.c:1316
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define ereport(elevel,...)
Definition: elog.h:149
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
#define IndexTupleSize(itup)
Definition: itup.h:70
#define BTMaxItemSizeNoHeapTid(page)
Definition: nbtree.h:169
#define BTREE_VERSION
Definition: nbtree.h:150
#define BTMaxItemSize(page)
Definition: nbtree.h:164
#define BTREE_NOVAC_VERSION
Definition: nbtree.h:152
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5993

References BTMaxItemSize, BTMaxItemSizeNoHeapTid, BTPageGetOpaque, BTREE_NOVAC_VERSION, BTREE_VERSION, BTreeTupleGetHeapTID(), elog(), ereport, errcode(), errdetail(), errhint(), errmsg(), ERROR, errtableconstraint(), IndexTupleSize, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), MAXALIGN, P_ISLEAF, and RelationGetRelationName.

Referenced by _bt_buildadd(), and _bt_findinsertloc().

◆ _bt_checkkeys()

bool _bt_checkkeys ( IndexScanDesc  scan,
IndexTuple  tuple,
int  tupnatts,
ScanDirection  dir,
bool continuescan,
bool  requiredMatchedByPrecheck 
)

Definition at line 1371 of file nbtutils.c.

1374 {
1375  TupleDesc tupdesc;
1376  BTScanOpaque so;
1377  int keysz;
1378  int ikey;
1379  ScanKey key;
1380 
1381  Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
1382 
1383  *continuescan = true; /* default assumption */
1384 
1385  tupdesc = RelationGetDescr(scan->indexRelation);
1386  so = (BTScanOpaque) scan->opaque;
1387  keysz = so->numberOfKeys;
1388 
1389  for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
1390  {
1391  Datum datum;
1392  bool isNull;
1393  Datum test;
1394  bool requiredSameDir = false,
1395  requiredOppositeDir = false;
1396 
1397  /*
1398  * Check if the key is required for ordered scan in the same or
1399  * opposite direction. Save as flag variables for future usage.
1400  */
1401  if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
1402  ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
1403  requiredSameDir = true;
1404  else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) ||
1405  ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir)))
1406  requiredOppositeDir = true;
1407 
1408  /*
1409  * Is the key required for scanning for either forward or backward
1410  * direction? If so and caller told us that these types of keys are
1411  * known to be matched, skip the check. Except for the row keys,
1412  * where NULLs could be found in the middle of matching values.
1413  */
1414  if ((requiredSameDir || requiredOppositeDir) &&
1415  !(key->sk_flags & SK_ROW_HEADER) && requiredMatchedByPrecheck)
1416  continue;
1417 
1418  if (key->sk_attno > tupnatts)
1419  {
1420  /*
1421  * This attribute is truncated (must be high key). The value for
1422  * this attribute in the first non-pivot tuple on the page to the
1423  * right could be any possible value. Assume that truncated
1424  * attribute passes the qual.
1425  */
1427  Assert(BTreeTupleIsPivot(tuple));
1428  continue;
1429  }
1430 
1431  /* row-comparison keys need special processing */
1432  if (key->sk_flags & SK_ROW_HEADER)
1433  {
1434  if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir,
1435  continuescan))
1436  continue;
1437  return false;
1438  }
1439 
1440  datum = index_getattr(tuple,
1441  key->sk_attno,
1442  tupdesc,
1443  &isNull);
1444 
1445  if (key->sk_flags & SK_ISNULL)
1446  {
1447  /* Handle IS NULL/NOT NULL tests */
1448  if (key->sk_flags & SK_SEARCHNULL)
1449  {
1450  if (isNull)
1451  continue; /* tuple satisfies this qual */
1452  }
1453  else
1454  {
1455  Assert(key->sk_flags & SK_SEARCHNOTNULL);
1456  if (!isNull)
1457  continue; /* tuple satisfies this qual */
1458  }
1459 
1460  /*
1461  * Tuple fails this qual. If it's a required qual for the current
1462  * scan direction, then we can conclude no further tuples will
1463  * pass, either.
1464  */
1465  if (requiredSameDir)
1466  *continuescan = false;
1467 
1468  /*
1469  * In any case, this indextuple doesn't match the qual.
1470  */
1471  return false;
1472  }
1473 
1474  if (isNull)
1475  {
1476  if (key->sk_flags & SK_BT_NULLS_FIRST)
1477  {
1478  /*
1479  * Since NULLs are sorted before non-NULLs, we know we have
1480  * reached the lower limit of the range of values for this
1481  * index attr. On a backward scan, we can stop if this qual
1482  * is one of the "must match" subset. We can stop regardless
1483  * of whether the qual is > or <, so long as it's required,
1484  * because it's not possible for any future tuples to pass. On
1485  * a forward scan, however, we must keep going, because we may
1486  * have initially positioned to the start of the index.
1487  */
1488  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1490  *continuescan = false;
1491  }
1492  else
1493  {
1494  /*
1495  * Since NULLs are sorted after non-NULLs, we know we have
1496  * reached the upper limit of the range of values for this
1497  * index attr. On a forward scan, we can stop if this qual is
1498  * one of the "must match" subset. We can stop regardless of
1499  * whether the qual is > or <, so long as it's required,
1500  * because it's not possible for any future tuples to pass. On
1501  * a backward scan, however, we must keep going, because we
1502  * may have initially positioned to the end of the index.
1503  */
1504  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1506  *continuescan = false;
1507  }
1508 
1509  /*
1510  * In any case, this indextuple doesn't match the qual.
1511  */
1512  return false;
1513  }
1514 
1515  /*
1516  * Apply the key checking function. When the key is required for
1517  * opposite direction scan, it must be already satisfied by
1518  * _bt_first() except for the NULLs checking, which have already done
1519  * above.
1520  */
1521  if (!requiredOppositeDir)
1522  {
1523  test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
1524  datum, key->sk_argument);
1525  }
1526  else
1527  {
1528  test = true;
1529  Assert(test == FunctionCall2Coll(&key->sk_func, key->sk_collation,
1530  datum, key->sk_argument));
1531  }
1532 
1533  if (!DatumGetBool(test))
1534  {
1535  /*
1536  * Tuple fails this qual. If it's a required qual for the current
1537  * scan direction, then we can conclude no further tuples will
1538  * pass, either.
1539  *
1540  * Note: because we stop the scan as soon as any required equality
1541  * qual fails, it is critical that equality quals be used for the
1542  * initial positioning in _bt_first() when they are available. See
1543  * comments in _bt_first().
1544  */
1545  if (requiredSameDir)
1546  *continuescan = false;
1547 
1548  /*
1549  * In any case, this indextuple doesn't match the qual.
1550  */
1551  return false;
1552  }
1553  }
1554 
1555  /* If we get here, the tuple passes all index quals. */
1556  return true;
1557 }
static bool _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
Definition: nbtutils.c:1569
static void test(void)
#define RelationGetDescr(relation)
Definition: rel.h:530
#define SK_ROW_HEADER
Definition: skey.h:117
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define SK_SEARCHNULL
Definition: skey.h:121
ScanKey keyData
Definition: nbtree.h:1037
Relation indexRelation
Definition: relscan.h:118

References _bt_check_rowcompare(), Assert(), BTreeTupleGetNAtts, BTreeTupleIsPivot(), DatumGetBool(), FunctionCall2Coll(), index_getattr(), IndexScanDescData::indexRelation, sort-test::key, BTScanOpaqueData::keyData, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, RelationGetDescr, ScanDirectionIsBackward, ScanDirectionIsForward, SK_BT_NULLS_FIRST, SK_BT_REQBKWD, SK_BT_REQFWD, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHNOTNULL, SK_SEARCHNULL, and test().

Referenced by _bt_readpage().

◆ _bt_compare_array_elements()

static int _bt_compare_array_elements ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 495 of file nbtutils.c.

496 {
497  Datum da = *((const Datum *) a);
498  Datum db = *((const Datum *) b);
500  int32 compare;
501 
503  cxt->collation,
504  da, db));
505  if (cxt->reverse)
507  return compare;
508 }
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
int b
Definition: isn.c:70
int a
Definition: isn.c:69
void * arg
FmgrInfo flinfo
Definition: nbtutils.c:36

References a, arg, b, BTSortArrayContext::collation, compare(), DatumGetInt32(), BTSortArrayContext::flinfo, FunctionCall2Coll(), INVERT_COMPARE_RESULT, and BTSortArrayContext::reverse.

Referenced by _bt_sort_array_elements().

◆ _bt_compare_scankey_args()

static bool _bt_compare_scankey_args ( IndexScanDesc  scan,
ScanKey  op,
ScanKey  leftarg,
ScanKey  rightarg,
bool result 
)
static

Definition at line 1046 of file nbtutils.c.

1049 {
1050  Relation rel = scan->indexRelation;
1051  Oid lefttype,
1052  righttype,
1053  optype,
1054  opcintype,
1055  cmp_op;
1056  StrategyNumber strat;
1057 
1058  /*
1059  * First, deal with cases where one or both args are NULL. This should
1060  * only happen when the scankeys represent IS NULL/NOT NULL conditions.
1061  */
1062  if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
1063  {
1064  bool leftnull,
1065  rightnull;
1066 
1067  if (leftarg->sk_flags & SK_ISNULL)
1068  {
1070  leftnull = true;
1071  }
1072  else
1073  leftnull = false;
1074  if (rightarg->sk_flags & SK_ISNULL)
1075  {
1076  Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
1077  rightnull = true;
1078  }
1079  else
1080  rightnull = false;
1081 
1082  /*
1083  * We treat NULL as either greater than or less than all other values.
1084  * Since true > false, the tests below work correctly for NULLS LAST
1085  * logic. If the index is NULLS FIRST, we need to flip the strategy.
1086  */
1087  strat = op->sk_strategy;
1088  if (op->sk_flags & SK_BT_NULLS_FIRST)
1089  strat = BTCommuteStrategyNumber(strat);
1090 
1091  switch (strat)
1092  {
1093  case BTLessStrategyNumber:
1094  *result = (leftnull < rightnull);
1095  break;
1097  *result = (leftnull <= rightnull);
1098  break;
1099  case BTEqualStrategyNumber:
1100  *result = (leftnull == rightnull);
1101  break;
1103  *result = (leftnull >= rightnull);
1104  break;
1106  *result = (leftnull > rightnull);
1107  break;
1108  default:
1109  elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
1110  *result = false; /* keep compiler quiet */
1111  break;
1112  }
1113  return true;
1114  }
1115 
1116  /*
1117  * The opfamily we need to worry about is identified by the index column.
1118  */
1119  Assert(leftarg->sk_attno == rightarg->sk_attno);
1120 
1121  opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
1122 
1123  /*
1124  * Determine the actual datatypes of the ScanKey arguments. We have to
1125  * support the convention that sk_subtype == InvalidOid means the opclass
1126  * input type; this is a hack to simplify life for ScanKeyInit().
1127  */
1128  lefttype = leftarg->sk_subtype;
1129  if (lefttype == InvalidOid)
1130  lefttype = opcintype;
1131  righttype = rightarg->sk_subtype;
1132  if (righttype == InvalidOid)
1133  righttype = opcintype;
1134  optype = op->sk_subtype;
1135  if (optype == InvalidOid)
1136  optype = opcintype;
1137 
1138  /*
1139  * If leftarg and rightarg match the types expected for the "op" scankey,
1140  * we can use its already-looked-up comparison function.
1141  */
1142  if (lefttype == opcintype && righttype == optype)
1143  {
1144  *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
1145  op->sk_collation,
1146  leftarg->sk_argument,
1147  rightarg->sk_argument));
1148  return true;
1149  }
1150 
1151  /*
1152  * Otherwise, we need to go to the syscache to find the appropriate
1153  * operator. (This cannot result in infinite recursion, since no
1154  * indexscan initiated by syscache lookup will use cross-data-type
1155  * operators.)
1156  *
1157  * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
1158  * un-flip it to get the correct opfamily member.
1159  */
1160  strat = op->sk_strategy;
1161  if (op->sk_flags & SK_BT_DESC)
1162  strat = BTCommuteStrategyNumber(strat);
1163 
1164  cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
1165  lefttype,
1166  righttype,
1167  strat);
1168  if (OidIsValid(cmp_op))
1169  {
1170  RegProcedure cmp_proc = get_opcode(cmp_op);
1171 
1172  if (RegProcedureIsValid(cmp_proc))
1173  {
1174  *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
1175  op->sk_collation,
1176  leftarg->sk_argument,
1177  rightarg->sk_argument));
1178  return true;
1179  }
1180  }
1181 
1182  /* Can't make the comparison */
1183  *result = false; /* suppress compiler warnings */
1184  return false;
1185 }
#define RegProcedureIsValid(p)
Definition: c.h:766
regproc RegProcedure
Definition: c.h:639
Datum OidFunctionCall2Coll(Oid functionId, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1421
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1289
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:165
#define BTCommuteStrategyNumber(strat)
Definition: nbtree.h:685
#define InvalidOid
Definition: postgres_ext.h:36
uint16 StrategyNumber
Definition: stratnum.h:22
#define BTEqualStrategyNumber
Definition: stratnum.h:31
Oid sk_subtype
Definition: skey.h:69

References Assert(), BTCommuteStrategyNumber, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, DatumGetBool(), elog(), ERROR, FunctionCall2Coll(), get_opcode(), get_opfamily_member(), IndexScanDescData::indexRelation, InvalidOid, OidFunctionCall2Coll(), OidIsValid, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, SK_SEARCHNOTNULL, SK_SEARCHNULL, ScanKeyData::sk_strategy, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_keys().

◆ _bt_end_vacuum()

void _bt_end_vacuum ( Relation  rel)

Definition at line 2073 of file nbtutils.c.

2074 {
2075  int i;
2076 
2077  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
2078 
2079  /* Find the array entry */
2080  for (i = 0; i < btvacinfo->num_vacuums; i++)
2081  {
2082  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
2083 
2084  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
2085  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
2086  {
2087  /* Remove it by shifting down the last entry */
2088  *vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1];
2090  break;
2091  }
2092  }
2093 
2094  LWLockRelease(BtreeVacuumLock);
2095 }
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1195
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1808
@ LW_EXCLUSIVE
Definition: lwlock.h:116
static BTVacInfo * btvacinfo
Definition: nbtutils.c:1969
LockRelId relid
Definition: nbtutils.c:1957
int num_vacuums
Definition: nbtutils.c:1964
BTOneVacInfo vacuums[FLEXIBLE_ARRAY_MEMBER]
Definition: nbtutils.c:1966
LockRelId lockRelId
Definition: rel.h:46
Oid relId
Definition: rel.h:40
Oid dbId
Definition: rel.h:41
LockInfoData rd_lockInfo
Definition: rel.h:114

References btvacinfo, LockRelId::dbId, i, LockInfoData::lockRelId, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), BTVacInfo::num_vacuums, RelationData::rd_lockInfo, BTOneVacInfo::relid, LockRelId::relId, and BTVacInfo::vacuums.

Referenced by _bt_end_vacuum_callback(), and btbulkdelete().

◆ _bt_end_vacuum_callback()

void _bt_end_vacuum_callback ( int  code,
Datum  arg 
)

Definition at line 2101 of file nbtutils.c.

2102 {
2104 }
void _bt_end_vacuum(Relation rel)
Definition: nbtutils.c:2073

References _bt_end_vacuum(), arg, and DatumGetPointer().

Referenced by btbulkdelete().

◆ _bt_find_extreme_element()

static Datum _bt_find_extreme_element ( IndexScanDesc  scan,
ScanKey  skey,
StrategyNumber  strat,
Datum elems,
int  nelems 
)
static

Definition at line 374 of file nbtutils.c.

377 {
378  Relation rel = scan->indexRelation;
379  Oid elemtype,
380  cmp_op;
381  RegProcedure cmp_proc;
382  FmgrInfo flinfo;
383  Datum result;
384  int i;
385 
386  /*
387  * Determine the nominal datatype of the array elements. We have to
388  * support the convention that sk_subtype == InvalidOid means the opclass
389  * input type; this is a hack to simplify life for ScanKeyInit().
390  */
391  elemtype = skey->sk_subtype;
392  if (elemtype == InvalidOid)
393  elemtype = rel->rd_opcintype[skey->sk_attno - 1];
394 
395  /*
396  * Look up the appropriate comparison operator in the opfamily.
397  *
398  * Note: it's possible that this would fail, if the opfamily is
399  * incomplete, but it seems quite unlikely that an opfamily would omit
400  * non-cross-type comparison operators for any datatype that it supports
401  * at all.
402  */
403  cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
404  elemtype,
405  elemtype,
406  strat);
407  if (!OidIsValid(cmp_op))
408  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
409  strat, elemtype, elemtype,
410  rel->rd_opfamily[skey->sk_attno - 1]);
411  cmp_proc = get_opcode(cmp_op);
412  if (!RegProcedureIsValid(cmp_proc))
413  elog(ERROR, "missing oprcode for operator %u", cmp_op);
414 
415  fmgr_info(cmp_proc, &flinfo);
416 
417  Assert(nelems > 0);
418  result = elems[0];
419  for (i = 1; i < nelems; i++)
420  {
421  if (DatumGetBool(FunctionCall2Coll(&flinfo,
422  skey->sk_collation,
423  elems[i],
424  result)))
425  result = elems[i];
426  }
427 
428  return result;
429 }
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:127
Definition: fmgr.h:57

References Assert(), DatumGetBool(), elog(), ERROR, fmgr_info(), FunctionCall2Coll(), get_opcode(), get_opfamily_member(), i, IndexScanDescData::indexRelation, InvalidOid, OidIsValid, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_attno, ScanKeyData::sk_collation, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_array_keys().

◆ _bt_fix_scankey_strategy()

static bool _bt_fix_scankey_strategy ( ScanKey  skey,
int16 indoption 
)
static

Definition at line 1210 of file nbtutils.c.

1211 {
1212  int addflags;
1213 
1214  addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
1215 
1216  /*
1217  * We treat all btree operators as strict (even if they're not so marked
1218  * in pg_proc). This means that it is impossible for an operator condition
1219  * with a NULL comparison constant to succeed, and we can reject it right
1220  * away.
1221  *
1222  * However, we now also support "x IS NULL" clauses as search conditions,
1223  * so in that case keep going. The planner has not filled in any
1224  * particular strategy in this case, so set it to BTEqualStrategyNumber
1225  * --- we can treat IS NULL as an equality operator for purposes of search
1226  * strategy.
1227  *
1228  * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
1229  * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
1230  * FIRST index.
1231  *
1232  * Note: someday we might have to fill in sk_collation from the index
1233  * column's collation. At the moment this is a non-issue because we'll
1234  * never actually call the comparison operator on a NULL.
1235  */
1236  if (skey->sk_flags & SK_ISNULL)
1237  {
1238  /* SK_ISNULL shouldn't be set in a row header scankey */
1239  Assert(!(skey->sk_flags & SK_ROW_HEADER));
1240 
1241  /* Set indoption flags in scankey (might be done already) */
1242  skey->sk_flags |= addflags;
1243 
1244  /* Set correct strategy for IS NULL or NOT NULL search */
1245  if (skey->sk_flags & SK_SEARCHNULL)
1246  {
1248  skey->sk_subtype = InvalidOid;
1249  skey->sk_collation = InvalidOid;
1250  }
1251  else if (skey->sk_flags & SK_SEARCHNOTNULL)
1252  {
1253  if (skey->sk_flags & SK_BT_NULLS_FIRST)
1255  else
1257  skey->sk_subtype = InvalidOid;
1258  skey->sk_collation = InvalidOid;
1259  }
1260  else
1261  {
1262  /* regular qual, so it cannot be satisfied */
1263  return false;
1264  }
1265 
1266  /* Needn't do the rest */
1267  return true;
1268  }
1269 
1270  /* Adjust strategy for DESC, if we didn't already */
1271  if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
1273  skey->sk_flags |= addflags;
1274 
1275  /* If it's a row header, fix row member flags and strategies similarly */
1276  if (skey->sk_flags & SK_ROW_HEADER)
1277  {
1278  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1279 
1280  for (;;)
1281  {
1282  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1283  addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
1284  if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
1285  subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
1286  subkey->sk_flags |= addflags;
1287  if (subkey->sk_flags & SK_ROW_END)
1288  break;
1289  subkey++;
1290  }
1291  }
1292 
1293  return true;
1294 }
#define SK_BT_INDOPTION_SHIFT
Definition: nbtree.h:1088

References Assert(), BTCommuteStrategyNumber, BTEqualStrategyNumber, BTGreaterStrategyNumber, BTLessStrategyNumber, DatumGetPointer(), InvalidOid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_INDOPTION_SHIFT, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNOTNULL, SK_SEARCHNULL, ScanKeyData::sk_strategy, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_keys().

◆ _bt_freestack()

void _bt_freestack ( BTStack  stack)

Definition at line 174 of file nbtutils.c.

175 {
176  BTStack ostack;
177 
178  while (stack != NULL)
179  {
180  ostack = stack;
181  stack = stack->bts_parent;
182  pfree(ostack);
183  }
184 }
void pfree(void *pointer)
Definition: mcxt.c:1456
struct BTStackData * bts_parent
Definition: nbtree.h:736

References BTStackData::bts_parent, and pfree().

Referenced by _bt_doinsert(), _bt_first(), and bt_rootdescend().

◆ _bt_keep_natts()

static int _bt_keep_natts ( Relation  rel,
IndexTuple  lastleft,
IndexTuple  firstright,
BTScanInsert  itup_key 
)
static

Definition at line 2390 of file nbtutils.c.

2392 {
2393  int nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
2394  TupleDesc itupdesc = RelationGetDescr(rel);
2395  int keepnatts;
2396  ScanKey scankey;
2397 
2398  /*
2399  * _bt_compare() treats truncated key attributes as having the value minus
2400  * infinity, which would break searches within !heapkeyspace indexes. We
2401  * must still truncate away non-key attribute values, though.
2402  */
2403  if (!itup_key->heapkeyspace)
2404  return nkeyatts;
2405 
2406  scankey = itup_key->scankeys;
2407  keepnatts = 1;
2408  for (int attnum = 1; attnum <= nkeyatts; attnum++, scankey++)
2409  {
2410  Datum datum1,
2411  datum2;
2412  bool isNull1,
2413  isNull2;
2414 
2415  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
2416  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
2417 
2418  if (isNull1 != isNull2)
2419  break;
2420 
2421  if (!isNull1 &&
2423  scankey->sk_collation,
2424  datum1,
2425  datum2)) != 0)
2426  break;
2427 
2428  keepnatts++;
2429  }
2430 
2431  /*
2432  * Assert that _bt_keep_natts_fast() agrees with us in passing. This is
2433  * expected in an allequalimage index.
2434  */
2435  Assert(!itup_key->allequalimage ||
2436  keepnatts == _bt_keep_natts_fast(rel, lastleft, firstright));
2437 
2438  return keepnatts;
2439 }
int _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
Definition: nbtutils.c:2464
int16 attnum
Definition: pg_attribute.h:74
bool allequalimage
Definition: nbtree.h:787
bool heapkeyspace
Definition: nbtree.h:786
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:793

References _bt_keep_natts_fast(), BTScanInsertData::allequalimage, Assert(), attnum, DatumGetInt32(), FunctionCall2Coll(), BTScanInsertData::heapkeyspace, index_getattr(), IndexRelationGetNumberOfKeyAttributes, RelationGetDescr, BTScanInsertData::scankeys, ScanKeyData::sk_collation, and ScanKeyData::sk_func.

Referenced by _bt_truncate().

◆ _bt_keep_natts_fast()

int _bt_keep_natts_fast ( Relation  rel,
IndexTuple  lastleft,
IndexTuple  firstright 
)

Definition at line 2464 of file nbtutils.c.

2465 {
2466  TupleDesc itupdesc = RelationGetDescr(rel);
2467  int keysz = IndexRelationGetNumberOfKeyAttributes(rel);
2468  int keepnatts;
2469 
2470  keepnatts = 1;
2471  for (int attnum = 1; attnum <= keysz; attnum++)
2472  {
2473  Datum datum1,
2474  datum2;
2475  bool isNull1,
2476  isNull2;
2477  Form_pg_attribute att;
2478 
2479  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
2480  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
2481  att = TupleDescAttr(itupdesc, attnum - 1);
2482 
2483  if (isNull1 != isNull2)
2484  break;
2485 
2486  if (!isNull1 &&
2487  !datum_image_eq(datum1, datum2, att->attbyval, att->attlen))
2488  break;
2489 
2490  keepnatts++;
2491  }
2492 
2493  return keepnatts;
2494 }
bool datum_image_eq(Datum value1, Datum value2, bool typByVal, int typLen)
Definition: datum.c:266
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:209
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92

References attnum, datum_image_eq(), index_getattr(), IndexRelationGetNumberOfKeyAttributes, RelationGetDescr, and TupleDescAttr.

Referenced by _bt_afternewitemoff(), _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_do_singleval(), _bt_keep_natts(), _bt_load(), _bt_split_penalty(), and _bt_strategy().

◆ _bt_killitems()

void _bt_killitems ( IndexScanDesc  scan)

Definition at line 1765 of file nbtutils.c.

1766 {
1767  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1768  Page page;
1769  BTPageOpaque opaque;
1770  OffsetNumber minoff;
1771  OffsetNumber maxoff;
1772  int i;
1773  int numKilled = so->numKilled;
1774  bool killedsomething = false;
1775  bool droppedpin PG_USED_FOR_ASSERTS_ONLY;
1776 
1778 
1779  /*
1780  * Always reset the scan state, so we don't look for same items on other
1781  * pages.
1782  */
1783  so->numKilled = 0;
1784 
1785  if (BTScanPosIsPinned(so->currPos))
1786  {
1787  /*
1788  * We have held the pin on this page since we read the index tuples,
1789  * so all we need to do is lock it. The pin will have prevented
1790  * re-use of any TID on the page, so there is no need to check the
1791  * LSN.
1792  */
1793  droppedpin = false;
1795 
1796  page = BufferGetPage(so->currPos.buf);
1797  }
1798  else
1799  {
1800  Buffer buf;
1801 
1802  droppedpin = true;
1803  /* Attempt to re-read the buffer, getting pin and lock. */
1805 
1806  page = BufferGetPage(buf);
1807  if (BufferGetLSNAtomic(buf) == so->currPos.lsn)
1808  so->currPos.buf = buf;
1809  else
1810  {
1811  /* Modified while not pinned means hinting is not safe. */
1812  _bt_relbuf(scan->indexRelation, buf);
1813  return;
1814  }
1815  }
1816 
1817  opaque = BTPageGetOpaque(page);
1818  minoff = P_FIRSTDATAKEY(opaque);
1819  maxoff = PageGetMaxOffsetNumber(page);
1820 
1821  for (i = 0; i < numKilled; i++)
1822  {
1823  int itemIndex = so->killedItems[i];
1824  BTScanPosItem *kitem = &so->currPos.items[itemIndex];
1825  OffsetNumber offnum = kitem->indexOffset;
1826 
1827  Assert(itemIndex >= so->currPos.firstItem &&
1828  itemIndex <= so->currPos.lastItem);
1829  if (offnum < minoff)
1830  continue; /* pure paranoia */
1831  while (offnum <= maxoff)
1832  {
1833  ItemId iid = PageGetItemId(page, offnum);
1834  IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
1835  bool killtuple = false;
1836 
1837  if (BTreeTupleIsPosting(ituple))
1838  {
1839  int pi = i + 1;
1840  int nposting = BTreeTupleGetNPosting(ituple);
1841  int j;
1842 
1843  /*
1844  * We rely on the convention that heap TIDs in the scanpos
1845  * items array are stored in ascending heap TID order for a
1846  * group of TIDs that originally came from a posting list
1847  * tuple. This convention even applies during backwards
1848  * scans, where returning the TIDs in descending order might
1849  * seem more natural. This is about effectiveness, not
1850  * correctness.
1851  *
1852  * Note that the page may have been modified in almost any way
1853  * since we first read it (in the !droppedpin case), so it's
1854  * possible that this posting list tuple wasn't a posting list
1855  * tuple when we first encountered its heap TIDs.
1856  */
1857  for (j = 0; j < nposting; j++)
1858  {
1859  ItemPointer item = BTreeTupleGetPostingN(ituple, j);
1860 
1861  if (!ItemPointerEquals(item, &kitem->heapTid))
1862  break; /* out of posting list loop */
1863 
1864  /*
1865  * kitem must have matching offnum when heap TIDs match,
1866  * though only in the common case where the page can't
1867  * have been concurrently modified
1868  */
1869  Assert(kitem->indexOffset == offnum || !droppedpin);
1870 
1871  /*
1872  * Read-ahead to later kitems here.
1873  *
1874  * We rely on the assumption that not advancing kitem here
1875  * will prevent us from considering the posting list tuple
1876  * fully dead by not matching its next heap TID in next
1877  * loop iteration.
1878  *
1879  * If, on the other hand, this is the final heap TID in
1880  * the posting list tuple, then tuple gets killed
1881  * regardless (i.e. we handle the case where the last
1882  * kitem is also the last heap TID in the last index tuple
1883  * correctly -- posting tuple still gets killed).
1884  */
1885  if (pi < numKilled)
1886  kitem = &so->currPos.items[so->killedItems[pi++]];
1887  }
1888 
1889  /*
1890  * Don't bother advancing the outermost loop's int iterator to
1891  * avoid processing killed items that relate to the same
1892  * offnum/posting list tuple. This micro-optimization hardly
1893  * seems worth it. (Further iterations of the outermost loop
1894  * will fail to match on this same posting list's first heap
1895  * TID instead, so we'll advance to the next offnum/index
1896  * tuple pretty quickly.)
1897  */
1898  if (j == nposting)
1899  killtuple = true;
1900  }
1901  else if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
1902  killtuple = true;
1903 
1904  /*
1905  * Mark index item as dead, if it isn't already. Since this
1906  * happens while holding a buffer lock possibly in shared mode,
1907  * it's possible that multiple processes attempt to do this
1908  * simultaneously, leading to multiple full-page images being sent
1909  * to WAL (if wal_log_hints or data checksums are enabled), which
1910  * is undesirable.
1911  */
1912  if (killtuple && !ItemIdIsDead(iid))
1913  {
1914  /* found the item/all posting list items */
1915  ItemIdMarkDead(iid);
1916  killedsomething = true;
1917  break; /* out of inner search loop */
1918  }
1919  offnum = OffsetNumberNext(offnum);
1920  }
1921  }
1922 
1923  /*
1924  * Since this can be redone later if needed, mark as dirty hint.
1925  *
1926  * Whenever we mark anything LP_DEAD, we also set the page's
1927  * BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we
1928  * only rely on the page-level flag in !heapkeyspace indexes.)
1929  */
1930  if (killedsomething)
1931  {
1932  opaque->btpo_flags |= BTP_HAS_GARBAGE;
1933  MarkBufferDirtyHint(so->currPos.buf, true);
1934  }
1935 
1936  _bt_unlockbuf(scan->indexRelation, so->currPos.buf);
1937 }
int Buffer
Definition: buf.h:23
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
Definition: bufmgr.c:3647
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:4637
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:350
Pointer Page
Definition: bufpage.h:78
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:171
int j
Definition: isn.c:74
#define ItemIdMarkDead(itemId)
Definition: itemid.h:179
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1023
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Definition: nbtpage.c:845
void _bt_unlockbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1070
void _bt_lockbuf(Relation rel, Buffer buf, int access)
Definition: nbtpage.c:1039
#define BTScanPosIsPinned(scanpos)
Definition: nbtree.h:990
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:518
#define BTP_HAS_GARBAGE
Definition: nbtree.h:82
#define BTScanPosIsValid(scanpos)
Definition: nbtree.h:1007
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:544
#define BT_READ
Definition: nbtree.h:719
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
static char * buf
Definition: pg_test_fsync.c:73
BTScanPosData currPos
Definition: nbtree.h:1075
int * killedItems
Definition: nbtree.h:1051
Buffer buf
Definition: nbtree.h:953
BlockNumber currPage
Definition: nbtree.h:956
int firstItem
Definition: nbtree.h:981
BTScanPosItem items[MaxTIDsPerBTreePage]
Definition: nbtree.h:985
XLogRecPtr lsn
Definition: nbtree.h:955
ItemPointerData heapTid
Definition: nbtree.h:946
OffsetNumber indexOffset
Definition: nbtree.h:947

References _bt_getbuf(), _bt_lockbuf(), _bt_relbuf(), _bt_unlockbuf(), Assert(), BT_READ, BTP_HAS_GARBAGE, BTPageGetOpaque, BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), BTScanPosIsPinned, BTScanPosIsValid, buf, BTScanPosData::buf, BufferGetLSNAtomic(), BufferGetPage(), BTScanPosData::currPage, BTScanOpaqueData::currPos, BTScanPosData::firstItem, BTScanPosItem::heapTid, i, BTScanPosItem::indexOffset, IndexScanDescData::indexRelation, ItemIdIsDead, ItemIdMarkDead, ItemPointerEquals(), BTScanPosData::items, j, BTScanOpaqueData::killedItems, BTScanPosData::lsn, MarkBufferDirtyHint(), BTScanOpaqueData::numKilled, OffsetNumberNext, IndexScanDescData::opaque, P_FIRSTDATAKEY, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), PG_USED_FOR_ASSERTS_ONLY, and IndexTupleData::t_tid.

Referenced by _bt_steppage(), btendscan(), btrescan(), and btrestrpos().

◆ _bt_mark_array_keys()

void _bt_mark_array_keys ( IndexScanDesc  scan)

Definition at line 612 of file nbtutils.c.

613 {
614  BTScanOpaque so = (BTScanOpaque) scan->opaque;
615  int i;
616 
617  for (i = 0; i < so->numArrayKeys; i++)
618  {
619  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
620 
621  curArrayKey->mark_elem = curArrayKey->cur_elem;
622  }
623 }

References BTScanOpaqueData::arrayKeys, BTArrayKeyInfo::cur_elem, i, BTArrayKeyInfo::mark_elem, BTScanOpaqueData::numArrayKeys, and IndexScanDescData::opaque.

◆ _bt_mark_scankey_required()

static void _bt_mark_scankey_required ( ScanKey  skey)
static

Definition at line 1312 of file nbtutils.c.

1313 {
1314  int addflags;
1315 
1316  switch (skey->sk_strategy)
1317  {
1318  case BTLessStrategyNumber:
1320  addflags = SK_BT_REQFWD;
1321  break;
1322  case BTEqualStrategyNumber:
1323  addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
1324  break;
1327  addflags = SK_BT_REQBKWD;
1328  break;
1329  default:
1330  elog(ERROR, "unrecognized StrategyNumber: %d",
1331  (int) skey->sk_strategy);
1332  addflags = 0; /* keep compiler quiet */
1333  break;
1334  }
1335 
1336  skey->sk_flags |= addflags;
1337 
1338  if (skey->sk_flags & SK_ROW_HEADER)
1339  {
1340  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1341 
1342  /* First subkey should be same column/operator as the header */
1343  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1344  Assert(subkey->sk_attno == skey->sk_attno);
1345  Assert(subkey->sk_strategy == skey->sk_strategy);
1346  subkey->sk_flags |= addflags;
1347  }
1348 }

References Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, DatumGetPointer(), elog(), ERROR, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_REQBKWD, SK_BT_REQFWD, ScanKeyData::sk_flags, SK_ROW_HEADER, SK_ROW_MEMBER, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_keys().

◆ _bt_mkscankey()

BTScanInsert _bt_mkscankey ( Relation  rel,
IndexTuple  itup 
)

Definition at line 82 of file nbtutils.c.

83 {
85  ScanKey skey;
86  TupleDesc itupdesc;
87  int indnkeyatts;
88  int16 *indoption;
89  int tupnatts;
90  int i;
91 
92  itupdesc = RelationGetDescr(rel);
93  indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
94  indoption = rel->rd_indoption;
95  tupnatts = itup ? BTreeTupleGetNAtts(itup, rel) : 0;
96 
98 
99  /*
100  * We'll execute search using scan key constructed on key columns.
101  * Truncated attributes and non-key attributes are omitted from the final
102  * scan key.
103  */
104  key = palloc(offsetof(BTScanInsertData, scankeys) +
105  sizeof(ScanKeyData) * indnkeyatts);
106  if (itup)
107  _bt_metaversion(rel, &key->heapkeyspace, &key->allequalimage);
108  else
109  {
110  /* Utility statement callers can set these fields themselves */
111  key->heapkeyspace = true;
112  key->allequalimage = false;
113  }
114  key->anynullkeys = false; /* initial assumption */
115  key->nextkey = false; /* usual case, required by btinsert */
116  key->backward = false; /* usual case, required by btinsert */
117  key->keysz = Min(indnkeyatts, tupnatts);
118  key->scantid = key->heapkeyspace && itup ?
119  BTreeTupleGetHeapTID(itup) : NULL;
120  skey = key->scankeys;
121  for (i = 0; i < indnkeyatts; i++)
122  {
123  FmgrInfo *procinfo;
124  Datum arg;
125  bool null;
126  int flags;
127 
128  /*
129  * We can use the cached (default) support procs since no cross-type
130  * comparison can be needed.
131  */
132  procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
133 
134  /*
135  * Key arguments built from truncated attributes (or when caller
136  * provides no tuple) are defensively represented as NULL values. They
137  * should never be used.
138  */
139  if (i < tupnatts)
140  arg = index_getattr(itup, i + 1, itupdesc, &null);
141  else
142  {
143  arg = (Datum) 0;
144  null = true;
145  }
146  flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT);
148  flags,
149  (AttrNumber) (i + 1),
151  InvalidOid,
152  rel->rd_indcollation[i],
153  procinfo,
154  arg);
155  /* Record if any key attribute is NULL (or truncated) */
156  if (null)
157  key->anynullkeys = true;
158  }
159 
160  /*
161  * In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so
162  * that full uniqueness check is done.
163  */
164  if (rel->rd_index->indnullsnotdistinct)
165  key->anynullkeys = false;
166 
167  return key;
168 }
int16 AttrNumber
Definition: attnum.h:21
#define Min(x, y)
Definition: c.h:993
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:826
void * palloc(Size size)
Definition: mcxt.c:1226
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:739
#define BTORDER_PROC
Definition: nbtree.h:707
void ScanKeyEntryInitializeWithInfo(ScanKey entry, int flags, AttrNumber attributeNumber, StrategyNumber strategy, Oid subtype, Oid collation, FmgrInfo *finfo, Datum argument)
Definition: scankey.c:101
#define InvalidStrategy
Definition: stratnum.h:24
int16 * rd_indoption
Definition: rel.h:210
Form_pg_index rd_index
Definition: rel.h:191

References _bt_metaversion(), arg, Assert(), BTORDER_PROC, BTreeTupleGetHeapTID(), BTreeTupleGetNAtts, i, index_getattr(), index_getprocinfo(), IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, InvalidOid, InvalidStrategy, sort-test::key, Min, palloc(), RelationData::rd_indcollation, RelationData::rd_index, RelationData::rd_indoption, RelationGetDescr, ScanKeyEntryInitializeWithInfo(), SK_BT_INDOPTION_SHIFT, and SK_ISNULL.

Referenced by _bt_doinsert(), _bt_leafbuild(), _bt_pagedel(), bt_mkscankey_pivotsearch(), bt_rootdescend(), tuplesort_begin_cluster(), and tuplesort_begin_index_btree().

◆ _bt_preprocess_array_keys()

void _bt_preprocess_array_keys ( IndexScanDesc  scan)

Definition at line 202 of file nbtutils.c.

203 {
204  BTScanOpaque so = (BTScanOpaque) scan->opaque;
205  int numberOfKeys = scan->numberOfKeys;
206  int16 *indoption = scan->indexRelation->rd_indoption;
207  int numArrayKeys;
208  ScanKey cur;
209  int i;
210  MemoryContext oldContext;
211 
212  /* Quick check to see if there are any array keys */
213  numArrayKeys = 0;
214  for (i = 0; i < numberOfKeys; i++)
215  {
216  cur = &scan->keyData[i];
217  if (cur->sk_flags & SK_SEARCHARRAY)
218  {
219  numArrayKeys++;
220  Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
221  /* If any arrays are null as a whole, we can quit right now. */
222  if (cur->sk_flags & SK_ISNULL)
223  {
224  so->numArrayKeys = -1;
225  so->arrayKeyData = NULL;
226  return;
227  }
228  }
229  }
230 
231  /* Quit if nothing to do. */
232  if (numArrayKeys == 0)
233  {
234  so->numArrayKeys = 0;
235  so->arrayKeyData = NULL;
236  return;
237  }
238 
239  /*
240  * Make a scan-lifespan context to hold array-associated data, or reset it
241  * if we already have one from a previous rescan cycle.
242  */
243  if (so->arrayContext == NULL)
245  "BTree array context",
247  else
249 
250  oldContext = MemoryContextSwitchTo(so->arrayContext);
251 
252  /* Create modifiable copy of scan->keyData in the workspace context */
253  so->arrayKeyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
254  memcpy(so->arrayKeyData,
255  scan->keyData,
256  scan->numberOfKeys * sizeof(ScanKeyData));
257 
258  /* Allocate space for per-array data in the workspace context */
259  so->arrayKeys = (BTArrayKeyInfo *) palloc0(numArrayKeys * sizeof(BTArrayKeyInfo));
260 
261  /* Now process each array key */
262  numArrayKeys = 0;
263  for (i = 0; i < numberOfKeys; i++)
264  {
265  ArrayType *arrayval;
266  int16 elmlen;
267  bool elmbyval;
268  char elmalign;
269  int num_elems;
270  Datum *elem_values;
271  bool *elem_nulls;
272  int num_nonnulls;
273  int j;
274 
275  cur = &so->arrayKeyData[i];
276  if (!(cur->sk_flags & SK_SEARCHARRAY))
277  continue;
278 
279  /*
280  * First, deconstruct the array into elements. Anything allocated
281  * here (including a possibly detoasted array value) is in the
282  * workspace context.
283  */
284  arrayval = DatumGetArrayTypeP(cur->sk_argument);
285  /* We could cache this data, but not clear it's worth it */
287  &elmlen, &elmbyval, &elmalign);
288  deconstruct_array(arrayval,
289  ARR_ELEMTYPE(arrayval),
290  elmlen, elmbyval, elmalign,
291  &elem_values, &elem_nulls, &num_elems);
292 
293  /*
294  * Compress out any null elements. We can ignore them since we assume
295  * all btree operators are strict.
296  */
297  num_nonnulls = 0;
298  for (j = 0; j < num_elems; j++)
299  {
300  if (!elem_nulls[j])
301  elem_values[num_nonnulls++] = elem_values[j];
302  }
303 
304  /* We could pfree(elem_nulls) now, but not worth the cycles */
305 
306  /* If there's no non-nulls, the scan qual is unsatisfiable */
307  if (num_nonnulls == 0)
308  {
309  numArrayKeys = -1;
310  break;
311  }
312 
313  /*
314  * If the comparison operator is not equality, then the array qual
315  * degenerates to a simple comparison against the smallest or largest
316  * non-null array element, as appropriate.
317  */
318  switch (cur->sk_strategy)
319  {
322  cur->sk_argument =
325  elem_values, num_nonnulls);
326  continue;
328  /* proceed with rest of loop */
329  break;
332  cur->sk_argument =
335  elem_values, num_nonnulls);
336  continue;
337  default:
338  elog(ERROR, "unrecognized StrategyNumber: %d",
339  (int) cur->sk_strategy);
340  break;
341  }
342 
343  /*
344  * Sort the non-null elements and eliminate any duplicates. We must
345  * sort in the same ordering used by the index column, so that the
346  * successive primitive indexscans produce data in index order.
347  */
348  num_elems = _bt_sort_array_elements(scan, cur,
349  (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0,
350  elem_values, num_nonnulls);
351 
352  /*
353  * And set up the BTArrayKeyInfo data.
354  */
355  so->arrayKeys[numArrayKeys].scan_key = i;
356  so->arrayKeys[numArrayKeys].num_elems = num_elems;
357  so->arrayKeys[numArrayKeys].elem_values = elem_values;
358  numArrayKeys++;
359  }
360 
361  so->numArrayKeys = numArrayKeys;
362 
363  MemoryContextSwitchTo(oldContext);
364 }
#define DatumGetArrayTypeP(X)
Definition: array.h:261
#define ARR_ELEMTYPE(a)
Definition: array.h:292
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3613
struct cursor * cur
Definition: ecpg.c:28
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2253
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:330
void * palloc0(Size size)
Definition: mcxt.c:1257
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
#define AllocSetContextCreate
Definition: memutils.h:126
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:160
static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, StrategyNumber strat, Datum *elems, int nelems)
Definition: nbtutils.c:374
static int _bt_sort_array_elements(IndexScanDesc scan, ScanKey skey, bool reverse, Datum *elems, int nelems)
Definition: nbtutils.c:441
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
#define SK_SEARCHARRAY
Definition: skey.h:120
MemoryContext arrayContext
Definition: nbtree.h:1048
struct ScanKeyData * keyData
Definition: relscan.h:122

References _bt_find_extreme_element(), _bt_sort_array_elements(), ALLOCSET_SMALL_SIZES, AllocSetContextCreate, ARR_ELEMTYPE, BTScanOpaqueData::arrayContext, BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, cur, CurrentMemoryContext, DatumGetArrayTypeP, deconstruct_array(), BTArrayKeyInfo::elem_values, elog(), ERROR, get_typlenbyvalalign(), i, IndexScanDescData::indexRelation, j, IndexScanDescData::keyData, MemoryContextReset(), MemoryContextSwitchTo(), BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, palloc(), palloc0(), RelationData::rd_indoption, BTArrayKeyInfo::scan_key, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHARRAY, SK_SEARCHNOTNULL, and SK_SEARCHNULL.

Referenced by btrescan().

◆ _bt_preprocess_keys()

void _bt_preprocess_keys ( IndexScanDesc  scan)

Definition at line 756 of file nbtutils.c.

757 {
758  BTScanOpaque so = (BTScanOpaque) scan->opaque;
759  int numberOfKeys = scan->numberOfKeys;
760  int16 *indoption = scan->indexRelation->rd_indoption;
761  int new_numberOfKeys;
762  int numberOfEqualCols;
763  ScanKey inkeys;
764  ScanKey outkeys;
765  ScanKey cur;
767  bool test_result;
768  int i,
769  j;
770  AttrNumber attno;
771 
772  /* initialize result variables */
773  so->qual_ok = true;
774  so->numberOfKeys = 0;
775 
776  if (numberOfKeys < 1)
777  return; /* done if qual-less scan */
778 
779  /*
780  * Read so->arrayKeyData if array keys are present, else scan->keyData
781  */
782  if (so->arrayKeyData != NULL)
783  inkeys = so->arrayKeyData;
784  else
785  inkeys = scan->keyData;
786 
787  outkeys = so->keyData;
788  cur = &inkeys[0];
789  /* we check that input keys are correctly ordered */
790  if (cur->sk_attno < 1)
791  elog(ERROR, "btree index keys must be ordered by attribute");
792 
793  /* We can short-circuit most of the work if there's just one key */
794  if (numberOfKeys == 1)
795  {
796  /* Apply indoption to scankey (might change sk_strategy!) */
797  if (!_bt_fix_scankey_strategy(cur, indoption))
798  so->qual_ok = false;
799  memcpy(outkeys, cur, sizeof(ScanKeyData));
800  so->numberOfKeys = 1;
801  /* We can mark the qual as required if it's for first index col */
802  if (cur->sk_attno == 1)
803  _bt_mark_scankey_required(outkeys);
804  return;
805  }
806 
807  /*
808  * Otherwise, do the full set of pushups.
809  */
810  new_numberOfKeys = 0;
811  numberOfEqualCols = 0;
812 
813  /*
814  * Initialize for processing of keys for attr 1.
815  *
816  * xform[i] points to the currently best scan key of strategy type i+1; it
817  * is NULL if we haven't yet found such a key for this attr.
818  */
819  attno = 1;
820  memset(xform, 0, sizeof(xform));
821 
822  /*
823  * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
824  * handle after-last-key processing. Actual exit from the loop is at the
825  * "break" statement below.
826  */
827  for (i = 0;; cur++, i++)
828  {
829  if (i < numberOfKeys)
830  {
831  /* Apply indoption to scankey (might change sk_strategy!) */
832  if (!_bt_fix_scankey_strategy(cur, indoption))
833  {
834  /* NULL can't be matched, so give up */
835  so->qual_ok = false;
836  return;
837  }
838  }
839 
840  /*
841  * If we are at the end of the keys for a particular attr, finish up
842  * processing and emit the cleaned-up keys.
843  */
844  if (i == numberOfKeys || cur->sk_attno != attno)
845  {
846  int priorNumberOfEqualCols = numberOfEqualCols;
847 
848  /* check input keys are correctly ordered */
849  if (i < numberOfKeys && cur->sk_attno < attno)
850  elog(ERROR, "btree index keys must be ordered by attribute");
851 
852  /*
853  * If = has been specified, all other keys can be eliminated as
854  * redundant. If we have a case like key = 1 AND key > 2, we can
855  * set qual_ok to false and abandon further processing.
856  *
857  * We also have to deal with the case of "key IS NULL", which is
858  * unsatisfiable in combination with any other index condition. By
859  * the time we get here, that's been classified as an equality
860  * check, and we've rejected any combination of it with a regular
861  * equality condition; but not with other types of conditions.
862  */
863  if (xform[BTEqualStrategyNumber - 1])
864  {
865  ScanKey eq = xform[BTEqualStrategyNumber - 1];
866 
867  for (j = BTMaxStrategyNumber; --j >= 0;)
868  {
869  ScanKey chk = xform[j];
870 
871  if (!chk || j == (BTEqualStrategyNumber - 1))
872  continue;
873 
874  if (eq->sk_flags & SK_SEARCHNULL)
875  {
876  /* IS NULL is contradictory to anything else */
877  so->qual_ok = false;
878  return;
879  }
880 
881  if (_bt_compare_scankey_args(scan, chk, eq, chk,
882  &test_result))
883  {
884  if (!test_result)
885  {
886  /* keys proven mutually contradictory */
887  so->qual_ok = false;
888  return;
889  }
890  /* else discard the redundant non-equality key */
891  xform[j] = NULL;
892  }
893  /* else, cannot determine redundancy, keep both keys */
894  }
895  /* track number of attrs for which we have "=" keys */
896  numberOfEqualCols++;
897  }
898 
899  /* try to keep only one of <, <= */
900  if (xform[BTLessStrategyNumber - 1]
901  && xform[BTLessEqualStrategyNumber - 1])
902  {
903  ScanKey lt = xform[BTLessStrategyNumber - 1];
904  ScanKey le = xform[BTLessEqualStrategyNumber - 1];
905 
906  if (_bt_compare_scankey_args(scan, le, lt, le,
907  &test_result))
908  {
909  if (test_result)
910  xform[BTLessEqualStrategyNumber - 1] = NULL;
911  else
912  xform[BTLessStrategyNumber - 1] = NULL;
913  }
914  }
915 
916  /* try to keep only one of >, >= */
917  if (xform[BTGreaterStrategyNumber - 1]
918  && xform[BTGreaterEqualStrategyNumber - 1])
919  {
920  ScanKey gt = xform[BTGreaterStrategyNumber - 1];
921  ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1];
922 
923  if (_bt_compare_scankey_args(scan, ge, gt, ge,
924  &test_result))
925  {
926  if (test_result)
927  xform[BTGreaterEqualStrategyNumber - 1] = NULL;
928  else
929  xform[BTGreaterStrategyNumber - 1] = NULL;
930  }
931  }
932 
933  /*
934  * Emit the cleaned-up keys into the outkeys[] array, and then
935  * mark them if they are required. They are required (possibly
936  * only in one direction) if all attrs before this one had "=".
937  */
938  for (j = BTMaxStrategyNumber; --j >= 0;)
939  {
940  if (xform[j])
941  {
942  ScanKey outkey = &outkeys[new_numberOfKeys++];
943 
944  memcpy(outkey, xform[j], sizeof(ScanKeyData));
945  if (priorNumberOfEqualCols == attno - 1)
947  }
948  }
949 
950  /*
951  * Exit loop here if done.
952  */
953  if (i == numberOfKeys)
954  break;
955 
956  /* Re-initialize for new attno */
957  attno = cur->sk_attno;
958  memset(xform, 0, sizeof(xform));
959  }
960 
961  /* check strategy this key's operator corresponds to */
962  j = cur->sk_strategy - 1;
963 
964  /* if row comparison, push it directly to the output array */
965  if (cur->sk_flags & SK_ROW_HEADER)
966  {
967  ScanKey outkey = &outkeys[new_numberOfKeys++];
968 
969  memcpy(outkey, cur, sizeof(ScanKeyData));
970  if (numberOfEqualCols == attno - 1)
972 
973  /*
974  * We don't support RowCompare using equality; such a qual would
975  * mess up the numberOfEqualCols tracking.
976  */
977  Assert(j != (BTEqualStrategyNumber - 1));
978  continue;
979  }
980 
981  /* have we seen one of these before? */
982  if (xform[j] == NULL)
983  {
984  /* nope, so remember this scankey */
985  xform[j] = cur;
986  }
987  else
988  {
989  /* yup, keep only the more restrictive key */
990  if (_bt_compare_scankey_args(scan, cur, cur, xform[j],
991  &test_result))
992  {
993  if (test_result)
994  xform[j] = cur;
995  else if (j == (BTEqualStrategyNumber - 1))
996  {
997  /* key == a && key == b, but a != b */
998  so->qual_ok = false;
999  return;
1000  }
1001  /* else old key is more restrictive, keep it */
1002  }
1003  else
1004  {
1005  /*
1006  * We can't determine which key is more restrictive. Keep the
1007  * previous one in xform[j] and push this one directly to the
1008  * output array.
1009  */
1010  ScanKey outkey = &outkeys[new_numberOfKeys++];
1011 
1012  memcpy(outkey, cur, sizeof(ScanKeyData));
1013  if (numberOfEqualCols == attno - 1)
1014  _bt_mark_scankey_required(outkey);
1015  }
1016  }
1017  }
1018 
1019  so->numberOfKeys = new_numberOfKeys;
1020 }
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
Definition: nbtutils.c:1210
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, bool *result)
Definition: nbtutils.c:1046
static void _bt_mark_scankey_required(ScanKey skey)
Definition: nbtutils.c:1312
#define BTMaxStrategyNumber
Definition: stratnum.h:35

References _bt_compare_scankey_args(), _bt_fix_scankey_strategy(), _bt_mark_scankey_required(), BTScanOpaqueData::arrayKeyData, Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTMaxStrategyNumber, cur, elog(), ERROR, i, if(), IndexScanDescData::indexRelation, j, BTScanOpaqueData::keyData, IndexScanDescData::keyData, BTScanOpaqueData::numberOfKeys, IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, BTScanOpaqueData::qual_ok, RelationData::rd_indoption, ScanKeyData::sk_flags, SK_ROW_HEADER, and SK_SEARCHNULL.

Referenced by _bt_first(), and _bt_restore_array_keys().

◆ _bt_restore_array_keys()

void _bt_restore_array_keys ( IndexScanDesc  scan)

Definition at line 631 of file nbtutils.c.

632 {
633  BTScanOpaque so = (BTScanOpaque) scan->opaque;
634  bool changed = false;
635  int i;
636 
637  /* Restore each array key to its position when the mark was set */
638  for (i = 0; i < so->numArrayKeys; i++)
639  {
640  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
641  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
642  int mark_elem = curArrayKey->mark_elem;
643 
644  if (curArrayKey->cur_elem != mark_elem)
645  {
646  curArrayKey->cur_elem = mark_elem;
647  skey->sk_argument = curArrayKey->elem_values[mark_elem];
648  changed = true;
649  }
650  }
651 
652  /*
653  * If we changed any keys, we must redo _bt_preprocess_keys. That might
654  * sound like overkill, but in cases with multiple keys per index column
655  * it seems necessary to do the full set of pushups.
656  *
657  * Also do this whenever the scan's set of array keys "wrapped around" at
658  * the end of the last primitive index scan. There won't have been a call
659  * to _bt_preprocess_keys from some other place following wrap around, so
660  * we do it for ourselves.
661  */
662  if (changed || !so->arraysStarted)
663  {
664  _bt_preprocess_keys(scan);
665  /* The mark should have been set on a consistent set of keys... */
666  Assert(so->qual_ok);
667  }
668 }
void _bt_preprocess_keys(IndexScanDesc scan)
Definition: nbtutils.c:756

References _bt_preprocess_keys(), BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, BTScanOpaqueData::arraysStarted, Assert(), BTArrayKeyInfo::cur_elem, BTArrayKeyInfo::elem_values, i, BTArrayKeyInfo::mark_elem, BTScanOpaqueData::numArrayKeys, IndexScanDescData::opaque, BTScanOpaqueData::qual_ok, BTArrayKeyInfo::scan_key, and ScanKeyData::sk_argument.

Referenced by btrestrpos().

◆ _bt_sort_array_elements()

static int _bt_sort_array_elements ( IndexScanDesc  scan,
ScanKey  skey,
bool  reverse,
Datum elems,
int  nelems 
)
static

Definition at line 441 of file nbtutils.c.

444 {
445  Relation rel = scan->indexRelation;
446  Oid elemtype;
447  RegProcedure cmp_proc;
448  BTSortArrayContext cxt;
449 
450  if (nelems <= 1)
451  return nelems; /* no work to do */
452 
453  /*
454  * Determine the nominal datatype of the array elements. We have to
455  * support the convention that sk_subtype == InvalidOid means the opclass
456  * input type; this is a hack to simplify life for ScanKeyInit().
457  */
458  elemtype = skey->sk_subtype;
459  if (elemtype == InvalidOid)
460  elemtype = rel->rd_opcintype[skey->sk_attno - 1];
461 
462  /*
463  * Look up the appropriate comparison function in the opfamily.
464  *
465  * Note: it's possible that this would fail, if the opfamily is
466  * incomplete, but it seems quite unlikely that an opfamily would omit
467  * non-cross-type support functions for any datatype that it supports at
468  * all.
469  */
470  cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
471  elemtype,
472  elemtype,
473  BTORDER_PROC);
474  if (!RegProcedureIsValid(cmp_proc))
475  elog(ERROR, "missing support function %d(%u,%u) in opfamily %u",
476  BTORDER_PROC, elemtype, elemtype,
477  rel->rd_opfamily[skey->sk_attno - 1]);
478 
479  /* Sort the array elements */
480  fmgr_info(cmp_proc, &cxt.flinfo);
481  cxt.collation = skey->sk_collation;
482  cxt.reverse = reverse;
483  qsort_arg(elems, nelems, sizeof(Datum),
485 
486  /* Now scan the sorted elements and remove duplicates */
487  return qunique_arg(elems, nelems, sizeof(Datum),
489 }
static int _bt_compare_array_elements(const void *a, const void *b, void *arg)
Definition: nbtutils.c:495
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static size_t qunique_arg(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *, void *), void *arg)
Definition: qunique.h:46

References _bt_compare_array_elements(), BTORDER_PROC, BTSortArrayContext::collation, elog(), ERROR, BTSortArrayContext::flinfo, fmgr_info(), get_opfamily_proc(), IndexScanDescData::indexRelation, InvalidOid, qsort_arg(), qunique_arg(), RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, BTSortArrayContext::reverse, ScanKeyData::sk_attno, ScanKeyData::sk_collation, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_array_keys().

◆ _bt_start_array_keys()

void _bt_start_array_keys ( IndexScanDesc  scan,
ScanDirection  dir 
)

Definition at line 517 of file nbtutils.c.

518 {
519  BTScanOpaque so = (BTScanOpaque) scan->opaque;
520  int i;
521 
522  for (i = 0; i < so->numArrayKeys; i++)
523  {
524  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
525  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
526 
527  Assert(curArrayKey->num_elems > 0);
528  if (ScanDirectionIsBackward(dir))
529  curArrayKey->cur_elem = curArrayKey->num_elems - 1;
530  else
531  curArrayKey->cur_elem = 0;
532  skey->sk_argument = curArrayKey->elem_values[curArrayKey->cur_elem];
533  }
534 
535  so->arraysStarted = true;
536 }

References BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, BTScanOpaqueData::arraysStarted, Assert(), BTArrayKeyInfo::cur_elem, BTArrayKeyInfo::elem_values, i, BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::opaque, BTArrayKeyInfo::scan_key, ScanDirectionIsBackward, and ScanKeyData::sk_argument.

Referenced by btgetbitmap(), and btgettuple().

◆ _bt_start_vacuum()

BTCycleId _bt_start_vacuum ( Relation  rel)

Definition at line 2016 of file nbtutils.c.

2017 {
2018  BTCycleId result;
2019  int i;
2020  BTOneVacInfo *vac;
2021 
2022  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
2023 
2024  /*
2025  * Assign the next cycle ID, being careful to avoid zero as well as the
2026  * reserved high values.
2027  */
2028  result = ++(btvacinfo->cycle_ctr);
2029  if (result == 0 || result > MAX_BT_CYCLE_ID)
2030  result = btvacinfo->cycle_ctr = 1;
2031 
2032  /* Let's just make sure there's no entry already for this index */
2033  for (i = 0; i < btvacinfo->num_vacuums; i++)
2034  {
2035  vac = &btvacinfo->vacuums[i];
2036  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
2037  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
2038  {
2039  /*
2040  * Unlike most places in the backend, we have to explicitly
2041  * release our LWLock before throwing an error. This is because
2042  * we expect _bt_end_vacuum() to be called before transaction
2043  * abort cleanup can run to release LWLocks.
2044  */
2045  LWLockRelease(BtreeVacuumLock);
2046  elog(ERROR, "multiple active vacuums for index \"%s\"",
2048  }
2049  }
2050 
2051  /* OK, add an entry */
2053  {
2054  LWLockRelease(BtreeVacuumLock);
2055  elog(ERROR, "out of btvacinfo slots");
2056  }
2058  vac->relid = rel->rd_lockInfo.lockRelId;
2059  vac->cycleid = result;
2061 
2062  LWLockRelease(BtreeVacuumLock);
2063  return result;
2064 }
#define MAX_BT_CYCLE_ID
Definition: nbtree.h:93
uint16 BTCycleId
Definition: nbtree.h:29
BTCycleId cycleid
Definition: nbtutils.c:1958
BTCycleId cycle_ctr
Definition: nbtutils.c:1963
int max_vacuums
Definition: nbtutils.c:1965

References btvacinfo, BTVacInfo::cycle_ctr, BTOneVacInfo::cycleid, LockRelId::dbId, elog(), ERROR, i, LockInfoData::lockRelId, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), MAX_BT_CYCLE_ID, BTVacInfo::max_vacuums, BTVacInfo::num_vacuums, RelationData::rd_lockInfo, RelationGetRelationName, BTOneVacInfo::relid, LockRelId::relId, and BTVacInfo::vacuums.

Referenced by btbulkdelete().

◆ _bt_truncate()

IndexTuple _bt_truncate ( Relation  rel,
IndexTuple  lastleft,
IndexTuple  firstright,
BTScanInsert  itup_key 
)

Definition at line 2245 of file nbtutils.c.

2247 {
2248  TupleDesc itupdesc = RelationGetDescr(rel);
2250  int keepnatts;
2251  IndexTuple pivot;
2252  IndexTuple tidpivot;
2253  ItemPointer pivotheaptid;
2254  Size newsize;
2255 
2256  /*
2257  * We should only ever truncate non-pivot tuples from leaf pages. It's
2258  * never okay to truncate when splitting an internal page.
2259  */
2260  Assert(!BTreeTupleIsPivot(lastleft) && !BTreeTupleIsPivot(firstright));
2261 
2262  /* Determine how many attributes must be kept in truncated tuple */
2263  keepnatts = _bt_keep_natts(rel, lastleft, firstright, itup_key);
2264 
2265 #ifdef DEBUG_NO_TRUNCATE
2266  /* Force truncation to be ineffective for testing purposes */
2267  keepnatts = nkeyatts + 1;
2268 #endif
2269 
2270  pivot = index_truncate_tuple(itupdesc, firstright,
2271  Min(keepnatts, nkeyatts));
2272 
2273  if (BTreeTupleIsPosting(pivot))
2274  {
2275  /*
2276  * index_truncate_tuple() just returns a straight copy of firstright
2277  * when it has no attributes to truncate. When that happens, we may
2278  * need to truncate away a posting list here instead.
2279  */
2280  Assert(keepnatts == nkeyatts || keepnatts == nkeyatts + 1);
2281  Assert(IndexRelationGetNumberOfAttributes(rel) == nkeyatts);
2282  pivot->t_info &= ~INDEX_SIZE_MASK;
2283  pivot->t_info |= MAXALIGN(BTreeTupleGetPostingOffset(firstright));
2284  }
2285 
2286  /*
2287  * If there is a distinguishing key attribute within pivot tuple, we're
2288  * done
2289  */
2290  if (keepnatts <= nkeyatts)
2291  {
2292  BTreeTupleSetNAtts(pivot, keepnatts, false);
2293  return pivot;
2294  }
2295 
2296  /*
2297  * We have to store a heap TID in the new pivot tuple, since no non-TID
2298  * key attribute value in firstright distinguishes the right side of the
2299  * split from the left side. nbtree conceptualizes this case as an
2300  * inability to truncate away any key attributes, since heap TID is
2301  * treated as just another key attribute (despite lacking a pg_attribute
2302  * entry).
2303  *
2304  * Use enlarged space that holds a copy of pivot. We need the extra space
2305  * to store a heap TID at the end (using the special pivot tuple
2306  * representation). Note that the original pivot already has firstright's
2307  * possible posting list/non-key attribute values removed at this point.
2308  */
2309  newsize = MAXALIGN(IndexTupleSize(pivot)) + MAXALIGN(sizeof(ItemPointerData));
2310  tidpivot = palloc0(newsize);
2311  memcpy(tidpivot, pivot, MAXALIGN(IndexTupleSize(pivot)));
2312  /* Cannot leak memory here */
2313  pfree(pivot);
2314 
2315  /*
2316  * Store all of firstright's key attribute values plus a tiebreaker heap
2317  * TID value in enlarged pivot tuple
2318  */
2319  tidpivot->t_info &= ~INDEX_SIZE_MASK;
2320  tidpivot->t_info |= newsize;
2321  BTreeTupleSetNAtts(tidpivot, nkeyatts, true);
2322  pivotheaptid = BTreeTupleGetHeapTID(tidpivot);
2323 
2324  /*
2325  * Lehman & Yao use lastleft as the leaf high key in all cases, but don't
2326  * consider suffix truncation. It seems like a good idea to follow that
2327  * example in cases where no truncation takes place -- use lastleft's heap
2328  * TID. (This is also the closest value to negative infinity that's
2329  * legally usable.)
2330  */
2331  ItemPointerCopy(BTreeTupleGetMaxHeapTID(lastleft), pivotheaptid);
2332 
2333  /*
2334  * We're done. Assert() that heap TID invariants hold before returning.
2335  *
2336  * Lehman and Yao require that the downlink to the right page, which is to
2337  * be inserted into the parent page in the second phase of a page split be
2338  * a strict lower bound on items on the right page, and a non-strict upper
2339  * bound for items on the left page. Assert that heap TIDs follow these
2340  * invariants, since a heap TID value is apparently needed as a
2341  * tiebreaker.
2342  */
2343 #ifndef DEBUG_NO_TRUNCATE
2345  BTreeTupleGetHeapTID(firstright)) < 0);
2346  Assert(ItemPointerCompare(pivotheaptid,
2347  BTreeTupleGetHeapTID(lastleft)) >= 0);
2348  Assert(ItemPointerCompare(pivotheaptid,
2349  BTreeTupleGetHeapTID(firstright)) < 0);
2350 #else
2351 
2352  /*
2353  * Those invariants aren't guaranteed to hold for lastleft + firstright
2354  * heap TID attribute values when they're considered here only because
2355  * DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually
2356  * needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap
2357  * TID value that always works as a strict lower bound for items to the
2358  * right. In particular, it must avoid using firstright's leading key
2359  * attribute values along with lastleft's heap TID value when lastleft's
2360  * TID happens to be greater than firstright's TID.
2361  */
2362  ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid);
2363 
2364  /*
2365  * Pivot heap TID should never be fully equal to firstright. Note that
2366  * the pivot heap TID will still end up equal to lastleft's heap TID when
2367  * that's the only usable value.
2368  */
2369  ItemPointerSetOffsetNumber(pivotheaptid,
2371  Assert(ItemPointerCompare(pivotheaptid,
2372  BTreeTupleGetHeapTID(firstright)) < 0);
2373 #endif
2374 
2375  return tidpivot;
2376 }
IndexTuple index_truncate_tuple(TupleDesc sourceDescriptor, IndexTuple source, int leavenatts)
Definition: indextuple.c:576
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
Definition: itemptr.c:51
static void ItemPointerSetOffsetNumber(ItemPointerData *pointer, OffsetNumber offsetNumber)
Definition: itemptr.h:158
static void ItemPointerCopy(const ItemPointerData *fromPointer, ItemPointerData *toPointer)
Definition: itemptr.h:172
#define INDEX_SIZE_MASK
Definition: itup.h:65
static uint32 BTreeTupleGetPostingOffset(IndexTuple posting)
Definition: nbtree.h:529
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:664
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
Definition: nbtree.h:595
static int _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition: nbtutils.c:2390
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:54
unsigned short t_info
Definition: itup.h:49

References _bt_keep_natts(), Assert(), BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTreeTupleSetNAtts(), INDEX_SIZE_MASK, index_truncate_tuple(), IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, IndexTupleSize, ItemPointerCompare(), ItemPointerCopy(), ItemPointerGetOffsetNumber(), ItemPointerSetOffsetNumber(), MAXALIGN, Min, OffsetNumberPrev, palloc0(), pfree(), RelationGetDescr, and IndexTupleData::t_info.

Referenced by _bt_buildadd(), and _bt_split().

◆ _bt_vacuum_cycleid()

BTCycleId _bt_vacuum_cycleid ( Relation  rel)

Definition at line 1982 of file nbtutils.c.

1983 {
1984  BTCycleId result = 0;
1985  int i;
1986 
1987  /* Share lock is enough since this is a read-only operation */
1988  LWLockAcquire(BtreeVacuumLock, LW_SHARED);
1989 
1990  for (i = 0; i < btvacinfo->num_vacuums; i++)
1991  {
1992  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
1993 
1994  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
1995  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
1996  {
1997  result = vac->cycleid;
1998  break;
1999  }
2000  }
2001 
2002  LWLockRelease(BtreeVacuumLock);
2003  return result;
2004 }
@ LW_SHARED
Definition: lwlock.h:117

References btvacinfo, BTOneVacInfo::cycleid, LockRelId::dbId, i, LockInfoData::lockRelId, LW_SHARED, LWLockAcquire(), LWLockRelease(), BTVacInfo::num_vacuums, RelationData::rd_lockInfo, BTOneVacInfo::relid, LockRelId::relId, and BTVacInfo::vacuums.

Referenced by _bt_split().

◆ btbuildphasename()

char* btbuildphasename ( int64  phasenum)

Definition at line 2197 of file nbtutils.c.

2198 {
2199  switch (phasenum)
2200  {
2202  return "initializing";
2204  return "scanning table";
2206  return "sorting live tuples";
2208  return "sorting dead tuples";
2210  return "loading tuples in tree";
2211  default:
2212  return NULL;
2213  }
2214 }
#define PROGRESS_BTREE_PHASE_PERFORMSORT_2
Definition: nbtree.h:1121
#define PROGRESS_BTREE_PHASE_LEAF_LOAD
Definition: nbtree.h:1122
#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN
Definition: nbtree.h:1119
#define PROGRESS_BTREE_PHASE_PERFORMSORT_1
Definition: nbtree.h:1120
#define PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE
Definition: progress.h:106

References PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN, PROGRESS_BTREE_PHASE_LEAF_LOAD, PROGRESS_BTREE_PHASE_PERFORMSORT_1, PROGRESS_BTREE_PHASE_PERFORMSORT_2, and PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE.

Referenced by bthandler().

◆ btoptions()

bytea* btoptions ( Datum  reloptions,
bool  validate 
)

Definition at line 2151 of file nbtutils.c.

2152 {
2153  static const relopt_parse_elt tab[] = {
2154  {"fillfactor", RELOPT_TYPE_INT, offsetof(BTOptions, fillfactor)},
2155  {"vacuum_cleanup_index_scale_factor", RELOPT_TYPE_REAL,
2156  offsetof(BTOptions, vacuum_cleanup_index_scale_factor)},
2157  {"deduplicate_items", RELOPT_TYPE_BOOL,
2158  offsetof(BTOptions, deduplicate_items)}
2159  };
2160 
2161  return (bytea *) build_reloptions(reloptions, validate,
2163  sizeof(BTOptions),
2164  tab, lengthof(tab));
2165 }
#define lengthof(array)
Definition: c.h:777
int fillfactor
Definition: pgbench.c:187
void * build_reloptions(Datum reloptions, bool validate, relopt_kind kind, Size relopt_struct_size, const relopt_parse_elt *relopt_elems, int num_relopt_elems)
Definition: reloptions.c:1910
@ RELOPT_KIND_BTREE
Definition: reloptions.h:44
@ RELOPT_TYPE_INT
Definition: reloptions.h:32
@ RELOPT_TYPE_BOOL
Definition: reloptions.h:31
@ RELOPT_TYPE_REAL
Definition: reloptions.h:33
Definition: c.h:676

References build_reloptions(), fillfactor, lengthof, RELOPT_KIND_BTREE, RELOPT_TYPE_BOOL, RELOPT_TYPE_INT, and RELOPT_TYPE_REAL.

Referenced by bthandler().

◆ btproperty()

bool btproperty ( Oid  index_oid,
int  attno,
IndexAMProperty  prop,
const char *  propname,
bool res,
bool isnull 
)

Definition at line 2174 of file nbtutils.c.

2177 {
2178  switch (prop)
2179  {
2180  case AMPROP_RETURNABLE:
2181  /* answer only for columns, not AM or whole index */
2182  if (attno == 0)
2183  return false;
2184  /* otherwise, btree can always return data */
2185  *res = true;
2186  return true;
2187 
2188  default:
2189  return false; /* punt to generic code */
2190  }
2191 }
@ AMPROP_RETURNABLE
Definition: amapi.h:43

References AMPROP_RETURNABLE, and res.

Referenced by bthandler().

◆ BTreeShmemInit()

void BTreeShmemInit ( void  )

Definition at line 2123 of file nbtutils.c.

2124 {
2125  bool found;
2126 
2127  btvacinfo = (BTVacInfo *) ShmemInitStruct("BTree Vacuum State",
2128  BTreeShmemSize(),
2129  &found);
2130 
2131  if (!IsUnderPostmaster)
2132  {
2133  /* Initialize shared memory area */
2134  Assert(!found);
2135 
2136  /*
2137  * It doesn't really matter what the cycle counter starts at, but
2138  * having it always start the same doesn't seem good. Seed with
2139  * low-order bits of time() instead.
2140  */
2141  btvacinfo->cycle_ctr = (BTCycleId) time(NULL);
2142 
2143  btvacinfo->num_vacuums = 0;
2145  }
2146  else
2147  Assert(found);
2148 }
bool IsUnderPostmaster
Definition: globals.c:115
int MaxBackends
Definition: globals.c:142
Size BTreeShmemSize(void)
Definition: nbtutils.c:2110
void * ShmemInitStruct(const char *name, Size size, bool *foundPtr)
Definition: shmem.c:388

References Assert(), BTreeShmemSize(), btvacinfo, BTVacInfo::cycle_ctr, IsUnderPostmaster, BTVacInfo::max_vacuums, MaxBackends, BTVacInfo::num_vacuums, and ShmemInitStruct().

Referenced by CreateOrAttachShmemStructs().

◆ BTreeShmemSize()

Size BTreeShmemSize ( void  )

Definition at line 2110 of file nbtutils.c.

2111 {
2112  Size size;
2113 
2114  size = offsetof(BTVacInfo, vacuums);
2115  size = add_size(size, mul_size(MaxBackends, sizeof(BTOneVacInfo)));
2116  return size;
2117 }
Size add_size(Size s1, Size s2)
Definition: shmem.c:494
Size mul_size(Size s1, Size s2)
Definition: shmem.c:511

References add_size(), MaxBackends, and mul_size().

Referenced by BTreeShmemInit(), and CalculateShmemSize().

Variable Documentation

◆ btvacinfo

BTVacInfo* btvacinfo
static

Definition at line 1969 of file nbtutils.c.

Referenced by _bt_end_vacuum(), _bt_start_vacuum(), _bt_vacuum_cycleid(), and BTreeShmemInit().