← Back to branch summary

~ubuntu-branches/ubuntu/natty/postgresql-8.4/natty-updates

« back to all changes in this revision

Viewing changes to src/backend/tsearch/ts_selfuncs.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/tsearch/ts_selfuncs.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * ts_selfuncs.c
 
4
 *        Selectivity estimation functions for text search operators.
 
5
 *
 
6
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 
7
 *
 
8
 *
 
9
 * IDENTIFICATION
 
10
 *        $PostgreSQL$
 
11
 *
 
12
 *-------------------------------------------------------------------------
 
13
 */
 
14
#include "postgres.h"
 
15
 
 
16
#include "catalog/pg_statistic.h"
 
17
#include "catalog/pg_type.h"
 
18
#include "miscadmin.h"
 
19
#include "nodes/nodes.h"
 
20
#include "tsearch/ts_type.h"
 
21
#include "utils/lsyscache.h"
 
22
#include "utils/selfuncs.h"
 
23
#include "utils/syscache.h"
 
24
 
 
25
 
 
26
/*
 
27
 * The default text search selectivity is chosen to be small enough to
 
28
 * encourage indexscans for typical table densities.  See selfuncs.h and
 
29
 * DEFAULT_EQ_SEL for details.
 
30
 */
 
31
#define DEFAULT_TS_MATCH_SEL 0.005
 
32
 
 
33
/* lookup table type for binary searching through MCELEMs */
 
34
typedef struct
 
35
{
 
36
        text   *element;
 
37
        float4  frequency;
 
38
} TextFreq;
 
39
 
 
40
/* type of keys for bsearch'ing through an array of TextFreqs */
 
41
typedef struct
 
42
{
 
43
        char    *lexeme;
 
44
        int             length;
 
45
} LexemeKey;
 
46
 
 
47
static Selectivity tsquerysel(VariableStatData *vardata, Datum constval);
 
48
static Selectivity mcelem_tsquery_selec(TSQuery query,
 
49
                                                                                Datum *mcelem, int nmcelem,
 
50
                                                                                float4 *numbers, int nnumbers);
 
51
static Selectivity tsquery_opr_selec(QueryItem *item, char *operand,
 
52
                                                                 TextFreq *lookup, int length, float4 minfreq);
 
53
static int      compare_lexeme_textfreq(const void *e1, const void *e2);
 
54
 
 
55
 
 
56
/*
 
57
 *      tsmatchsel -- Selectivity of "@@"
 
58
 *
 
59
 * restriction selectivity function for tsvector @@ tsquery and
 
60
 * tsquery @@ tsvector
 
61
 */
 
62
Datum
 
63
tsmatchsel(PG_FUNCTION_ARGS)
 
64
{
 
65
        PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
 
66
#ifdef NOT_USED
 
67
        Oid                     operator = PG_GETARG_OID(1);
 
68
#endif
 
69
        List       *args = (List *) PG_GETARG_POINTER(2);
 
70
        int                     varRelid = PG_GETARG_INT32(3);
 
71
        VariableStatData vardata;
 
72
        Node       *other;
 
73
        bool            varonleft;
 
74
        Selectivity     selec;
 
75
 
 
76
        /*
 
77
         * If expression is not variable = something or something = variable, then
 
78
         * punt and return a default estimate.
 
79
         */
 
80
        if (!get_restriction_variable(root, args, varRelid,
 
81
                                                                  &vardata, &other, &varonleft))
 
82
                PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
83
 
 
84
        /*
 
85
         * Can't do anything useful if the something is not a constant, either.
 
86
         */
 
87
        if (!IsA(other, Const))
 
88
        {
 
89
                ReleaseVariableStats(vardata);
 
90
                PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
91
        }
 
92
 
 
93
        /*
 
94
         * The "@@" operator is strict, so we can cope with NULL right away
 
95
         */
 
96
        if (((Const *) other)->constisnull)
 
97
        {
 
98
                ReleaseVariableStats(vardata);
 
99
                PG_RETURN_FLOAT8(0.0);
 
100
        }
 
101
 
 
102
        /*
 
103
         * OK, there's a Var and a Const we're dealing with here. We need the Var
 
104
         * to be a TSVector (or else we don't have any useful statistic for it).
 
105
         * We have to check this because the Var might be the TSQuery not the
 
106
         * TSVector.
 
107
         */
 
108
        if (vardata.vartype == TSVECTOROID)
 
109
        {
 
110
                /* tsvector @@ tsquery or the other way around */
 
111
                Assert(((Const *) other)->consttype == TSQUERYOID);
 
112
 
 
113
                selec = tsquerysel(&vardata, ((Const *) other)->constvalue);
 
114
        }
 
115
        else
 
116
        {
 
117
                /* The Var is something we don't have useful statistics for */
 
118
                selec = DEFAULT_TS_MATCH_SEL;
 
119
        }
 
120
 
 
121
        ReleaseVariableStats(vardata);
 
122
 
 
123
        CLAMP_PROBABILITY(selec);
 
124
 
 
125
        PG_RETURN_FLOAT8((float8) selec);
 
126
}
 
