PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 {
99  key->collation,
101  UInt16GetDatum(key->strategy),
102  key->query,
107 }
108 
109 /*
110  * This function implements a binary logic consistency check, using a ternary
111  * logic consistent function provided by the opclass. GIN_MAYBE return value
112  * is interpreted as true with recheck flag.
113  */
114 static bool
116 {
118 
121  key->collation,
123  UInt16GetDatum(key->strategy),
124  key->query,
129  if (result == GIN_MAYBE)
130  {
131  key->recheckCurItem = true;
132  return true;
133  }
134  else
135  {
136  key->recheckCurItem = false;
137  return result;
138  }
139 }
140 
141 /*
142  * This function implements a tri-state consistency check, using a boolean
143  * consistent function provided by the opclass.
144  *
145  * Our strategy is to call consistentFn with MAYBE inputs replaced with every
146  * combination of TRUE/FALSE. If consistentFn returns the same value for every
147  * combination, that's the overall result. Otherwise, return MAYBE. Testing
148  * every combination is O(n^2), so this is only feasible for a small number of
149  * MAYBE inputs.
150  *
151  * NB: This function modifies the key->entryRes array!
152  */
153 static GinTernaryValue
155 {
156  int nmaybe;
157  int maybeEntries[MAX_MAYBE_ENTRIES];
158  int i;
159  bool boolResult;
160  bool recheck = false;
161  GinTernaryValue curResult;
162 
163  /*
164  * Count how many MAYBE inputs there are, and store their indexes in
165  * maybeEntries. If there are too many MAYBE inputs, it's not feasible to
166  * test all combinations, so give up and return MAYBE.
167  */
168  nmaybe = 0;
169  for (i = 0; i < key->nentries; i++)
170  {
171  if (key->entryRes[i] == GIN_MAYBE)
172  {
173  if (nmaybe >= MAX_MAYBE_ENTRIES)
174  return GIN_MAYBE;
175  maybeEntries[nmaybe++] = i;
176  }
177  }
178 
179  /*
180  * If none of the inputs were MAYBE, so we can just call consistent
181  * function as is.
182  */
183  if (nmaybe == 0)
184  return directBoolConsistentFn(key);
185 
186  /* First call consistent function with all the maybe-inputs set FALSE */
187  for (i = 0; i < nmaybe; i++)
188  key->entryRes[maybeEntries[i]] = GIN_FALSE;
189  curResult = directBoolConsistentFn(key);
190 
191  for (;;)
192  {
193  /* Twiddle the entries for next combination. */
194  for (i = 0; i < nmaybe; i++)
195  {
196  if (key->entryRes[maybeEntries[i]] == GIN_FALSE)
197  {
198  key->entryRes[maybeEntries[i]] = GIN_TRUE;
199  break;
200  }
201  else
202  key->entryRes[maybeEntries[i]] = GIN_FALSE;
203  }
204  if (i == nmaybe)
205  break;
206 
207  boolResult = directBoolConsistentFn(key);
208  recheck |= key->recheckCurItem;
209 
210  if (curResult != boolResult)
211  return GIN_MAYBE;
212  }
213 
214  /* TRUE with recheck is taken to mean MAYBE */
215  if (curResult == GIN_TRUE && recheck)
216  curResult = GIN_MAYBE;
217 
218  return curResult;
219 }
220 
221 /*
222  * Set up the implementation of the consistent functions for a scan key.
223  */
224 void
226 {
228  {
231  }
232  else
233  {
234  key->consistentFmgrInfo = &ginstate->consistentFn[key->attnum - 1];
235  key->triConsistentFmgrInfo = &ginstate->triConsistentFn[key->attnum - 1];
236  key->collation = ginstate->supportCollation[key->attnum - 1];
237 
238  if (OidIsValid(ginstate->consistentFn[key->attnum - 1].fn_oid))
240  else
242 
243  if (OidIsValid(ginstate->triConsistentFn[key->attnum - 1].fn_oid))
245  else
247  }
248 }
#define GIN_TRUE
Definition: gin.h:60
FmgrInfo * triConsistentFmgrInfo
Definition: gin_private.h:288
Datum * queryValues
Definition: gin_private.h:294
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:82
Pointer * extra_data
Definition: gin_private.h:296
static GinTernaryValue directTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:95
#define GIN_MAYBE
Definition: gin.h:61
#define PointerGetDatum(X)
Definition: postgres.h:562
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:1216
static GinTernaryValue shimTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:154
#define GIN_SEARCH_MODE_EVERYTHING
Definition: gin.h:36
#define DatumGetGinTernaryValue(X)
Definition: gin.h:64
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gin_private.h:76
return result
Definition: formatting.c:1618
FmgrInfo * consistentFmgrInfo
Definition: gin_private.h:287
#define OidIsValid(objectId)
Definition: c.h:538
Datum FunctionCall7Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5, Datum arg6, Datum arg7)
Definition: fmgr.c:1182
char GinTernaryValue
Definition: gin.h:57
StrategyNumber strategy
Definition: gin_private.h:297
GinTernaryValue * entryRes
Definition: gin_private.h:284
#define DatumGetBool(X)
Definition: postgres.h:399
#define MAX_MAYBE_ENTRIES
Definition: ginlogic.c:50
#define UInt32GetDatum(X)
Definition: postgres.h:499
OffsetNumber attnum
Definition: gin_private.h:299
static GinTernaryValue trueTriConsistentFn(GinScanKey key)
Definition: ginlogic.c:62
uint32 nuserentries
Definition: gin_private.h:265
GinNullCategory * queryCategories
Definition: gin_private.h:295
Oid fn_oid
Definition: fmgr.h:59
#define GIN_FALSE
Definition: gin.h:59
static bool directBoolConsistentFn(GinScanKey key)
Definition: ginlogic.c:71
static bool trueConsistentFn(GinScanKey key)
Definition: ginlogic.c:56
bool(* boolConsistentFn)(GinScanKey key)
Definition: gin_private.h:285
void ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
Definition: ginlogic.c:225
GinTernaryValue(* triConsistentFn)(GinScanKey key)
Definition: gin_private.h:286
int i
static bool shimBoolConsistentFn(GinScanKey key)
Definition: ginlogic.c:115
FmgrInfo triConsistentFn[INDEX_MAX_KEYS]
Definition: gin_private.h:77
#define UInt16GetDatum(X)
Definition: postgres.h:471