Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit03e56f7

Browse files
committed
Restructure SPGiST opclass interface API to support whole-index scans.
The original API definition was incapable of supporting whole-index scansbecause there was no way to invoke leaf-value reconstruction withoutchecking any qual conditions. Also, it was inefficient formultiple-qual-condition scans because value reconstruction got done overagain for each qual condition, and because other internal work in theconsistent functions likewise had to be done for each qual. To fix theseissues, pass the whole scankey array to the opclass consistent functions,instead of only letting them see one item at a time. (Essentially, theloop over scankey entries is now inside the consistent functions notoutside them. This makes the consistent functions a bit more complicated,but not unreasonably so.)In itself this commit does nothing except save a few cycles inmultiple-qual-condition index scans, since we can't support whole-indexscans on SPGiST indexes until nulls are included in the index. However,I consider this a must-fix for 9.2 because once we release it will getvery much harder to change the opclass API definition.
1 parent39d74e3 commit03e56f7

File tree

7 files changed

+517
-526
lines changed

7 files changed

+517
-526
lines changed

‎doc/src/sgml/spgist.sgml

Lines changed: 28 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -439,8 +439,8 @@ CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
439439
<programlisting>
440440
typedef struct spgInnerConsistentIn
441441
{
442-
StrategyNumber strategy; /*operator strategy number */
443-
Datumquery; /*operator's RHS value */
442+
ScanKey scankeys;/*array of operators and comparison values */
443+
int nkeys; /*length of array */
444444

445445
Datum reconstructedValue; /* value reconstructed at parent */
446446
int level; /* current level (counting from zero) */
@@ -463,8 +463,17 @@ typedef struct spgInnerConsistentOut
463463
} spgInnerConsistentOut;
464464
</programlisting>
465465

466-
<structfield>strategy</> and
467-
<structfield>query</> describe the index search condition.
466+
The array <structfield>scankeys</>, of length <structfield>nkeys</>,
467+
describes the index search condition(s). These conditions are
468+
combined with AND &mdash; only index entries that satisfy all of
469+
them are interesting. (Note that <structfield>nkeys</> = 0 implies
470+
that all index entries satisfy the query.) Usually the consistent
471+
function only cares about the <structfield>sk_strategy</> and
472+
<structfield>sk_argument</> fields of each array entry, which
473+
respectively give the indexable operator and comparison value.
474+
In particular it is not necessary to check <structfield>sk_flags</> to
475+
see if the comparison value is NULL, because the SP-GiST core code
476+
will filter out such conditions.
468477
<structfield>reconstructedValue</> is the value reconstructed for the
469478
parent tuple; it is <literal>(Datum) 0</> at the root level or if the
470479
<function>inner_consistent</> function did not provide a value at the
@@ -527,8 +536,8 @@ CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
527536
<programlisting>
528537
typedef struct spgLeafConsistentIn
529538
{
530-
StrategyNumber strategy; /*operator strategy number */
531-
Datumquery; /*operator's RHS value */
539+
ScanKey scankeys;/*array of operators and comparison values */
540+
int nkeys; /*length of array */
532541

533542
Datum reconstructedValue; /* value reconstructed at parent */
534543
int level; /* current level (counting from zero) */
@@ -544,8 +553,17 @@ typedef struct spgLeafConsistentOut
544553
} spgLeafConsistentOut;
545554
</programlisting>
546555

547-
<structfield>strategy</> and
548-
<structfield>query</> define the index search condition.
556+
The array <structfield>scankeys</>, of length <structfield>nkeys</>,
557+
describes the index search condition(s). These conditions are
558+
combined with AND &mdash; only index entries that satisfy all of
559+
them satisfy the query. (Note that <structfield>nkeys</> = 0 implies
560+
that all index entries satisfy the query.) Usually the consistent
561+
function only cares about the <structfield>sk_strategy</> and
562+
<structfield>sk_argument</> fields of each array entry, which
563+
respectively give the indexable operator and comparison value.
564+
In particular it is not necessary to check <structfield>sk_flags</> to
565+
see if the comparison value is NULL, because the SP-GiST core code
566+
will filter out such conditions.
549567
<structfield>reconstructedValue</> is the value reconstructed for the
550568
parent tuple; it is <literal>(Datum) 0</> at the root level or if the
551569
<function>inner_consistent</> function did not provide a value at the
@@ -566,8 +584,8 @@ typedef struct spgLeafConsistentOut
566584
<structfield>leafValue</> must be set to the value originally supplied
567585
to be indexed for this leaf tuple. Also,
568586
<structfield>recheck</> may be set to <literal>true</> if the match
569-
is uncertain and so the operator must be re-applied to the actual heap
570-
tuple to verify the match.
587+
is uncertain and so the operator(s) must be re-applied to the actual
588+
heaptuple to verify the match.
571589
</para>
572590
</listitem>
573591
</varlistentry>

‎src/backend/access/spgist/spgkdtreeproc.c

Lines changed: 80 additions & 108 deletions
Original file line numberDiff line numberDiff line change
@@ -159,136 +159,108 @@ spg_kd_inner_consistent(PG_FUNCTION_ARGS)
159159
{
160160
spgInnerConsistentIn*in= (spgInnerConsistentIn*)PG_GETARG_POINTER(0);
161161
spgInnerConsistentOut*out= (spgInnerConsistentOut*)PG_GETARG_POINTER(1);
162-
Point*query;
163-
BOX*boxQuery;
164162
doublecoord;
163+
intwhich;
164+
inti;
165165

166-
query=DatumGetPointP(in->query);
167166
Assert(in->hasPrefix);
168167
coord=DatumGetFloat8(in->prefixDatum);
169168

170169
if (in->allTheSame)
171170
elog(ERROR,"allTheSame should not occur for k-d trees");
172171

173172
Assert(in->nNodes==2);
174-
out->nodeNumbers= (int*)palloc(sizeof(int)*2);
175-
out->levelAdds= (int*)palloc(sizeof(int)*2);
176-
out->levelAdds[0]=1;
177-
out->levelAdds[1]=1;
178-
out->nNodes=0;
179173

180-
switch (in->strategy)
174+
/* "which" is a bitmask of children that satisfy all constraints */
175+
which= (1 <<1) | (1 <<2);
176+
177+
for (i=0;i<in->nkeys;i++)
181178
{
182-
caseRTLeftStrategyNumber:
183-
out->nNodes=1;
184-
out->nodeNumbers[0]=0;
185-
186-
if ((in->level %2)==0||FPge(query->x,coord))
187-
{
188-
out->nodeNumbers[1]=1;
189-
out->nNodes++;
190-
}
191-
break;
192-
caseRTRightStrategyNumber:
193-
out->nNodes=1;
194-
out->nodeNumbers[0]=1;
195-
196-
if ((in->level %2)==0||FPle(query->x,coord))
197-
{
198-
out->nodeNumbers[1]=0;
199-
out->nNodes++;
200-
}
201-
break;
202-
caseRTSameStrategyNumber:
203-
if (in->level %2)
204-
{
205-
if (FPle(query->x,coord))
206-
{
207-
out->nodeNumbers[out->nNodes]=0;
208-
out->nNodes++;
209-
}
210-
if (FPge(query->x,coord))
211-
{
212-
out->nodeNumbers[out->nNodes]=1;
213-
out->nNodes++;
214-
}
215-
}
216-
else
217-
{
218-
if (FPle(query->y,coord))
179+
Point*query=DatumGetPointP(in->scankeys[i].sk_argument);
180+
BOX*boxQuery;
181+
182+
switch (in->scankeys[i].sk_strategy)
183+
{
184+
caseRTLeftStrategyNumber:
185+
if ((in->level %2)!=0&&FPlt(query->x,coord))
186+
which &= (1 <<1);
187+
break;
188+
caseRTRightStrategyNumber:
189+
if ((in->level %2)!=0&&FPgt(query->x,coord))
190+
which &= (1 <<2);
191+
break;
192+
caseRTSameStrategyNumber:
193+
if ((in->level %2)!=0)
219194
{
220-
out->nodeNumbers[out->nNodes]=0;
221-
out->nNodes++;
195+
if (FPlt(query->x,coord))
196+
which &= (1 <<1);
197+
elseif (FPgt(query->x,coord))
198+
which &= (1 <<2);
222199
}
223-
if (FPge(query->y,coord))
200+
else
224201
{
225-
out->nodeNumbers[out->nNodes]=1;
226-
out->nNodes++;
202+
if (FPlt(query->y,coord))
203+
which &= (1 <<1);
204+
elseif (FPgt(query->y,coord))
205+
which &= (1 <<2);
227206
}
228-
}
229-
break;
230-
caseRTBelowStrategyNumber:
231-
out->nNodes=1;
232-
out->nodeNumbers[0]=0;
233-
234-
if ((in->level %2)==1||FPge(query->y,coord))
235-
{
236-
out->nodeNumbers[1]=1;
237-
out->nNodes++;
238-
}
239-
break;
240-
caseRTAboveStrategyNumber:
241-
out->nNodes=1;
242-
out->nodeNumbers[0]=1;
243-
244-
if ((in->level %2)==1||FPle(query->y,coord))
245-
{
246-
out->nodeNumbers[1]=0;
247-
out->nNodes++;
248-
}
249-
break;
250-
caseRTContainedByStrategyNumber:
251-
252-
/*
253-
* For this operator, the query is a box not a point. We cheat to
254-
* the extent of assuming that DatumGetPointP won't do anything
255-
* that would be bad for a pointer-to-box.
256-
*/
257-
boxQuery=DatumGetBoxP(in->query);
258-
259-
out->nNodes=1;
260-
if (in->level %2)
261-
{
262-
if (FPlt(boxQuery->high.x,coord))
263-
out->nodeNumbers[0]=0;
264-
elseif (FPgt(boxQuery->low.x,coord))
265-
out->nodeNumbers[0]=1;
266-
else
207+
break;
208+
caseRTBelowStrategyNumber:
209+
if ((in->level %2)==0&&FPlt(query->y,coord))
210+
which &= (1 <<1);
211+
break;
212+
caseRTAboveStrategyNumber:
213+
if ((in->level %2)==0&&FPgt(query->y,coord))
214+
which &= (1 <<2);
215+
break;
216+
caseRTContainedByStrategyNumber:
217+
218+
/*
219+
* For this operator, the query is a box not a point. We
220+
* cheat to the extent of assuming that DatumGetPointP won't
221+
* do anything that would be bad for a pointer-to-box.
222+
*/
223+
boxQuery=DatumGetBoxP(in->scankeys[i].sk_argument);
224+
225+
if ((in->level %2)!=0)
267226
{
268-
out->nodeNumbers[0]=0;
269-
out->nodeNumbers[1]=1;
270-
out->nNodes=2;
227+
if (FPlt(boxQuery->high.x,coord))
228+
which &= (1 <<1);
229+
elseif (FPgt(boxQuery->low.x,coord))
230+
which &= (1 <<2);
271231
}
272-
}
273-
else
274-
{
275-
if (FPlt(boxQuery->high.y,coord))
276-
out->nodeNumbers[0]=0;
277-
elseif (FPgt(boxQuery->low.y,coord))
278-
out->nodeNumbers[0]=1;
279232
else
280233
{
281-
out->nodeNumbers[0]=0;
282-
out->nodeNumbers[1]=1;
283-
out->nNodes=2;
234+
if (FPlt(boxQuery->high.y,coord))
235+
which &= (1 <<1);
236+
elseif (FPgt(boxQuery->low.y,coord))
237+
which &= (1 <<2);
284238
}
285-
}
286-
break;
287-
default:
288-
elog(ERROR,"unrecognized strategy number: %d",in->strategy);
289-
break;
239+
break;
240+
default:
241+
elog(ERROR,"unrecognized strategy number: %d",
242+
in->scankeys[i].sk_strategy);
243+
break;
244+
}
245+
246+
if (which==0)
247+
break;/* no need to consider remaining conditions */
290248
}
291249

250+
/* We must descend into the children identified by which */
251+
out->nodeNumbers= (int*)palloc(sizeof(int)*2);
252+
out->nNodes=0;
253+
for (i=1;i <=2;i++)
254+
{
255+
if (which& (1 <<i))
256+
out->nodeNumbers[out->nNodes++]=i-1;
257+
}
258+
259+
/* Set up level increments, too */
260+
out->levelAdds= (int*)palloc(sizeof(int)*2);
261+
out->levelAdds[0]=1;
262+
out->levelAdds[1]=1;
263+
292264
PG_RETURN_VOID();
293265
}
294266

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp