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