Context Navigation

← Previous Changeset
Next Changeset →

Changeset 23

Timestamp:

09/24/07 03:55:40 (5 years ago)

Author:

cs186

Message:

Changes to PostgreSQL to provide a skeleton for HW2.

Location:

hw/hw2/postgresql-8.2.4/src

Files:

: 11 modified

backend/access/gist/gist.c (modified) (1 diff)
backend/access/gist/gistget.c (modified) (8 diffs)
backend/access/gist/gistproc.c (modified) (2 diffs)
backend/access/gist/gistscan.c (modified) (3 diffs)
include/access/gist.h (modified) (1 diff)
include/access/gist_private.h (modified) (4 diffs)
include/catalog/pg_am.h (modified) (1 diff)
include/catalog/pg_amproc.h (modified) (3 diffs)
include/catalog/pg_operator.h (modified) (1 diff)
include/catalog/pg_proc.h (modified) (1 diff)
include/utils/geo_decls.h (modified) (2 diffs)

Legend:

: Unmodified
: Added
: Removed

hw/hw2/postgresql-8.2.4/src/backend/access/gist/gist.c

r22	r23
1065	1065	index_getprocinfo(index, i + 1, GIST_EQUAL_PROC),
1066	1066	CurrentMemoryContext);
	1067	fmgr_info_copy(&(giststate->distanceFn[i]),
	1068	index_getprocinfo(index, i + 1, GIST_DISTANCE_PROC),
	1069	CurrentMemoryContext);
1067	1070	}
1068	1071	}

hw/hw2/postgresql-8.2.4/src/backend/access/gist/gistget.c

r22	r23
2	2	*
3	3	* gistget.c
4		* ~~fetch tuples from a Gi~~ST scan.
	4	* fetch tuples from a GIST scan.
5	5	*
6	6	*
…	…
9	9	*
10	10	* IDENTIFICATION
11		* $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.62 2006/11/12 06:55:53 neilc Exp $
	11	* $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.62 2006/11/12 06:55:53 neilc Exp $
12	12	*
13	13	*-------------------------------------------------------------------------
…	…
19	19	#include "pgstat.h"
20	20	#include "utils/memutils.h"
	21	#include "utils/builtins.h"
	22	#include <stdio.h>
21	23
22	24
23	25	static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n,
24		ScanDirection dir);
25		static int gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples);
	26	ScanDirection dir);
	27	static int gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples);
	28	static double gistindex_keydistance(IndexTuple tuple, IndexScanDesc scan,
	29	OffsetNumber offset);
26	30	static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan,
27		OffsetNumber offset);
	31	OffsetNumber offset);
28	32
29	33	static void
30	34	killtuple(Relation r, GISTScanOpaque so, ItemPointer iptr)
31	35	{
32		~~Buffer~~ buffer = so->curbuf;
33
34		for (;;)
35		{
36		~~Page~~ p;
37		BlockNumber blkno;
38		OffsetNumber offset,
39		maxoff;
40
41		LockBuffer(buffer, GIST_SHARE);
42		gistcheckpage(r, buffer);
43		p = (Page) BufferGetPage(buffer);
44
45		if (buffer == so->curbuf && XLByteEQ(so->stack->lsn, PageGetLSN(p)))
46		{
47		/* page unchanged, so all is simple */
48		offset = ItemPointerGetOffsetNumber(iptr);
49		PageGetItemId(p, offset)->lp_flags \|= LP_DELETE;
50		SetBufferCommitInfoNeedsSave(buffer);
51		LockBuffer(buffer, GIST_UNLOCK);
52		break;
53		}
54
55		maxoff = PageGetMaxOffsetNumber(p);
56
57		for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
58		{
59		~~IndexTuple~~ ituple = (IndexTuple) PageGetItem(p, PageGetItemId(p, offset));
60
61		if (ItemPointerEquals(&(ituple->t_tid), iptr))
62		{
63		/* found */
64		PageGetItemId(p, offset)->lp_flags \|= LP_DELETE;
65		SetBufferCommitInfoNeedsSave(buffer);
66		LockBuffer(buffer, GIST_UNLOCK);
67		if (buffer != so->curbuf)
68		ReleaseBuffer(buffer);
69		return;
70		}
71		}
72
73		/* follow right link */
74
75		/*
76		* ??? is it good? if tuple dropped by concurrent vacuum, we will read
77		* all leaf pages...
78		*/
79		blkno = GistPageGetOpaque(p)->rightlink;
80		LockBuffer(buffer, GIST_UNLOCK);
81		if (buffer != so->curbuf)
82		ReleaseBuffer(buffer);
83
84		if (blkno == InvalidBlockNumber)
85		/* can't found, dropped by somebody else */
86		return;
87		buffer = ReadBuffer(r, blkno);
88		}
	36	Buffer buffer = so->curbuf;
	37
	38	for (;;)
	39	{
	40	Page p;
	41	BlockNumber blkno;
	42	OffsetNumber offset,
	43	maxoff;
	44
	45	LockBuffer(buffer, GIST_SHARE);
	46	gistcheckpage(r, buffer);
	47	p = (Page) BufferGetPage(buffer);
	48
	49	if (buffer == so->curbuf && XLByteEQ(so->stack->lsn, PageGetLSN(p)))
	50	{
	51	/* page unchanged, so all is simple */
	52	offset = ItemPointerGetOffsetNumber(iptr);
	53	PageGetItemId(p, offset)->lp_flags \|= LP_DELETE;
	54	SetBufferCommitInfoNeedsSave(buffer);
	55	LockBuffer(buffer, GIST_UNLOCK);
	56	break;
	57	}
	58
	59	maxoff = PageGetMaxOffsetNumber(p);
	60
	61	for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
	62	{
	63	IndexTuple ituple = (IndexTuple) PageGetItem(p, PageGetItemId(p, offset));
	64
	65	if (ItemPointerEquals(&(ituple->t_tid), iptr))
	66	{
	67	/* found */
	68	PageGetItemId(p, offset)->lp_flags \|= LP_DELETE;
	69	SetBufferCommitInfoNeedsSave(buffer);
	70	LockBuffer(buffer, GIST_UNLOCK);
	71	if (buffer != so->curbuf)
	72	ReleaseBuffer(buffer);
	73	return;
	74	}
	75	}
	76
	77	/* follow right link */
	78
	79	/*
	80	* ??? is it good? if tuple dropped by concurrent vacuum, we will read
	81	* all leaf pages...
	82	*/
	83	blkno = GistPageGetOpaque(p)->rightlink;
	84	LockBuffer(buffer, GIST_UNLOCK);
	85	if (buffer != so->curbuf)
	86	ReleaseBuffer(buffer);
	87
	88	if (blkno == InvalidBlockNumber)
	89	/* can't found, dropped by somebody else */
	90	return;
	91	buffer = ReadBuffer(r, blkno);
	92	}
89	93	}
90	94
…	…
95	99	gistgettuple(PG_FUNCTION_ARGS)
96	100	{
97		IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
98		ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1);
99		GISTScanOpaque so;
100		ItemPointerData tid;
101		~~bool~~ res;
102
103		so = (GISTScanOpaque) scan->opaque;
104
105		/*
106		* If we have produced an index tuple in the past and the executor has
107		* informed us we need to mark it as "killed", do so now.
108		*/
109		if (scan->kill_prior_tuple && ItemPointerIsValid(&(scan->currentItemData)))
110		killtuple(scan->indexRelation, so, &(scan->currentItemData));
111
112		/*
113		* Get the next tuple that matches the search key. If asked to skip killed
114		* tuples, continue looping until we find a non-killed tuple that matches
115		* the search key.
116		*/
117		res = (gistnext(scan, dir, &tid, 1, scan->ignore_killed_tuples)) ? true : false;
118
119		PG_RETURN_BOOL(res);
	101	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
	102	ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1);
	103	GISTScanOpaque so;
	104	ItemPointerData tid;
	105	bool res;
	106
	107	so = (GISTScanOpaque) scan->opaque;
	108
	109	/*
	110	* If we have produced an index tuple in the past and the executor has
	111	* informed us we need to mark it as "killed", do so now.
	112	*/
	113	if (scan->kill_prior_tuple && ItemPointerIsValid(&(scan->currentItemData)))
	114	killtuple(scan->indexRelation, so, &(scan->currentItemData));
	115
	116	/*
	117	* Get the next tuple that matches the search key. If asked to skip killed
	118	* tuples, continue looping until we find a non-killed tuple that matches
	119	* the search key.
	120	*/
	121	res = (gistnext(scan, dir, &tid, 1, scan->ignore_killed_tuples)) ? true : false;
	122
	123	PG_RETURN_BOOL(res);
120	124	}
121	125
…	…
123	127	gistgetmulti(PG_FUNCTION_ARGS)
124	128	{
125		IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
126		ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
127		~~int32~~ max_tids = PG_GETARG_INT32(2);
128		~~int32~~ returned_tids = (int32 ) PG_GETARG_POINTER(3);
129
130		*returned_tids = gistnext(scan, ForwardScanDirection, tids, max_tids, false);
131
132		PG_RETURN_BOOL(*returned_tids == max_tids);
	129	IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
	130	ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
	131	int32 max_tids = PG_GETARG_INT32(2);
	132	int32 returned_tids = (int32 ) PG_GETARG_POINTER(3);
	133
	134	*returned_tids = gistnext(scan, ForwardScanDirection, tids, max_tids, false);
	135
	136	PG_RETURN_BOOL(*returned_tids == max_tids);
133	137	}
134	138
135	139	/*
136		* Fetch a tuples that matchs the search key; this can be invoked
	140	* CS186 HW2: RELEVANT CODE BEGINS HERE
	141	*/
	142
	143	/* insert a new priority queue entry into so->pq */
	144	static void
	145	gist_pq_insertpq(GISTScanOpaque so, GISTPQ *newpq)
	146	{
	147	/* CS186 HW2: fill me in! */
	148	}
	149
	150	/*
	151	* given the current state of the index scan, generate a GISTPQ to insert into
	152	* the priority queue, and insert it.
	153	*/
	154	static void
	155	gist_pq_insert(IndexScanDesc scan, /* scan descriptor */
	156	OffsetNumber offset, /* "slot number" of item being inserted */
	157	GISTSearchStack stack, / search stack to this item */
	158	bool isData /* is the item being inserted a pointer to data? */
	159	)
	160	{
	161	/* CS186 HW2: fill me in! Should call gist_pq_insertpq. */
	162
	163	}
	164
	165	/* Find the minimum item in the priority queue (without deleting it) */
	166	static GISTPQ *
	167	gist_pq_findmin(GISTScanOpaque so)
	168	{
	169	/* CS186 HW2: implement me */
	170	return NULL;
	171	}
	172
	173	/*
	174	* Find the min item in the priority queue, remove it from the queue, and
	175	* return it. Should NOT free the space allocated for the min; the caller
	176	* does that when they're done with it.
	177	*/
	178	static GISTPQ *
	179	gist_pq_deletemin(GISTScanOpaque so)
	180	{
	181	/* CS186 HW2: implement me! */
	182	return NULL;
	183	}
	184
	185	/* Optional debugging routine -- dump the state of the priority queue */
	186	static void
	187	gist_pq_dump(GISTScanOpaque so)
	188	{
	189	/* CS186 HW2: fill me in if you like. */
	190	}
	191
	192	/* Support routine for gistnext, to load in the root element on first call */
	193	static void
	194	gistnext_get_root(IndexScanDesc scan, GISTScanOpaque so)
	195	{
	196	GISTSearchStack *stk;
	197	GISTPQ *pq;
	198
	199	/* Being asked to fetch the first entry, so start at the root */
	200	Assert(so->curbuf == InvalidBuffer);
	201	Assert(so->stack == NULL);
	202	Assert(so->pq == NULL);
	203
	204	so->curbuf = ReadBuffer(scan->indexRelation, GIST_ROOT_BLKNO);
	205
	206	stk = so->stack = (GISTSearchStack *) palloc0(sizeof(GISTSearchStack));
	207	pq = so->pq = (GISTPQ *) palloc0(sizeof(GISTPQ));
	208
	209	stk->next = NULL;
	210	pq->next = NULL;
	211	pq->block = stk->block = GIST_ROOT_BLKNO;
	212	pq->stk = stk;
	213
	214	/* NN: set pq->priority! */
	215
	216	pgstat_count_index_scan(&scan->xs_pgstat_info);
	217	}
	218
	219	/*
	220	* Support routine for gistnext. Deals with concurrency control issues to
	221	* check if a node on the (cached) search stack was split by a concurrent
	222	* inserter. If so, the result of the split can be found by adding right-hand
	223	* neighbors of the split node to the search stack. See
	224	* Kornacker/Mohan/Hellerstein, SIGMOD 2007, for the protocol description.
	225	*/
	226	static void
	227	gistnext_checksplit(IndexScanDesc scan, GISTScanOpaque so, Page p,
	228	GISTPageOpaque opaque)
	229	{
	230	bool resetoffset = false;
	231	GISTSearchStack *stk;
	232
	233	if (XLogRecPtrIsInvalid(so->stack->lsn) \|\| !XLByteEQ(so->stack->lsn, PageGetLSN(p)))
	234	{
	235	/* page changed from last visit or visit first time , reset offset */
	236	so->stack->lsn = PageGetLSN(p);
	237	resetoffset = true;
	238
	239	/* check page split, occured from last visit or visit to parent */
	240	if (!XLogRecPtrIsInvalid(so->stack->parentlsn) &&
	241	XLByteLT(so->stack->parentlsn, opaque->nsn) &&
	242	opaque->rightlink != InvalidBlockNumber /* sanity check */ &&
	243	(so->stack->next == NULL \|\| so->stack->next->block != opaque->rightlink) /* check if already
	244	added */ )
	245	{
	246	/* detect page split, follow right link to add pages */
	247
	248	stk = (GISTSearchStack *) palloc0(sizeof(GISTSearchStack));
	249	stk->next = so->stack->next;
	250	stk->block = opaque->rightlink;
	251	stk->parentlsn = so->stack->parentlsn;
	252	memset(&(stk->lsn), 0, sizeof(GistNSN));
	253	so->stack->next = stk;
	254	}
	255	}
	256	}
	257
	258	/*
	259	* Fetch tuples that matchs the search key; this can be invoked
137	260	* either to fetch the first such tuple or subsequent matching
138	261	* tuples. Returns true iff a matching tuple was found.
…	…
141	264	gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples)
142	265	{
143		Page p;
144		OffsetNumber n;
145		GISTScanOpaque so;
146		GISTSearchStack *stk;
147		IndexTuple it;
148		GISTPageOpaque opaque;
149		bool resetoffset = false;
150		int ntids = 0;
151
152		so = (GISTScanOpaque) scan->opaque;
153
154		if (ItemPointerIsValid(&scan->currentItemData) == false)
155		{
156		/* Being asked to fetch the first entry, so start at the root */
157		Assert(so->curbuf == InvalidBuffer);
158		Assert(so->stack == NULL);
159
160		so->curbuf = ReadBuffer(scan->indexRelation, GIST_ROOT_BLKNO);
161
162		stk = so->stack = (GISTSearchStack *) palloc0(sizeof(GISTSearchStack));
163
164		stk->next = NULL;
165		stk->block = GIST_ROOT_BLKNO;
166
167		pgstat_count_index_scan(&scan->xs_pgstat_info);
168		}
169		else if (so->curbuf == InvalidBuffer)
170		{
171		return 0;
172		}
173
174		for (;;)
175		{
176		/* First of all, we need lock buffer */
177		Assert(so->curbuf != InvalidBuffer);
178		LockBuffer(so->curbuf, GIST_SHARE);
179		gistcheckpage(scan->indexRelation, so->curbuf);
180		p = BufferGetPage(so->curbuf);
181		opaque = GistPageGetOpaque(p);
182		resetoffset = false;
183
184		if (XLogRecPtrIsInvalid(so->stack->lsn) \|\| !XLByteEQ(so->stack->lsn, PageGetLSN(p)))
185		{
186		/* page changed from last visit or visit first time , reset offset */
187		so->stack->lsn = PageGetLSN(p);
188		resetoffset = true;
189
190		/* check page split, occured from last visit or visit to parent */
191		if (!XLogRecPtrIsInvalid(so->stack->parentlsn) &&
192		XLByteLT(so->stack->parentlsn, opaque->nsn) &&
193		opaque->rightlink != InvalidBlockNumber /* sanity check */ &&
194		(so->stack->next == NULL \|\| so->stack->next->block != opaque->rightlink) /* check if already
195		added */ )
196		{
197		/* detect page split, follow right link to add pages */
198
199		stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack));
200		stk->next = so->stack->next;
201		stk->block = opaque->rightlink;
202		stk->parentlsn = so->stack->parentlsn;
203		memset(&(stk->lsn), 0, sizeof(GistNSN));
204		so->stack->next = stk;
205		}
206		}
207
208		/* if page is empty, then just skip it */
209		if (PageIsEmpty(p))
210		{
211		LockBuffer(so->curbuf, GIST_UNLOCK);
212		stk = so->stack->next;
213		pfree(so->stack);
214		so->stack = stk;
215
216		if (so->stack == NULL)
217		{
218		ReleaseBuffer(so->curbuf);
219		so->curbuf = InvalidBuffer;
220		return ntids;
221		}
222
223		so->curbuf = ReleaseAndReadBuffer(so->curbuf, scan->indexRelation,
224		stk->block);
225		continue;
226		}
227
228		if (!GistPageIsLeaf(p) \|\| resetoffset \|\|
229		!ItemPointerIsValid(&scan->currentItemData))
230		{
231		if (ScanDirectionIsBackward(dir))
232		n = PageGetMaxOffsetNumber(p);
233		else
234		n = FirstOffsetNumber;
235		}
236		else
237		{
238		n = ItemPointerGetOffsetNumber(&(scan->currentItemData));
239
240		if (ScanDirectionIsBackward(dir))
241		n = OffsetNumberPrev(n);
242		else
243		n = OffsetNumberNext(n);
244		}
245
246		/* wonderful, we can look at page */
247
248		for (;;)
249		{
250		n = gistfindnext(scan, n, dir);
251
252		if (!OffsetNumberIsValid(n))
253		{
254		/*
255		* We ran out of matching index entries on the current page,
256		* so pop the top stack entry and use it to continue the
257		* search.
258		*/
259		LockBuffer(so->curbuf, GIST_UNLOCK);
260		stk = so->stack->next;
261		pfree(so->stack);
262		so->stack = stk;
263
264		/* If we're out of stack entries, we're done */
265
266		if (so->stack == NULL)
267		{
268		ReleaseBuffer(so->curbuf);
269		so->curbuf = InvalidBuffer;
270		return ntids;
271		}
272
273		so->curbuf = ReleaseAndReadBuffer(so->curbuf,
274		scan->indexRelation,
275		stk->block);
276		/* XXX go up */
277		break;
278		}
279
280		if (GistPageIsLeaf(p))
281		{
282		/*
283		* We've found a matching index entry in a leaf page, so
284		* return success. Note that we keep "curbuf" pinned so that
285		* we can efficiently resume the index scan later.
286		*/
287
288		ItemPointerSet(&(scan->currentItemData),
289		BufferGetBlockNumber(so->curbuf), n);
290
291		if (!(ignore_killed_tuples && ItemIdDeleted(PageGetItemId(p, n))))
292		{
293		it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
294		tids[ntids] = scan->xs_ctup.t_self = it->t_tid;
295		ntids++;
296
297		if (ntids == maxtids)
298		{
299		LockBuffer(so->curbuf, GIST_UNLOCK);
300		return ntids;
301		}
302		}
303		}
304		else
305		{
306		/*
307		* We've found an entry in an internal node whose key is
308		* consistent with the search key, so push it to stack
309		*/
310
311		stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack));
312
313		it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
314		stk->block = ItemPointerGetBlockNumber(&(it->t_tid));
315		memset(&(stk->lsn), 0, sizeof(GistNSN));
316		stk->parentlsn = so->stack->lsn;
317
318		stk->next = so->stack->next;
319		so->stack->next = stk;
320
321		}
322
323		if (ScanDirectionIsBackward(dir))
324		n = OffsetNumberPrev(n);
325		else
326		n = OffsetNumberNext(n);
327		}
328		}
329
330		return ntids;
331		}
	266	Page p;
	267	OffsetNumber n;
	268	GISTScanOpaque so;
	269	GISTSearchStack *stk;
	270	IndexTuple it;
	271	GISTPageOpaque opaque;
	272	bool resetoffset = false;
	273	int ntids = 0;
	274
	275	/* CS186 HW2: This code currently returns tuples that match the query in
	276	* an arbitrary order (depth-first left-to-right). Modify it to return
	277	* matching tuples ordered by distance to search key
	278	*/
	279
	280	so = (GISTScanOpaque) scan->opaque;
	281
	282	if (ItemPointerIsValid(&scan->currentItemData) == false)
	283	{
	284	gistnext_get_root(scan, so);
	285	}
	286	else if (so->curbuf == InvalidBuffer)
	287	{
	288	return 0;
	289	}
	290
	291	for (;;)
	292	{
	293	/* First of all, we need to get a "lightweight" lock on the buffer */
	294	Assert(so->curbuf != InvalidBuffer);
	295	LockBuffer(so->curbuf, GIST_SHARE);
	296
	297	gistcheckpage(scan->indexRelation, so->curbuf);
	298	p = BufferGetPage(so->curbuf);
	299	opaque = GistPageGetOpaque(p);
	300	resetoffset = false;
	301
	302	/* deal with case where this page split since last we saw it */
	303	gistnext_checksplit(scan, so, p, opaque);
	304
	305	/* if page is empty, then just skip it */
	306	if (PageIsEmpty(p))
	307	{
	308	LockBuffer(so->curbuf, GIST_UNLOCK);
	309	stk = so->stack->next;
	310	pfree(so->stack);
	311	so->stack = stk;
	312
	313	if (so->stack == NULL)
	314	{
	315	ReleaseBuffer(so->curbuf);
	316	so->curbuf = InvalidBuffer;
	317	return ntids;
	318	}
	319
	320	so->curbuf = ReleaseAndReadBuffer(so->curbuf, scan->indexRelation,
	321	stk->block);
	322	continue;
	323	}
	324
	325	if (!GistPageIsLeaf(p) \|\| resetoffset \|\|
	326	!ItemPointerIsValid(&scan->currentItemData))
	327	{
	328	if (ScanDirectionIsBackward(dir))
	329	n = PageGetMaxOffsetNumber(p);
	330	else
	331	n = FirstOffsetNumber;
	332	}
	333	else
	334	{
	335	n = ItemPointerGetOffsetNumber(&(scan->currentItemData));
	336
	337	if (ScanDirectionIsBackward(dir))
	338	n = OffsetNumberPrev(n);
	339	else
	340	n = OffsetNumberNext(n);
	341	}
	342
	343	/* wonderful, we can look at page */
	344
	345	for (;;)
	346	{
	347	n = gistfindnext(scan, n, dir);
	348
	349	if (!OffsetNumberIsValid(n))
	350	{
	351	/*
	352	* We ran out of matching index entries on the current page,
	353	* so pop the top stack entry and use it to continue the
	354	* search.
	355	*/
	356	LockBuffer(so->curbuf, GIST_UNLOCK);
	357	stk = so->stack->next;
	358	pfree(so->stack);
	359	so->stack = stk;
	360
	361	/* If we're out of stack entries, we're done */
	362
	363	if (so->stack == NULL)
	364	{
	365	ReleaseBuffer(so->curbuf);
	366	so->curbuf = InvalidBuffer;
	367	return ntids;
	368	}
	369
	370	so->curbuf = ReleaseAndReadBuffer(so->curbuf,
	371	scan->indexRelation,
	372	stk->block);
	373	/* XXX go up */
	374	break;
	375	}
	376
	377	if (GistPageIsLeaf(p))
	378	{
	379	/*
	380	* We've found a matching index entry in a leaf page, so
	381	* return success. Note that we keep "curbuf" pinned so that
	382	* we can efficiently resume the index scan later.
	383	*/
	384
	385	ItemPointerSet(&(scan->currentItemData),
	386	BufferGetBlockNumber(so->curbuf), n);
	387
	388	if (!(ignore_killed_tuples && ItemIdDeleted(PageGetItemId(p, n))))
	389	{
	390	it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
	391	tids[ntids] = scan->xs_ctup.t_self = it->t_tid;
	392	ntids++;
	393
	394	if (ntids == maxtids)
	395	{
	396	LockBuffer(so->curbuf, GIST_UNLOCK);
	397	return ntids;
	398	}
	399	}
	400	}
	401	else
	402	{
	403	/*
	404	* We've found an entry in an internal node whose key is
	405	* consistent with the search key, so push it to stack
	406	*/
	407
	408	stk = (GISTSearchStack *) palloc0(sizeof(GISTSearchStack));
	409
	410	it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
	411	stk->block = ItemPointerGetBlockNumber(&(it->t_tid));
	412	memset(&(stk->lsn), 0, sizeof(GistNSN));
	413	stk->parentlsn = so->stack->lsn;
	414
	415	stk->next = so->stack->next;
	416	so->stack->next = stk;
	417
	418	}
	419
	420	if (ScanDirectionIsBackward(dir))
	421	n = OffsetNumberPrev(n);
	422	else
	423	n = OffsetNumberNext(n);
	424	}
	425	}
	426
	427	return ntids;
	428	}
	429
332	430
333	431	/*
…	…
344	442	static bool
345	443	gistindex_keytest(IndexTuple tuple,
346		IndexScanDesc scan,
347		OffsetNumber offset)
348		{
349		int keySize = scan->numberOfKeys;
350		ScanKey key = scan->keyData;
351		Relation r = scan->indexRelation;
352		GISTScanOpaque so;
353		Page p;
354		GISTSTATE *giststate;
355
356		so = (GISTScanOpaque) scan->opaque;
357		giststate = so->giststate;
358		p = BufferGetPage(so->curbuf);
359
360		IncrIndexProcessed();
361
362		/*
363		* Tuple doesn't restore after crash recovery because of incomplete insert
364		*/
365		if (!GistPageIsLeaf(p) && GistTupleIsInvalid(tuple))
366		return true;
367
368		while (keySize > 0)
369		{
370		Datum datum;
371		bool isNull;
372		Datum test;
373		GISTENTRY de;
374
375		datum = index_getattr(tuple,
376		key->sk_attno,
377		giststate->tupdesc,
378		&isNull);
379
380		if (key->sk_flags & SK_ISNULL)
381		{
382		/*
383		* is the compared-to datum NULL? on non-leaf page it's possible
384		* to have nulls in childs :(
385		*/
386
387		if (isNull \|\| !GistPageIsLeaf(p))
388		return true;
389		return false;
390		}
391		else if (isNull)
392		return false;
393
394		gistdentryinit(giststate, key->sk_attno - 1, &de,
395		datum, r, p, offset,
396		FALSE, isNull);
397
398		/*
399		* Call the Consistent function to evaluate the test. The arguments
400		* are the index datum (as a GISTENTRY*), the comparison datum, and
401		* the comparison operator's strategy number and subtype from pg_amop.
402		*
403		* (Presently there's no need to pass the subtype since it'll always
404		* be zero, but might as well pass it for possible future use.)
405		*/
406		test = FunctionCall4(&key->sk_func,
407		PointerGetDatum(&de),
408		key->sk_argument,
409		Int32GetDatum(key->sk_strategy),
410		ObjectIdGetDatum(key->sk_subtype));
411
412		if (!DatumGetBool(test))
413		return false;
414
415		keySize--;
416		key++;
417		}
418
419		return true;
	444	IndexScanDesc scan,
	445	OffsetNumber offset)
	446	{
	447	int keySize = scan->numberOfKeys;
	448	ScanKey key = scan->keyData;
	449	Relation r = scan->indexRelation;
	450	GISTScanOpaque so;
	451	Page p;
	452	GISTSTATE *giststate;
	453
	454	so = (GISTScanOpaque) scan->opaque;
	455	giststate = so->giststate;
	456	p = BufferGetPage(so->curbuf);
	457
	458	IncrIndexProcessed();
	459
	460	/*
	461	* Tuple doesn't restore after crash recovery because of incomplete insert
	462	*/
	463	if (!GistPageIsLeaf(p) && GistTupleIsInvalid(tuple))
	464	return true;
	465
	466	while (keySize > 0)
	467	{
	468	Datum datum;
	469	bool isNull;
	470	Datum test;
	471	GISTENTRY de;
	472
	473	datum = index_getattr(tuple,
	474	key->sk_attno,
	475	giststate->tupdesc,
	476	&isNull);
	477
	478	if (key->sk_flags & SK_ISNULL)
	479	{
	480	/*
	481	* is the compared-to datum NULL? on non-leaf page it's possible
	482	* to have nulls in childs :(
	483	*/
	484
	485	if (isNull \|\| !GistPageIsLeaf(p))
	486	return true;
	487	return false;
	488	}
	489	else if (isNull)
	490	return false;
	491
	492	/* decompress the key! */
	493	gistdentryinit(giststate, key->sk_attno - 1, &de,
	494	datum, r, p, offset,
	495	FALSE, isNull);
	496
	497	/*
	498	* Call the Consistent function to evaluate the test. The arguments
	499	* are the index datum (as a GISTENTRY*), the comparison datum, and
	500	* the comparison operator's strategy number and subtype from pg_amop.
	501	*
	502	* (Presently there's no need to pass the subtype since it'll always
	503	* be zero, but might as well pass it for possible future use.)
	504	*/
	505	test = FunctionCall4(&key->sk_func,
	506	PointerGetDatum(&de),
	507	key->sk_argument,
	508	Int32GetDatum(key->sk_strategy),
	509	ObjectIdGetDatum(key->sk_subtype));
	510
	511	if (!DatumGetBool(test))
	512	return false;
	513
	514	keySize--;
	515	key++;
	516	}
	517
	518	return true;
	519	}
	520
	521	/*
	522	* Use the mindistance function to compute the distance of the given index
	523	* entry from the constant in the scan. See gistindex_keytest for an
	524	* analogous task.
	525	*/
	526
	527	static double
	528	gistindex_keydistance( IndexTuple tuple,
	529	IndexScanDesc scan,
	530	OffsetNumber offset)
	531	{
	532	/* fill me in! */
	533	return get_float8_infinity();
420	534	}
421	535
…	…
429	543	gistfindnext(IndexScanDesc scan, OffsetNumber n, ScanDirection dir)
430	544	{
431		OffsetNumber maxoff;
432		~~IndexTuple~~ it;
433		GISTScanOpaque so;
434		MemoryContext oldcxt;
435		~~Page~~ p;
436
437		so = (GISTScanOpaque) scan->opaque;
438		p = BufferGetPage(so->curbuf);
439		maxoff = PageGetMaxOffsetNumber(p);
440
441		/*
442		* Make sure we're in a short-lived memory context when we invoke a
443		* user-supplied GiST method in gistindex_keytest(), so we don't leak
444		* memory
445		*/
446		oldcxt = MemoryContextSwitchTo(so->tempCxt);
447
448		/*
449		* If we modified the index during the scan, we may have a pointer to a
450		* ghost tuple, before the scan. If this is the case, back up one.
451		*/
452		if (so->flags & GS_CURBEFORE)
453		{
454		so->flags &= ~GS_CURBEFORE;
455		n = OffsetNumberPrev(n);
456		}
457
458		while (n >= FirstOffsetNumber && n <= maxoff)
459		{
460		it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
461		if (gistindex_keytest(it, scan, n))
462		break;
463
464		if (ScanDirectionIsBackward(dir))
465		n = OffsetNumberPrev(n);
466		else
467		n = OffsetNumberNext(n);
468		}
469
470		MemoryContextSwitchTo(oldcxt);
471		MemoryContextReset(so->tempCxt);
472
473		/*
474		* If we found a matching entry, return its offset; otherwise return
475		* InvalidOffsetNumber to inform the caller to go to the next page.
476		*/
477		if (n >= FirstOffsetNumber && n <= maxoff)
478		return n;
479		else
480		return InvalidOffsetNumber;
481		}
	545	OffsetNumber maxoff;
	546	IndexTuple it;
	547	GISTScanOpaque so;
	548	MemoryContext oldcxt;
	549	Page p;
	550
	551	so = (GISTScanOpaque) scan->opaque;
	552	p = BufferGetPage(so->curbuf);
	553	maxoff = PageGetMaxOffsetNumber(p);
	554
	555	/*
	556	* Make sure we're in a short-lived memory context when we invoke a
	557	* user-supplied GIST method in gistindex_keytest(), so we don't leak
	558	* memory
	559	*/
	560	oldcxt = MemoryContextSwitchTo(so->tempCxt);
	561
	562	/*
	563	* If we modified the index during the scan, we may have a pointer to a
	564	* ghost tuple, before the scan. If this is the case, back up one.
	565	*/
	566	if (so->flags & GS_CURBEFORE)
	567	{
	568	so->flags &= ~GS_CURBEFORE;
	569	n = OffsetNumberPrev(n);
	570	}
	571
	572	while (n >= FirstOffsetNumber && n <= maxoff)
	573	{
	574	it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
	575	if (gistindex_keytest(it, scan, n))
	576	break;
	577
	578	if (ScanDirectionIsBackward(dir))
	579	n = OffsetNumberPrev(n);
	580	else
	581	n = OffsetNumberNext(n);
	582	}
	583
	584	MemoryContextSwitchTo(oldcxt);
	585	MemoryContextReset(so->tempCxt);
	586
	587	/*
	588	* If we found a matching entry, return its offset; otherwise return
	589	* InvalidOffsetNumber to inform the caller to go to the next page.
	590	*/
	591	if (n >= FirstOffsetNumber && n <= maxoff)
	592	return n;
	593	else
	594	return InvalidOffsetNumber;
	595	}

hw/hw2/postgresql-8.2.4/src/backend/access/gist/gistproc.c

r22	r23
20	20	#include "access/skey.h"
21	21	#include "utils/geo_decls.h"
	22	#include "utils/builtins.h"
22	23
23	24
…	…
110	111	query,
111	112	strategy));
	113	}
	114
	115	/*
	116	* The GiST MinDist method for boxes
	117	*
	118	*/
	119	Datum
	120	gist_box_mindistance(PG_FUNCTION_ARGS)
	121	{
	122	GISTENTRY entry = (GISTENTRY ) PG_GETARG_POINTER(0);
	123	BOX *query = PG_GETARG_BOX_P(1);
	124	double d;
	125
	126	if (DatumGetBoxP(entry->key) == NULL \|\| query == NULL) {
	127	d = get_float8_infinity();
	128	PG_RETURN_FLOAT8(d);
	129	}
	130	d = box_mindist_internal(DatumGetBoxP(entry->key), query);
	131	PG_RETURN_FLOAT8(d);
	132	}
	133
	134	Datum gist_infinite_mindistance(PG_FUNCTION_ARGS)
	135	{
	136	double d = get_float8_infinity();
	137	PG_RETURN_FLOAT8(d);
112	138	}
113	139

hw/hw2/postgresql-8.2.4/src/backend/access/gist/gistscan.c

r22	r23
19	19	#include "access/gistscan.h"
20	20	#include "utils/memutils.h"
21
22		~~static void gistfreestack(GISTSearchStack *s);~~
23	21
24	22	Datum
…	…
227	225	}
228	226
229		~~static~~ void
	227	void
230	228	gistfreestack(GISTSearchStack *s)
231	229	{
…	…
238	236	}
239	237	}
	238
	239	GISTSearchStack *
	240	gistcopystack(GISTSearchStack *s)
	241	{
	242	GISTSearchStack *newstk = NULL;
	243
	244	if (s != NULL)
	245	{
	246	newstk = (GISTSearchStack *)palloc(sizeof(GISTSearchStack));
	247	memcpy(newstk, s, sizeof(GISTSearchStack));
	248	newstk->next = gistcopystack(s->next);
	249	}
	250	return newstk;
	251	}

hw/hw2/postgresql-8.2.4/src/include/access/gist.h

r22	r23
33	33	#define GIST_PICKSPLIT_PROC 6
34	34	#define GIST_EQUAL_PROC 7
35		#define GISTNProcs 7
	35	#define GIST_DISTANCE_PROC 8
	36	#define GISTNProcs 8
36	37
37	38	/*

hw/hw2/postgresql-8.2.4/src/include/access/gist_private.h

r22	r23
48	48	} GISTSearchStack;
49	49
	50
	51	/*
	52	* GiST priority queue for search traversal. Priority is defined by a
	53	* user-specified mindist metric. For now, a naive linked-list
	54	* implementation, should be replaced with a smarter heap
	55	*/
	56	typedef struct GISTPQ
	57	{
	58	/* fill me in! */
	59	} GISTPQ;
	60
