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
trueConsistentFn(GinScanKey key)56 trueConsistentFn(GinScanKey key)
57 {
58 key->recheckCurItem = false;
59 return true;
60 }
61 static GinTernaryValue
trueTriConsistentFn(GinScanKey key)62 trueTriConsistentFn(GinScanKey key)
63 {
64 return GIN_TRUE;
65 }
66
67 /*
68 * A helper function for calling a regular, binary logic, consistent function.
69 */
70 static bool
directBoolConsistentFn(GinScanKey key)71 directBoolConsistentFn(GinScanKey key)
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
79 return DatumGetBool(FunctionCall8Coll(key->consistentFmgrInfo,
80 key->collation,
81 PointerGetDatum(key->entryRes),
82 UInt16GetDatum(key->strategy),
83 key->query,
84 UInt32GetDatum(key->nuserentries),
85 PointerGetDatum(key->extra_data),
86 PointerGetDatum(&key->recheckCurItem),
87 PointerGetDatum(key->queryValues),
88 PointerGetDatum(key->queryCategories)));
89 }
90
91 /*
92 * A helper function for calling a native ternary logic consistent function.
93 */
94 static GinTernaryValue
directTriConsistentFn(GinScanKey key)95 directTriConsistentFn(GinScanKey key)
96 {
97 return DatumGetGinTernaryValue(FunctionCall7Coll(
98 key->triConsistentFmgrInfo,
99 key->collation,
100 PointerGetDatum(key->entryRes),
101 UInt16GetDatum(key->strategy),
102 key->query,
103 UInt32GetDatum(key->nuserentries),
104 PointerGetDatum(key->extra_data),
105 PointerGetDatum(key->queryValues),
106 PointerGetDatum(key->queryCategories)));
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
shimBoolConsistentFn(GinScanKey key)115 shimBoolConsistentFn(GinScanKey key)
116 {
117 GinTernaryValue result;
118
119 result = DatumGetGinTernaryValue(FunctionCall7Coll(
120 key->triConsistentFmgrInfo,
121 key->collation,
122 PointerGetDatum(key->entryRes),
123 UInt16GetDatum(key->strategy),
124 key->query,
125 UInt32GetDatum(key->nuserentries),
126 PointerGetDatum(key->extra_data),
127 PointerGetDatum(key->queryValues),
128 PointerGetDatum(key->queryCategories)));
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
shimTriConsistentFn(GinScanKey key)154 shimTriConsistentFn(GinScanKey key)
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
ginInitConsistentFunction(GinState * ginstate,GinScanKey key)225 ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
226 {
227 if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING)
228 {
229 key->boolConsistentFn = trueConsistentFn;
230 key->triConsistentFn = trueTriConsistentFn;
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))
239 key->boolConsistentFn = directBoolConsistentFn;
240 else
241 key->boolConsistentFn = shimBoolConsistentFn;
242
243 if (OidIsValid(ginstate->triConsistentFn[key->attnum - 1].fn_oid))
244 key->triConsistentFn = directTriConsistentFn;
245 else
246 key->triConsistentFn = shimTriConsistentFn;
247 }
248 }
249