127
 
 
128
 
 
129
/*
 
130
 *      tsmatchjoinsel -- join selectivity of "@@"
 
131
 *
 
132
 * join selectivity function for tsvector @@ tsquery and tsquery @@ tsvector
 
133
 */
 
134
Datum
 
135
tsmatchjoinsel(PG_FUNCTION_ARGS)
 
136
{
 
137
        /* for the moment we just punt */
 
138
        PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
139
}
 
140
 
 
141
 
 
142
/*
 
143
 * @@ selectivity for tsvector var vs tsquery constant
 
144
 */
 
145
static Selectivity
 
146
tsquerysel(VariableStatData *vardata, Datum constval)
 
147
{
 
148
        Selectivity                     selec;
 
149
 
 
150
        if (HeapTupleIsValid(vardata->statsTuple))
 
151
        {
 
152
                TSQuery                         query;
 
153
                Form_pg_statistic       stats;
 
154
                Datum                           *values;
 
155
                int                                     nvalues;
 
156
                float4                          *numbers;
 
157
                int                                     nnumbers;
 
158
 
 
159
                /* The caller made sure the const is a TSQuery, so get it now */
 
160
                query = DatumGetTSQuery(constval);
 
161
 
 
162
                stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
 
163
 
 
164
                /* MCELEM will be an array of TEXT elements for a tsvector column */
 
165
                if (get_attstatsslot(vardata->statsTuple,
 
166
                                                         TEXTOID, -1,
 
167
                                                         STATISTIC_KIND_MCELEM, InvalidOid,
 
168
                                                         &values, &nvalues,
 
169
                                                         &numbers, &nnumbers))
 
170
                {
 
171
                        /*
 
172
                         * There is a most-common-elements slot for the tsvector Var, so
 
173
                         * use that.
 
174
                         */
 
175
                        selec = mcelem_tsquery_selec(query, values, nvalues,
 
176
                                                                                 numbers, nnumbers);
 
177
                        free_attstatsslot(TEXTOID, values, nvalues, numbers, nnumbers);
 
178
                }
 
179
                else
 
180
                {
 
181
                        /* No most-common-elements info, so we must punt */
 
182
                        selec = (Selectivity) DEFAULT_TS_MATCH_SEL;
 
183
                }
 
184
        }
 
185
        else
 
186
        {
 
187
                /* No stats at all, so we must punt */
 
188
                selec = (Selectivity) DEFAULT_TS_MATCH_SEL;
 
189
        }
 
190
 
 
191
        return selec;
 
192
}
 
193
 
 
194
/*
 
195
 * Extract data from the pg_statistic arrays into useful format.
 
196
 */
 
197
static Selectivity
 
198
mcelem_tsquery_selec(TSQuery query, Datum *mcelem, int nmcelem,
 
199
                                         float4 *numbers, int nnumbers)
 
200
{
 
201
        float4                  minfreq;
 
202
        TextFreq                *lookup;
 
203
        Selectivity             selec;
 
204
        int                             i;
 
205
 
 
206
        /*
 
207
         * There should be two more Numbers than Values, because the last two
 
208
         * cells are taken for minimal and maximal frequency.  Punt if not.
 
209
         */
 
210
        if (nnumbers != nmcelem + 2)
 
211
                return DEFAULT_TS_MATCH_SEL;
 
212
 
 
213
        /*
 
214
         * Transpose the data into a single array so we can use bsearch().
 
215
         */
 
216
        lookup = (TextFreq *) palloc(sizeof(TextFreq) * nmcelem);
 
217
        for (i = 0; i < nmcelem; i++)
 
218
        {
 
219
                /*
 
220
                 * The text Datums came from an array, so it cannot be compressed
 
221
                 * or stored out-of-line -- it's safe to use VARSIZE_ANY*.
 
222
                 */
 
223
                Assert(!VARATT_IS_COMPRESSED(mcelem[i]) && !VARATT_IS_EXTERNAL(mcelem[i]));
 
224
                lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
 
225
                lookup[i].frequency = numbers[i];
 
226
        }
 
227
 
 
228
        /*
 
229
         * Grab the lowest frequency. compute_tsvector_stats() stored it for us in
 
230
         * the one before the last cell of the Numbers array. See ts_typanalyze.c
 
231
         */
 
232
        minfreq = numbers[nnumbers - 2];
 
233
 
 
234
        selec = tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), lookup,
 
235
                                                          nmcelem, minfreq);
 
236
 
 
237
        pfree(lookup);
 
238
 
 
239
        return selec;
 
240
}
 
241
 
 
242
/*
 
243
 * Traverse the tsquery in preorder, calculating selectivity as:
 
244
 *
 
245
 *   selec(left_oper) * selec(right_oper) in AND nodes,
 
246
 *
 
247
 *   selec(left_oper) + selec(right_oper) -
 
248
 *      selec(left_oper) * selec(right_oper) in OR nodes,
 
249
 *
 
250
 *   1 - select(oper) in NOT nodes
 
251
 *
 
252
 *   freq[val] in VAL nodes, if the value is in MCELEM
 
253
 *   min(freq[MCELEM]) / 2 in VAL nodes, if it is not
 
254
 *
 
255
 *
 
256
 * The MCELEM array is already sorted (see ts_typanalyze.c), so we can use
 
257
 * binary search for determining freq[MCELEM].
 
258
 */
 
259
static Selectivity
 
260
tsquery_opr_selec(QueryItem *item, char *operand,
 
261
                                  TextFreq *lookup, int length, float4 minfreq)
 
262
{
 
263
        LexemeKey       key;
 
264
        TextFreq        *searchres;
 
265
        Selectivity     selec, s1, s2;
 
266
 
 
267
        /* since this function recurses, it could be driven to stack overflow */
 
268
        check_stack_depth();
 
269
 
 
270
        if (item->type == QI_VAL)
 
271
        {
 
272
                QueryOperand *oper = (QueryOperand *) item;
 
273
 
 
274
                /*
 
275
                 * Prepare the key for bsearch().
 
276
                 */
 
277
                key.lexeme = operand + oper->distance;
 
278
                key.length = oper->length;
 
279
 
 
280
                searchres = (TextFreq *) bsearch(&key, lookup, length,
 
281
                                                                                 sizeof(TextFreq),
 
282
                                                                                 compare_lexeme_textfreq);
 
283
 
 
284
                if (searchres)
 
285
                {
 
286
                        /*
 
287
                         * The element is in MCELEM. Return precise selectivity (or at
 
288
                         * least as precise as ANALYZE could find out).
 
289
                         */
 
290
                        return (Selectivity) searchres->frequency;
 
291
                }
 
292
                else
 
293
                {
 
294
                        /*
 
295
                         * The element is not in MCELEM. Punt, but assert that the
 
296
                         * selectivity cannot be more than minfreq / 2.
 
297
                         */
 
298
                        return (Selectivity) Min(DEFAULT_TS_MATCH_SEL, minfreq / 2);
 
299
                }
 
300
        }
 
301
 
 
302
        /* Current TSQuery node is an operator */
 
303
        switch (item->operator.oper)
 
304
        {
 
305
                case OP_NOT:
 
306
                        selec =  1.0 - tsquery_opr_selec(item + 1, operand,
 
307
                                                                                         lookup, length, minfreq);
 
308
                        break;
 
309
 
 
310
                case OP_AND:
 
311
                        s1 = tsquery_opr_selec(item + 1, operand,
 
312
                                                                         lookup, length, minfreq);
 
313
                        s2 = tsquery_opr_selec(item + item->operator.left, operand,
 
314
                                                                   lookup, length, minfreq);
 
315
                        selec = s1 * s2;
 
316
                        break;
 
317
 
 
318
                case OP_OR:
 
319
                        s1 = tsquery_opr_selec(item + 1, operand,
 
320
                                                                   lookup, length, minfreq);
 
321
                        s2 = tsquery_opr_selec(item + item->operator.left, operand,
 
322
                                                                   lookup, length, minfreq);
 
323
                        selec = s1 + s2 - s1 * s2;
 
324
                        break;
 
325
 
 
326
                default:
 
327
                        elog(ERROR, "unrecognized operator: %d", item->operator.oper);
 
328
                        selec = 0;                      /* keep compiler quiet */
 
329
                        break;
 
330
        }
 
331
 
 
332
        /* Clamp intermediate results to stay sane despite roundoff error */
 
333
        CLAMP_PROBABILITY(selec);
 
334
 
 
335
        return selec;
 
336
}
 
337
 
 
338
/*
 
339
 * bsearch() comparator for a lexeme (non-NULL terminated string with length)
 
340
 * and a TextFreq. Use length, then byte-for-byte comparison, because that's
 
341
 * how ANALYZE code sorted data before storing it in a statistic tuple.
 
342
 * See ts_typanalyze.c for details.
 
343
 */
 
344
static int
 
345
compare_lexeme_textfreq(const void *e1, const void *e2)
 
346
{
 
347
        const LexemeKey *key = (const LexemeKey *) e1;
 
348
        const TextFreq  *t = (const TextFreq *) e2;
 
349
        int                             len1,
 
350
                                        len2;
 
351
 
 
352
        len1 = key->length;
 
353
        len2 = VARSIZE_ANY_EXHDR(t->element);
 
354
 
 
355
        /* Compare lengths first, possibly avoiding a strncmp call */
 
356
        if (len1 > len2)
 
357
                return 1;
 
358
        else if (len1 < len2)
 
359
                return -1;
 
360
 
 
361
        /* Fall back on byte-for-byte comparison */
 
362
        return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
 
363
}