50	61	typedef struct GISTSTATE
51	62	{
…	…
57	68	FmgrInfo picksplitFn[INDEX_MAX_KEYS];
58	69	FmgrInfo equalFn[INDEX_MAX_KEYS];
	70	FmgrInfo distanceFn[INDEX_MAX_KEYS];
59	71
60	72	TupleDesc tupdesc;
…	…
74	86	Buffer curbuf;
75	87	Buffer markbuf;
	88	GISTPQ *pq;
76	89	} GISTScanOpaqueData;
77	90
…	…
271	284	extern Datum gistgettuple(PG_FUNCTION_ARGS);
272	285	extern Datum gistgetmulti(PG_FUNCTION_ARGS);
	286
	287	/* gistscan.c */
	288	extern void gistfreestack(GISTSearchStack *s);
	289	extern GISTSearchStack gistcopystack(GISTSearchStack s);
273	290
274	291	/* gistutil.c */

hw/hw2/postgresql-8.2.4/src/include/catalog/pg_am.h

r22	r23
115	115	DESCR("hash index access method");
116	116	#define HASH_AM_OID 405
117		DATA(insert OID = 783 ( gist 100 7 0 f t t t t t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
	117	DATA(insert OID = 783 ( gist 100 8 0 f t t t t t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
118	118	DESCR("GiST index access method");
119	119	#define GIST_AM_OID 783

hw/hw2/postgresql-8.2.4/src/include/catalog/pg_amproc.h

r22	r23
172	172	DATA(insert ( 2593 0 6 2582 ));
173	173	DATA(insert ( 2593 0 7 2584 ));
	174	DATA(insert ( 2593 0 8 2893 ));
174	175	DATA(insert ( 2594 0 1 2585 ));
175	176	DATA(insert ( 2594 0 2 2583 ));
…	…
179	180	DATA(insert ( 2594 0 6 2582 ));
180	181	DATA(insert ( 2594 0 7 2584 ));
	182	DATA(insert ( 2594 0 8 2895 ));
181	183	DATA(insert ( 2595 0 1 2591 ));
182	184	DATA(insert ( 2595 0 2 2583 ));
…	…
186	188	DATA(insert ( 2595 0 6 2582 ));
187	189	DATA(insert ( 2595 0 7 2584 ));
	190	DATA(insert ( 2595 0 8 2895 ));
188	191
189	192	/* gin */

hw/hw2/postgresql-8.2.4/src/include/catalog/pg_operator.h

r22	r23
904	904	DATA(insert OID = 2877 ( "~" PGNSP PGUID b f 1034 1033 16 0 0 0 0 0 0 aclcontains - - ));
905	905
	906	/* mindist function for near-neighbor search on boxes */
	907	DATA(insert OID = 2880 ( "~~" PGNSP PGUID b f 603 603 16 0 0 0 0 0 0 box_mindistance positionsel positionjoinsel ));
906	908
907	909	/*

hw/hw2/postgresql-8.2.4/src/include/catalog/pg_proc.h

r22	r23
3974	3974	DATA(insert OID = 2892 ( pg_advisory_unlock_all PGNSP PGUID 12 f f t f v 0 2278 "" _null_ _null_ _null_ pg_advisory_unlock_all - _null_ ));
3975	3975	DESCR("release all advisory locks");
	3976	DATA(insert OID = 2893 ( gist_box_mindistance PGNSP PGUID 12 f f t f i 2 701 "2281 603" _null_ _null_ _null_ gist_box_mindistance - _null_ ));
	3977	DESCR("gist support");
	3978	DATA(insert OID = 2894 ( box_mindistance PGNSP PGUID 12 f f t f i 2 701 "603 603" _null_ _null_ _null_ box_mindistance - _null_ ));
	3979	DESCR("bounding box minimum distance metric for gist NN search");
	3980	DATA(insert OID = 2895 ( gist_infinite_mindistance PGNSP PGUID 12 f f t f i 2 701 "2281 603" _null_ _null_ _null_ gist_infinite_mindistance - _null_ ));
	3981	DESCR("gist support");
3976	3982
3977	3983	/*

hw/hw2/postgresql-8.2.4/src/include/utils/geo_decls.h

r22	r23
310	310	extern Datum box_mul(PG_FUNCTION_ARGS);
311	311	extern Datum box_div(PG_FUNCTION_ARGS);
	312	extern Datum box_mindistance(PG_FUNCTION_ARGS);
	313	extern double box_mindist_internal(BOX box1, BOX box2);
312	314
313	315	/* public path routines */
…	…
421	423	extern Datum gist_circle_compress(PG_FUNCTION_ARGS);
422	424	extern Datum gist_circle_consistent(PG_FUNCTION_ARGS);
	425	extern Datum gist_box_mindistance(PG_FUNCTION_ARGS);
	426	extern Datum gist_infinite_mindistance(PG_FUNCTION_ARGS);
423	427
424	428	/* geo_selfuncs.c */

Context Navigation

Changeset 23

Legend:

Download in other formats: