⭐ 欢迎来到虫虫下载站! | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站

📄 nbtsearch.c

📁 postgresql8.3.4源码,开源数据库
💻 C
📖 第 1 页 / 共 3 页
字号:
	 * contradictory.	 *	 * In this loop, row-comparison keys are treated the same as keys on their	 * first (leftmost) columns.  We'll add on lower-order columns of the row	 * comparison below, if possible.	 *	 * The selected scan keys (at most one per index column) are remembered by	 * storing their addresses into the local startKeys[] array.	 *----------	 */	strat_total = BTEqualStrategyNumber;	if (so->numberOfKeys > 0)	{		AttrNumber	curattr;		ScanKey		chosen;		ScanKey		cur;		/*		 * chosen is the so-far-chosen key for the current attribute, if any.		 * We don't cast the decision in stone until we reach keys for the		 * next attribute.		 */		curattr = 1;		chosen = NULL;		/*		 * Loop iterates from 0 to numberOfKeys inclusive; we use the last		 * pass to handle after-last-key processing.  Actual exit from the		 * loop is at one of the "break" statements below.		 */		for (cur = so->keyData, i = 0;; cur++, i++)		{			if (i >= so->numberOfKeys || cur->sk_attno != curattr)			{				/*				 * Done looking at keys for curattr.  If we didn't find a				 * usable boundary key, quit; else save the boundary key				 * pointer in startKeys.				 */				if (chosen == NULL)					break;				startKeys[keysCount++] = chosen;				/*				 * Adjust strat_total, and quit if we have stored a > or <				 * key.				 */				strat = chosen->sk_strategy;				if (strat != BTEqualStrategyNumber)				{					strat_total = strat;					if (strat == BTGreaterStrategyNumber ||						strat == BTLessStrategyNumber)						break;				}				/*				 * Done if that was the last attribute, or if next key is not				 * in sequence (implying no boundary key is available for the				 * next attribute).				 */				if (i >= so->numberOfKeys ||					cur->sk_attno != curattr + 1)					break;				/*				 * Reset for next attr.				 */				curattr = cur->sk_attno;				chosen = NULL;			}			/* Can we use this key as a starting boundary for this attr? */			switch (cur->sk_strategy)			{				case BTLessStrategyNumber:				case BTLessEqualStrategyNumber:					if (chosen == NULL && ScanDirectionIsBackward(dir))						chosen = cur;					break;				case BTEqualStrategyNumber:					/* override any non-equality choice */					chosen = cur;					break;				case BTGreaterEqualStrategyNumber:				case BTGreaterStrategyNumber:					if (chosen == NULL && ScanDirectionIsForward(dir))						chosen = cur;					break;			}		}	}	/*	 * If we found no usable boundary keys, we have to start from one end of	 * the tree.  Walk down that edge to the first or last key, and scan from	 * there.	 */	if (keysCount == 0)		return _bt_endpoint(scan, dir);	/*	 * We want to start the scan somewhere within the index.  Set up an	 * insertion scankey we can use to search for the boundary point we	 * identified above.  The insertion scankey is built in the local	 * scankeys[] array, using the keys identified by startKeys[].	 */	Assert(keysCount <= INDEX_MAX_KEYS);	for (i = 0; i < keysCount; i++)	{		ScanKey		cur = startKeys[i];		Assert(cur->sk_attno == i + 1);		if (cur->sk_flags & SK_ROW_HEADER)		{			/*			 * Row comparison header: look to the first row member instead.			 *			 * The member scankeys are already in insertion format (ie, they			 * have sk_func = 3-way-comparison function), but we have to watch			 * out for nulls, which _bt_preprocess_keys didn't check. A null			 * in the first row member makes the condition unmatchable, just			 * like qual_ok = false.			 */			ScanKey		subkey = (ScanKey) DatumGetPointer(cur->sk_argument);			Assert(subkey->sk_flags & SK_ROW_MEMBER);			if (subkey->sk_flags & SK_ISNULL)				return false;			memcpy(scankeys + i, subkey, sizeof(ScanKeyData));			/*			 * If the row comparison is the last positioning key we accepted,			 * try to add additional keys from the lower-order row members.			 * (If we accepted independent conditions on additional index			 * columns, we use those instead --- doesn't seem worth trying to			 * determine which is more restrictive.)  Note that this is OK			 * even if the row comparison is of ">" or "<" type, because the			 * condition applied to all but the last row member is effectively			 * ">=" or "<=", and so the extra keys don't break the positioning			 * scheme.	But, by the same token, if we aren't able to use all			 * the row members, then the part of the row comparison that we			 * did use has to be treated as just a ">=" or "<=" condition, and			 * so we'd better adjust strat_total accordingly.			 */			if (i == keysCount - 1)			{				bool		used_all_subkeys = false;				Assert(!(subkey->sk_flags & SK_ROW_END));				for (;;)				{					subkey++;					Assert(subkey->sk_flags & SK_ROW_MEMBER);					if (subkey->sk_attno != keysCount + 1)						break;	/* out-of-sequence, can't use it */					if (subkey->sk_strategy != cur->sk_strategy)						break;	/* wrong direction, can't use it */					if (subkey->sk_flags & SK_ISNULL)						break;	/* can't use null keys */					Assert(keysCount < INDEX_MAX_KEYS);					memcpy(scankeys + keysCount, subkey, sizeof(ScanKeyData));					keysCount++;					if (subkey->sk_flags & SK_ROW_END)					{						used_all_subkeys = true;						break;					}				}				if (!used_all_subkeys)				{					switch (strat_total)					{						case BTLessStrategyNumber:							strat_total = BTLessEqualStrategyNumber;							break;						case BTGreaterStrategyNumber:							strat_total = BTGreaterEqualStrategyNumber;							break;					}				}				break;			/* done with outer loop */			}		}		else		{			/*			 * Ordinary comparison key.  Transform the search-style scan key			 * to an insertion scan key by replacing the sk_func with the			 * appropriate btree comparison function.			 *			 * If scankey operator is not a cross-type comparison, we can use			 * the cached comparison function; otherwise gotta look it up in			 * the catalogs.  (That can't lead to infinite recursion, since no			 * indexscan initiated by syscache lookup will use cross-data-type			 * operators.)			 *			 * We support the convention that sk_subtype == InvalidOid means			 * the opclass input type; this is a hack to simplify life for			 * ScanKeyInit().			 */			if (cur->sk_subtype == rel->rd_opcintype[i] ||				cur->sk_subtype == InvalidOid)			{				FmgrInfo   *procinfo;				procinfo = index_getprocinfo(rel, cur->sk_attno, BTORDER_PROC);				ScanKeyEntryInitializeWithInfo(scankeys + i,											   cur->sk_flags,											   cur->sk_attno,											   InvalidStrategy,											   cur->sk_subtype,											   procinfo,											   cur->sk_argument);			}			else			{				RegProcedure cmp_proc;				cmp_proc = get_opfamily_proc(rel->rd_opfamily[i],											 rel->rd_opcintype[i],											 cur->sk_subtype,											 BTORDER_PROC);				if (!RegProcedureIsValid(cmp_proc))					elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",						 BTORDER_PROC, rel->rd_opcintype[i], cur->sk_subtype,						 cur->sk_attno, RelationGetRelationName(rel));				ScanKeyEntryInitialize(scankeys + i,									   cur->sk_flags,									   cur->sk_attno,									   InvalidStrategy,									   cur->sk_subtype,									   cmp_proc,									   cur->sk_argument);			}		}	}	/*----------	 * Examine the selected initial-positioning strategy to determine exactly	 * where we need to start the scan, and set flag variables to control the	 * code below.	 *	 * If nextkey = false, _bt_search and _bt_binsrch will locate the first	 * item >= scan key.  If nextkey = true, they will locate the first	 * item > scan key.	 *	 * If goback = true, we will then step back one item, while if	 * goback = false, we will start the scan on the located item.	 *----------	 */	switch (strat_total)	{		case BTLessStrategyNumber:			/*			 * Find first item >= scankey, then back up one to arrive at last			 * item < scankey.	(Note: this positioning strategy is only used			 * for a backward scan, so that is always the correct starting			 * position.)			 */			nextkey = false;			goback = true;			break;		case BTLessEqualStrategyNumber:			/*			 * Find first item > scankey, then back up one to arrive at last			 * item <= scankey.  (Note: this positioning strategy is only used			 * for a backward scan, so that is always the correct starting			 * position.)			 */			nextkey = true;			goback = true;			break;		case BTEqualStrategyNumber:			/*			 * If a backward scan was specified, need to start with last equal			 * item not first one.			 */			if (ScanDirectionIsBackward(dir))			{				/*				 * This is the same as the <= strategy.  We will check at the				 * end whether the found item is actually =.				 */				nextkey = true;				goback = true;			}			else			{				/*				 * This is the same as the >= strategy.  We will check at the				 * end whether the found item is actually =.				 */				nextkey = false;				goback = false;			}			break;		case BTGreaterEqualStrategyNumber:			/*			 * Find first item >= scankey.	(This is only used for forward			 * scans.)			 */			nextkey = false;			goback = false;			break;		case BTGreaterStrategyNumber:			/*			 * Find first item > scankey.  (This is only used for forward			 * scans.)			 */			nextkey = true;			goback = false;			break;		default:			/* can't get here, but keep compiler quiet */			elog(ERROR, "unrecognized strat_total: %d", (int) strat_total);			return false;	}	/*	 * Use the manufactured insertion scan key to descend the tree and	 * position ourselves on the target leaf page.	 */	stack = _bt_search(rel, keysCount, scankeys, nextkey, &buf, BT_READ);	/* don't need to keep the stack around... */	_bt_freestack(stack);	/* remember which buffer we have pinned, if any */	so->currPos.buf = buf;	if (!BufferIsValid(buf))	{		/* Only get here if index is completely empty */		return false;	}	/* initialize moreLeft/moreRight appropriately for scan direction */	if (ScanDirectionIsForward(dir))	{		so->currPos.moreLeft = false;		so->currPos.moreRight = true;	}	else	{		so->currPos.moreLeft = true;		so->currPos.moreRight = false;	}	so->numKilled = 0;			/* just paranoia */	so->markItemIndex = -1;		/* ditto */	/* position to the precise item on the page */	offnum = _bt_binsrch(rel, buf, keysCount, scankeys, nextkey);	/*	 * If nextkey = false, we are positioned at the first item >= scan key, or	 * possibly at the end of a page on which all the existing items are less	 * than the scan key and we know that everything on later pages is greater	 * than or equal to scan key.	 *	 * If nextkey = true, we are positioned at the first item > scan key, or	 * possibly at the end of a page on which all the existing items are less	 * than or equal to the scan key and we know that everything on later	 * pages is greater than scan key.	 *	 * The actually desired starting point is either this item or the prior	 * one, or in the end-of-page case it's the first item on the next page or	 * the last item on this page.	Adjust the starting offset if needed. (If	 * this results in an offset before the first item or after the last one,	 * _bt_readpage will report no items found, and then we'll step to the	 * next page as needed.)	 */	if (goback)		offnum = OffsetNumberPrev(offnum);	/*	 * Now load data from the first page of the scan.	 */	if (!_bt_readpage(scan, dir, offnum))	{		/*		 * There's no actually-matching data on this page.  Try to advance to		 * the next page.  Return false if there's no matching data at all.		 */		if (!_bt_steppage(scan, dir))			return false;	}	/* Drop the lock, but not pin, on the current page */	LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);	/* OK, itemIndex says what to return */	scan->xs_ctup.t_self = so->currPos.items[so->currPos.itemIndex].heapTid;	return true;}/* *	_bt_next() -- Get the next item in a scan. * *		On entry, so->currPos describes the current page, which is pinned *		but not locked, and so->currPos.itemIndex identifies which item was *		previously returned. * *		On successful exit, scan->xs_ctup.t_self is set to the TID of the *		next heap tuple, and so->currPos is updated as needed. * *		On failure exit (no more tuples), we release pin and set *		so->currPos.buf to InvalidBuffer. */bool_bt_next(IndexScanDesc scan, ScanDirection dir){	BTScanOpaque so = (BTScanOpaque) scan->opaque;	/*	 * Advance to next tuple on current page; or if there's no more, try to	 * step to the next page with data.	 */	if (ScanDirectionIsForward(dir))	{		if (++so->currPos.itemIndex > so->currPos.lastItem)		{			/* We must acquire lock before applying _bt_steppage */			Assert(BufferIsValid(so->currPos.buf));			LockBuffer(so->currPos.buf, BT_READ);			if (!_bt_steppage(scan, dir))				return false;			/* Drop the lock, but not pin, on the new page */			LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);		}	}	else	{		if (--so->currPos.itemIndex < so->currPos.firstItem)		{			/* We must acquire lock before applying _bt_steppage */			Assert(BufferIsValid(so->currPos.buf));			LockBuffer(so->currPos.buf, BT_READ);			if (!_bt_steppage(scan, dir))				return false;			/* Drop the lock, but not pin, on the new page */			LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);		}	}	/* OK, itemIndex says what to return */	scan->xs_ctup.t_self = so->currPos.items[so->currPos.itemIndex].heapTid;	return true;}/* *	_bt_readpage() -- Load data from current index page into so->currPos * * Caller must have pinned and read-locked so->currPos.buf; the buffer's state * is not changed here.  Also, currPos.moreLeft and moreRight must be valid; * they are updated as appropriate.  All other fields of so->currPos are * initialized from scratch here. * * We scan the current page starting at offnum and moving in the indicated * direction.  All items matching the scan keys are loaded into currPos.items. * moreLeft or moreRight (as appropriate) is cleared if _bt_checkkeys reports * that there can be no more matching tuples in the current scan direction. * * Returns true if any matching items found on the page, false if none. */static bool_bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum){	BTScanOpaque so = (BTScanOpaque) scan->opaque;	Page		page;	BTPageOpaque opaque;	OffsetNumber minoff;	OffsetNumber maxoff;	int			itemIndex;	bool		continuescan;	/* we must have the buffer pinned and locked */	Assert(BufferIsValid(so->currPos.buf));	page = BufferGetPage(so->currPos.buf);	opaque = (BTPageOpaque) PageGetSpecialPointer(page);	minoff = P_FIRSTDATAKEY(opaque);	maxoff = PageGetMaxOffsetNumber(page);	/*

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -