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

Commitc5608ea

Browse files
committed
Allow opclasses to provide tri-valued GIN consistent functions.
With the GIN "fast scan" feature, GIN can skip items without fetching allthe keys for them, if it can prove that they don't match regardless ofthose keys. So far, it has done the proving by calling the booleanconsistent function with all combinations of TRUE/FALSE for the unfetchedkeys, but since that's O(n^2), it becomes unfeasible with more than a fewkeys. We can avoid calling consistent with all the combinations, if we cantell the operator class implementation directly which keys are unknown.This commit includes a triConsistent function for the built-in array andtsvector opclasses.Alexander Korotkov, with some changes by me.
1 parentfecfc2b commitc5608ea

File tree

16 files changed

+469
-103
lines changed

16 files changed

+469
-103
lines changed

‎doc/src/sgml/gin.sgml

Lines changed: 47 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -74,15 +74,15 @@
7474

7575
<para>
7676
All it takes to get a <acronym>GIN</acronym> access method working is to
77-
implementfour (or five) user-defined methods, which define the behavior of
77+
implementa few user-defined methods, which define the behavior of
7878
keys in the tree and the relationships between keys, indexed items,
7979
and indexable queries. In short, <acronym>GIN</acronym> combines
8080
extensibility with generality, code reuse, and a clean interface.
8181
</para>
8282

8383
<para>
84-
The four methods that an operator class for
85-
<acronym>GIN</acronym> must provide are:
84+
There are three methods that an operator class for
85+
<acronym>GIN</acronym> must provide:
8686

8787
<variablelist>
8888
<varlistentry>
@@ -190,7 +190,18 @@
190190

191191
</listitem>
192192
</varlistentry>
193+
</variablelist>
194+
195+
An operator class must also provide a function to check if an indexed item
196+
matches the query. It comes in two flavors, a boolean <function>consistent</>
197+
function, and a ternary <function>triConsistent</> function.
198+
<function>triConsistent</> covers the functionality of both, so providing
199+
triConsistent alone is sufficient. However, if the boolean variant is
200+
significantly cheaper to calculate, it can be advantegous to provide both.
201+
If only the boolean variant is provided, some optimizations that depend on
202+
refuting index items before fetching all the keys are disabled.
193203

204+
<variablelist>
194205
<varlistentry>
195206
<term><function>bool consistent(bool check[], StrategyNumber n, Datum query,
196207
int32 nkeys, Pointer extra_data[], bool *recheck,
@@ -241,10 +252,38 @@
241252
</para>
242253
</listitem>
243254
</varlistentry>
255+
256+
<varlistentry>
257+
<term><function>GinLogicValue triConsistent(GinLogicValue check[], StrategyNumber n, Datum query,
258+
int32 nkeys, Pointer extra_data[],
259+
Datum queryKeys[], bool nullFlags[])</></term>
260+
<listitem>
261+
<para>
262+
<function>triConsistent</> is similar to <function>consistent</>,
263+
but instead of a boolean <literal>check[]</>, there are three possible
264+
values for each key: <literal>GIN_TRUE</>, <literal>GIN_FALSE</> and
265+
<literal>GIN_MAYBE</>. <literal>GIN_FALSE</> and <literal>GIN_TRUE</>
266+
have the same meaning as regular boolean values.
267+
<literal>GIN_MAYBE</> means that the presence of that key is not known.
268+
When <literal>GIN_MAYBE</> values are present, the function should only
269+
return GIN_TRUE if the item matches whether or not the index item
270+
contains the corresponding query keys. Likewise, the function must
271+
return GIN_FALSE only if the item does not match, whether or not it
272+
contains the GIN_MAYBE keys. If the result depends on the GIN_MAYBE
273+
entries, ie. the match cannot be confirmed or refuted based on the
274+
known query keys, the function must return GIN_MAYBE.
275+
</para>
276+
<para>
277+
When there are no GIN_MAYBE values in the <literal>check</> vector,
278+
<literal>GIN_MAYBE</> return value is equivalent of setting
279+
<literal>recheck</> flag in the boolean <function>consistent</> function.
280+
</para>
281+
</listitem>
282+
</varlistentry>
244283
</variablelist>
245284

246-
Optionally, an operator class for
247-
<acronym>GIN</acronym> can supply a fifth method:
285+
Optionally, an operator class for <acronym>GIN</acronym> can supply the
286+
following method:
248287

249288
<variablelist>
250289
<varlistentry>
@@ -282,8 +321,9 @@
282321
above vary depending on the operator class. The item values passed to
283322
<function>extractValue</> are always of the operator class's input type, and
284323
all key values must be of the class's <literal>STORAGE</> type. The type of
285-
the <literal>query</> argument passed to <function>extractQuery</> and
286-
<function>consistent</> is whatever is specified as the right-hand input
324+
the <literal>query</> argument passed to <function>extractQuery</>,
325+
<function>consistent</> and <function>triConsistent</> is whatever is
326+
specified as the right-hand input
287327
type of the class member operator identified by the strategy number.
288328
This need not be the same as the item type, so long as key values of the
289329
correct type can be extracted from it.

‎doc/src/sgml/xindex.sgml

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -567,7 +567,10 @@
567567
</row>
568568
<row>
569569
<entry><function>consistent</></entry>
570-
<entry>determine whether value matches query condition</entry>
570+
<entry>
571+
determine whether value matches query condition (boolean variant)
572+
(optional if support function 6 is present)
573+
</entry>
571574
<entry>4</entry>
572575
</row>
573576
<row>
@@ -580,6 +583,14 @@
580583
</entry>
581584
<entry>5</entry>
582585
</row>
586+
<row>
587+
<entry><function>triConsistent</></entry>
588+
<entry>
589+
determine whether value matches query condition (ternary variant)
590+
(optional if support function 4 is present)
591+
</entry>
592+
<entry>6</entry>
593+
</row>
583594
</tbody>
584595
</tgroup>
585596
</table>

‎src/backend/access/gin/ginarrayproc.c

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,3 +218,87 @@ ginarrayconsistent(PG_FUNCTION_ARGS)
218218

219219
PG_RETURN_BOOL(res);
220220
}
221+
222+
/*
223+
* triconsistent support function
224+
*/
225+
Datum
226+
ginarraytriconsistent(PG_FUNCTION_ARGS)
227+
{
228+
GinLogicValue*check= (GinLogicValue*)PG_GETARG_POINTER(0);
229+
StrategyNumberstrategy=PG_GETARG_UINT16(1);
230+
231+
/* ArrayType *query = PG_GETARG_ARRAYTYPE_P(2); */
232+
int32nkeys=PG_GETARG_INT32(3);
233+
234+
/* Pointer *extra_data = (Pointer *) PG_GETARG_POINTER(4); */
235+
/* Datum *queryKeys = (Datum *) PG_GETARG_POINTER(5); */
236+
bool*nullFlags= (bool*)PG_GETARG_POINTER(6);
237+
GinLogicValueres;
238+
int32i;
239+
240+
switch (strategy)
241+
{
242+
caseGinOverlapStrategy:
243+
/* must have a match for at least one non-null element */
244+
res=GIN_FALSE;
245+
for (i=0;i<nkeys;i++)
246+
{
247+
if (!nullFlags[i])
248+
{
249+
if (check[i]==GIN_TRUE)
250+
{
251+
res=GIN_TRUE;
252+
break;
253+
}
254+
elseif (check[i]==GIN_MAYBE&&res==GIN_FALSE)
255+
{
256+
res=GIN_MAYBE;
257+
}
258+
}
259+
}
260+
break;
261+
caseGinContainsStrategy:
262+
/* must have all elements in check[] true, and no nulls */
263+
res=GIN_TRUE;
264+
for (i=0;i<nkeys;i++)
265+
{
266+
if (check[i]==GIN_FALSE||nullFlags[i])
267+
{
268+
res=GIN_FALSE;
269+
break;
270+
}
271+
if (check[i]==GIN_MAYBE)
272+
{
273+
res=GIN_MAYBE;
274+
}
275+
}
276+
break;
277+
caseGinContainedStrategy:
278+
/* can't do anything else useful here */
279+
res=GIN_MAYBE;
280+
break;
281+
caseGinEqualStrategy:
282+
/*
283+
* Must have all elements in check[] true; no discrimination
284+
* against nulls here.This is because array_contain_compare and
285+
* array_eq handle nulls differently ...
286+
*/
287+
res=GIN_MAYBE;
288+
for (i=0;i<nkeys;i++)
289+
{
290+
if (check[i]==GIN_FALSE)
291+
{
292+
res=GIN_FALSE;
293+
break;
294+
}
295+
}
296+
break;
297+
default:
298+
elog(ERROR,"ginarrayconsistent: unknown strategy number: %d",
299+
strategy);
300+
res= false;
301+
}
302+
303+
PG_RETURN_GIN_LOGIC_VALUE(res);
304+
}

‎src/backend/access/gin/ginlogic.c

Lines changed: 62 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ trueTriConsistentFn(GinScanKey key)
6161
* A helper function for calling a regular, binary logic, consistent function.
6262
*/
6363
staticbool
64-
normalBoolConsistentFn(GinScanKeykey)
64+
directBoolConsistentFn(GinScanKeykey)
6565
{
6666
/*
6767
* Initialize recheckCurItem in case the consistentFn doesn't know it
@@ -81,6 +81,53 @@ normalBoolConsistentFn(GinScanKey key)
8181
PointerGetDatum(key->queryCategories)));
8282
}
8383

84+
/*
85+
* A helper function for calling a native ternary logic consistent function.
86+
*/
87+
staticGinLogicValue
88+
directTriConsistentFn(GinScanKeykey)
89+
{
90+
returnDatumGetGinLogicValue(FunctionCall7Coll(key->triConsistentFmgrInfo,
91+
key->collation,
92+
PointerGetDatum(key->entryRes),
93+
UInt16GetDatum(key->strategy),
94+
key->query,
95+
UInt32GetDatum(key->nuserentries),
96+
PointerGetDatum(key->extra_data),
97+
PointerGetDatum(key->queryValues),
98+
PointerGetDatum(key->queryCategories)));
99+
}
100+
101+
/*
102+
* This function implements a binary logic consistency check, using a ternary
103+
* logic consistent function provided by the opclass. GIN_MAYBE return value
104+
* is interpreted as true with recheck flag.
105+
*/
106+
staticbool
107+
shimBoolConsistentFn(GinScanKeykey)
108+
{
109+
GinLogicValueresult;
110+
result=DatumGetGinLogicValue(FunctionCall7Coll(key->triConsistentFmgrInfo,
111+
key->collation,
112+
PointerGetDatum(key->entryRes),
113+
UInt16GetDatum(key->strategy),
114+
key->query,
115+
UInt32GetDatum(key->nuserentries),
116+
PointerGetDatum(key->extra_data),
117+
PointerGetDatum(key->queryValues),
118+
PointerGetDatum(key->queryCategories)));
119+
if (result==GIN_MAYBE)
120+
{
121+
key->recheckCurItem= true;
122+
return true;
123+
}
124+
else
125+
{
126+
key->recheckCurItem= false;
127+
returnresult;
128+
}
129+
}
130+
84131
/*
85132
* This function implements a tri-state consistency check, using a boolean
86133
* consistent function provided by the opclass.
@@ -124,12 +171,12 @@ shimTriConsistentFn(GinScanKey key)
124171
* function as is.
125172
*/
126173
if (nmaybe==0)
127-
returnnormalBoolConsistentFn(key);
174+
returndirectBoolConsistentFn(key);
128175

129176
/* First call consistent function with all the maybe-inputs set FALSE */
130177
for (i=0;i<nmaybe;i++)
131178
key->entryRes[maybeEntries[i]]=GIN_FALSE;
132-
curResult=normalBoolConsistentFn(key);
179+
curResult=directBoolConsistentFn(key);
133180

134181
for (;;)
135182
{
@@ -147,7 +194,7 @@ shimTriConsistentFn(GinScanKey key)
147194
if (i==nmaybe)
148195
break;
149196

150-
boolResult=normalBoolConsistentFn(key);
197+
boolResult=directBoolConsistentFn(key);
151198
recheck |=key->recheckCurItem;
152199

153200
if (curResult!=boolResult)
@@ -175,8 +222,17 @@ ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
175222
else
176223
{
177224
key->consistentFmgrInfo=&ginstate->consistentFn[key->attnum-1];
225+
key->triConsistentFmgrInfo=&ginstate->triConsistentFn[key->attnum-1];
178226
key->collation=ginstate->supportCollation[key->attnum-1];
179-
key->boolConsistentFn=normalBoolConsistentFn;
180-
key->triConsistentFn=shimTriConsistentFn;
227+
228+
if (OidIsValid(ginstate->consistentFn[key->attnum-1].fn_oid))
229+
key->boolConsistentFn=directBoolConsistentFn;
230+
else
231+
key->boolConsistentFn=shimBoolConsistentFn;
232+
233+
if (OidIsValid(ginstate->triConsistentFn[key->attnum-1].fn_oid))
234+
key->triConsistentFn=directTriConsistentFn;
235+
else
236+
key->triConsistentFn=shimTriConsistentFn;
181237
}
182238
}

‎src/backend/access/gin/ginutil.c

Lines changed: 25 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -67,9 +67,31 @@ initGinState(GinState *state, Relation index)
6767
fmgr_info_copy(&(state->extractQueryFn[i]),
6868
index_getprocinfo(index,i+1,GIN_EXTRACTQUERY_PROC),
6969
CurrentMemoryContext);
70-
fmgr_info_copy(&(state->consistentFn[i]),
71-
index_getprocinfo(index,i+1,GIN_CONSISTENT_PROC),
72-
CurrentMemoryContext);
70+
/*
71+
* Check opclass capability to do tri-state or binary logic consistent
72+
* check.
73+
*/
74+
if (index_getprocid(index,i+1,GIN_TRICONSISTENT_PROC)!=InvalidOid)
75+
{
76+
fmgr_info_copy(&(state->triConsistentFn[i]),
77+
index_getprocinfo(index,i+1,GIN_TRICONSISTENT_PROC),
78+
CurrentMemoryContext);
79+
}
80+
81+
if (index_getprocid(index,i+1,GIN_CONSISTENT_PROC)!=InvalidOid)
82+
{
83+
fmgr_info_copy(&(state->consistentFn[i]),
84+
index_getprocinfo(index,i+1,GIN_CONSISTENT_PROC),
85+
CurrentMemoryContext);
86+
}
87+
88+
if (state->consistentFn[i].fn_oid==InvalidOid&&
89+
state->triConsistentFn[i].fn_oid==InvalidOid)
90+
{
91+
elog(ERROR,"missing GIN support function (%d or %d) for attribute %d of index \"%s\"",
92+
GIN_CONSISTENT_PROC,GIN_TRICONSISTENT_PROC,
93+
i+1,RelationGetRelationName(index));
94+
}
7395

7496
/*
7597
* Check opclass capability to do partial match.

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp