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 : : */
8174 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);
2037 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
8174 bruce@momjian.us 47 : 131207 : g_int_consistent(PG_FUNCTION_ARGS)
48 : : {
49 : 131207 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
5405 tgl@sss.pgh.pa.us 50 : 131207 : ArrayType *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
8174 bruce@momjian.us 51 : 131207 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
52 : :
53 : : /* Oid subtype = PG_GETARG_OID(3); */
6405 tgl@sss.pgh.pa.us 54 : 131207 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1126 peter@eisentraut.org 55 : 131207 : bool retval = false; /* silence compiler warning */
56 : :
57 : : /* this is exact except for RTSameStrategyNumber */
6405 tgl@sss.pgh.pa.us 58 : 131207 : *recheck = (strategy == RTSameStrategyNumber);
59 : :
6963 bruce@momjian.us 60 [ + + ]: 131207 : if (strategy == BooleanSearchStrategy)
61 : : {
7147 teodor@sigaev.ru 62 : 83216 : retval = execconsistent((QUERYTYPE *) query,
6963 bruce@momjian.us 63 : 83216 : (ArrayType *) DatumGetPointer(entry->key),
64 : 83216 : GIST_LEAF(entry));
65 : :
66 : 83216 : pfree(query);
7147 teodor@sigaev.ru 67 : 83216 : PG_RETURN_BOOL(retval);
68 : : }
69 : :
70 : : /* sort query for fast search, key is already sorted */
7282 tgl@sss.pgh.pa.us 71 [ - + - - : 47991 : CHECKARRVALID(query);
- - ]
8174 bruce@momjian.us 72 [ - + ]: 47991 : PREPAREARR(query);
73 : :
74 [ + + + - : 47991 : switch (strategy)
- ]
75 : : {
76 : 16500 : case RTOverlapStrategyNumber:
77 : 16500 : retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
78 : : query);
79 : 16500 : break;
80 : 4706 : case RTSameStrategyNumber:
81 [ + + ]: 4706 : if (GIST_LEAF(entry))
5405 tgl@sss.pgh.pa.us 82 : 4384 : DirectFunctionCall3(g_int_same,
83 : : entry->key,
84 : : PointerGetDatum(query),
85 : : PointerGetDatum(&retval));
86 : : else
8174 bruce@momjian.us 87 : 322 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
88 : : query);
89 : 4706 : break;
90 : 26785 : case RTContainsStrategyNumber:
91 : : case RTOldContainsStrategyNumber:
92 : 26785 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
93 : : query);
94 : 26785 : break;
8174 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,
3050 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 : : */
2274 112 : 0 : retval = true;
113 : : }
8174 bruce@momjian.us 114 : 0 : break;
115 : 0 : default:
2994 peter_e@gmx.net 116 : 0 : retval = false;
117 : : }
6963 bruce@momjian.us 118 :CBC 47991 : pfree(query);
8174 119 : 47991 : PG_RETURN_BOOL(retval);
120 : : }
121 : :
122 : : Datum
8120 123 : 57432 : g_int_union(PG_FUNCTION_ARGS)
124 : : {
7729 125 : 57432 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8120 126 : 57432 : int *size = (int *) PG_GETARG_POINTER(1);
127 : : int32 i,
128 : : *ptr;
129 : : ArrayType *res;
7282 tgl@sss.pgh.pa.us 130 : 57432 : int totlen = 0;
131 : :
7881 teodor@sigaev.ru 132 [ + + ]: 172932 : for (i = 0; i < entryvec->n; i++)
133 : : {
7279 bruce@momjian.us 134 : 115500 : ArrayType *ent = GETENTRY(entryvec, i);
135 : :
7282 tgl@sss.pgh.pa.us 136 [ - + - - : 115500 : CHECKARRVALID(ent);
- - ]
137 : 115500 : totlen += ARRNELEMS(ent);
138 : : }
139 : :
8120 bruce@momjian.us 140 : 57432 : res = new_intArrayType(totlen);
141 [ - + ]: 57432 : ptr = ARRPTR(res);
142 : :
7881 teodor@sigaev.ru 143 [ + + ]: 172932 : for (i = 0; i < entryvec->n; i++)
144 : : {
7279 bruce@momjian.us 145 : 115500 : ArrayType *ent = GETENTRY(entryvec, i);
146 : : int nel;
147 : :
7282 tgl@sss.pgh.pa.us 148 : 115500 : nel = ARRNELEMS(ent);
4872 peter_e@gmx.net 149 [ - + ]: 115500 : memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
7282 tgl@sss.pgh.pa.us 150 : 115500 : ptr += nel;
151 : : }
152 : :
8120 bruce@momjian.us 153 [ - + ]: 57432 : QSORT(res, 1);
154 : 57432 : res = _int_unique(res);
155 : 57432 : *size = VARSIZE(res);
8174 156 : 57432 : PG_RETURN_POINTER(res);
157 : : }
158 : :
159 : : /*
160 : : ** GiST Compress and Decompress methods
161 : : */
162 : : Datum
163 : 30093 : g_int_compress(PG_FUNCTION_ARGS)
164 : : {
165 : 30093 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
166 : : GISTENTRY *retval;
167 : : ArrayType *r;
2037 akorotkov@postgresql 168 [ + - ]: 30093 : 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 : :
8174 bruce@momjian.us 177 [ + + ]: 30093 : if (entry->leafkey)
178 : : {
5405 tgl@sss.pgh.pa.us 179 : 20272 : r = DatumGetArrayTypePCopy(entry->key);
7282 180 [ - + - - : 20272 : CHECKARRVALID(r);
- - ]
8174 bruce@momjian.us 181 [ - + ]: 20272 : PREPAREARR(r);
182 : :
2037 akorotkov@postgresql 183 [ + + ]: 20272 : if (ARRNELEMS(r) >= 2 * num_ranges)
865 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 : :
8174 bruce@momjian.us 189 : 20271 : retval = palloc(sizeof(GISTENTRY));
190 : 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 : :
5405 tgl@sss.pgh.pa.us 201 : 9821 : r = DatumGetArrayTypeP(entry->key);
7282 202 [ - + - - : 9821 : CHECKARRVALID(r);
- - ]
5405 203 [ - + ]: 9821 : if (ARRISEMPTY(r))
204 : : {
8174 bruce@momjian.us 205 [ # # ]:UBC 0 : if (r != (ArrayType *) DatumGetPointer(entry->key))
206 : 0 : pfree(r);
207 : 0 : PG_RETURN_POINTER(entry);
208 : : }
209 : :
2037 akorotkov@postgresql 210 [ + + ]:CBC 9821 : if ((len = ARRNELEMS(r)) >= 2 * num_ranges)
211 : : { /* compress */
8174 bruce@momjian.us 212 [ + - ]: 1442 : if (r == (ArrayType *) DatumGetPointer(entry->key))
5405 tgl@sss.pgh.pa.us 213 : 1442 : r = DatumGetArrayTypePCopy(entry->key);
8174 bruce@momjian.us 214 : 1442 : r = resize_intArrayType(r, 2 * (len));
215 : :
216 [ - + ]: 1442 : 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 : : */
2037 akorotkov@postgresql 223 : 1442 : 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 : : */
2530 rhodiumtoad@postgres 229 [ + - + + ]: 62861 : for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
230 : : {
2350 tgl@sss.pgh.pa.us 231 : 61419 : int r_end = dr[i];
232 : 61419 : int r_start = r_end;
233 : :
234 [ + - + + : 715155 : while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
+ + ]
2530 rhodiumtoad@postgres 235 : 653736 : --r_start, --i, --lenr;
2350 tgl@sss.pgh.pa.us 236 : 61419 : dr[2 * j] = r_start;
237 : 61419 : dr[2 * j + 1] = r_end;
238 : : }
239 : : /* just copy the rest, if any, as trivial ranges */
2530 rhodiumtoad@postgres 240 [ + + ]: 285775 : for (; i >= 0; i--, j--)
2350 tgl@sss.pgh.pa.us 241 : 284333 : dr[2 * j] = dr[2 * j + 1] = dr[i];
242 : :
2530 rhodiumtoad@postgres 243 [ + - ]: 1442 : if (++j)
244 : : {
245 : : /*
246 : : * shunt everything down to start at the right place
247 : : */
993 peter@eisentraut.org 248 : 1442 : 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 : : */
2350 tgl@sss.pgh.pa.us 254 : 1442 : len = 2 * (len - j);
8174 bruce@momjian.us 255 : 1442 : cand = 1;
2037 akorotkov@postgresql 256 [ - + ]: 1442 : while (len > num_ranges * 2)
257 : : {
2530 rhodiumtoad@postgres 258 :UBC 0 : min = PG_INT64_MAX;
8174 bruce@momjian.us 259 [ # # ]: 0 : for (i = 2; i < len; i += 2)
2350 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]);
8174 bruce@momjian.us 263 : 0 : cand = i;
264 : : }
993 peter@eisentraut.org 265 : 0 : memmove(&dr[cand - 1], &dr[cand + 1], (len - cand - 1) * sizeof(int32));
8174 bruce@momjian.us 266 : 0 : len -= 2;
267 : : }
268 : :
269 : : /*
270 : : * check sparseness of result
271 : : */
2530 rhodiumtoad@postgres 272 :CBC 1442 : lenr = internal_size(dr, len);
273 [ + - - + ]: 1442 : if (lenr < 0 || lenr > MAXNUMELTS)
2530 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 : :
8174 bruce@momjian.us 278 :CBC 1442 : r = resize_intArrayType(r, len);
279 : 1442 : retval = palloc(sizeof(GISTENTRY));
280 : 1442 : gistentryinit(*retval, PointerGetDatum(r),
281 : : entry->rel, entry->page, entry->offset, false);
282 : 1442 : PG_RETURN_POINTER(retval);
283 : : }
284 : : else
285 : 8379 : PG_RETURN_POINTER(entry);
286 : : }
287 : :
288 : : Datum
289 : 652764 : g_int_decompress(PG_FUNCTION_ARGS)
290 : : {
291 : 652764 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
292 : : GISTENTRY *retval;
293 : : ArrayType *r;
2037 akorotkov@postgresql 294 [ + - ]: 652764 : 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 : :
5405 tgl@sss.pgh.pa.us 302 : 652764 : in = DatumGetArrayTypeP(entry->key);
303 : :
7282 304 [ - + - - : 652764 : CHECKARRVALID(in);
- - ]
5405 305 [ + + ]: 652764 : if (ARRISEMPTY(in))
306 : : {
6556 bruce@momjian.us 307 [ + - ]: 344 : if (in != (ArrayType *) DatumGetPointer(entry->key))
308 : : {
6779 tgl@sss.pgh.pa.us 309 : 344 : retval = palloc(sizeof(GISTENTRY));
310 : 344 : gistentryinit(*retval, PointerGetDatum(in),
311 : : entry->rel, entry->page, entry->offset, false);
312 : 344 : PG_RETURN_POINTER(retval);
313 : : }
314 : :
8174 bruce@momjian.us 315 :UBC 0 : PG_RETURN_POINTER(entry);
316 : : }
317 : :
8174 bruce@momjian.us 318 :CBC 652420 : lenin = ARRNELEMS(in);
319 : :
2037 akorotkov@postgresql 320 [ + + ]: 652420 : if (lenin < 2 * num_ranges)
321 : : { /* not compressed value */
8174 bruce@momjian.us 322 [ + + ]: 626035 : if (in != (ArrayType *) DatumGetPointer(entry->key))
323 : : {
324 : 271014 : retval = palloc(sizeof(GISTENTRY));
325 : 271014 : gistentryinit(*retval, PointerGetDatum(in),
326 : : entry->rel, entry->page, entry->offset, false);
327 : :
328 : 271014 : PG_RETURN_POINTER(retval);
329 : : }
330 : 355021 : PG_RETURN_POINTER(entry);
331 : : }
332 : :
333 [ - + ]: 26385 : din = ARRPTR(in);
334 : 26385 : lenr = internal_size(din, lenin);
2530 rhodiumtoad@postgres 335 [ + - - + ]: 26385 : if (lenr < 0 || lenr > MAXNUMELTS)
2530 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 : :
8174 bruce@momjian.us 340 :CBC 26385 : r = new_intArrayType(lenr);
341 [ - + ]: 26385 : dr = ARRPTR(r);
342 : :
343 [ + + ]: 6382045 : for (i = 0; i < lenin; i += 2)
344 : : {
345 : : /* use int64 for j in case din[i + 1] is INT_MAX */
659 tgl@sss.pgh.pa.us 346 [ + + ]: 25755613 : for (int64 j = din[i]; j <= din[i + 1]; j++)
8174 bruce@momjian.us 347 [ + + + - ]: 19399953 : if ((!i) || *(dr - 1) != j)
659 tgl@sss.pgh.pa.us 348 : 19399953 : *dr++ = (int) j;
349 : : }
350 : :
8174 bruce@momjian.us 351 [ + - ]: 26385 : if (in != (ArrayType *) DatumGetPointer(entry->key))
352 : 26385 : pfree(in);
353 : 26385 : retval = palloc(sizeof(GISTENTRY));
354 : 26385 : gistentryinit(*retval, PointerGetDatum(r),
355 : : entry->rel, entry->page, entry->offset, false);
356 : :
357 : 26385 : PG_RETURN_POINTER(retval);
358 : : }
359 : :
360 : : /*
361 : : ** The GiST Penalty method for _intments
362 : : */
363 : : Datum
8120 364 : 312623 : g_int_penalty(PG_FUNCTION_ARGS)
365 : : {
366 : 312623 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
367 : 312623 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
368 : 312623 : float *result = (float *) PG_GETARG_POINTER(2);
369 : : ArrayType *ud;
370 : : float tmp1,
371 : : tmp2;
372 : :
8174 373 : 312623 : ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
8120 374 : 312623 : (ArrayType *) DatumGetPointer(newentry->key));
8174 375 : 312623 : rt__int_size(ud, &tmp1);
376 : 312623 : rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
377 : 312623 : *result = tmp1 - tmp2;
378 : 312623 : pfree(ud);
379 : :
8120 380 : 312623 : PG_RETURN_POINTER(result);
381 : : }
382 : :
383 : :
384 : :
385 : : Datum
8174 386 : 61789 : g_int_same(PG_FUNCTION_ARGS)
387 : : {
5405 tgl@sss.pgh.pa.us 388 : 61789 : ArrayType *a = PG_GETARG_ARRAYTYPE_P(0);
389 : 61789 : ArrayType *b = PG_GETARG_ARRAYTYPE_P(1);
8174 bruce@momjian.us 390 : 61789 : bool *result = (bool *) PG_GETARG_POINTER(2);
4872 peter_e@gmx.net 391 : 61789 : int32 n = ARRNELEMS(a);
392 : : int32 *da,
393 : : *db;
394 : :
7282 tgl@sss.pgh.pa.us 395 [ - + - - : 61789 : CHECKARRVALID(a);
- - ]
396 [ - + - - : 61789 : CHECKARRVALID(b);
- - ]
397 : :
8174 bruce@momjian.us 398 [ + + ]: 61789 : if (n != ARRNELEMS(b))
399 : : {
400 : 12181 : *result = false;
401 : 12181 : PG_RETURN_POINTER(result);
402 : : }
2994 peter_e@gmx.net 403 : 49608 : *result = true;
8174 bruce@momjian.us 404 [ - + ]: 49608 : da = ARRPTR(a);
405 [ - + ]: 49608 : db = ARRPTR(b);
406 [ + + ]: 14996689 : while (n--)
407 : : {
408 [ + + ]: 14947791 : if (*da++ != *db++)
409 : : {
2994 peter_e@gmx.net 410 : 710 : *result = false;
8174 bruce@momjian.us 411 : 710 : break;
412 : : }
413 : : }
414 : :
415 : 49608 : 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 : 63001 : comparecost(const void *a, const void *b)
430 : : {
5160 peter_e@gmx.net 431 [ + + ]: 63001 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
8174 bruce@momjian.us 432 : 32901 : return 0;
433 : : else
5160 peter_e@gmx.net 434 [ + + ]: 30100 : 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
8120 bruce@momjian.us 442 : 649 : g_int_picksplit(PG_FUNCTION_ARGS)
443 : : {
7729 444 : 649 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
8174 445 : 649 : 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 : 649 : OffsetNumber seed_1 = 0,
467 : 649 : 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 : :
7881 teodor@sigaev.ru 477 : 649 : maxoff = entryvec->n - 2;
8174 bruce@momjian.us 478 : 649 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
479 : 649 : v->spl_left = (OffsetNumber *) palloc(nbytes);
480 : 649 : v->spl_right = (OffsetNumber *) palloc(nbytes);
481 : :
482 : 649 : firsttime = true;
483 : 649 : waste = 0.0;
484 [ + + ]: 32846 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
485 : : {
7729 486 : 32197 : datum_alpha = GETENTRY(entryvec, i);
8174 487 [ + + ]: 1799713 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
488 : : {
7729 489 : 1767516 : datum_beta = GETENTRY(entryvec, j);
490 : :
491 : : /* compute the wasted space by unioning these guys */
492 : : /* size_waste = size_union - size_inter; */
8174 493 : 1767516 : union_d = inner_int_union(datum_alpha, datum_beta);
494 : 1767516 : rt__int_size(union_d, &size_union);
495 : 1767516 : inter_d = inner_int_inter(datum_alpha, datum_beta);
496 : 1767516 : rt__int_size(inter_d, &size_inter);
497 : 1767516 : size_waste = size_union - size_inter;
498 : :
499 : 1767516 : pfree(union_d);
3906 kgrittn@postgresql.o 500 : 1767516 : pfree(inter_d);
501 : :
502 : : /*
503 : : * are these a more promising split that what we've already seen?
504 : : */
505 : :
8174 bruce@momjian.us 506 [ + + + + ]: 1767516 : if (size_waste > waste || firsttime)
507 : : {
508 : 3147 : waste = size_waste;
509 : 3147 : seed_1 = i;
510 : 3147 : seed_2 = j;
511 : 3147 : firsttime = false;
512 : : }
513 : : }
514 : : }
515 : :
516 : 649 : left = v->spl_left;
517 : 649 : v->spl_nleft = 0;
518 : 649 : right = v->spl_right;
519 : 649 : v->spl_nright = 0;
520 [ + - - + ]: 649 : if (seed_1 == 0 || seed_2 == 0)
521 : : {
8174 bruce@momjian.us 522 :UBC 0 : seed_1 = 1;
523 : 0 : seed_2 = 2;
524 : : }
525 : :
7729 bruce@momjian.us 526 :CBC 649 : datum_alpha = GETENTRY(entryvec, seed_1);
8174 527 : 649 : datum_l = copy_intArrayType(datum_alpha);
528 : 649 : rt__int_size(datum_l, &size_l);
7729 529 : 649 : datum_beta = GETENTRY(entryvec, seed_2);
8174 530 : 649 : datum_r = copy_intArrayType(datum_beta);
531 : 649 : rt__int_size(datum_r, &size_r);
532 : :
533 : 649 : maxoff = OffsetNumberNext(maxoff);
534 : :
535 : : /*
536 : : * sort entries
537 : : */
538 : 649 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
539 [ + + ]: 34144 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
540 : : {
541 : 33495 : costvector[i - 1].pos = i;
7729 542 : 33495 : datum_alpha = GETENTRY(entryvec, i);
8174 543 : 33495 : union_d = inner_int_union(datum_l, datum_alpha);
544 : 33495 : rt__int_size(union_d, &size_alpha);
545 : 33495 : pfree(union_d);
546 : 33495 : union_d = inner_int_union(datum_r, datum_alpha);
547 : 33495 : rt__int_size(union_d, &size_beta);
548 : 33495 : pfree(union_d);
1115 peter@eisentraut.org 549 : 33495 : costvector[i - 1].cost = fabsf((size_alpha - size_l) - (size_beta - size_r));
550 : : }
993 551 : 649 : 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 : :
8174 bruce@momjian.us 566 [ + + ]: 34144 : for (j = 0; j < maxoff; j++)
567 : : {
568 : 33495 : 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 [ + + ]: 33495 : if (i == seed_1)
577 : : {
578 : 649 : *left++ = i;
579 : 649 : v->spl_nleft++;
580 : 649 : continue;
581 : : }
582 [ + + ]: 32846 : else if (i == seed_2)
583 : : {
584 : 649 : *right++ = i;
585 : 649 : v->spl_nright++;
586 : 649 : continue;
587 : : }
588 : :
589 : : /* okay, which page needs least enlargement? */
7729 590 : 32197 : datum_alpha = GETENTRY(entryvec, i);
8174 591 : 32197 : union_dl = inner_int_union(datum_l, datum_alpha);
592 : 32197 : union_dr = inner_int_union(datum_r, datum_alpha);
593 : 32197 : rt__int_size(union_dl, &size_alpha);
594 : 32197 : rt__int_size(union_dr, &size_beta);
595 : :
596 : : /* pick which page to add it to */
597 [ + + ]: 32197 : if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
598 : : {
3906 kgrittn@postgresql.o 599 : 15408 : pfree(datum_l);
600 : 15408 : pfree(union_dr);
8174 bruce@momjian.us 601 : 15408 : datum_l = union_dl;
602 : 15408 : size_l = size_alpha;
603 : 15408 : *left++ = i;
604 : 15408 : v->spl_nleft++;
605 : : }
606 : : else
607 : : {
3906 kgrittn@postgresql.o 608 : 16789 : pfree(datum_r);
609 : 16789 : pfree(union_dl);
8174 bruce@momjian.us 610 : 16789 : datum_r = union_dr;
611 : 16789 : size_r = size_beta;
612 : 16789 : *right++ = i;
613 : 16789 : v->spl_nright++;
614 : : }
615 : : }
616 : 649 : pfree(costvector);
617 : 649 : *right = *left = FirstOffsetNumber;
618 : :
619 : 649 : v->spl_ldatum = PointerGetDatum(datum_l);
620 : 649 : v->spl_rdatum = PointerGetDatum(datum_r);
621 : :
622 : 649 : PG_RETURN_POINTER(v);
623 : : }
624 : :
625 : : Datum
2037 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 : : }
|
