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