granicus.if.org Git - postgresql/blob - src/backend/utils/adt/tsquery_gist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * tsquery_gist.c
   4  *        GiST index support for tsquery
   5  *
   6  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $PostgreSQL: pgsql/src/backend/utils/adt/tsquery_gist.c,v 1.1 2007/08/21 01:11:19 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/skey.h"
  18 #include "access/gist.h"
  19 #include "tsearch/ts_type.h"
  20 #include "tsearch/ts_utils.h"
  21
  22 #define GETENTRY(vec,pos) ((TSQuerySign *) DatumGetPointer((vec)->vector[(pos)].key))
  23
  24 Datum
  25 gtsquery_compress(PG_FUNCTION_ARGS)
  26 {
  27         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  28         GISTENTRY  *retval = entry;
  29
  30         if (entry->leafkey)
  31         {
  32                 TSQuerySign *sign = (TSQuerySign *) palloc(sizeof(TSQuerySign));
  33
  34                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  35                 *sign = makeTSQuerySign(DatumGetTSQuery(entry->key));
  36
  37                 gistentryinit(*retval, PointerGetDatum(sign),
  38                                           entry->rel, entry->page,
  39                                           entry->offset, FALSE);
  40         }
  41
  42         PG_RETURN_POINTER(retval);
  43 }
  44
  45 Datum
  46 gtsquery_decompress(PG_FUNCTION_ARGS)
  47 {
  48         PG_RETURN_DATUM(PG_GETARG_DATUM(0));
  49 }
  50
  51 Datum
  52 gtsquery_consistent(PG_FUNCTION_ARGS)
  53 {
  54         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  55         TSQuerySign *key = (TSQuerySign *) DatumGetPointer(entry->key);
  56         TSQuery         query = PG_GETARG_TSQUERY(1);
  57         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
  58         TSQuerySign sq = makeTSQuerySign(query);
  59         bool            retval;
  60
  61         switch (strategy)
  62         {
  63                 case RTContainsStrategyNumber:
  64                         if (GIST_LEAF(entry))
  65                                 retval = (*key & sq) == sq;
  66                         else
  67                                 retval = (*key & sq) != 0;
  68                         break;
  69                 case RTContainedByStrategyNumber:
  70                         if (GIST_LEAF(entry))
  71                                 retval = (*key & sq) == *key;
  72                         else
  73                                 retval = (*key & sq) != 0;
  74                         break;
  75                 default:
  76                         retval = FALSE;
  77         }
  78         PG_RETURN_BOOL(retval);
  79 }
  80
  81 Datum
  82 gtsquery_union(PG_FUNCTION_ARGS)
  83 {
  84         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
  85         int                *size = (int *) PG_GETARG_POINTER(1);
  86         TSQuerySign *sign = (TSQuerySign *) palloc(sizeof(TSQuerySign));
  87         int                     i;
  88
  89         memset(sign, 0, sizeof(TSQuerySign));
  90
  91         for (i = 0; i < entryvec->n; i++)
  92                 *sign |= *GETENTRY(entryvec, i);
  93
  94         *size = sizeof(TSQuerySign);
  95
  96         PG_RETURN_POINTER(sign);
  97 }
  98
  99 Datum
 100 gtsquery_same(PG_FUNCTION_ARGS)
 101 {
 102         TSQuerySign *a = (TSQuerySign *) PG_GETARG_POINTER(0);
 103         TSQuerySign *b = (TSQuerySign *) PG_GETARG_POINTER(1);
 104
 105         PG_RETURN_POINTER(*a == *b);
 106 }
 107
 108 static int
 109 sizebitvec(TSQuerySign sign)
 110 {
 111         int                     size = 0,
 112                                 i;
 113
 114         for (i = 0; i < TSQS_SIGLEN; i++)
 115                 size += 0x01 & (sign >> i);
 116
 117         return size;
 118 }
 119
 120 static int
 121 hemdist(TSQuerySign a, TSQuerySign b)
 122 {
 123         TSQuerySign res = a ^ b;
 124
 125         return sizebitvec(res);
 126 }
 127
 128 Datum
 129 gtsquery_penalty(PG_FUNCTION_ARGS)
 130 {
 131         TSQuerySign *origval = (TSQuerySign *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
 132         TSQuerySign *newval = (TSQuerySign *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
 133         float      *penalty = (float *) PG_GETARG_POINTER(2);
 134
 135         *penalty = hemdist(*origval, *newval);
 136
 137         PG_RETURN_POINTER(penalty);
 138 }
 139
 140
 141 typedef struct
 142 {
 143         OffsetNumber pos;
 144         int4            cost;
 145 } SPLITCOST;
 146
 147 static int
 148 comparecost(const void *a, const void *b)
 149 {
 150         if (((SPLITCOST *) a)->cost == ((SPLITCOST *) b)->cost)
 151                 return 0;
 152         else
 153                 return (((SPLITCOST *) a)->cost > ((SPLITCOST *) b)->cost) ? 1 : -1;
 154 }
 155
 156 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
 157
 158 Datum
 159 gtsquery_picksplit(PG_FUNCTION_ARGS)
 160 {
 161         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 162         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 163         OffsetNumber maxoff = entryvec->n - 2;
 164         OffsetNumber k,
 165                                 j;
 166
 167         TSQuerySign *datum_l,
 168                            *datum_r;
 169         int4            size_alpha,
 170                                 size_beta;
 171         int4            size_waste,
 172                                 waste = -1;
 173         int4            nbytes;
 174         OffsetNumber seed_1 = 0,
 175                                 seed_2 = 0;
 176         OffsetNumber *left,
 177                            *right;
 178
 179         SPLITCOST  *costvector;
 180
 181         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 182         left = v->spl_left = (OffsetNumber *) palloc(nbytes);
 183         right = v->spl_right = (OffsetNumber *) palloc(nbytes);
 184         v->spl_nleft = v->spl_nright = 0;
 185
 186         for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 187                 for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 188                 {
 189                         size_waste = hemdist(*GETENTRY(entryvec, j), *GETENTRY(entryvec, k));
 190                         if (size_waste > waste)
 191                         {
 192                                 waste = size_waste;
 193                                 seed_1 = k;
 194                                 seed_2 = j;
 195                         }
 196                 }
 197
 198
 199         if (seed_1 == 0 || seed_2 == 0)
 200         {
 201                 seed_1 = 1;
 202                 seed_2 = 2;
 203         }
 204
 205         datum_l = (TSQuerySign *) palloc(sizeof(TSQuerySign));
 206         *datum_l = *GETENTRY(entryvec, seed_1);
 207         datum_r = (TSQuerySign *) palloc(sizeof(TSQuerySign));
 208         *datum_r = *GETENTRY(entryvec, seed_2);
 209
 210
 211         maxoff = OffsetNumberNext(maxoff);
 212         costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 213         for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 214         {
 215                 costvector[j - 1].pos = j;
 216                 size_alpha = hemdist(*GETENTRY(entryvec, seed_1), *GETENTRY(entryvec, j));
 217                 size_beta = hemdist(*GETENTRY(entryvec, seed_2), *GETENTRY(entryvec, j));
 218                 costvector[j - 1].cost = abs(size_alpha - size_beta);
 219         }
 220         qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 221
 222         for (k = 0; k < maxoff; k++)
 223         {
 224                 j = costvector[k].pos;
 225                 if (j == seed_1)
 226                 {
 227                         *left++ = j;
 228                         v->spl_nleft++;
 229                         continue;
 230                 }
 231                 else if (j == seed_2)
 232                 {
 233                         *right++ = j;
 234                         v->spl_nright++;
 235                         continue;
 236                 }
 237                 size_alpha = hemdist(*datum_l, *GETENTRY(entryvec, j));
 238                 size_beta = hemdist(*datum_r, *GETENTRY(entryvec, j));
 239
 240                 if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.05))
 241                 {
 242                         *datum_l |= *GETENTRY(entryvec, j);
 243                         *left++ = j;
 244                         v->spl_nleft++;
 245                 }
 246                 else
 247                 {
 248                         *datum_r |= *GETENTRY(entryvec, j);
 249                         *right++ = j;
 250                         v->spl_nright++;
 251                 }
 252         }
 253
 254         *right = *left = FirstOffsetNumber;
 255         v->spl_ldatum = PointerGetDatum(datum_l);
 256         v->spl_rdatum = PointerGetDatum(datum_r);
 257
 258         PG_RETURN_POINTER(v);
 259 }