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