PostgreSQL Source Code  git master
ginlogic.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * ginlogic.c
4  * routines for performing binary- and ternary-logic consistent checks.
5  *
6  * A GIN operator class can provide a boolean or ternary consistent
7  * function, or both. This file provides both boolean and ternary
8  * interfaces to the rest of the GIN code, even if only one of them is
9  * implemented by the opclass.
10  *
11  * Providing a boolean interface when the opclass implements only the
12  * ternary function is straightforward - just call the ternary function
13  * with the check-array as is, and map the GIN_TRUE, GIN_FALSE, GIN_MAYBE
14  * return codes to TRUE, FALSE and TRUE+recheck, respectively. Providing
15  * a ternary interface when the opclass only implements a boolean function
16  * is implemented by calling the boolean function many times, with all the
17  * MAYBE arguments set to all combinations of TRUE and FALSE (up to a
18  * certain number of MAYBE arguments).
19  *
20  * (A boolean function is enough to determine if an item matches, but a
21  * GIN scan can apply various optimizations if it can determine that an
22  * item matches or doesn't match, even if it doesn't know if some of the
23  * keys are present or not. That's what the ternary consistent function
24  * is used for.)
25  *
26  *
27  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
28  * Portions Copyright (c) 1994, Regents of the University of California
29  *
30  * IDENTIFICATION
31  * src/backend/access/gin/ginlogic.c
32  *-------------------------------------------------------------------------
33  */
34 
35 #include "postgres.h"
36 
37 #include "access/gin_private.h"
38 #include "access/reloptions.h"
39 #include "catalog/pg_collation.h"
40 #include "catalog/pg_type.h"
41 #include "miscadmin.h"
42 #include "storage/indexfsm.h"
43 #include "storage/lmgr.h"
44 
45 
46 /*
47  * Maximum number of MAYBE inputs that shimTriConsistentFn will try to
48  * resolve by calling all combinations.
49  */
50 #define MAX_MAYBE_ENTRIES 4
51 
52 /*
53  * Dummy consistent functions for an EVERYTHING key. Just claim it matches.
54  */
55 static bool
57 {
58  key->recheckCurItem = false;
59  return true;
60 }
61 static GinTernaryValue
63 {
64  return GIN_TRUE;
65 }
66 
67 /*
68  * A helper function for calling a regular, binary logic, consistent function.
69  */
70 static bool
72 {
73  /*
74  * Initialize recheckCurItem in case the consistentFn doesn't know it
75  * should set it. The safe assumption in that case is to force recheck.
76  */
77  key->recheckCurItem = true;
78 
80  key->collation,
83  key->query,
89 }
90 
91 /*
92  * A helper function for calling a native ternary logic consistent function.
93  */
94 static GinTernaryValue
96 {
98  key->collation,
100  UInt16GetDatum(key->strategy),
101  key->query,
106 }
107 
108 /*
109  * This function implements a binary logic consistency check, using a ternary
110  * logic consistent function provided by the opclass. GIN_MAYBE return value
111  * is interpreted as true with recheck flag.
112  */
113 static bool
115 {
116  GinTernaryValue result;
117 
119  key->collation,
121  UInt16GetDatum(key->strategy),
122  key->query,
127  if (result == GIN_MAYBE)
128  {
129  key->recheckCurItem = true;
130  return true;
131  }
132  else
133  {
134  key->recheckCurItem = false;
135  return result;
136  }
137 }
138 
139 /*
140  * This function implements a tri-state consistency check, using a boolean
141  * consistent function provided by the opclass.
142  *
143  * Our strategy is to call consistentFn with MAYBE inputs replaced with every
144  * combination of TRUE/FALSE. If consistentFn returns the same value for every
145  * combination, that's the overall result. Otherwise, return MAYBE. Testing
146  * every combination is O(n^2), so this is only feasible for a small number of
147  * MAYBE inputs.
148  *
149  * NB: This function modifies the key->entryRes array!
150  */
151 static GinTernaryValue
153 {
154  int nmaybe;
155  int maybeEntries[MAX_MAYBE_ENTRIES];
156  int i;
157  bool boolResult;
158  bool recheck = false;
159  GinTernaryValue curResult;
160 
161  /*
162  * Count how many MAYBE inputs there are, and store their indexes in
163  * maybeEntries. If there are too many MAYBE inputs, it's not feasible to
164  * test all combinations, so give up and return MAYBE.
165  */
166  nmaybe = 0;
167  for (i = 0; i < key->nentries; i++)
168  {
169  if (key->entryRes[i] == GIN_MAYBE)
170  {
171  if (nmaybe >= MAX_MAYBE_ENTRIES)
172  return GIN_MAYBE;
173  maybeEntries[nmaybe++] = i;
174  }
175  }
176 
177  /*
178  * If none of the inputs were MAYBE, so we can just call consistent
179  * function as is.
180  */
181  if (nmaybe == 0)
182  return directBoolConsistentFn(key);
183 
184  /* First call consistent function with all the maybe-inputs set FALSE */
185  for (i = 0; i < nmaybe; i++)
186  key->entryRes[maybeEntries[i]] = GIN_FALSE;
187  curResult = directBoolConsistentFn(key);
188 
189  for (;;)
190  {
191  /* Twiddle the entries for next combination. */
192  for (i = 0; i < nmaybe; i++)
193  {
194  if (key->entryRes[maybeEntries[i]] == GIN_FALSE)
195  {
196  key->entryRes[maybeEntries[i]] = GIN_TRUE;
197  break;
198  }
199  else
200  key->entryRes[maybeEntries[i]] = GIN_FALSE;
201  }
202  if (i == nmaybe)
203  break;
204 
205  boolResult = directBoolConsistentFn(key);
206  recheck |= key->recheckCurItem;
207 
208  if (curResult != boolResult)
209  return GIN_MAYBE;
210  }
211 
212  /* TRUE with recheck is taken to mean MAYBE */
213  if (curResult == GIN_TRUE && recheck)
214  curResult = GIN_MAYBE;
215 
216  return curResult;
217 }
218 
219 /*
220  * Set up the implementation of the consistent functions for a scan key.
221  */
222 void
224 {
226  {
229  }
230  else
231  {
232  key->consistentFmgrInfo = &ginstate->consistentFn[key->attnum - 1];
233  key->triConsistentFmgrInfo = &ginstate->triConsistentFn[key->attnum - 1];
234  key->collation = ginstate->supportCollation[key->attnum - 1];
235 
236  if (OidIsValid(ginstate->consistentFn[key->attnum - 1].fn_oid))
238  else
240 
241  if (OidIsValid(ginstate->triConsistentFn[key->attnum - 1].fn_oid))
243  else
245  }
246 }
#define GIN_TRUE
Definition: gin.h:61
FmgrInfo * triConsistentFmgrInfo
Definition: gin_private.h:293
Datum * queryValues
Definition: gin_private.h:299
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:87
Pointer * extra_data
Definition: gin_private.h:301
static GinTernaryValue directTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:95
#define GIN_MAYBE
Definition: gin.h:62
#define PointerGetDatum(X)
Definition: postgres.h:556
Datum FunctionCall8Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5, Datum arg6, Datum arg7, Datum arg8)
Definition: fmgr.c:1321
static GinTernaryValue shimTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:152
#define GIN_SEARCH_MODE_EVERYTHING
Definition: gin.h:37
#define DatumGetGinTernaryValue(X)
Definition: gin.h:65
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gin_private.h:81
FmgrInfo * consistentFmgrInfo
Definition: gin_private.h:292
#define OidIsValid(objectId)
Definition: c.h:651
Datum FunctionCall7Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5, Datum arg6, Datum arg7)
Definition: fmgr.c:1287
char GinTernaryValue
Definition: gin.h:58
StrategyNumber strategy
Definition: gin_private.h:302
GinTernaryValue * entryRes
Definition: gin_private.h:289
#define DatumGetBool(X)
Definition: postgres.h:393
#define MAX_MAYBE_ENTRIES
Definition: ginlogic.c:50
#define UInt32GetDatum(X)
Definition: postgres.h:493
OffsetNumber attnum
Definition: gin_private.h:304
static GinTernaryValue trueTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:62
uint32 nuserentries
Definition: gin_private.h:270
bool(* boolConsistentFn)(GinScanKey key)
Definition: gin_private.h:290
GinNullCategory * queryCategories
Definition: gin_private.h:300
Oid fn_oid
Definition: fmgr.h:59
GinTernaryValue(* triConsistentFn)(GinScanKey key)
Definition: gin_private.h:291
#define GIN_FALSE
Definition: gin.h:60
static bool directBoolConsistentFn(GinScanKey key)
Definition: ginlogic.c:71
static bool trueConsistentFn(GinScanKey key)
Definition: ginlogic.c:56
void ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
Definition: ginlogic.c:223
int i
static bool shimBoolConsistentFn(GinScanKey key)
Definition: ginlogic.c:114
FmgrInfo triConsistentFn[INDEX_MAX_KEYS]
Definition: gin_private.h:82
#define UInt16GetDatum(X)
Definition: postgres.h:465