Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * contrib/intarray/_int_gist.c
3 : : */
4 : : #include "postgres.h"
5 : :
6 : : #include <limits.h>
7 : : #include <math.h>
8 : :
9 : : #include "_int.h"
10 : : #include "access/gist.h"
11 : : #include "access/reloptions.h"
12 : : #include "access/stratnum.h"
13 : :
14 : : #define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer((vec)->vector[(pos)].key))
15 : :
16 : : /*
17 : : * Control the maximum sparseness of compressed keys.
18 : : *
19 : : * The upper safe bound for this limit is half the maximum allocatable array
20 : : * size. A lower bound would give more guarantees that pathological data
21 : : * wouldn't eat excessive CPU and memory, but at the expense of breaking
22 : : * possibly working (after a fashion) indexes.
23 : : */
24 : : #define MAXNUMELTS (Min((MaxAllocSize / sizeof(Datum)),((MaxAllocSize - ARR_OVERHEAD_NONULLS(1)) / sizeof(int)))/2)
25 : : /* or: #define MAXNUMELTS 1000000 */
26 : :
27 : : /*
28 : : ** GiST support methods
29 : : */
8224 bruce@momjian.us 30 :CBC 2 : PG_FUNCTION_INFO_V1(g_int_consistent);
31 : 2 : PG_FUNCTION_INFO_V1(g_int_compress);
32 : 2 : PG_FUNCTION_INFO_V1(g_int_decompress);
33 : 2 : PG_FUNCTION_INFO_V1(g_int_penalty);
34 : 2 : PG_FUNCTION_INFO_V1(g_int_picksplit);
35 : 2 : PG_FUNCTION_INFO_V1(g_int_union);
36 : 2 : PG_FUNCTION_INFO_V1(g_int_same);
2087 akorotkov@postgresql 37 : 2 : PG_FUNCTION_INFO_V1(g_int_options);
38 : :
39 : :
40 : : /*
41 : : ** The GiST Consistent method for _intments
42 : : ** Should return false if for all data items x below entry,
43 : : ** the predicate x op query == false, where op is the oper
44 : : ** corresponding to strategy in the pg_amop table.
45 : : */
46 : : Datum
8224 bruce@momjian.us 47 : 132261 : g_int_consistent(PG_FUNCTION_ARGS)
48 : : {
49 : 132261 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
5455 tgl@sss.pgh.pa.us 50 : 132261 : ArrayType *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
8224 bruce@momjian.us 51 : 132261 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
52 : :
53 : : /* Oid subtype = PG_GETARG_OID(3); */
6455 tgl@sss.pgh.pa.us 54 : 132261 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1176 peter@eisentraut.org 55 : 132261 : bool retval = false; /* silence compiler warning */
56 : :
57 : : /* this is exact except for RTSameStrategyNumber */
6455 tgl@sss.pgh.pa.us 58 : 132261 : *recheck = (strategy == RTSameStrategyNumber);
59 : :
7013 bruce@momjian.us 60 [ + + ]: 132261 : if (strategy == BooleanSearchStrategy)
61 : : {
7197 teodor@sigaev.ru 62 : 84332 : retval = execconsistent((QUERYTYPE *) query,
7013 bruce@momjian.us 63 : 84332 : (ArrayType *) DatumGetPointer(entry->key),
64 : 84332 : GIST_LEAF(entry));
65 : :
66 : 84332 : pfree(query);
7197 teodor@sigaev.ru 67 : 84332 : PG_RETURN_BOOL(retval);
68 : : }
69 : :
70 : : /* sort query for fast search, key is already sorted */
7332 tgl@sss.pgh.pa.us 71 [ - + - - : 47929 : CHECKARRVALID(query);
- - ]
8224 bruce@momjian.us 72 [ - + ]: 47929 : PREPAREARR(query);
73 : :
74 [ + + + - : 47929 : switch (strategy)
- ]
75 : : {
76 : 16654 : case RTOverlapStrategyNumber:
77 : 16654 : retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
78 : : query);
79 : 16654 : break;
80 : 3433 : case RTSameStrategyNumber:
81 [ + + ]: 3433 : if (GIST_LEAF(entry))
5455 tgl@sss.pgh.pa.us 82 : 3141 : DirectFunctionCall3(g_int_same,
83 : : entry->key,
84 : : PointerGetDatum(query),
85 : : PointerGetDatum(&retval));
86 : : else
8224 bruce@momjian.us 87 : 292 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
88 : : query);
89 : 3433 : break;
90 : 27842 : case RTContainsStrategyNumber:
91 : : case RTOldContainsStrategyNumber:
92 : 27842 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
93 : : query);
94 : 27842 : break;
8224 bruce@momjian.us 95 :UBC 0 : case RTContainedByStrategyNumber:
96 : : case RTOldContainedByStrategyNumber:
97 : :
98 : : /*
99 : : * This code is unreachable as of intarray 1.4, because the <@
100 : : * operator has been removed from the opclass. We keep it for now
101 : : * to support older versions of the SQL definitions.
102 : : */
103 [ # # ]: 0 : if (GIST_LEAF(entry))
104 : 0 : retval = inner_int_contains(query,
3100 tgl@sss.pgh.pa.us 105 : 0 : (ArrayType *) DatumGetPointer(entry->key));
106 : : else
107 : : {
108 : : /*
109 : : * Unfortunately, because empty arrays could be anywhere in
110 : : * the index, we must search the whole tree.
111 : : */
2324 112 : 0 : retval = true;
113 : : }
8224 bruce@momjian.us 114 : 0 : break;
115 : 0 : default:
3044 peter_e@gmx.net 116 : 0 : retval = false;
117 : : }
7013 bruce@momjian.us 118 :CBC 47929 : pfree(query);
8224 119 : 47929 : PG_RETURN_BOOL(retval);
120 : : }
121 : :
122 : : Datum
8170 123 : 55793 : g_int_union(PG_FUNCTION_ARGS)
124 : : {
7779 125 : 55793 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8170 126 : 55793 : int *size = (int *) PG_GETARG_POINTER(1);
127 : : int32 i,
128 : : *ptr;
129 : : ArrayType *res;
7332 tgl@sss.pgh.pa.us 130 : 55793 : int totlen = 0;
131 : :
7931 teodor@sigaev.ru 132 [ + + ]: 167853 : for (i = 0; i < entryvec->n; i++)
133 : : {
7329 bruce@momjian.us 134 : 112060 : ArrayType *ent = GETENTRY(entryvec, i);
135 : :
7332 tgl@sss.pgh.pa.us 136 [ - + - - : 112060 : CHECKARRVALID(ent);
- - ]
137 : 112060 : totlen += ARRNELEMS(ent);
138 : : }
139 : :
8170 bruce@momjian.us 140 : 55793 : res = new_intArrayType(totlen);
141 [ - + ]: 55793 : ptr = ARRPTR(res);
142 : :
7931 teodor@sigaev.ru 143 [ + + ]: 167853 : for (i = 0; i < entryvec->n; i++)
144 : : {
7329 bruce@momjian.us 145 : 112060 : ArrayType *ent = GETENTRY(entryvec, i);
146 : : int nel;
147 : :
7332 tgl@sss.pgh.pa.us 148 : 112060 : nel = ARRNELEMS(ent);
4922 peter_e@gmx.net 149 [ - + ]: 112060 : memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
7332 tgl@sss.pgh.pa.us 150 : 112060 : ptr += nel;
151 : : }
152 : :
8170 bruce@momjian.us 153 [ - + ]: 55793 : QSORT(res, 1);
154 : 55793 : res = _int_unique(res);
155 : 55793 : *size = VARSIZE(res);
8224 156 : 55793 : PG_RETURN_POINTER(res);
157 : : }
158 : :
159 : : /*
160 : : ** GiST Compress and Decompress methods
161 : : */
162 : : Datum
163 : 30474 : g_int_compress(PG_FUNCTION_ARGS)
164 : : {
165 : 30474 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
166 : : GISTENTRY *retval;
167 : : ArrayType *r;
2087 akorotkov@postgresql 168 [ + - ]: 30474 : int num_ranges = G_INT_GET_NUMRANGES();
169 : : int len,
170 : : lenr;
171 : : int *dr;
172 : : int i,
173 : : j,
174 : : cand;
175 : : int64 min;
176 : :
8224 bruce@momjian.us 177 [ + + ]: 30474 : if (entry->leafkey)
178 : : {
5455 tgl@sss.pgh.pa.us 179 : 20272 : r = DatumGetArrayTypePCopy(entry->key);
7332 180 [ - + - - : 20272 : CHECKARRVALID(r);
- - ]
8224 bruce@momjian.us 181 [ - + ]: 20272 : PREPAREARR(r);
182 : :
2087 akorotkov@postgresql 183 [ + + ]: 20272 : if (ARRNELEMS(r) >= 2 * num_ranges)
915 michael@paquier.xyz 184 [ + - ]: 1 : ereport(ERROR,
185 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
186 : : errmsg("input array is too big (%d maximum allowed, %d current), use gist__intbig_ops opclass instead",
187 : : 2 * num_ranges - 1, ARRNELEMS(r))));
188 : :
11 michael@paquier.xyz 189 :GNC 20271 : retval = palloc_object(GISTENTRY);
8224 bruce@momjian.us 190 :CBC 20271 : gistentryinit(*retval, PointerGetDatum(r),
191 : : entry->rel, entry->page, entry->offset, false);
192 : :
193 : 20271 : PG_RETURN_POINTER(retval);
194 : : }
195 : :
196 : : /*
197 : : * leaf entries never compress one more time, only when entry->leafkey
198 : : * ==true, so now we work only with internal keys
199 : : */
200 : :
5455 tgl@sss.pgh.pa.us 201 : 10202 : r = DatumGetArrayTypeP(entry->key);
7332 202 [ - + - - : 10202 : CHECKARRVALID(r);
- - ]
5455 203 [ - + ]: 10202 : if (ARRISEMPTY(r))
204 : : {
8224 bruce@momjian.us 205 [ # # ]:UBC 0 : if (r != (ArrayType *) DatumGetPointer(entry->key))
206 : 0 : pfree(r);
207 : 0 : PG_RETURN_POINTER(entry);
208 : : }
209 : :
2087 akorotkov@postgresql 210 [ + + ]:CBC 10202 : if ((len = ARRNELEMS(r)) >= 2 * num_ranges)
211 : : { /* compress */
8224 bruce@momjian.us 212 [ + - ]: 1409 : if (r == (ArrayType *) DatumGetPointer(entry->key))
5455 tgl@sss.pgh.pa.us 213 : 1409 : r = DatumGetArrayTypePCopy(entry->key);
8224 bruce@momjian.us 214 : 1409 : r = resize_intArrayType(r, 2 * (len));
215 : :
216 [ - + ]: 1409 : dr = ARRPTR(r);
217 : :
218 : : /*
219 : : * "len" at this point is the number of ranges we will construct.
220 : : * "lenr" is the number of ranges we must eventually remove by
221 : : * merging, we must be careful to remove no more than this number.
222 : : */
2087 akorotkov@postgresql 223 : 1409 : lenr = len - num_ranges;
224 : :
225 : : /*
226 : : * Initially assume we can merge consecutive ints into a range. but we
227 : : * must count every value removed and stop when lenr runs out
228 : : */
2580 rhodiumtoad@postgres 229 [ + - + + ]: 62772 : for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
230 : : {
2400 tgl@sss.pgh.pa.us 231 : 61363 : int r_end = dr[i];
232 : 61363 : int r_start = r_end;
233 : :
234 [ + - + + : 678508 : while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
+ + ]
2580 rhodiumtoad@postgres 235 : 617145 : --r_start, --i, --lenr;
2400 tgl@sss.pgh.pa.us 236 : 61363 : dr[2 * j] = r_start;
237 : 61363 : dr[2 * j + 1] = r_end;
238 : : }
239 : : /* just copy the rest, if any, as trivial ranges */
2580 rhodiumtoad@postgres 240 [ + + ]: 268362 : for (; i >= 0; i--, j--)
2400 tgl@sss.pgh.pa.us 241 : 266953 : dr[2 * j] = dr[2 * j + 1] = dr[i];
242 : :
2580 rhodiumtoad@postgres 243 [ + - ]: 1409 : if (++j)
244 : : {
245 : : /*
246 : : * shunt everything down to start at the right place
247 : : */
1043 peter@eisentraut.org 248 : 1409 : memmove(&dr[0], &dr[2 * j], 2 * (len - j) * sizeof(int32));
249 : : }
250 : :
251 : : /*
252 : : * make "len" be number of array elements, not ranges
253 : : */
2400 tgl@sss.pgh.pa.us 254 : 1409 : len = 2 * (len - j);
8224 bruce@momjian.us 255 : 1409 : cand = 1;
2087 akorotkov@postgresql 256 [ - + ]: 1409 : while (len > num_ranges * 2)
257 : : {
2580 rhodiumtoad@postgres 258 :UBC 0 : min = PG_INT64_MAX;
8224 bruce@momjian.us 259 [ # # ]: 0 : for (i = 2; i < len; i += 2)
2400 tgl@sss.pgh.pa.us 260 [ # # ]: 0 : if (min > ((int64) dr[i] - (int64) dr[i - 1]))
261 : : {
262 : 0 : min = ((int64) dr[i] - (int64) dr[i - 1]);
8224 bruce@momjian.us 263 : 0 : cand = i;
264 : : }
1043 peter@eisentraut.org 265 : 0 : memmove(&dr[cand - 1], &dr[cand + 1], (len - cand - 1) * sizeof(int32));
8224 bruce@momjian.us 266 : 0 : len -= 2;
267 : : }
268 : :
269 : : /*
270 : : * check sparseness of result
271 : : */
2580 rhodiumtoad@postgres 272 :CBC 1409 : lenr = internal_size(dr, len);
273 [ + - - + ]: 1409 : if (lenr < 0 || lenr > MAXNUMELTS)
2580 rhodiumtoad@postgres 274 [ # # ]:UBC 0 : ereport(ERROR,
275 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
276 : : errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));
277 : :
8224 bruce@momjian.us 278 :CBC 1409 : r = resize_intArrayType(r, len);
11 michael@paquier.xyz 279 :GNC 1409 : retval = palloc_object(GISTENTRY);
8224 bruce@momjian.us 280 :CBC 1409 : gistentryinit(*retval, PointerGetDatum(r),
281 : : entry->rel, entry->page, entry->offset, false);
282 : 1409 : PG_RETURN_POINTER(retval);
283 : : }
284 : : else
285 : 8793 : PG_RETURN_POINTER(entry);
286 : : }
287 : :
288 : : Datum
289 : 625724 : g_int_decompress(PG_FUNCTION_ARGS)
290 : : {
291 : 625724 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
292 : : GISTENTRY *retval;
293 : : ArrayType *r;
2087 akorotkov@postgresql 294 [ + - ]: 625724 : int num_ranges = G_INT_GET_NUMRANGES();
295 : : int *dr,
296 : : lenr;
297 : : ArrayType *in;
298 : : int lenin;
299 : : int *din;
300 : : int i;
301 : :
5455 tgl@sss.pgh.pa.us 302 : 625724 : in = DatumGetArrayTypeP(entry->key);
303 : :
7332 304 [ - + - - : 625724 : CHECKARRVALID(in);
- - ]
5455 305 [ + + ]: 625724 : if (ARRISEMPTY(in))
306 : : {
6606 bruce@momjian.us 307 [ + - ]: 345 : if (in != (ArrayType *) DatumGetPointer(entry->key))
308 : : {
11 michael@paquier.xyz 309 :GNC 345 : retval = palloc_object(GISTENTRY);
6829 tgl@sss.pgh.pa.us 310 :CBC 345 : gistentryinit(*retval, PointerGetDatum(in),
311 : : entry->rel, entry->page, entry->offset, false);
312 : 345 : PG_RETURN_POINTER(retval);
313 : : }
314 : :
8224 bruce@momjian.us 315 :UBC 0 : PG_RETURN_POINTER(entry);
316 : : }
317 : :
8224 bruce@momjian.us 318 :CBC 625379 : lenin = ARRNELEMS(in);
319 : :
2087 akorotkov@postgresql 320 [ + + ]: 625379 : if (lenin < 2 * num_ranges)
321 : : { /* not compressed value */
8224 bruce@momjian.us 322 [ + + ]: 600777 : if (in != (ArrayType *) DatumGetPointer(entry->key))
323 : : {
11 michael@paquier.xyz 324 :GNC 269187 : retval = palloc_object(GISTENTRY);
8224 bruce@momjian.us 325 :CBC 269187 : gistentryinit(*retval, PointerGetDatum(in),
326 : : entry->rel, entry->page, entry->offset, false);
327 : :
328 : 269187 : PG_RETURN_POINTER(retval);
329 : : }
330 : 331590 : PG_RETURN_POINTER(entry);
331 : : }
332 : :
333 [ - + ]: 24602 : din = ARRPTR(in);
334 : 24602 : lenr = internal_size(din, lenin);
2580 rhodiumtoad@postgres 335 [ + - - + ]: 24602 : if (lenr < 0 || lenr > MAXNUMELTS)
2580 rhodiumtoad@postgres 336 [ # # ]:UBC 0 : ereport(ERROR,
337 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
338 : : errmsg("compressed array is too big, recreate index using gist__intbig_ops opclass instead")));
339 : :
8224 bruce@momjian.us 340 :CBC 24602 : r = new_intArrayType(lenr);
341 [ - + ]: 24602 : dr = ARRPTR(r);
342 : :
343 [ + + ]: 5747634 : for (i = 0; i < lenin; i += 2)
344 : : {
345 : : /* use int64 for j in case din[i + 1] is INT_MAX */
709 tgl@sss.pgh.pa.us 346 [ + + ]: 23048108 : for (int64 j = din[i]; j <= din[i + 1]; j++)
8224 bruce@momjian.us 347 [ + + + - ]: 17325076 : if ((!i) || *(dr - 1) != j)
709 tgl@sss.pgh.pa.us 348 : 17325076 : *dr++ = (int) j;
349 : : }
350 : :
8224 bruce@momjian.us 351 [ + - ]: 24602 : if (in != (ArrayType *) DatumGetPointer(entry->key))
352 : 24602 : pfree(in);
11 michael@paquier.xyz 353 :GNC 24602 : retval = palloc_object(GISTENTRY);
8224 bruce@momjian.us 354 :CBC 24602 : gistentryinit(*retval, PointerGetDatum(r),
355 : : entry->rel, entry->page, entry->offset, false);
356 : :
357 : 24602 : PG_RETURN_POINTER(retval);
358 : : }
359 : :
360 : : /*
361 : : ** The GiST Penalty method for _intments
362 : : */
363 : : Datum
8170 364 : 289984 : g_int_penalty(PG_FUNCTION_ARGS)
365 : : {
366 : 289984 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
367 : 289984 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
368 : 289984 : float *result = (float *) PG_GETARG_POINTER(2);
369 : : ArrayType *ud;
370 : : float tmp1,
371 : : tmp2;
372 : :
8224 373 : 289984 : ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
8170 374 : 289984 : (ArrayType *) DatumGetPointer(newentry->key));
8224 375 : 289984 : rt__int_size(ud, &tmp1);
376 : 289984 : rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
377 : 289984 : *result = tmp1 - tmp2;
378 : 289984 : pfree(ud);
379 : :
8170 380 : 289984 : PG_RETURN_POINTER(result);
381 : : }
382 : :
383 : :
384 : :
385 : : Datum
8224 386 : 58915 : g_int_same(PG_FUNCTION_ARGS)
387 : : {
5455 tgl@sss.pgh.pa.us 388 : 58915 : ArrayType *a = PG_GETARG_ARRAYTYPE_P(0);
389 : 58915 : ArrayType *b = PG_GETARG_ARRAYTYPE_P(1);
8224 bruce@momjian.us 390 : 58915 : bool *result = (bool *) PG_GETARG_POINTER(2);
4922 peter_e@gmx.net 391 : 58915 : int32 n = ARRNELEMS(a);
392 : : int32 *da,
393 : : *db;
394 : :
7332 tgl@sss.pgh.pa.us 395 [ - + - - : 58915 : CHECKARRVALID(a);
- - ]
396 [ - + - - : 58915 : CHECKARRVALID(b);
- - ]
397 : :
8224 bruce@momjian.us 398 [ + + ]: 58915 : if (n != ARRNELEMS(b))
399 : : {
400 : 11616 : *result = false;
401 : 11616 : PG_RETURN_POINTER(result);
402 : : }
3044 peter_e@gmx.net 403 : 47299 : *result = true;
8224 bruce@momjian.us 404 [ - + ]: 47299 : da = ARRPTR(a);
405 [ - + ]: 47299 : db = ARRPTR(b);
406 [ + + ]: 13742605 : while (n--)
407 : : {
408 [ + + ]: 13695819 : if (*da++ != *db++)
409 : : {
3044 peter_e@gmx.net 410 : 513 : *result = false;
8224 bruce@momjian.us 411 : 513 : break;
412 : : }
413 : : }
414 : :
415 : 47299 : PG_RETURN_POINTER(result);
416 : : }
417 : :
418 : : /*****************************************************************
419 : : ** Common GiST Method
420 : : *****************************************************************/
421 : :
422 : : typedef struct
423 : : {
424 : : OffsetNumber pos;
425 : : float cost;
426 : : } SPLITCOST;
427 : :
428 : : static int
429 : 61223 : comparecost(const void *a, const void *b)
430 : : {
5210 peter_e@gmx.net 431 [ + + ]: 61223 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
8224 bruce@momjian.us 432 : 32994 : return 0;
433 : : else
5210 peter_e@gmx.net 434 [ + + ]: 28229 : return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
435 : : }
436 : :
437 : : /*
438 : : ** The GiST PickSplit method for _intments
439 : : ** We use Guttman's poly time split algorithm
440 : : */
441 : : Datum
8170 bruce@momjian.us 442 : 601 : g_int_picksplit(PG_FUNCTION_ARGS)
443 : : {
7779 444 : 601 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8224 445 : 601 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
446 : : OffsetNumber i,
447 : : j;
448 : : ArrayType *datum_alpha,
449 : : *datum_beta;
450 : : ArrayType *datum_l,
451 : : *datum_r;
452 : : ArrayType *union_d,
453 : : *union_dl,
454 : : *union_dr;
455 : : ArrayType *inter_d;
456 : : bool firsttime;
457 : : float size_alpha,
458 : : size_beta,
459 : : size_union,
460 : : size_inter;
461 : : float size_waste,
462 : : waste;
463 : : float size_l,
464 : : size_r;
465 : : int nbytes;
466 : 601 : OffsetNumber seed_1 = 0,
467 : 601 : seed_2 = 0;
468 : : OffsetNumber *left,
469 : : *right;
470 : : OffsetNumber maxoff;
471 : : SPLITCOST *costvector;
472 : :
473 : : #ifdef GIST_DEBUG
474 : : elog(DEBUG3, "--------picksplit %d", entryvec->n);
475 : : #endif
476 : :
7931 teodor@sigaev.ru 477 : 601 : maxoff = entryvec->n - 2;
8224 bruce@momjian.us 478 : 601 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
479 : 601 : v->spl_left = (OffsetNumber *) palloc(nbytes);
480 : 601 : v->spl_right = (OffsetNumber *) palloc(nbytes);
481 : :
482 : 601 : firsttime = true;
483 : 601 : waste = 0.0;
484 [ + + ]: 32503 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
485 : : {
7779 486 : 31902 : datum_alpha = GETENTRY(entryvec, i);
8224 487 [ + + ]: 1811385 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
488 : : {
7779 489 : 1779483 : datum_beta = GETENTRY(entryvec, j);
490 : :
491 : : /* compute the wasted space by unioning these guys */
492 : : /* size_waste = size_union - size_inter; */
8224 493 : 1779483 : union_d = inner_int_union(datum_alpha, datum_beta);
494 : 1779483 : rt__int_size(union_d, &size_union);
495 : 1779483 : inter_d = inner_int_inter(datum_alpha, datum_beta);
496 : 1779483 : rt__int_size(inter_d, &size_inter);
497 : 1779483 : size_waste = size_union - size_inter;
498 : :
499 : 1779483 : pfree(union_d);
3956 kgrittn@postgresql.o 500 : 1779483 : pfree(inter_d);
501 : :
502 : : /*
503 : : * are these a more promising split that what we've already seen?
504 : : */
505 : :
8224 bruce@momjian.us 506 [ + + + + ]: 1779483 : if (size_waste > waste || firsttime)
507 : : {
508 : 2846 : waste = size_waste;
509 : 2846 : seed_1 = i;
510 : 2846 : seed_2 = j;
511 : 2846 : firsttime = false;
512 : : }
513 : : }
514 : : }
515 : :
516 : 601 : left = v->spl_left;
517 : 601 : v->spl_nleft = 0;
518 : 601 : right = v->spl_right;
519 : 601 : v->spl_nright = 0;
520 [ + - - + ]: 601 : if (seed_1 == 0 || seed_2 == 0)
521 : : {
8224 bruce@momjian.us 522 :UBC 0 : seed_1 = 1;
523 : 0 : seed_2 = 2;
524 : : }
525 : :
7779 bruce@momjian.us 526 :CBC 601 : datum_alpha = GETENTRY(entryvec, seed_1);
8224 527 : 601 : datum_l = copy_intArrayType(datum_alpha);
528 : 601 : rt__int_size(datum_l, &size_l);
7779 529 : 601 : datum_beta = GETENTRY(entryvec, seed_2);
8224 530 : 601 : datum_r = copy_intArrayType(datum_beta);
531 : 601 : rt__int_size(datum_r, &size_r);
532 : :
533 : 601 : maxoff = OffsetNumberNext(maxoff);
534 : :
535 : : /*
536 : : * sort entries
537 : : */
11 michael@paquier.xyz 538 :GNC 601 : costvector = palloc_array(SPLITCOST, maxoff);
8224 bruce@momjian.us 539 [ + + ]:CBC 33705 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
540 : : {
541 : 33104 : costvector[i - 1].pos = i;
7779 542 : 33104 : datum_alpha = GETENTRY(entryvec, i);
8224 543 : 33104 : union_d = inner_int_union(datum_l, datum_alpha);
544 : 33104 : rt__int_size(union_d, &size_alpha);
545 : 33104 : pfree(union_d);
546 : 33104 : union_d = inner_int_union(datum_r, datum_alpha);
547 : 33104 : rt__int_size(union_d, &size_beta);
548 : 33104 : pfree(union_d);
1165 peter@eisentraut.org 549 : 33104 : costvector[i - 1].cost = fabsf((size_alpha - size_l) - (size_beta - size_r));
550 : : }
1043 551 : 601 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
552 : :
553 : : /*
554 : : * Now split up the regions between the two seeds. An important property
555 : : * of this split algorithm is that the split vector v has the indices of
556 : : * items to be split in order in its left and right vectors. We exploit
557 : : * this property by doing a merge in the code that actually splits the
558 : : * page.
559 : : *
560 : : * For efficiency, we also place the new index tuple in this loop. This is
561 : : * handled at the very end, when we have placed all the existing tuples
562 : : * and i == maxoff + 1.
563 : : */
564 : :
565 : :
8224 bruce@momjian.us 566 [ + + ]: 33705 : for (j = 0; j < maxoff; j++)
567 : : {
568 : 33104 : i = costvector[j].pos;
569 : :
570 : : /*
571 : : * If we've already decided where to place this item, just put it on
572 : : * the right list. Otherwise, we need to figure out which page needs
573 : : * the least enlargement in order to store the item.
574 : : */
575 : :
576 [ + + ]: 33104 : if (i == seed_1)
577 : : {
578 : 601 : *left++ = i;
579 : 601 : v->spl_nleft++;
580 : 601 : continue;
581 : : }
582 [ + + ]: 32503 : else if (i == seed_2)
583 : : {
584 : 601 : *right++ = i;
585 : 601 : v->spl_nright++;
586 : 601 : continue;
587 : : }
588 : :
589 : : /* okay, which page needs least enlargement? */
7779 590 : 31902 : datum_alpha = GETENTRY(entryvec, i);
8224 591 : 31902 : union_dl = inner_int_union(datum_l, datum_alpha);
592 : 31902 : union_dr = inner_int_union(datum_r, datum_alpha);
593 : 31902 : rt__int_size(union_dl, &size_alpha);
594 : 31902 : rt__int_size(union_dr, &size_beta);
595 : :
596 : : /* pick which page to add it to */
597 [ + + ]: 31902 : if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
598 : : {
3956 kgrittn@postgresql.o 599 : 15470 : pfree(datum_l);
600 : 15470 : pfree(union_dr);
8224 bruce@momjian.us 601 : 15470 : datum_l = union_dl;
602 : 15470 : size_l = size_alpha;
603 : 15470 : *left++ = i;
604 : 15470 : v->spl_nleft++;
605 : : }
606 : : else
607 : : {
3956 kgrittn@postgresql.o 608 : 16432 : pfree(datum_r);
609 : 16432 : pfree(union_dl);
8224 bruce@momjian.us 610 : 16432 : datum_r = union_dr;
611 : 16432 : size_r = size_beta;
612 : 16432 : *right++ = i;
613 : 16432 : v->spl_nright++;
614 : : }
615 : : }
616 : 601 : pfree(costvector);
617 : 601 : *right = *left = FirstOffsetNumber;
618 : :
619 : 601 : v->spl_ldatum = PointerGetDatum(datum_l);
620 : 601 : v->spl_rdatum = PointerGetDatum(datum_r);
621 : :
622 : 601 : PG_RETURN_POINTER(v);
623 : : }
624 : :
625 : : Datum
2087 akorotkov@postgresql 626 : 13 : g_int_options(PG_FUNCTION_ARGS)
627 : : {
628 : 13 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
629 : :
630 : 13 : init_local_reloptions(relopts, sizeof(GISTIntArrayOptions));
631 : 13 : add_local_int_reloption(relopts, "numranges",
632 : : "number of ranges for compression",
633 : : G_INT_NUMRANGES_DEFAULT, 1, G_INT_NUMRANGES_MAX,
634 : : offsetof(GISTIntArrayOptions, num_ranges));
635 : :
636 : 13 : PG_RETURN_VOID();
637 : : }
|
