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 : : */
8420 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);
2283 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
8420 bruce@momjian.us 47 : 129804 : g_int_consistent(PG_FUNCTION_ARGS)
48 : : {
49 : 129804 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
5651 tgl@sss.pgh.pa.us 50 : 129804 : ArrayType *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
8420 bruce@momjian.us 51 : 129804 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
52 : : #ifdef NOT_USED
53 : : Oid subtype = PG_GETARG_OID(3);
54 : : #endif
6651 tgl@sss.pgh.pa.us 55 : 129804 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1372 peter@eisentraut.org 56 : 129804 : bool retval = false; /* silence compiler warning */
57 : :
58 : : /* this is exact except for RTSameStrategyNumber */
6651 tgl@sss.pgh.pa.us 59 : 129804 : *recheck = (strategy == RTSameStrategyNumber);
60 : :
7209 bruce@momjian.us 61 [ + + ]: 129804 : if (strategy == BooleanSearchStrategy)
62 : : {
7393 teodor@sigaev.ru 63 : 82648 : retval = execconsistent((QUERYTYPE *) query,
7209 bruce@momjian.us 64 : 82648 : (ArrayType *) DatumGetPointer(entry->key),
65 : 82648 : GIST_LEAF(entry));
66 : :
67 : 82648 : pfree(query);
7393 teodor@sigaev.ru 68 : 82648 : PG_RETURN_BOOL(retval);
69 : : }
70 : :
71 : : /* sort query for fast search, key is already sorted */
7528 tgl@sss.pgh.pa.us 72 [ - + - - : 47156 : CHECKARRVALID(query);
- - ]
8420 bruce@momjian.us 73 [ - + ]: 47156 : PREPAREARR(query);
74 : :
75 [ + + + - : 47156 : switch (strategy)
- ]
76 : : {
77 : 16839 : case RTOverlapStrategyNumber:
78 : 16839 : retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
79 : : query);
80 : 16839 : break;
81 : 3943 : case RTSameStrategyNumber:
82 [ + + ]: 3943 : if (GIST_LEAF(entry))
5651 tgl@sss.pgh.pa.us 83 : 3662 : DirectFunctionCall3(g_int_same,
84 : : entry->key,
85 : : PointerGetDatum(query),
86 : : PointerGetDatum(&retval));
87 : : else
8420 bruce@momjian.us 88 : 281 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
89 : : query);
90 : 3943 : break;
91 : 26374 : case RTContainsStrategyNumber:
92 : : case RTOldContainsStrategyNumber:
93 : 26374 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
94 : : query);
95 : 26374 : break;
8420 bruce@momjian.us 96 :UBC 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,
3296 tgl@sss.pgh.pa.us 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 : : */
2520 113 : 0 : retval = true;
114 : : }
8420 bruce@momjian.us 115 : 0 : break;
116 : 0 : default:
3240 peter_e@gmx.net 117 : 0 : retval = false;
118 : : }
7209 bruce@momjian.us 119 :CBC 47156 : pfree(query);
8420 120 : 47156 : PG_RETURN_BOOL(retval);
121 : : }
122 : :
123 : : Datum
8366 124 : 57375 : g_int_union(PG_FUNCTION_ARGS)
125 : : {
7975 126 : 57375 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8366 127 : 57375 : int *size = (int *) PG_GETARG_POINTER(1);
128 : : int32 i,
129 : : *ptr;
130 : : ArrayType *res;
7528 tgl@sss.pgh.pa.us 131 : 57375 : int totlen = 0;
132 : :
8127 teodor@sigaev.ru 133 [ + + ]: 173193 : for (i = 0; i < entryvec->n; i++)
134 : : {
7525 bruce@momjian.us 135 : 115818 : ArrayType *ent = GETENTRY(entryvec, i);
136 : :
7528 tgl@sss.pgh.pa.us 137 [ - + - - : 115818 : CHECKARRVALID(ent);
- - ]
138 : 115818 : totlen += ARRNELEMS(ent);
139 : : }
140 : :
8366 bruce@momjian.us 141 : 57375 : res = new_intArrayType(totlen);
142 [ - + ]: 57375 : ptr = ARRPTR(res);
143 : :
8127 teodor@sigaev.ru 144 [ + + ]: 173193 : for (i = 0; i < entryvec->n; i++)
145 : : {
7525 bruce@momjian.us 146 : 115818 : ArrayType *ent = GETENTRY(entryvec, i);
147 : : int nel;
148 : :
7528 tgl@sss.pgh.pa.us 149 : 115818 : nel = ARRNELEMS(ent);
5118 peter_e@gmx.net 150 [ - + ]: 115818 : memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
7528 tgl@sss.pgh.pa.us 151 : 115818 : ptr += nel;
152 : : }
153 : :
8366 bruce@momjian.us 154 [ - + ]: 57375 : QSORT(res, 1);
155 : 57375 : res = _int_unique(res);
156 : 57375 : *size = VARSIZE(res);
8420 157 : 57375 : PG_RETURN_POINTER(res);
158 : : }
159 : :
160 : : /*
161 : : * GiST Compress and Decompress methods
162 : : */
163 : : Datum
164 : 29994 : g_int_compress(PG_FUNCTION_ARGS)
165 : : {
166 : 29994 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
167 : : GISTENTRY *retval;
168 : : ArrayType *r;
2283 akorotkov@postgresql 169 [ + - ]: 29994 : 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 : :
8420 bruce@momjian.us 178 [ + + ]: 29994 : if (entry->leafkey)
179 : : {
5651 tgl@sss.pgh.pa.us 180 : 20272 : r = DatumGetArrayTypePCopy(entry->key);
7528 181 [ - + - - : 20272 : CHECKARRVALID(r);
- - ]
8420 bruce@momjian.us 182 [ - + ]: 20272 : PREPAREARR(r);
183 : :
2283 akorotkov@postgresql 184 [ + + ]: 20272 : if (ARRNELEMS(r) >= 2 * num_ranges)
1111 michael@paquier.xyz 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 : :
207 michael@paquier.xyz 190 :GNC 20271 : retval = palloc_object(GISTENTRY);
8420 bruce@momjian.us 191 :CBC 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 : :
5651 tgl@sss.pgh.pa.us 202 : 9722 : r = DatumGetArrayTypeP(entry->key);
7528 203 [ - + - - : 9722 : CHECKARRVALID(r);
- - ]
5651 204 [ - + ]: 9722 : if (ARRISEMPTY(r))
205 : : {
8420 bruce@momjian.us 206 [ # # ]:UBC 0 : if (r != (ArrayType *) DatumGetPointer(entry->key))
207 : 0 : pfree(r);
208 : 0 : PG_RETURN_POINTER(entry);
209 : : }
210 : :
2283 akorotkov@postgresql 211 [ + + ]:CBC 9722 : if ((len = ARRNELEMS(r)) >= 2 * num_ranges)
212 : : { /* compress */
8420 bruce@momjian.us 213 [ + - ]: 1457 : if (r == (ArrayType *) DatumGetPointer(entry->key))
5651 tgl@sss.pgh.pa.us 214 : 1457 : r = DatumGetArrayTypePCopy(entry->key);
8420 bruce@momjian.us 215 : 1457 : r = resize_intArrayType(r, 2 * (len));
216 : :
217 [ - + ]: 1457 : 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 : : */
2283 akorotkov@postgresql 224 : 1457 : 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 : : */
2776 rhodiumtoad@postgres 230 [ + - + + ]: 75395 : for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
231 : : {
2596 tgl@sss.pgh.pa.us 232 : 73938 : int r_end = dr[i];
233 : 73938 : int r_start = r_end;
234 : :
235 [ + - + + : 702679 : while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
+ + ]
2776 rhodiumtoad@postgres 236 : 628741 : --r_start, --i, --lenr;
2596 tgl@sss.pgh.pa.us 237 : 73938 : dr[2 * j] = r_start;
238 : 73938 : dr[2 * j + 1] = r_end;
239 : : }
240 : : /* just copy the rest, if any, as trivial ranges */
2776 rhodiumtoad@postgres 241 [ + + ]: 268387 : for (; i >= 0; i--, j--)
2596 tgl@sss.pgh.pa.us 242 : 266930 : dr[2 * j] = dr[2 * j + 1] = dr[i];
243 : :
2776 rhodiumtoad@postgres 244 [ + - ]: 1457 : if (++j)
245 : : {
246 : : /*
247 : : * shunt everything down to start at the right place
248 : : */
1239 peter@eisentraut.org 249 : 1457 : 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 : : */
2596 tgl@sss.pgh.pa.us 255 : 1457 : len = 2 * (len - j);
8420 bruce@momjian.us 256 : 1457 : cand = 1;
2283 akorotkov@postgresql 257 [ - + ]: 1457 : while (len > num_ranges * 2)
258 : : {
2776 rhodiumtoad@postgres 259 :UBC 0 : min = PG_INT64_MAX;
8420 bruce@momjian.us 260 [ # # ]: 0 : for (i = 2; i < len; i += 2)
2596 tgl@sss.pgh.pa.us 261 [ # # ]: 0 : if (min > ((int64) dr[i] - (int64) dr[i - 1]))
262 : : {
263 : 0 : min = ((int64) dr[i] - (int64) dr[i - 1]);
8420 bruce@momjian.us 264 : 0 : cand = i;
265 : : }
1239 peter@eisentraut.org 266 : 0 : memmove(&dr[cand - 1], &dr[cand + 1], (len - cand - 1) * sizeof(int32));
8420 bruce@momjian.us 267 : 0 : len -= 2;
268 : : }
269 : :
270 : : /*
271 : : * check sparseness of result
272 : : */
2776 rhodiumtoad@postgres 273 :CBC 1457 : lenr = internal_size(dr, len);
274 [ + - - + ]: 1457 : if (lenr < 0 || lenr > MAXNUMELTS)
2776 rhodiumtoad@postgres 275 [ # # ]:UBC 0 : ereport(ERROR,
276 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
277 : : errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));
278 : :
8420 bruce@momjian.us 279 :CBC 1457 : r = resize_intArrayType(r, len);
207 michael@paquier.xyz 280 :GNC 1457 : retval = palloc_object(GISTENTRY);
8420 bruce@momjian.us 281 :CBC 1457 : gistentryinit(*retval, PointerGetDatum(r),
282 : : entry->rel, entry->page, entry->offset, false);
283 : 1457 : PG_RETURN_POINTER(retval);
284 : : }
285 : : else
286 : 8265 : PG_RETURN_POINTER(entry);
287 : : }
288 : :
289 : : Datum
290 : 646342 : g_int_decompress(PG_FUNCTION_ARGS)
291 : : {
292 : 646342 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
293 : : GISTENTRY *retval;
294 : : ArrayType *r;
2283 akorotkov@postgresql 295 [ + - ]: 646342 : 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 : :
5651 tgl@sss.pgh.pa.us 303 : 646342 : in = DatumGetArrayTypeP(entry->key);
304 : :
7528 305 [ - + - - : 646342 : CHECKARRVALID(in);
- - ]
5651 306 [ + + ]: 646342 : if (ARRISEMPTY(in))
307 : : {
6802 bruce@momjian.us 308 [ + - ]: 385 : if (in != (ArrayType *) DatumGetPointer(entry->key))
309 : : {
207 michael@paquier.xyz 310 :GNC 385 : retval = palloc_object(GISTENTRY);
7025 tgl@sss.pgh.pa.us 311 :CBC 385 : gistentryinit(*retval, PointerGetDatum(in),
312 : : entry->rel, entry->page, entry->offset, false);
313 : 385 : PG_RETURN_POINTER(retval);
314 : : }
315 : :
8420 bruce@momjian.us 316 :UBC 0 : PG_RETURN_POINTER(entry);
317 : : }
318 : :
8420 bruce@momjian.us 319 :CBC 645957 : lenin = ARRNELEMS(in);
320 : :
2283 akorotkov@postgresql 321 [ + + ]: 645957 : if (lenin < 2 * num_ranges)
322 : : { /* not compressed value */
8420 bruce@momjian.us 323 [ + + ]: 617588 : if (in != (ArrayType *) DatumGetPointer(entry->key))
324 : : {
207 michael@paquier.xyz 325 :GNC 282577 : retval = palloc_object(GISTENTRY);
8420 bruce@momjian.us 326 :CBC 282577 : gistentryinit(*retval, PointerGetDatum(in),
327 : : entry->rel, entry->page, entry->offset, false);
328 : :
329 : 282577 : PG_RETURN_POINTER(retval);
330 : : }
331 : 335011 : PG_RETURN_POINTER(entry);
332 : : }
333 : :
334 [ - + ]: 28369 : din = ARRPTR(in);
335 : 28369 : lenr = internal_size(din, lenin);
2776 rhodiumtoad@postgres 336 [ + - - + ]: 28369 : if (lenr < 0 || lenr > MAXNUMELTS)
2776 rhodiumtoad@postgres 337 [ # # ]:UBC 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 : :
8420 bruce@momjian.us 341 :CBC 28369 : r = new_intArrayType(lenr);
342 [ - + ]: 28369 : dr = ARRPTR(r);
343 : :
344 [ + + ]: 6702357 : for (i = 0; i < lenin; i += 2)
345 : : {
346 : : /* use int64 for j in case din[i + 1] is INT_MAX */
905 tgl@sss.pgh.pa.us 347 [ + + ]: 26727056 : for (int64 j = din[i]; j <= din[i + 1]; j++)
8420 bruce@momjian.us 348 [ + + + - ]: 20053068 : if ((!i) || *(dr - 1) != j)
905 tgl@sss.pgh.pa.us 349 : 20053068 : *dr++ = (int) j;
350 : : }
351 : :
8420 bruce@momjian.us 352 [ + - ]: 28369 : if (in != (ArrayType *) DatumGetPointer(entry->key))
353 : 28369 : pfree(in);
207 michael@paquier.xyz 354 :GNC 28369 : retval = palloc_object(GISTENTRY);
8420 bruce@momjian.us 355 :CBC 28369 : gistentryinit(*retval, PointerGetDatum(r),
356 : : entry->rel, entry->page, entry->offset, false);
357 : :
358 : 28369 : PG_RETURN_POINTER(retval);
359 : : }
360 : :
361 : : /*
362 : : * The GiST Penalty method for _intments
363 : : */
364 : : Datum
8366 365 : 307699 : g_int_penalty(PG_FUNCTION_ARGS)
366 : : {
367 : 307699 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
368 : 307699 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
369 : 307699 : float *result = (float *) PG_GETARG_POINTER(2);
370 : : ArrayType *ud;
371 : : float tmp1,
372 : : tmp2;
373 : :
8420 374 : 307699 : ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
8366 375 : 307699 : (ArrayType *) DatumGetPointer(newentry->key));
8420 376 : 307699 : rt__int_size(ud, &tmp1);
377 : 307699 : rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
378 : 307699 : *result = tmp1 - tmp2;
379 : 307699 : pfree(ud);
380 : :
8366 381 : 307699 : PG_RETURN_POINTER(result);
382 : : }
383 : :
384 : :
385 : :
386 : : Datum
8420 387 : 61002 : g_int_same(PG_FUNCTION_ARGS)
388 : : {
5651 tgl@sss.pgh.pa.us 389 : 61002 : ArrayType *a = PG_GETARG_ARRAYTYPE_P(0);
390 : 61002 : ArrayType *b = PG_GETARG_ARRAYTYPE_P(1);
8420 bruce@momjian.us 391 : 61002 : bool *result = (bool *) PG_GETARG_POINTER(2);
5118 peter_e@gmx.net 392 : 61002 : int32 n = ARRNELEMS(a);
393 : : int32 *da,
394 : : *db;
395 : :
7528 tgl@sss.pgh.pa.us 396 [ - + - - : 61002 : CHECKARRVALID(a);
- - ]
397 [ - + - - : 61002 : CHECKARRVALID(b);
- - ]
398 : :
8420 bruce@momjian.us 399 [ + + ]: 61002 : if (n != ARRNELEMS(b))
400 : : {
401 : 11433 : *result = false;
402 : 11433 : PG_RETURN_POINTER(result);
403 : : }
3240 peter_e@gmx.net 404 : 49569 : *result = true;
8420 bruce@momjian.us 405 [ - + ]: 49569 : da = ARRPTR(a);
406 [ - + ]: 49569 : db = ARRPTR(b);
407 [ + + ]: 15019889 : while (n--)
408 : : {
409 [ + + ]: 14971011 : if (*da++ != *db++)
410 : : {
3240 peter_e@gmx.net 411 : 691 : *result = false;
8420 bruce@momjian.us 412 : 691 : break;
413 : : }
414 : : }
415 : :
416 : 49569 : 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 : 61978 : comparecost(const void *a, const void *b)
431 : : {
5406 peter_e@gmx.net 432 [ + + ]: 61978 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
8420 bruce@momjian.us 433 : 33114 : return 0;
434 : : else
5406 peter_e@gmx.net 435 [ + + ]: 28864 : 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
8366 bruce@momjian.us 443 : 619 : g_int_picksplit(PG_FUNCTION_ARGS)
444 : : {
7975 445 : 619 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8420 446 : 619 : 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 : 619 : OffsetNumber seed_1 = 0,
468 : 619 : 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 : :
8127 teodor@sigaev.ru 478 : 619 : maxoff = entryvec->n - 2;
8420 bruce@momjian.us 479 : 619 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
480 : 619 : v->spl_left = (OffsetNumber *) palloc(nbytes);
481 : 619 : v->spl_right = (OffsetNumber *) palloc(nbytes);
482 : :
483 : 619 : firsttime = true;
484 : 619 : waste = 0.0;
485 [ + + ]: 32585 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
486 : : {
7975 487 : 31966 : datum_alpha = GETENTRY(entryvec, i);
8420 488 [ + + ]: 1803509 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
489 : : {
7975 490 : 1771543 : datum_beta = GETENTRY(entryvec, j);
491 : :
492 : : /* compute the wasted space by unioning these guys */
493 : : /* size_waste = size_union - size_inter; */
8420 494 : 1771543 : union_d = inner_int_union(datum_alpha, datum_beta);
495 : 1771543 : rt__int_size(union_d, &size_union);
496 : 1771543 : inter_d = inner_int_inter(datum_alpha, datum_beta);
497 : 1771543 : rt__int_size(inter_d, &size_inter);
498 : 1771543 : size_waste = size_union - size_inter;
499 : :
500 : 1771543 : pfree(union_d);
4152 kgrittn@postgresql.o 501 : 1771543 : pfree(inter_d);
502 : :
503 : : /*
504 : : * are these a more promising split that what we've already seen?
505 : : */
506 : :
8420 bruce@momjian.us 507 [ + + - + ]: 1771543 : if (size_waste > waste || firsttime)
508 : : {
509 : 2947 : waste = size_waste;
510 : 2947 : seed_1 = i;
511 : 2947 : seed_2 = j;
512 : 2947 : firsttime = false;
513 : : }
514 : : }
515 : : }
516 : :
517 : 619 : left = v->spl_left;
518 : 619 : v->spl_nleft = 0;
519 : 619 : right = v->spl_right;
520 : 619 : v->spl_nright = 0;
521 [ + - - + ]: 619 : if (seed_1 == 0 || seed_2 == 0)
522 : : {
8420 bruce@momjian.us 523 :UBC 0 : seed_1 = 1;
524 : 0 : seed_2 = 2;
525 : : }
526 : :
7975 bruce@momjian.us 527 :CBC 619 : datum_alpha = GETENTRY(entryvec, seed_1);
8420 528 : 619 : datum_l = copy_intArrayType(datum_alpha);
529 : 619 : rt__int_size(datum_l, &size_l);
7975 530 : 619 : datum_beta = GETENTRY(entryvec, seed_2);
8420 531 : 619 : datum_r = copy_intArrayType(datum_beta);
532 : 619 : rt__int_size(datum_r, &size_r);
533 : :
534 : 619 : maxoff = OffsetNumberNext(maxoff);
535 : :
536 : : /*
537 : : * sort entries
538 : : */
207 michael@paquier.xyz 539 :GNC 619 : costvector = palloc_array(SPLITCOST, maxoff);
8420 bruce@momjian.us 540 [ + + ]:CBC 33823 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
541 : : {
542 : 33204 : costvector[i - 1].pos = i;
7975 543 : 33204 : datum_alpha = GETENTRY(entryvec, i);
8420 544 : 33204 : union_d = inner_int_union(datum_l, datum_alpha);
545 : 33204 : rt__int_size(union_d, &size_alpha);
546 : 33204 : pfree(union_d);
547 : 33204 : union_d = inner_int_union(datum_r, datum_alpha);
548 : 33204 : rt__int_size(union_d, &size_beta);
549 : 33204 : pfree(union_d);
1361 peter@eisentraut.org 550 : 33204 : costvector[i - 1].cost = fabsf((size_alpha - size_l) - (size_beta - size_r));
551 : : }
1239 552 : 619 : 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 : :
8420 bruce@momjian.us 567 [ + + ]: 33823 : for (j = 0; j < maxoff; j++)
568 : : {
569 : 33204 : 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 [ + + ]: 33204 : if (i == seed_1)
578 : : {
579 : 619 : *left++ = i;
580 : 619 : v->spl_nleft++;
581 : 619 : continue;
582 : : }
583 [ + + ]: 32585 : else if (i == seed_2)
584 : : {
585 : 619 : *right++ = i;
586 : 619 : v->spl_nright++;
587 : 619 : continue;
588 : : }
589 : :
590 : : /* okay, which page needs least enlargement? */
7975 591 : 31966 : datum_alpha = GETENTRY(entryvec, i);
8420 592 : 31966 : union_dl = inner_int_union(datum_l, datum_alpha);
593 : 31966 : union_dr = inner_int_union(datum_r, datum_alpha);
594 : 31966 : rt__int_size(union_dl, &size_alpha);
595 : 31966 : rt__int_size(union_dr, &size_beta);
596 : :
597 : : /* pick which page to add it to */
598 [ + + ]: 31966 : if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
599 : : {
4152 kgrittn@postgresql.o 600 : 15481 : pfree(datum_l);
601 : 15481 : pfree(union_dr);
8420 bruce@momjian.us 602 : 15481 : datum_l = union_dl;
603 : 15481 : size_l = size_alpha;
604 : 15481 : *left++ = i;
605 : 15481 : v->spl_nleft++;
606 : : }
607 : : else
608 : : {
4152 kgrittn@postgresql.o 609 : 16485 : pfree(datum_r);
610 : 16485 : pfree(union_dl);
8420 bruce@momjian.us 611 : 16485 : datum_r = union_dr;
612 : 16485 : size_r = size_beta;
613 : 16485 : *right++ = i;
614 : 16485 : v->spl_nright++;
615 : : }
616 : : }
617 : 619 : pfree(costvector);
618 : 619 : *right = *left = FirstOffsetNumber;
619 : :
620 : 619 : v->spl_ldatum = PointerGetDatum(datum_l);
621 : 619 : v->spl_rdatum = PointerGetDatum(datum_r);
622 : :
623 : 619 : PG_RETURN_POINTER(v);
624 : : }
625 : :
626 : : Datum
2283 akorotkov@postgresql 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 : : }
|
