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-2021, 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(key->triConsistentFmgrInfo,
98 key->collation,
99 PointerGetDatum(key->entryRes),
100 UInt16GetDatum(key->strategy),
101 key->query,
102 UInt32GetDatum(key->nuserentries),
103 PointerGetDatum(key->extra_data),
104 PointerGetDatum(key->queryValues),
105 PointerGetDatum(key->queryCategories)));
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
shimBoolConsistentFn(GinScanKey key)114 shimBoolConsistentFn(GinScanKey key)
115 {
116 GinTernaryValue result;
117
118 result = DatumGetGinTernaryValue(FunctionCall7Coll(key->triConsistentFmgrInfo,
119 key->collation,
120 PointerGetDatum(key->entryRes),
121 UInt16GetDatum(key->strategy),
122 key->query,
123 UInt32GetDatum(key->nuserentries),
124 PointerGetDatum(key->extra_data),
125 PointerGetDatum(key->queryValues),
126 PointerGetDatum(key->queryCategories)));
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
shimTriConsistentFn(GinScanKey key)152 shimTriConsistentFn(GinScanKey key)
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
ginInitConsistentFunction(GinState * ginstate,GinScanKey key)223 ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
224 {
225 if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING)
226 {
227 key->boolConsistentFn = trueConsistentFn;
228 key->triConsistentFn = trueTriConsistentFn;
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))
237 key->boolConsistentFn = directBoolConsistentFn;
238 else
239 key->boolConsistentFn = shimBoolConsistentFn;
240
241 if (OidIsValid(ginstate->triConsistentFn[key->attnum - 1].fn_oid))
242 key->triConsistentFn = directTriConsistentFn;
243 else
244 key->triConsistentFn = shimTriConsistentFn;
245 }
246 }
247