00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #include "postgres.h"
00029
00030 #include <float.h>
00031 #include <math.h>
00032
00033 #include "access/gist.h"
00034 #include "access/skey.h"
00035 #include "utils/builtins.h"
00036 #include "lib/stringinfo.h"
00037 #include "utils/array.h"
00038 #include "utils/builtins.h"
00039
00040 #define V1P 0.001
00041 #define V10P 0.01
00042 #define V25P 0.025
00043 #define V50P 0.05
00044
00045 #include "tsdata.h"
00046
00047 PG_FUNCTION_INFO_V1( sax_union);
00048 PG_FUNCTION_INFO_V1( sax_distance);
00049 SAX * i_sax_union(SAX * r1, SAX * r2);
00050 Datum sax_union( PG_FUNCTION_ARGS);
00051 Datum sax_distance( PG_FUNCTION_ARGS);
00052
00056 PG_FUNCTION_INFO_V1( sax_nar_1p);
00057 Datum sax_nar_1p( PG_FUNCTION_ARGS);
00058
00062 PG_FUNCTION_INFO_V1( sax_nar_10p);
00063 Datum sax_nar_10p( PG_FUNCTION_ARGS);
00064
00068 PG_FUNCTION_INFO_V1( sax_nar_25p);
00069 Datum sax_nar_25p( PG_FUNCTION_ARGS);
00070
00074 PG_FUNCTION_INFO_V1( sax_nar_50p);
00075 Datum sax_nar_50p( PG_FUNCTION_ARGS);
00076
00080 PG_FUNCTION_INFO_V1( sax_1p_away);
00081 Datum sax_1p_away( PG_FUNCTION_ARGS);
00082
00086 PG_FUNCTION_INFO_V1( sax_10p_away);
00087 Datum sax_10p_away( PG_FUNCTION_ARGS);
00088
00092 PG_FUNCTION_INFO_V1( sax_25p_away);
00093 Datum sax_25p_away( PG_FUNCTION_ARGS);
00094
00098 PG_FUNCTION_INFO_V1( sax_50p_away);
00099 Datum sax_50p_away( PG_FUNCTION_ARGS);
00100
00101
00102 PG_FUNCTION_INFO_V1(gsax_compress);
00103 Datum gsax_compress(PG_FUNCTION_ARGS);
00104
00105 PG_FUNCTION_INFO_V1(gsax_decompress);
00106 Datum gsax_decompress(PG_FUNCTION_ARGS);
00107
00108 PG_FUNCTION_INFO_V1(gsax_same);
00109 Datum gsax_same(PG_FUNCTION_ARGS);
00110
00111 PG_FUNCTION_INFO_V1(gsax_union);
00112 Datum gsax_union(PG_FUNCTION_ARGS);
00113
00114 PG_FUNCTION_INFO_V1(gsax_penalty);
00115 Datum gsax_penalty(PG_FUNCTION_ARGS);
00116
00117 PG_FUNCTION_INFO_V1(gsax_picksplit);
00118 Datum gsax_picksplit(PG_FUNCTION_ARGS);
00119
00120 PG_FUNCTION_INFO_V1(gsax_proximity);
00121 Datum gsax_proximity(PG_FUNCTION_ARGS);
00122
00123
00124 bool sax_closer_then(SAX *a, SAX *b, float threshold);
00125
00126 bool gsax_leaf_consistent(SAX * key, SAX * query, StrategyNumber strategy);
00127
00128 bool gsax_internal_consistent(SAX * key, SAX * query, StrategyNumber strategy);
00129
00130 float i_sax_distance(SAX * r1, SAX * r2);
00131
00136 unsigned char unify_cardinality_up(SAX_ELEMENT* a, SAX_ELEMENT* b,
00137 unsigned char *al, unsigned char *au, unsigned char *bl,
00138 unsigned char *bu) {
00139 unsigned char c;
00140
00141 #ifdef SAX_DEBUG
00142 fprintf(stderr, "\nunify_cardinality_up\ncardinality, %d %d\n", a->cardinality,b->cardinality);
00143 fprintf(stderr, "lower, %d %d\n", a->lower,b->lower);
00144 fprintf(stderr, "upper, %d %d\n", a->upper,b->upper);
00145 #endif
00146
00147 if (b->cardinality == a->cardinality) {
00148 *al = a->lower;
00149 *au = a->upper;
00150 *bu = b->upper;
00151 *bl = b->lower;
00152 c = b->cardinality;
00153 } else if (b->cardinality > a->cardinality) {
00154 *bl = b->lower;
00155 *bu = b->upper;
00156 *al = promoteLetter(a->lower, *bl, a->cardinality, b->cardinality);
00157 *au = promoteLetter(a->upper, *bu, a->cardinality, b->cardinality);
00158 c = b->cardinality;
00159 } else {
00160 *al = a->lower;
00161 *au = a->upper;
00162 *bl = promoteLetter(b->lower, *al, b->cardinality, a->cardinality);
00163 *bu = promoteLetter(b->upper, *au, b->cardinality, a->cardinality);
00164 c = a->cardinality;
00165 }
00166 #ifdef SAX_DEBUG
00167 fprintf(stderr, "c='%d';al='%d';au='%d';bl='%d';bu='%d'", c,*al,*au,*bl,*bu);
00168 #endif
00169
00170
00171 return c;
00172 }
00173
00174 unsigned char unify_cardinality_down(SAX_ELEMENT* a, SAX_ELEMENT* b,
00175 unsigned char *al, unsigned char *au, unsigned char *bl,
00176 unsigned char *bu) {
00177 unsigned char c;
00178
00179 #ifdef SAX_DEBUG
00180 fprintf(stderr, "\ncardinality, %d %d\n", a->cardinality,b->cardinality);
00181 fprintf(stderr, "lower, %d %d\n", a->lower,b->lower);
00182 fprintf(stderr, "upper, %d %d\n", a->upper,b->upper);
00183 #endif
00184
00185 if (b->cardinality == a->cardinality) {
00186 *al = a->lower;
00187 *au = a->upper;
00188 *bu = b->upper;
00189 *bl = b->lower;
00190 c = b->cardinality;
00191 } else if (b->cardinality < a->cardinality) {
00192 *bl = b->lower;
00193 *bu = b->upper;
00194 *al = downgradeLetter(a->lower, a->cardinality, b->cardinality);
00195 *au = downgradeLetter(a->upper, a->cardinality, b->cardinality);
00196 c = b->cardinality;
00197 } else {
00198 *al = a->lower;
00199 *au = a->upper;
00200 *bl = downgradeLetter(b->lower, b->cardinality, a->cardinality);
00201 *bu = downgradeLetter(b->upper, b->cardinality, a->cardinality);
00202 c = a->cardinality;
00203 }
00204 #ifdef SAX_DEBUG
00205 fprintf(stderr, "c='%d';al='%d';au='%d';bl='%d';bu='%d'", c,*al,*au,*bl,*bu);
00206 #endif
00207
00208
00209 return c;
00210 }
00211
00212 bool sax_uoverlap(SAX *a, SAX *b) {
00213 int i;
00214 unsigned char al, bl, au, bu, c;
00215 int length = (a->length >= b->length) ? b->length : a->length;
00216
00217
00218 for (i = 0; i < length; i++) {
00219
00220 #ifdef SAX_DEBUG
00221 fprintf(stderr, "\nsax_uoverlap\ncardinality, %d %d\n", a->data[i].cardinality,b->data[i].cardinality);
00222 fprintf(stderr, "lower, %d %d\n", a->data[i].lower,b->data[i].lower);
00223 fprintf(stderr, "upper, %d %d\n", a->data[i].upper,b->data[i].upper);
00224 fprintf(stderr, "isNull, %d %d\n", sax_isNull(&(a->data[i])),sax_isNull(&(b->data[i])));
00225 #endif
00226 if (NONE_IS_NULL(a, b, i)) {
00227 c = unify_cardinality_up(&(a->data[i]), &(b->data[i]), &al, &au,
00228 &bl, &bu);
00229
00230 if (bl > al || al > bu)
00231 return false;
00232 }
00233 }
00234 return true;
00235 }
00236
00237 bool sax_loverlap(SAX *a, SAX *b) {
00238 int i;
00239 unsigned char al, bl, au, bu, c;
00240 int length = (a->length >= b->length) ? b->length : a->length;
00241 for (i = 0; i < length; i++) {
00242 if (NONE_IS_NULL(a, b, i)) {
00243 c = unify_cardinality_up(&(a->data[i]), &(b->data[i]), &al, &au,
00244 &bl, &bu);
00245 if (bu < au || au < bl)
00246 return false;
00247 }
00248 }
00249 return true;
00250
00251 }
00252
00253 bool sax_contained(SAX *a, SAX *b) {
00254 return (sax_uoverlap(a, b) && sax_loverlap(a, b));
00255 }
00256
00257 bool sax_contains(SAX *a, SAX *b) {
00258 return (sax_contained(b, a));
00259 }
00260
00261 bool sax_intersect(SAX *a, SAX *b) {
00262 return !(sax_greater(a, b) || sax_less(a, b));
00263 }
00264
00265 bool sax_greater(SAX *a, SAX *b) {
00266 int i;
00267 unsigned char al, bl, au, bu, c;
00268 int length = (a->length >= b->length) ? b->length : a->length;
00269 for (i = 0; i < length; i++) {
00270 if (NONE_IS_NULL(a, b, i)) {
00271 c = unify_cardinality_up(&(a->data[i]), &(b->data[i]), &al, &au,
00272 &bl, &bu);
00273 if (bu >= al)
00274 return false;
00275 }
00276 }
00277 return true;
00278
00279 }
00280
00281 bool sax_less(SAX *a, SAX *b) {
00282 int i;
00283 unsigned char al, bl, au, bu, c;
00284 int length = (a->length >= b->length) ? b->length : a->length;
00285 for (i = 0; i < length; i++) {
00286 if (NONE_IS_NULL(a, b, i)) {
00287 c = unify_cardinality_up(&(a->data[i]), &(b->data[i]), &al, &au,
00288 &bl, &bu);
00289 if (bl <= au)
00290 return false;
00291 }
00292 }
00293 return true;
00294
00295 }
00296
00300 bool sax_closer_then(SAX *a, SAX *b, float threshold) {
00301 int i;
00302 float dist;
00303 int length = (a->length >= b->length) ? b->length : a->length;
00304 dist = i_sax_distance(a, b);
00305
00306 return (dist / (float) length) < threshold * MAX_DIST;
00307
00308 }
00309
00310 bool sax_same(SAX *a, SAX *b) {
00311 int i;
00312 unsigned char al, bl, au, bu, c;
00313 int length = (a->length >= b->length) ? b->length : a->length;
00314 for (i = 0; i < length; i++) {
00315 if (NONE_IS_NULL(a, b, i)) {
00316 c = unify_cardinality_up(&(a->data[i]), &(b->data[i]), &al, &au,
00317 &bl, &bu);
00318 if (bl != al)
00319 return false;
00320 if (bu != au)
00321 return false;
00322 }
00323 }
00324 return true;
00325
00326 }
00327
00328 bool sax_different(SAX *a, SAX *b) {
00329 return (!sax_same(a, b));
00330 }
00331
00332 float i_sax_elem_distance(SAX_ELEMENT *e1, SAX_ELEMENT *e2) {
00333 unsigned char al, bl, au, bu, c;
00334 float result, d;
00335 d = 0.0;
00336
00337 if (NEITHER_ELEMENT_NULL(e1, e2)) {
00338 c = unify_cardinality_up(e1, e2, &al, &au, &bl, &bu);
00339 if (al > bu) {
00340 d = dist(al, bu, c);
00341 } else if (au < bl) {
00342 d = dist(au, bl, c);
00343 }
00344 }
00345 result = d * d;
00346 return result;
00347 }
00348
00349 float i_sax_distance(SAX * r1, SAX * r2) {
00350 int i;
00351 unsigned char al, bl, au, bu, c;
00352 SAX_ELEMENT *e1, *e2;
00353 float result, d;
00354 result = 0.0;
00355 int length = (r1->length >= r2->length) ? r2->length : r1->length;
00356 for (i = 0; i < length; i++) {
00357 e1 = &(r1->data[i]);
00358 e2 = &(r2->data[i]);
00359 result += i_sax_elem_distance(e1, e2);
00360 #ifdef SAX_DEBUG
00361 fprintf(stderr, "\ni_sax_distance, %d %f\n", i,result);
00362 #endif
00363
00364 }
00365
00366 return result;
00367 }
00368
00369 float i_sax_penalty(SAX * r1, SAX * r2) {
00370 int i;
00371 unsigned char al, bl, au, bu, c;
00372 SAX_ELEMENT *e1, *e2;
00373 float result, d,f;
00374 result = 0.0;
00375 c=0;
00376 int length = (r1->length >= r2->length) ? r2->length : r1->length;
00377 for (i = 0; i < length; i++) {
00378 e1 = &(r1->data[i]);
00379 e2 = &(r2->data[i]);
00380 if (NEITHER_ELEMENT_NULL(e1, e2)) {
00381 c = unify_cardinality_down(e1, e2, &al, &au, &bl, &bu);
00382 if(c>0){
00383 f=((1<<(9-c))-1);
00384 d=f*((al+au)/2.0-(bl+bu)/2.0);
00385 }
00386 }
00387 result += d * d;
00388 #ifdef SAX_DEBUG
00389 fprintf(stderr, "\ni_sax_penalty, %d %f\n", i,result);
00390 #endif
00391
00392 }
00393 return result;
00394 }
00395
00396
00397 Datum sax_distance( PG_FUNCTION_ARGS) {
00398 SAX *sax1 = PG_GETARG_SAX(0);
00399 SAX *sax2 = PG_GETARG_SAX(1);
00400 float result;
00401 result = i_sax_distance(sax1, sax2);
00402 #ifdef SAX_DEBUG
00403 fprintf(stderr, "\nsax_distance, %f\n", result);
00404 #endif
00405 PG_FREE_IF_COPY(sax1, 0);
00406 PG_FREE_IF_COPY(sax2, 1);
00407 PG_RETURN_FLOAT4(result);
00408
00409 }
00410
00414 Datum sax_nar_1p( PG_FUNCTION_ARGS) {
00415 SAX *sax1 = PG_GETARG_SAX(0);
00416 SAX *sax2 = PG_GETARG_SAX(1);
00417 bool result;
00418 result = sax_closer_then(sax1, sax2, V1P);
00419 PG_FREE_IF_COPY(sax1, 0);
00420 PG_FREE_IF_COPY(sax2, 1);
00421 PG_RETURN_BOOL(result);
00422 }
00423
00427 Datum sax_nar_10p( PG_FUNCTION_ARGS) {
00428 SAX *sax1 = PG_GETARG_SAX(0);
00429 SAX *sax2 = PG_GETARG_SAX(1);
00430 bool result;
00431 result = sax_closer_then(sax1, sax2, V10P);
00432 PG_FREE_IF_COPY(sax1, 0);
00433 PG_FREE_IF_COPY(sax2, 1);
00434 PG_RETURN_BOOL(result);
00435 }
00436
00440 Datum sax_nar_25p( PG_FUNCTION_ARGS) {
00441 SAX *sax1 = PG_GETARG_SAX(0);
00442 SAX *sax2 = PG_GETARG_SAX(1);
00443 bool result;
00444 result = sax_closer_then(sax1, sax2, V25P);
00445 PG_FREE_IF_COPY(sax1, 0);
00446 PG_FREE_IF_COPY(sax2, 1);
00447 PG_RETURN_BOOL(result);
00448 }
00449
00453 Datum sax_nar_50p( PG_FUNCTION_ARGS) {
00454 SAX *sax1 = PG_GETARG_SAX(0);
00455 SAX *sax2 = PG_GETARG_SAX(1);
00456 bool result;
00457 result = sax_closer_then(sax1, sax2, V50P);
00458 PG_FREE_IF_COPY(sax1, 0);
00459 PG_FREE_IF_COPY(sax2, 1);
00460 PG_RETURN_BOOL(result);
00461 }
00462
00466 Datum sax_1p_away( PG_FUNCTION_ARGS) {
00467 SAX *sax1 = PG_GETARG_SAX(0);
00468 SAX *sax2 = PG_GETARG_SAX(1);
00469 bool result;
00470 result = !sax_closer_then(sax1, sax2, V1P);
00471 PG_FREE_IF_COPY(sax1, 0);
00472 PG_FREE_IF_COPY(sax2, 1);
00473 PG_RETURN_BOOL(result);
00474 }
00475
00479 Datum sax_10p_away( PG_FUNCTION_ARGS) {
00480 SAX *sax1 = PG_GETARG_SAX(0);
00481 SAX *sax2 = PG_GETARG_SAX(1);
00482 bool result;
00483 result = !sax_closer_then(sax1, sax2, V10P);
00484 PG_FREE_IF_COPY(sax1, 0);
00485 PG_FREE_IF_COPY(sax2, 1);
00486 PG_RETURN_BOOL(result);
00487 }
00488
00492 Datum sax_25p_away( PG_FUNCTION_ARGS) {
00493 SAX *sax1 = PG_GETARG_SAX(0);
00494 SAX *sax2 = PG_GETARG_SAX(1);
00495 bool result;
00496 result = !sax_closer_then(sax1, sax2, V25P);
00497 PG_FREE_IF_COPY(sax1, 0);
00498 PG_FREE_IF_COPY(sax2, 1);
00499 PG_RETURN_BOOL(result);
00500 }
00501
00505 Datum sax_50p_away( PG_FUNCTION_ARGS) {
00506 SAX *sax1 = PG_GETARG_SAX(0);
00507 SAX *sax2 = PG_GETARG_SAX(1);
00508 bool result;
00509 result = !sax_closer_then(sax1, sax2, V50P);
00510 PG_FREE_IF_COPY(sax1, 0);
00511 PG_FREE_IF_COPY(sax2, 1);
00512 PG_RETURN_BOOL(result);
00513 }
00514
00515 int32 sax_cmp(SAX * a, SAX * b) {
00516 if (sax_less(a, b) || sax_loverlap(a, b))
00517 return -1;
00518 if (sax_greater(a, b) || sax_uoverlap(a, b))
00519 return 1;
00520 return 0;
00521 }
00522
00523 SAX_ELEMENT*
00524 sax_element_intersect(SAX_ELEMENT* a, SAX_ELEMENT* b, SAX_ELEMENT* u) {
00525 unsigned char al, bl, au, bu, c;
00526 c = unify_cardinality_down(a, b, &al, &au, &bl, &bu);
00527 if (al > bu || bl > au) {
00528 u->lower = 1;
00529 u->upper = 0;
00530 } else {
00531 if (al < bl) {
00532 u->lower = bl;
00533 } else {
00534 u->lower = al;
00535 }
00536 if (au < bu) {
00537 u->upper = au;
00538 } else {
00539 u->upper = bu;
00540 }
00541 }
00542 u->cardinality = c;
00543 return u;
00544 }
00545
00546 float sax_element_size(SAX_ELEMENT* a) {
00547 float size, cd;
00548 if (!sax_isNull(a)) {
00549 size = dist(a->upper, a->lower, a->cardinality);
00550 } else {
00551 size = 0;
00552 }
00553
00554 #ifdef SAX_DEBUG
00555 fprintf(stderr, "\nsax_element_size\ncardinality, %d\n", a->cardinality);
00556 fprintf(stderr, "bounds, %d %d\n", a->lower,a->upper);
00557 fprintf(stderr, "size, %f \n", size);
00558 #endif
00559
00560
00561 return size;
00562 }
00563 void sax_element_union(SAX_ELEMENT* a, SAX_ELEMENT* b, SAX_ELEMENT* u) {
00564 unsigned char al, bl, au, bu, c;
00565 if (NEITHER_ELEMENT_NULL(a, b)) {
00566 c = unify_cardinality_down(a, b, &al, &au, &bl, &bu);
00567 u->cardinality = c;
00568 u->lower = (al > bl) ? bl : al;
00569 u->upper = (au > bu) ? au : bu;
00570 } else if (!sax_isNull(a)) {
00571 u->cardinality = a->cardinality;
00572 u->lower = a->lower;
00573 u->upper = a->upper;
00574 } else if (!sax_isNull(b)) {
00575 u->cardinality = b->cardinality;
00576 u->lower = b->lower;
00577 u->upper = b->upper;
00578 } else {
00579 u->cardinality = 1;
00580 u->lower = 1;
00581 u->upper = 0;
00582 }
00583
00584 }
00585
00589 SAX* i_sax_union(SAX * r1, SAX * r2) {
00590 SAX * retval;
00591 int i, size;
00592 unsigned char al, bl, au, bu, c;
00593 if (r1->length != r2->length) {
00594 ereport(ERROR, (errcode(ERRCODE_GROUPING_ERROR), errmsg(
00595 "sax union of different length"), errdetail(
00596 "Length of SAX string to union are not the same: %d and %d",
00597 r1->length, r2->length)));
00598
00599 }
00600 size = SIZE_OF_SAX(r1->length);
00601 retval = palloc0(size);
00602 SET_VARSIZE(retval, size);
00603 retval->length = r1->length;
00604 retval->points_per_letter = r1->points_per_letter;
00605 for (i = 0; i < r1->length; i++) {
00606 sax_element_union(&(r1->data[i]), &(r2->data[i]), &(retval->data[i]));
00607 }
00608 return retval;
00609
00610 }
00611
00612 Datum sax_union( PG_FUNCTION_ARGS) {
00613 SAX *sax1 = PG_GETARG_SAX(0);
00614 SAX *sax2 = PG_GETARG_SAX(1);
00615 SAX *result;
00616 result = i_sax_union(sax1, sax2);
00617 PG_FREE_IF_COPY(sax1, 0);
00618 PG_FREE_IF_COPY(sax2, 1);
00619 PG_RETURN_SAX(result);
00620
00621 }
00622
00623
00624
00625 Datum gsax_proximity(PG_FUNCTION_ARGS){
00626
00627 bool retval;
00628 int i;
00629 GISTENTRY *entry=(GISTENTRY *)PG_GETARG_POINTER(0);
00630 SAX * query=(SAX *)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
00631 StrategyNumber strategy=(StrategyNumber)PG_GETARG_UINT16(2);
00632
00633 SAX * key = (SAX *) DatumGetPointer(entry->key);
00634
00635 switch (strategy) {
00636 case 1:
00637 retval = (bool) sax_closer_then(key, query, V1P);
00638 break;
00639 case 2:
00640 retval = (bool) sax_closer_then(key, query, V10P);
00641 break;
00642 case 3:
00643 retval = (bool) sax_closer_then(key, query, V25P);
00644 break;
00645 case 4:
00646 retval = (bool) sax_closer_then(key, query, V50P);
00647 break;
00648 case 5:
00649 retval = (bool) !sax_closer_then(key, query, V1P);
00650 break;
00651 case 6:
00652 retval = (bool) !sax_closer_then(key, query, V10P);
00653 break;
00654 case 7:
00655 retval = (bool) !sax_closer_then(key, query, V25P);
00656 break;
00657 case 8:
00658 retval = (bool) !sax_closer_then(key, query, V50P);
00659 break;
00660 default:
00661 retval = FALSE;
00662 }
00663
00664 #ifdef GIST_DEBUG
00665 fprintf(stderr, "leaf_consistent, strategy=%d; retval=%d\n", strategy,retval);
00666 for(i=0;i<key->length;i++) {
00667 if ( i> 0 )
00668 fprintf(stderr,"; ");
00669
00670 if ( key->data[i].lower <= key->data[i].upper ) {
00671 fprintf(stderr, "%x", key->data[i].lower);
00672
00673 if ( key->data[i].lower != key->data[i].upper ) {
00674 fprintf(stderr, ":%x", key->data[i].upper);
00675 }
00676 fprintf(stderr, "|%x", key->data[i].cardinality);
00677 }
00678 else {
00679 fprintf(stderr, "NULL");
00680 }
00681 }
00682 fprintf(stderr, "\n");
00683
00684 fprintf(stderr, "==================================\n");
00685 for(i=0;i<query->length;i++) {
00686 if ( i> 0 )
00687 fprintf(stderr,"; ");
00688
00689 if ( query->data[i].lower <= query->data[i].upper ) {
00690 fprintf(stderr, "%x", query->data[i].lower);
00691
00692 if ( query->data[i].lower != query->data[i].upper ) {
00693 fprintf(stderr, ":%x", query->data[i].upper);
00694 }
00695 fprintf(stderr, "|%x", query->data[i].cardinality);
00696 }
00697 else {
00698 fprintf(stderr, "NULL");
00699 }
00700 }
00701 fprintf(stderr, "\n");
00702
00703 fprintf(stderr, "==================================\n");
00704 #endif
00705
00706 return (retval);
00707
00708 }
00709
00716 bool gsax_consistent(GISTENTRY *entry, SAX * query, StrategyNumber strategy) {
00717
00718
00719
00720
00721 #ifdef GIST_DEBUG
00722 fprintf(stderr, "gsax_consistent\n");
00723 #endif
00724
00725 if (GIST_LEAF(entry))
00726 return (gsax_leaf_consistent((SAX *) DatumGetPointer(entry->key),
00727 query, strategy));
00728 else
00729 return (gsax_internal_consistent((SAX *) DatumGetPointer(entry->key),
00730 query, strategy));
00731 }
00732
00733 void printSAX_ELM(SAX_ELEMENT elem) {
00734 if (elem.lower <= elem.upper) {
00735 fprintf(stderr, "%x", elem.lower);
00736
00737 if (elem.lower != elem.upper) {
00738 fprintf(stderr, ":%x", elem.upper);
00739 }
00740 fprintf(stderr, "|%x", elem.cardinality);
00741 } else {
00742 fprintf(stderr, "NULL");
00743 }
00744
00745 }
00746
00754 SAX* singular_sax(SAX* sax) {
00755 SAX* result;
00756 int size, i;
00757 size = SIZE_OF_SAX(sax->length);
00758 result = (SAX *) palloc0(size);
00759 SET_VARSIZE(result, size);
00760 result->length = sax->length;
00761 result->points_per_letter = sax->points_per_letter;
00762 for (i = 0; i < sax->length; i++) {
00763 result->data[i].lower = (sax->data[i].upper + sax->data[i].lower) / 2;
00764 result->data[i].upper = result->data[i].lower;
00765 result->data[i].cardinality = sax->data[i].cardinality;
00766 }
00767
00768 return result;
00769 }
00770
00774 void printSAX(SAX* sax) {
00775 int i, j;
00776 fprintf(stderr, "%d\t%d\t", sax->vl_len_, sax->length);
00777 for (i = 0; i < sax->length; i++) {
00778 if (i > 0)
00779 fprintf(stderr, "; ");
00780 SAX_ELEMENT elem = sax->data[i];
00781 printSAX_ELM(elem);
00782 }
00783 fprintf(stderr, "\n");
00784
00785 }
00786
00787 SAX* i_gsax_union_old(GistEntryVector *entryvec, int offset) {
00788 int numranges, len, d, k;
00789 SAX *out = (SAX *) NULL;
00790 SAX *tmp, *sax, *itmp;
00791 OffsetNumber i, j;
00792
00793 numranges = entryvec->n - 2;
00794 tmp = (SAX *) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
00795 #ifdef GIST_DEBUG
00796 fprintf(stderr, "Data to i_union, number=%d, length=%d\n",numranges,tmp->length);
00797 for (j = FirstOffsetNumber; j<= numranges; j=OffsetNumberNext(j))
00798 {
00799 fprintf(stderr, "%d\t",j);
00800 sax = (SAX *) DatumGetPointer(entryvec->vector[j].key);
00801 printSAX(sax);
00802 }
00803
00804 #endif
00805
00806 for (i = OffsetNumberNext(FirstOffsetNumber); i <= numranges; i
00807 = OffsetNumberNext(i)) {
00808 itmp = singular_sax((SAX *) DatumGetPointer(entryvec->vector[i].key));
00809 out = i_sax_union(tmp, itmp);
00810 pfree(itmp);
00811 tmp = out;
00812 }
00813
00814 for (i = 0; i < out->length; i++) {
00815 d = out->data[i].upper - out->data[i].lower;
00816 k = 0;
00817 while (d > 1) {
00818 d >>= 1;
00819 k++;
00820 }
00821 out->data[i].cardinality -= k;
00822 out->data[i].lower >>= k;
00823 out->data[i].upper >>= k;
00824 }
00825 #ifdef GIST_DEBUG
00826 fprintf(stderr, "==================================\n");
00827 fprintf(stderr, "%d\t%d\t",numranges+1,sax->length);
00828 for(i=0;i<out->length;i++) {
00829 if ( i> 0 )
00830 fprintf(stderr,"; ");
00831
00832 if ( out->data[i].lower <= out->data[i].upper ) {
00833 fprintf(stderr, "%x", out->data[i].lower);
00834
00835 if ( out->data[i].lower != out->data[i].upper ) {
00836 fprintf(stderr, ":%x", out->data[i].upper);
00837 }
00838 fprintf(stderr, "|%x", out->data[i].cardinality);
00839 }
00840 else {
00841 fprintf(stderr, "NULL");
00842 }
00843 }
00844 fprintf(stderr, "\n");
00845
00846 fprintf(stderr, "==================================\n");
00847 fprintf(stderr, "union-fin\n");
00848 #endif
00849 return (out);
00850
00851 }
00852
00853 SAX* singular_sax_union(SAX *out) {
00854 int i, len, d, k;
00855 unsigned char u, l;
00856
00857
00858
00859
00860
00861
00862 for (i = 0; i < out->length; i++) {
00863 d = out->data[i].upper - out->data[i].lower;
00864 k = 0;
00865 len = out->data[i].cardinality;
00866 u = out->data[i].upper;
00867 l = out->data[i].lower;
00868
00869
00870
00871 while (u != l) {
00872 u >>= 1;
00873 l >>= 1;
00874 len--;
00875 }
00876
00877
00878
00879
00880
00881
00882
00883 out->data[i].cardinality = len;
00884 out->data[i].lower = l;
00885 out->data[i].upper = u;
00886
00887
00888
00889 }
00890
00891
00892
00893
00894 return out;
00895 }
00896
00897 SAX* i_gsax_union(GistEntryVector *entryvec, int offset) {
00898 int numranges, len, d, k;
00899 SAX *out = (SAX *) NULL;
00900 SAX *tmp, *sax, *itmp;
00901 OffsetNumber i, j;
00902
00903 numranges = entryvec->n ;
00904 tmp = singular_sax((SAX *) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key));
00905 #ifdef GIST_DEBUG
00906 fprintf(stderr, "Data to i_gsax_union, number=%d, length=%d\n",numranges,tmp->length);
00907 for (j = (FirstOffsetNumber); j<= numranges; j=OffsetNumberNext(j))
00908 {
00909 fprintf(stderr, "%d\t",j);
00910 sax = (SAX *) DatumGetPointer(entryvec->vector[j].key);
00911 printSAX(sax);
00912 }
00913
00914 #endif
00915
00916 for (i = OffsetNumberNext(FirstOffsetNumber); i < numranges; i
00917 = OffsetNumberNext(i)) {
00918 itmp = singular_sax((SAX *) DatumGetPointer(entryvec->vector[i].key));
00919 out = i_sax_union(tmp, itmp);
00920
00921
00922
00923
00924
00925 pfree(itmp);
00926 pfree(tmp);
00927 tmp = out;
00928 }
00929 #ifdef GIST_DEBUG
00930 fprintf(stderr, "==================================\n");
00931 fprintf(stderr, "\ti_gsax_union, i=%d, length=%d\n",i,tmp->length);
00932 printSAX(out);
00933 #endif
00934 out = singular_sax_union(out);
00935 #ifdef GIST_DEBUG
00936 fprintf(stderr, "==================================\n");
00937 fprintf(stderr, "\ti_gsax_union, i=%d, length=%d\n",i,tmp->length);
00938 printSAX(out);
00939 fprintf(stderr, "==================================\n");
00940 #endif
00941 return (out);
00942
00943 }
00944
00945
00946
00947
00948
00949
00950 Datum gsax_union(PG_FUNCTION_ARGS){
00951
00952
00953 int32 numranges, len, d, k, i, j;
00954 SAX *out = (SAX *) NULL;
00955 SAX *tmp, *sax, *itmp;
00956 GistEntryVector *entryvec=(GistEntryVector *) PG_GETARG_POINTER(0);
00957 int *sizep=(int *) PG_GETARG_POINTER(1);
00958
00959 #ifdef GIST_DEBUG
00960 fprintf(stderr, "union %d\n",*sizep);
00961 #endif
00962
00963 numranges = entryvec->n;
00964 tmp = singular_sax((SAX *) DatumGetPointer(entryvec->vector[0].key));
00965 *sizep = SIZE_OF_SAX(tmp->length);
00966 #ifdef GIST_DEBUG
00967 fprintf(stderr, "Data to gsax_union, number=%d, length=%d\n",numranges,tmp->length);
00968 for (j = 0; j< numranges; j=OffsetNumberNext(j))
00969 {
00970 fprintf(stderr, "%d\t",j);
00971 sax = (SAX *) DatumGetPointer(entryvec->vector[j].key);
00972 printSAX(sax);
00973 }
00974
00975 #endif
00976 if (numranges > 1) {
00977 for (i = 0; i < numranges; i++) {
00978 itmp = singular_sax(
00979 (SAX *) DatumGetPointer(entryvec->vector[i].key));
00980 out = i_sax_union(tmp, itmp);
00981 pfree(itmp);
00982 pfree(tmp);
00983
00984
00985
00986 tmp = out;
00987 }
00988 } else {
00989 out = tmp;
00990 }
00991 #ifdef GIST_DEBUG
00992 fprintf(stderr, "==================================\n");
00993 fprintf(stderr, "%d\t%d\t",numranges,out->length);
00994 printSAX(out);
00995
00996 fprintf(stderr, "==================================\n");
00997 fprintf(stderr, "union-card\n");
00998 #endif
00999
01000 out = singular_sax_union(out);
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010
01011
01012
01013 #ifdef GIST_DEBUG
01014 fprintf(stderr, "==================================\n");
01015 fprintf(stderr, "%d\t%d\t",numranges,out->length);
01016 printSAX(out);
01017
01018 fprintf(stderr, "==================================\n");
01019 fprintf(stderr, "union-fin\n");
01020 #endif
01021
01022 PG_RETURN_POINTER(out);
01023 }
01024
01025
01026
01027
01028
01029 Datum gsax_compress(PG_FUNCTION_ARGS){
01030
01031
01032 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01033 PG_RETURN_POINTER(entry);
01034 }
01035
01036 Datum gsax_decompress(PG_FUNCTION_ARGS){
01037
01038
01039 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01040 PG_RETURN_POINTER(entry);
01041 }
01042
01043 Datum gsax_same(PG_FUNCTION_ARGS){
01044
01045
01046 SAX *b1 = (SAX *) PG_GETARG_POINTER(0);
01047 SAX *b2 = (SAX *) PG_GETARG_POINTER(1);
01048 bool *result = (bool *) PG_GETARG_POINTER(2);
01049 if (sax_same(b1, b2))
01050 *result = TRUE;
01051 else
01052 *result = FALSE;
01053 PG_RETURN_POINTER(result);
01054 }
01055
01056
01057
01058
01059 Datum gsax_penalty(PG_FUNCTION_ARGS){
01060
01061
01062 SAX *up, *down, *uni,*orig,*new;
01063 GISTENTRY *origentry=(GISTENTRY *) PG_GETARG_POINTER(0);
01064 GISTENTRY *newentry=(GISTENTRY *) PG_GETARG_POINTER(1);
01065 float *result=(float *) PG_GETARG_POINTER(2);
01066
01067 orig = singular_sax((SAX*) DatumGetPointer(origentry->key));
01068 new = singular_sax((SAX*) DatumGetPointer(newentry->key));
01069 float r;
01070 #ifdef GIST_DEBUG
01071 fprintf(stderr, "gsax_penalty\n");
01072 fprintf(stderr, "orig\t");
01073 printSAX(orig);
01074 fprintf(stderr, "new\t");
01075 printSAX(new);
01076 #endif
01077
01078
01079
01080
01081
01082
01083
01084 *result = i_sax_penalty(orig, new);
01085
01086 pfree(orig);
01087 pfree(new);
01088
01089
01090
01091
01092
01093 #ifdef GIST_DEBUG
01094 fprintf(stderr, "penalty\t");
01095 fprintf(stderr, "\t%g\n", *result);
01096 #endif
01097
01098
01099 PG_RETURN_POINTER(result);
01100 }
01101
01102
01103
01104
01105
01106 GIST_SPLITVEC *
01107 gsax_picksplit_old(GistEntryVector *entryvec, GIST_SPLITVEC *v) {
01108 OffsetNumber i, j;
01109 SAX *union_d, *datum_alpha, *datum_beta, *f_union_l, *f_union_r, *tmp;
01110 SAX_ELEMENT *datum_l, *datum_r;
01111 SAX_ELEMENT *union_ed, *union_dl, *union_dr;
01112 SAX_ELEMENT *inter_d, *exch_el;
01113 bool firsttime=true;
01114 float size_alpha, size_beta, size_union, size_inter;
01115 float size_waste, waste;
01116 float size_l, size_r;
01117 unsigned int nbytes, k, l, c_split, i_split;
01118 OffsetNumber seed_1 = 1, seed_2 = 2;
01119 OffsetNumber *left, *right;
01120 OffsetNumber maxoff;
01121
01122 #ifdef GIST_DEBUG
01123 fprintf(stderr, "picksplit\n");
01124 #endif
01125
01126 maxoff = entryvec->n - 2;
01127 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
01128 v->spl_left = (OffsetNumber *) palloc0(nbytes);
01129 v->spl_right = (OffsetNumber *) palloc0(nbytes);
01130
01131
01132
01133
01134 c_split = 256;
01135 i_split = 0;
01136 union_d = i_gsax_union(entryvec, 1);
01137 for (k = 0; k < union_d->length; k++) {
01138 l = union_d->data[k].cardinality;
01139 if (union_d->data[k].upper == union_d->data[k].lower) {
01140 l++;
01141 }
01142 if (c_split > l) {
01143 c_split = l;
01144 i_split = k;
01145 }
01146 }
01147 pfree(union_d);
01148 #ifdef GIST_DEBUG
01149 fprintf(stderr, "picksplit-3 maxoff=%d c_split=%d, i_split=%d\n", maxoff,c_split, i_split);
01150 #endif
01151 union_ed = palloc0(sizeof(SAX_ELEMENT));
01152 union_dl = palloc0(sizeof(SAX_ELEMENT));
01153 union_dr = palloc0(sizeof(SAX_ELEMENT));
01154 inter_d = palloc0(sizeof(SAX_ELEMENT));
01155 datum_l = palloc0(sizeof(SAX_ELEMENT));
01156 datum_r = palloc0(sizeof(SAX_ELEMENT));
01157 waste = 0;
01158 for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) {
01159 datum_alpha = (SAX *) DatumGetPointer(entryvec->vector[i].key);
01160 for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) {
01161 datum_beta = (SAX *) DatumGetPointer(entryvec->vector[j].key);
01162
01163
01164
01165 sax_element_union(&(datum_alpha->data[i_split]),
01166 &(datum_beta->data[i_split]), union_ed);
01167 size_union = sax_element_size(union_ed);
01168 sax_element_intersect(&(datum_alpha->data[i_split]),
01169 &(datum_beta->data[i_split]), inter_d);
01170 size_inter = sax_element_size(inter_d);
01171 size_waste = i_sax_elem_distance(&(datum_alpha->data[i_split]),
01172 &(datum_beta->data[i_split]));
01173 #ifdef GIST_DEBUG
01174 fprintf(stderr, "%d %d: u=%f i=%f w=%f; %f\t\t",i,j,size_union, size_inter,size_waste,waste);
01175 printSAX_ELM(datum_alpha->data[i_split]);
01176 fprintf(stderr, "\t\t");
01177 printSAX_ELM(datum_beta->data[i_split]);
01178 fprintf(stderr, "\t\t");
01179 printSAX_ELM(*inter_d);
01180 fprintf(stderr, "\t\t");
01181 printSAX_ELM(*union_ed);
01182 fprintf(stderr, "\n");
01183 #endif
01184
01185
01186
01187 if (size_waste > waste || firsttime) {
01188 waste = size_waste;
01189 seed_1 = i;
01190 seed_2 = j;
01191 firsttime = false;
01192 }
01193 }
01194 }
01195 #ifdef GIST_DEBUG
01196 fprintf(stderr, "picksplit-5 seed1=%d, seed2=%d, waste=%f\n",seed_1,seed_2,waste);
01197 #endif
01198 if (seed_1 == 0 || seed_2 == 0) {
01199 seed_1 = 1;
01200 seed_2 = 2;
01201 }
01202
01203 left = v->spl_left;
01204 v->spl_nleft = 0;
01205 right = v->spl_right;
01206 v->spl_nright = 0;
01207
01208 datum_alpha = (SAX *) DatumGetPointer(entryvec->vector[seed_1].key);
01209
01210 datum_l->cardinality = c_split;
01211 datum_l->lower = downgradeLetter(datum_alpha->data[i_split].lower,
01212 datum_alpha->data[i_split].cardinality, c_split);
01213 datum_l->upper = downgradeLetter(datum_alpha->data[i_split].upper,
01214 datum_alpha->data[i_split].cardinality, c_split);
01215 size_l = sax_element_size(datum_l);
01216 datum_beta = (SAX *) DatumGetPointer(entryvec->vector[seed_2].key);
01217
01218 datum_r->cardinality = c_split;
01219 datum_r->lower = downgradeLetter(datum_beta->data[i_split].lower,
01220 datum_beta->data[i_split].cardinality, c_split);
01221 datum_r->upper = downgradeLetter(datum_beta->data[i_split].upper,
01222 datum_beta->data[i_split].cardinality, c_split);
01223 size_r = sax_element_size(datum_r);
01224 #ifdef GIST_DEBUG
01225 fprintf(stderr, "size_l=%f, size_r=%f\t\t",size_l,size_r);
01226 printSAX_ELM(*datum_l);
01227 fprintf(stderr, "\t\t");
01228 printSAX_ELM(*datum_r);
01229 fprintf(stderr, "\n");
01230 #endif
01231
01232
01233
01234
01235
01236
01237
01238
01239
01240
01241
01242
01243
01244 maxoff = OffsetNumberNext(maxoff);
01245 f_union_l = i_sax_union(datum_alpha, datum_alpha);
01246 f_union_l->data[i_split].cardinality = c_split;
01247 f_union_l->data[i_split].lower = datum_l->lower;
01248 f_union_l->data[i_split].upper = datum_l->upper;
01249 f_union_r = i_sax_union(datum_beta, datum_beta);
01250 f_union_r->data[i_split].cardinality = c_split;
01251 f_union_r->data[i_split].lower = datum_r->lower;
01252 f_union_r->data[i_split].upper = datum_r->upper;
01253 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) {
01254
01255
01256
01257
01258
01259
01260 if (i == seed_1) {
01261 *left++ = i;
01262 v->spl_nleft++;
01263 continue;
01264 } else if (i == seed_2) {
01265 *right++ = i;
01266 v->spl_nright++;
01267 continue;
01268 }
01269
01270
01271 datum_alpha = (SAX *) DatumGetPointer(entryvec->vector[i].key);
01272
01273
01274 size_alpha
01275 = i_sax_elem_distance(datum_l, &(datum_alpha->data[i_split]));
01276 size_beta = i_sax_elem_distance(datum_r, &(datum_alpha->data[i_split]));
01277
01278
01279 if (size_alpha < size_beta) {
01280
01281
01282
01283
01284
01285
01286 tmp = f_union_l;
01287 f_union_l = i_sax_union(tmp, datum_alpha);
01288 pfree(tmp);
01289 size_l = size_alpha;
01290 *left++ = i;
01291 v->spl_nleft++;
01292 } else {
01293
01294
01295
01296
01297
01298
01299 tmp = f_union_r;
01300 f_union_r = i_sax_union(tmp, datum_alpha);
01301 pfree(tmp);
01302 size_r = size_alpha;
01303 *right++ = i;
01304 v->spl_nright++;
01305 }
01306 }
01307 #ifdef GIST_DEBUG
01308 fprintf(stderr, "picksplit left=%d, right=%d\n",v->spl_nleft, v->spl_nright);
01309 #endif
01310 pfree(union_ed);
01311 pfree(union_dl);
01312 pfree(union_dr);
01313 pfree(inter_d);
01314 pfree(datum_l);
01315 pfree(datum_r);
01316
01317 *left = *right = FirstOffsetNumber;
01318
01319 v->spl_ldatum = PointerGetDatum(f_union_l);
01320 v->spl_rdatum = PointerGetDatum(f_union_r);
01321 #ifdef GIST_DEBUG
01322 fprintf(stderr, "picksplit-fin\n");
01323 printSAX(f_union_l);
01324 printSAX(f_union_r);
01325 #endif
01326
01327 return v;
01328 }
01329
01330
01331
01332
01333 Datum gsax_picksplit(PG_FUNCTION_ARGS){
01334
01335
01336 OffsetNumber i, j;
01337 SAX *union_d, *datum_alpha, *datum_beta, *f_union_l, *f_union_r, *tmp;
01338
01339
01340
01341 bool firsttime;
01342 float size_alpha, size_beta, size_union, size_inter;
01343 float size_waste, waste;
01344 float size_l, size_r;
01345 unsigned char a, b, c, d;
01346 unsigned int nbytes, k, l, c_split, i_split, size;
01347 OffsetNumber seed_1 = 1, seed_2 = 2;
01348 OffsetNumber *left, *right;
01349 OffsetNumber maxoff;
01350
01351 GistEntryVector *entryvec=(GistEntryVector *) PG_GETARG_POINTER(0);
01352 GIST_SPLITVEC *v=(GIST_SPLITVEC *) PG_GETARG_POINTER(1);
01353
01354 #ifdef GIST_DEBUG
01355 fprintf(stderr, "picksplit\n");
01356 #endif
01357
01358 maxoff = entryvec->n ;
01359 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
01360 v->spl_left = (OffsetNumber *) palloc0(nbytes);
01361 v->spl_right = (OffsetNumber *) palloc0(nbytes);
01362 datum_alpha = (SAX *) DatumGetPointer(
01363 entryvec->vector[FirstOffsetNumber].key);
01364 size = SIZE_OF_SAX(datum_alpha->length);
01365 f_union_l = palloc0(size);
01366 SET_VARSIZE(f_union_l, size);
01367 f_union_r = palloc0(size);
01368 SET_VARSIZE(f_union_r, size);
01369 f_union_l->length = datum_alpha->length;
01370 f_union_r->length = datum_alpha->length;
01371
01372
01373
01374
01375 union_d = i_gsax_union(entryvec, 1);
01376
01377 i_split = 0;
01378 c_split = union_d->data[i_split].cardinality;
01379 for (k = 0; k < union_d->length; k++) {
01380 l = union_d->data[k].cardinality;
01381
01382
01383 if( c_split>l){
01384 c_split = l;
01385 i_split = k;
01386 break;
01387
01388
01389
01390
01391
01392
01393 }
01394 }
01395 l=c_split;
01396 c_split++;
01397 d = downgradeLetter(0xff, 8, c_split);
01398 union_d->data[i_split].upper = promoteLetter(union_d->data[i_split].upper,
01399 d, union_d->data[i_split].cardinality, c_split);
01400 union_d->data[i_split].lower = promoteLetter(union_d->data[i_split].lower,
01401 0, union_d->data[i_split].cardinality, c_split);
01402 union_d->data[i_split].cardinality = c_split;
01403
01404
01405
01406
01407
01408
01409
01410
01411
01412
01413
01414 for (k = 0; k < union_d->length; k++) {
01415 f_union_l->data[k].upper = union_d->data[k].lower;
01416 f_union_l->data[k].lower = union_d->data[k].lower;
01417 f_union_l->data[k].cardinality = union_d->data[k].cardinality;;
01418 f_union_r->data[k].upper = union_d->data[k].upper;
01419 f_union_r->data[k].lower = union_d->data[k].upper;
01420 f_union_r->data[k].cardinality = union_d->data[k].cardinality;;
01421 }
01422 waste = 0;
01423
01424 #ifdef GIST_DEBUG
01425 fprintf(stderr, "picksplit-3 maxoff=%d c_split=%d, i_split=%d\n", maxoff,c_split, i_split);
01426 printSAX(union_d);
01427 #endif
01428 left = v->spl_left;
01429 v->spl_nleft = 0;
01430 right = v->spl_right;
01431 v->spl_nright = 0;
01432
01433 for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) {
01434 datum_alpha = (SAX *) DatumGetPointer(entryvec->vector[i].key);
01435 if (datum_alpha->data[i_split].lower
01436 != datum_alpha->data[i_split].upper) {
01437 a = datum_alpha->data[i_split].lower >> 1;
01438 b = datum_alpha->data[i_split].upper >> 1;
01439 c = downgradeLetter((a + b),
01440 datum_alpha->data[i_split].cardinality, c_split);
01441 a = datum_alpha->data[i_split].lower;
01442 b = datum_alpha->data[i_split].upper;
01443 } else {
01444 a = datum_alpha->data[i_split].lower;
01445 b = datum_alpha->data[i_split].upper;
01446 c = downgradeLetter(a, datum_alpha->data[i_split].cardinality,
01447 c_split);
01448 }
01449
01450
01451
01452
01453 if (c == union_d->data[i_split].upper) {
01454 *right++ = i;
01455 v->spl_nright++;
01456
01457
01458 #ifdef GIST_DEBUG
01459 fprintf(stderr, "picksplit-5 Right i=%d c_split=%d,a=%d, b=%d, c=%d -> (%d,%d)\n", i,c_split,a, b,c,union_d->data[i_split].lower,union_d->data[i_split].upper);
01460 printSAX(datum_alpha);
01461
01462 printSAX(f_union_r);
01463 #endif
01464
01465 } else if (c == union_d->data[i_split].lower) {
01466 *left++ = i;
01467 v->spl_nleft++;
01468
01469
01470 #ifdef GIST_DEBUG
01471 fprintf(stderr, "picksplit-5 Left i=%d c_split=%d,a=%d, b=%d, c=%d -> (%d,%d)\n", i,c_split,a, b,c,union_d->data[i_split].lower,union_d->data[i_split].upper);
01472 printSAX(datum_alpha);
01473
01474 printSAX(f_union_l);
01475 #endif
01476
01477 } else {
01478
01479
01480 printSAX(datum_alpha);
01481 printSAX(f_union_l);
01482 printSAX(f_union_r);
01483 ereport(ERROR, (errcode(ERRCODE_GROUPING_ERROR), errmsg(
01484 "sax picksplit neither upper nor lower"), errdetail(
01485 "SAX at %d suppose to be either: %d or %d but is %d",i_split,
01486 union_d->data[i_split].lower, union_d->data[i_split].upper,
01487 c)));
01488
01489 }
01490
01491 }
01492 #ifdef GIST_DEBUG
01493 fprintf(stderr, "picksplit left=%d, right=%d\n",v->spl_nleft, v->spl_nright);
01494 printSAX(f_union_l);
01495 printSAX(f_union_r);
01496 #endif
01497
01498
01499
01500 *left = *right = FirstOffsetNumber;
01501
01502 v->spl_ldatum = PointerGetDatum(f_union_l);
01503 v->spl_rdatum = PointerGetDatum(f_union_r);
01504 #ifdef GIST_DEBUG
01505 fprintf(stderr, "picksplit-fin\n");
01506 printSAX(f_union_l);
01507 printSAX(f_union_r);
01508 #endif
01509 pfree(union_d);
01510
01511 PG_RETURN_POINTER(v);
01512 }
01513
01514
01515
01516
01517 bool gsax_leaf_consistent(SAX * key, SAX * query, StrategyNumber strategy) {
01518 bool retval;
01519 int i;
01520
01521 switch (strategy) {
01522 case RTLeftStrategyNumber:
01523 retval = (bool) sax_less(key, query);
01524 break;
01525 case RTOverLeftStrategyNumber:
01526 retval = (bool) sax_loverlap(key, query);
01527 break;
01528 case RTOverlapStrategyNumber:
01529 retval = (bool) sax_intersect(key, query);
01530 break;
01531 case RTOverRightStrategyNumber:
01532 retval = (bool) sax_uoverlap(key, query);
01533 break;
01534 case RTRightStrategyNumber:
01535 retval = (bool) sax_greater(key, query);
01536 break;
01537 case RTSameStrategyNumber:
01538 retval = (bool) sax_same(key, query);
01539 break;
01540 case RTContainsStrategyNumber:
01541 case RTOldContainsStrategyNumber:
01542 retval = (bool) sax_contains(key, query);
01543 break;
01544 case RTContainedByStrategyNumber:
01545 case RTOldContainedByStrategyNumber:
01546 retval = (bool) sax_contained(key, query);
01547 break;
01548 default:
01549 retval = FALSE;
01550 }
01551
01552 #ifdef GIST_DEBUG
01553 fprintf(stderr, "leaf_consistent, strategy=%d; retval=%d\n", strategy,retval);
01554 for(i=0;i<key->length;i++) {
01555 if ( i> 0 )
01556 fprintf(stderr,"; ");
01557
01558 if ( key->data[i].lower <= key->data[i].upper ) {
01559 fprintf(stderr, "%x", key->data[i].lower);
01560
01561 if ( key->data[i].lower != key->data[i].upper ) {
01562 fprintf(stderr, ":%x", key->data[i].upper);
01563 }
01564 fprintf(stderr, "|%x", key->data[i].cardinality);
01565 }
01566 else {
01567 fprintf(stderr, "NULL");
01568 }
01569 }
01570 fprintf(stderr, "\n");
01571
01572 fprintf(stderr, "==================================\n");
01573 for(i=0;i<query->length;i++) {
01574 if ( i> 0 )
01575 fprintf(stderr,"; ");
01576
01577 if ( query->data[i].lower <= query->data[i].upper ) {
01578 fprintf(stderr, "%x", query->data[i].lower);
01579
01580 if ( query->data[i].lower != query->data[i].upper ) {
01581 fprintf(stderr, ":%x", query->data[i].upper);
01582 }
01583 fprintf(stderr, "|%x", query->data[i].cardinality);
01584 }
01585 else {
01586 fprintf(stderr, "NULL");
01587 }
01588 }
01589 fprintf(stderr, "\n");
01590
01591 fprintf(stderr, "==================================\n");
01592 #endif
01593
01594 return (retval);
01595 }
01596
01597 bool gsax_internal_consistent(SAX * key, SAX * query, StrategyNumber strategy) {
01598 bool retval;
01599 int i;
01600
01601 switch (strategy) {
01602 case RTLeftStrategyNumber:
01603 retval = (bool) !sax_uoverlap(key, query);
01604 break;
01605 case RTOverLeftStrategyNumber:
01606 retval = (bool) !sax_greater(key, query);
01607 break;
01608 case RTOverlapStrategyNumber:
01609 retval = (bool) sax_intersect(key, query);
01610 break;
01611 case RTOverRightStrategyNumber:
01612 retval = (bool) !sax_less(key, query);
01613 break;
01614 case RTRightStrategyNumber:
01615 retval = (bool) !sax_loverlap(key, query);
01616 break;
01617 case RTSameStrategyNumber:
01618 case RTContainsStrategyNumber:
01619 case RTOldContainsStrategyNumber:
01620 retval = (bool) sax_intersect(key, query);
01621 break;
01622 case RTContainedByStrategyNumber:
01623 case RTOldContainedByStrategyNumber:
01624 retval = (bool) sax_intersect(key, query);
01625 break;
01626 default:
01627 retval = FALSE;
01628 }
01629
01630 #ifdef GIST_DEBUG
01631 fprintf(stderr, "internal_consistent, , strategy=%d; retval=%d\n", strategy,retval);
01632 for(i=0;i<key->length;i++) {
01633 if ( i> 0 )
01634 fprintf(stderr,"; ");
01635
01636 if ( key->data[i].lower <= key->data[i].upper ) {
01637 fprintf(stderr, "%x", key->data[i].lower);
01638
01639 if ( key->data[i].lower != key->data[i].upper ) {
01640 fprintf(stderr, ":%x", key->data[i].upper);
01641 }
01642 fprintf(stderr, "|%x", key->data[i].cardinality);
01643 }
01644 else {
01645 fprintf(stderr, "NULL");
01646 }
01647 }
01648 fprintf(stderr, "\n");
01649
01650 fprintf(stderr, "==================================\n");
01651 for(i=0;i<query->length;i++) {
01652 if ( i> 0 )
01653 fprintf(stderr,"; ");
01654
01655 if ( query->data[i].lower <= query->data[i].upper ) {
01656 fprintf(stderr, "%x", query->data[i].lower);
01657
01658 if ( query->data[i].lower != query->data[i].upper ) {
01659 fprintf(stderr, ":%x", query->data[i].upper);
01660 }
01661 fprintf(stderr, "|%x", query->data[i].cardinality);
01662 }
01663 else {
01664 fprintf(stderr, "NULL");
01665 }
01666 }
01667 fprintf(stderr, "\n");
01668
01669 fprintf(stderr, "==================================\n");
01670 #endif
01671 return (retval);
01672 }