Header And Logo

PostgreSQL
| The world's most advanced open source database.

tsquery_gist.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * tsquery_gist.c
00004  *    GiST index support for tsquery
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  *
00008  *
00009  * IDENTIFICATION
00010  *    src/backend/utils/adt/tsquery_gist.c
00011  *
00012  *-------------------------------------------------------------------------
00013  */
00014 
00015 #include "postgres.h"
00016 
00017 #include "access/skey.h"
00018 #include "access/gist.h"
00019 #include "tsearch/ts_utils.h"
00020 
00021 #define GETENTRY(vec,pos) DatumGetTSQuerySign((vec)->vector[pos].key)
00022 
00023 
00024 Datum
00025 gtsquery_compress(PG_FUNCTION_ARGS)
00026 {
00027     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00028     GISTENTRY  *retval = entry;
00029 
00030     if (entry->leafkey)
00031     {
00032         TSQuerySign sign;
00033 
00034         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
00035         sign = makeTSQuerySign(DatumGetTSQuery(entry->key));
00036 
00037         gistentryinit(*retval, TSQuerySignGetDatum(sign),
00038                       entry->rel, entry->page,
00039                       entry->offset, FALSE);
00040     }
00041 
00042     PG_RETURN_POINTER(retval);
00043 }
00044 
00045 Datum
00046 gtsquery_decompress(PG_FUNCTION_ARGS)
00047 {
00048     PG_RETURN_DATUM(PG_GETARG_DATUM(0));
00049 }
00050 
00051 Datum
00052 gtsquery_consistent(PG_FUNCTION_ARGS)
00053 {
00054     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00055     TSQuery     query = PG_GETARG_TSQUERY(1);
00056     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
00057 
00058     /* Oid      subtype = PG_GETARG_OID(3); */
00059     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
00060     TSQuerySign key = DatumGetTSQuerySign(entry->key);
00061     TSQuerySign sq = makeTSQuerySign(query);
00062     bool        retval;
00063 
00064     /* All cases served by this function are inexact */
00065     *recheck = true;
00066 
00067     switch (strategy)
00068     {
00069         case RTContainsStrategyNumber:
00070             if (GIST_LEAF(entry))
00071                 retval = (key & sq) == sq;
00072             else
00073                 retval = (key & sq) != 0;
00074             break;
00075         case RTContainedByStrategyNumber:
00076             if (GIST_LEAF(entry))
00077                 retval = (key & sq) == key;
00078             else
00079                 retval = (key & sq) != 0;
00080             break;
00081         default:
00082             retval = FALSE;
00083     }
00084     PG_RETURN_BOOL(retval);
00085 }
00086 
00087 Datum
00088 gtsquery_union(PG_FUNCTION_ARGS)
00089 {
00090     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00091     int        *size = (int *) PG_GETARG_POINTER(1);
00092     TSQuerySign sign;
00093     int         i;
00094 
00095     sign = 0;
00096 
00097     for (i = 0; i < entryvec->n; i++)
00098         sign |= GETENTRY(entryvec, i);
00099 
00100     *size = sizeof(TSQuerySign);
00101 
00102     PG_RETURN_TSQUERYSIGN(sign);
00103 }
00104 
00105 Datum
00106 gtsquery_same(PG_FUNCTION_ARGS)
00107 {
00108     TSQuerySign a = PG_GETARG_TSQUERYSIGN(0);
00109     TSQuerySign b = PG_GETARG_TSQUERYSIGN(1);
00110     bool       *result = (bool *) PG_GETARG_POINTER(2);
00111 
00112     *result = (a == b) ? true : false;
00113 
00114     PG_RETURN_POINTER(result);
00115 }
00116 
00117 static int
00118 sizebitvec(TSQuerySign sign)
00119 {
00120     int         size = 0,
00121                 i;
00122 
00123     for (i = 0; i < TSQS_SIGLEN; i++)
00124         size += 0x01 & (sign >> i);
00125 
00126     return size;
00127 }
00128 
00129 static int
00130 hemdist(TSQuerySign a, TSQuerySign b)
00131 {
00132     TSQuerySign res = a ^ b;
00133 
00134     return sizebitvec(res);
00135 }
00136 
00137 Datum
00138 gtsquery_penalty(PG_FUNCTION_ARGS)
00139 {
00140     TSQuerySign origval = DatumGetTSQuerySign(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
00141     TSQuerySign newval = DatumGetTSQuerySign(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
00142     float      *penalty = (float *) PG_GETARG_POINTER(2);
00143 
00144     *penalty = hemdist(origval, newval);
00145 
00146     PG_RETURN_POINTER(penalty);
00147 }
00148 
00149 
00150 typedef struct
00151 {
00152     OffsetNumber pos;
00153     int32       cost;
00154 } SPLITCOST;
00155 
00156 static int
00157 comparecost(const void *a, const void *b)
00158 {
00159     if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
00160         return 0;
00161     else
00162         return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
00163 }
00164 
00165 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
00166 
00167 Datum
00168 gtsquery_picksplit(PG_FUNCTION_ARGS)
00169 {
00170     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00171     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
00172     OffsetNumber maxoff = entryvec->n - 2;
00173     OffsetNumber k,
00174                 j;
00175     TSQuerySign datum_l,
00176                 datum_r;
00177     int32       size_alpha,
00178                 size_beta;
00179     int32       size_waste,
00180                 waste = -1;
00181     int32       nbytes;
00182     OffsetNumber seed_1 = 0,
00183                 seed_2 = 0;
00184     OffsetNumber *left,
00185                *right;
00186 
00187     SPLITCOST  *costvector;
00188 
00189     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
00190     left = v->spl_left = (OffsetNumber *) palloc(nbytes);
00191     right = v->spl_right = (OffsetNumber *) palloc(nbytes);
00192     v->spl_nleft = v->spl_nright = 0;
00193 
00194     for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
00195         for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
00196         {
00197             size_waste = hemdist(GETENTRY(entryvec, j), GETENTRY(entryvec, k));
00198             if (size_waste > waste)
00199             {
00200                 waste = size_waste;
00201                 seed_1 = k;
00202                 seed_2 = j;
00203             }
00204         }
00205 
00206 
00207     if (seed_1 == 0 || seed_2 == 0)
00208     {
00209         seed_1 = 1;
00210         seed_2 = 2;
00211     }
00212 
00213     datum_l = GETENTRY(entryvec, seed_1);
00214     datum_r = GETENTRY(entryvec, seed_2);
00215 
00216     maxoff = OffsetNumberNext(maxoff);
00217     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
00218     for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
00219     {
00220         costvector[j - 1].pos = j;
00221         size_alpha = hemdist(GETENTRY(entryvec, seed_1), GETENTRY(entryvec, j));
00222         size_beta = hemdist(GETENTRY(entryvec, seed_2), GETENTRY(entryvec, j));
00223         costvector[j - 1].cost = abs(size_alpha - size_beta);
00224     }
00225     qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
00226 
00227     for (k = 0; k < maxoff; k++)
00228     {
00229         j = costvector[k].pos;
00230         if (j == seed_1)
00231         {
00232             *left++ = j;
00233             v->spl_nleft++;
00234             continue;
00235         }
00236         else if (j == seed_2)
00237         {
00238             *right++ = j;
00239             v->spl_nright++;
00240             continue;
00241         }
00242         size_alpha = hemdist(datum_l, GETENTRY(entryvec, j));
00243         size_beta = hemdist(datum_r, GETENTRY(entryvec, j));
00244 
00245         if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.05))
00246         {
00247             datum_l |= GETENTRY(entryvec, j);
00248             *left++ = j;
00249             v->spl_nleft++;
00250         }
00251         else
00252         {
00253             datum_r |= GETENTRY(entryvec, j);
00254             *right++ = j;
00255             v->spl_nright++;
00256         }
00257     }
00258 
00259     *right = *left = FirstOffsetNumber;
00260     v->spl_ldatum = TSQuerySignGetDatum(datum_l);
00261     v->spl_rdatum = TSQuerySignGetDatum(datum_r);
00262 
00263     PG_RETURN_POINTER(v);
00264 }