← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« 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: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

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-2011, PostgreSQL Global Development Group
 
7
 *
 
8
 *
 
9
 * IDENTIFICATION
 
10
 *        src/backend/tsearch/ts_selfuncs.c
 
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
#define tsquery_opr_selec_no_stats(query) \
 
56
        tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), NULL, 0, 0)
 
57
 
 
58
 
 
59
/*
 
60
 *      tsmatchsel -- Selectivity of "@@"
 
61
 *
 
62
 * restriction selectivity function for tsvector @@ tsquery and
 
63
 * tsquery @@ tsvector
 
64
 */
 
65
Datum
 
66
tsmatchsel(PG_FUNCTION_ARGS)
 
67
{
 
68
        PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
 
69
 
 
70
#ifdef NOT_USED
 
71
        Oid                     operator = PG_GETARG_OID(1);
 
72
#endif
 
73
        List       *args = (List *) PG_GETARG_POINTER(2);
 
74
        int                     varRelid = PG_GETARG_INT32(3);
 
75
        VariableStatData vardata;
 
76
        Node       *other;
 
77
        bool            varonleft;
 
78
        Selectivity selec;
 
79
 
 
80
        /*
 
81
         * If expression is not variable = something or something = variable, then
 
82
         * punt and return a default estimate.
 
83
         */
 
84
        if (!get_restriction_variable(root, args, varRelid,
 
85
                                                                  &vardata, &other, &varonleft))
 
86
                PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
87
 
 
88
        /*
 
89
         * Can't do anything useful if the something is not a constant, either.
 
90
         */
 
91
        if (!IsA(other, Const))
 
92
        {
 
93
                ReleaseVariableStats(vardata);
 
94
                PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
95
        }
 
96
 
 
97
        /*
 
98
         * The "@@" operator is strict, so we can cope with NULL right away
 
99
         */
 
100
        if (((Const *) other)->constisnull)
 
101
        {
 
102
                ReleaseVariableStats(vardata);
 
103
                PG_RETURN_FLOAT8(0.0);
 
104
        }
 
105
 
 
106
        /*
 
107
         * OK, there's a Var and a Const we're dealing with here.  We need the
 
108
         * Const to be a TSQuery, else we can't do anything useful.  We have to
 
109
         * check this because the Var might be the TSQuery not the TSVector.
 
110
         */
 
111
        if (((Const *) other)->consttype == TSQUERYOID)
 
112
        {
 
113
                /* tsvector @@ tsquery or the other way around */
 
114
                Assert(vardata.vartype == TSVECTOROID);
 
115
 
 
116
                selec = tsquerysel(&vardata, ((Const *) other)->constvalue);
 
117
        }
 
118
        else
 
119
        {
 
120
                /* If we can't see the query structure, must punt */
 
121
                selec = DEFAULT_TS_MATCH_SEL;
 
122
        }
 
123
 
 
124
        ReleaseVariableStats(vardata);
 
125
 
 
126
        CLAMP_PROBABILITY(selec);
 
127
 
 
128
        PG_RETURN_FLOAT8((float8) selec);
 
129
}
 
130
 
 
131
 
 
132
/*
 
133
 *      tsmatchjoinsel -- join selectivity of "@@"
 
134
 *
 
135
 * join selectivity function for tsvector @@ tsquery and tsquery @@ tsvector
 
136
 */
 
137
Datum
 
138
tsmatchjoinsel(PG_FUNCTION_ARGS)
 
139
{
 
140
        /* for the moment we just punt */
 
141
        PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
 
142
}
 
143
 
 
144
 
 
145
/*
 
146
 * @@ selectivity for tsvector var vs tsquery constant
 
147
 */
 
148
static Selectivity
 
149
tsquerysel(VariableStatData *vardata, Datum constval)
 
150
{
 
151
        Selectivity selec;
 
152
        TSQuery         query;
 
153
 
 
154
        /* The caller made sure the const is a TSQuery, so get it now */
 
155
        query = DatumGetTSQuery(constval);
 
156
 
 
157
        /* Empty query matches nothing */
 
158
        if (query->size == 0)
 
159
                return (Selectivity) 0.0;
 
160
 
 
161
        if (HeapTupleIsValid(vardata->statsTuple))
 
162
        {
 
163
                Form_pg_statistic stats;
 
164
                Datum      *values;
 
165
                int                     nvalues;
 
166
                float4     *numbers;
 
167
                int                     nnumbers;
 
168
 
 
169
                stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
 
170
 
 
171
                /* MCELEM will be an array of TEXT elements for a tsvector column */
 
172
                if (get_attstatsslot(vardata->statsTuple,
 
173
                                                         TEXTOID, -1,
 
174
                                                         STATISTIC_KIND_MCELEM, InvalidOid,
 
175
                                                         NULL,
 
176
                                                         &values, &nvalues,
 
177
                                                         &numbers, &nnumbers))
 
178
                {
 
179
                        /*
 
180
                         * There is a most-common-elements slot for the tsvector Var, so
 
181
                         * use that.
 
182
                         */
 
183
                        selec = mcelem_tsquery_selec(query, values, nvalues,
 
184
                                                                                 numbers, nnumbers);
 
185
                        free_attstatsslot(TEXTOID, values, nvalues, numbers, nnumbers);
 
186
                }
 
187
                else
 
188
                {
 
189
                        /* No most-common-elements info, so do without */
 
190
                        selec = tsquery_opr_selec_no_stats(query);
 
191
                }
 
192
 
 
193
                /*
 
194
                 * MCE stats count only non-null rows, so adjust for null rows.
 
195
                 */
 
196
                selec *= (1.0 - stats->stanullfrac);
 
197
        }
 
198
        else
 
199
        {
 
200
                /* No stats at all, so do without */
 
201
                selec = tsquery_opr_selec_no_stats(query);
 
202
                /* we assume no nulls here, so no stanullfrac correction */
 
203
        }
 
204
 
 
205
        return selec;
 
206
}
 
207
 
 
208
/*
 
209
 * Extract data from the pg_statistic arrays into useful format.
 
210
 */
 
211
static Selectivity
 
212
mcelem_tsquery_selec(TSQuery query, Datum *mcelem, int nmcelem,
 
213
                                         float4 *numbers, int nnumbers)
 
214
{
 
215
        float4          minfreq;
 
216
        TextFreq   *lookup;
 
217
        Selectivity selec;
 
218
        int                     i;
 
219
 
 
220
        /*
 
221
         * There should be two more Numbers than Values, because the last two
 
222
         * cells are taken for minimal and maximal frequency.  Punt if not.
 
223
         */
 
224
        if (nnumbers != nmcelem + 2)
 
225
                return tsquery_opr_selec_no_stats(query);
 
226
 
 
227
        /*
 
228
         * Transpose the data into a single array so we can use bsearch().
 
229
         */
 
230
        lookup = (TextFreq *) palloc(sizeof(TextFreq) * nmcelem);
 
231
        for (i = 0; i < nmcelem; i++)
 
232
        {
 
233
                /*
 
234
                 * The text Datums came from an array, so it cannot be compressed or
 
235
                 * stored out-of-line -- it's safe to use VARSIZE_ANY*.
 
236
                 */
 
237
                Assert(!VARATT_IS_COMPRESSED(mcelem[i]) && !VARATT_IS_EXTERNAL(mcelem[i]));
 
238
                lookup[i].element = (text *) DatumGetPointer(mcelem[i]);
 
239
                lookup[i].frequency = numbers[i];
 
240
        }
 
241
 
 
242
        /*
 
243
         * Grab the lowest frequency. compute_tsvector_stats() stored it for us in
 
244
         * the one before the last cell of the Numbers array. See ts_typanalyze.c
 
245
         */
 
246
        minfreq = numbers[nnumbers - 2];
 
247
 
 
248
        selec = tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), lookup,
 
249
                                                          nmcelem, minfreq);
 
250
 
 
251
        pfree(lookup);
 
252
 
 
253
        return selec;
 
254
}
 
255
 
 
256
/*
 
257
 * Traverse the tsquery in preorder, calculating selectivity as:
 
258
 *
 
259
 *       selec(left_oper) * selec(right_oper) in AND nodes,
 
260
 *
 
261
 *       selec(left_oper) + selec(right_oper) -
 
262
 *              selec(left_oper) * selec(right_oper) in OR nodes,
 
263
 *
 
264
 *       1 - select(oper) in NOT nodes
 
265
 *
 
266
 *       histogram-based estimation in prefix VAL nodes
 
267
 *
 
268
 *       freq[val] in exact VAL nodes, if the value is in MCELEM
 
269
 *       min(freq[MCELEM]) / 2 in VAL nodes, if it is not
 
270
 *
 
271
 * The MCELEM array is already sorted (see ts_typanalyze.c), so we can use
 
272
 * binary search for determining freq[MCELEM].
 
273
 *
 
274
 * If we don't have stats for the tsvector, we still use this logic,
 
275
 * except we use default estimates for VAL nodes.  This case is signaled
 
276
 * by lookup == NULL.
 
277
 */
 
278
static Selectivity
 
279
tsquery_opr_selec(QueryItem *item, char *operand,
 
280
                                  TextFreq *lookup, int length, float4 minfreq)
 
281
{
 
282
        Selectivity selec;
 
283
 
 
284
        /* since this function recurses, it could be driven to stack overflow */
 
285
        check_stack_depth();
 
286
 
 
287
        if (item->type == QI_VAL)
 
288
        {
 
289
                QueryOperand *oper = (QueryOperand *) item;
 
290
                LexemeKey       key;
 
291
 
 
292
                /*
 
293
                 * Prepare the key for bsearch().
 
294
                 */
 
295
                key.lexeme = operand + oper->distance;
 
296
                key.length = oper->length;
 
297
 
 
298
                if (oper->prefix)
 
299
                {
 
300
                        /* Prefix match, ie the query item is lexeme:* */
 
301
                        Selectivity matched,
 
302
                                                allmcvs;
 
303
                        int                     i;
 
304
 
 
305
                        /*
 
306
                         * Our strategy is to scan through the MCV list and add up the
 
307
                         * frequencies of the ones that match the prefix, thereby assuming
 
308
                         * that the MCVs are representative of the whole lexeme population
 
309
                         * in this respect.  Compare histogram_selectivity().
 
310
                         *
 
311
                         * This is only a good plan if we have a pretty fair number of
 
312
                         * MCVs available; we set the threshold at 100.  If no stats or
 
313
                         * insufficient stats, arbitrarily use DEFAULT_TS_MATCH_SEL*4.
 
314
                         */
 
315
                        if (lookup == NULL || length < 100)
 
316
                                return (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);
 
317
 
 
318
                        matched = allmcvs = 0;
 
319
                        for (i = 0; i < length; i++)
 
320
                        {
 
321
                                TextFreq   *t = lookup + i;
 
322
                                int                     tlen = VARSIZE_ANY_EXHDR(t->element);
 
323
 
 
324
                                if (tlen >= key.length &&
 
325
                                        strncmp(key.lexeme, VARDATA_ANY(t->element),
 
326
                                                        key.length) == 0)
 
327
                                        matched += t->frequency;
 
328
                                allmcvs += t->frequency;
 
329
                        }
 
330
 
 
331
                        if (allmcvs > 0)        /* paranoia about zero divide */
 
332
                                selec = matched / allmcvs;
 
333
                        else
 
334
                                selec = (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);
 
335
 
 
336
                        /*
 
337
                         * In any case, never believe that a prefix match has selectivity
 
338
                         * less than DEFAULT_TS_MATCH_SEL.
 
339
                         */
 
340
                        selec = Max(DEFAULT_TS_MATCH_SEL, selec);
 
341
                }
 
342
                else
 
343
                {
 
344
                        /* Regular exact lexeme match */
 
345
                        TextFreq   *searchres;
 
346
 
 
347
                        /* If no stats for the variable, use DEFAULT_TS_MATCH_SEL */
 
348
                        if (lookup == NULL)
 
349
                                return (Selectivity) DEFAULT_TS_MATCH_SEL;
 
350
 
 
351
                        searchres = (TextFreq *) bsearch(&key, lookup, length,
 
352
                                                                                         sizeof(TextFreq),
 
353
                                                                                         compare_lexeme_textfreq);
 
354
 
 
355
                        if (searchres)
 
356
                        {
 
357
                                /*
 
358
                                 * The element is in MCELEM.  Return precise selectivity (or
 
359
                                 * at least as precise as ANALYZE could find out).
 
360
                                 */
 
361
                                selec = searchres->frequency;
 
362
                        }
 
363
                        else
 
364
                        {
 
365
                                /*
 
366
                                 * The element is not in MCELEM.  Punt, but assume that the
 
367
                                 * selectivity cannot be more than minfreq / 2.
 
368
                                 */
 
369
                                selec = Min(DEFAULT_TS_MATCH_SEL, minfreq / 2);
 
370
                        }
 
371
                }
 
372
        }
 
373
        else
 
374
        {
 
375
                /* Current TSQuery node is an operator */
 
376
                Selectivity s1,
 
377
                                        s2;
 
378
 
 
379
                switch (item->qoperator.oper)
 
380
                {
 
381
                        case OP_NOT:
 
382
                                selec = 1.0 - tsquery_opr_selec(item + 1, operand,
 
383
                                                                                                lookup, length, minfreq);
 
384
                                break;
 
385
 
 
386
                        case OP_AND:
 
387
                                s1 = tsquery_opr_selec(item + 1, operand,
 
388
                                                                           lookup, length, minfreq);
 
389
                                s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
 
390
                                                                           lookup, length, minfreq);
 
391
                                selec = s1 * s2;
 
392
                                break;
 
393
 
 
394
                        case OP_OR:
 
395
                                s1 = tsquery_opr_selec(item + 1, operand,
 
396
                                                                           lookup, length, minfreq);
 
397
                                s2 = tsquery_opr_selec(item + item->qoperator.left, operand,
 
398
                                                                           lookup, length, minfreq);
 
399
                                selec = s1 + s2 - s1 * s2;
 
400
                                break;
 
401
 
 
402
                        default:
 
403
                                elog(ERROR, "unrecognized operator: %d", item->qoperator.oper);
 
404
                                selec = 0;              /* keep compiler quiet */
 
405
                                break;
 
406
                }
 
407
        }
 
408
 
 
409
        /* Clamp intermediate results to stay sane despite roundoff error */
 
410
        CLAMP_PROBABILITY(selec);
 
411
 
 
412
        return selec;
 
413
}
 
414
 
 
415
/*
 
416
 * bsearch() comparator for a lexeme (non-NULL terminated string with length)
 
417
 * and a TextFreq. Use length, then byte-for-byte comparison, because that's
 
418
 * how ANALYZE code sorted data before storing it in a statistic tuple.
 
419
 * See ts_typanalyze.c for details.
 
420
 */
 
421
static int
 
422
compare_lexeme_textfreq(const void *e1, const void *e2)
 
423
{
 
424
        const LexemeKey *key = (const LexemeKey *) e1;
 
425
        const TextFreq *t = (const TextFreq *) e2;
 
426
        int                     len1,
 
427
                                len2;
 
428
 
 
429
        len1 = key->length;
 
430
        len2 = VARSIZE_ANY_EXHDR(t->element);
 
431
 
 
432
        /* Compare lengths first, possibly avoiding a strncmp call */
 
433
        if (len1 > len2)
 
434
                return 1;
 
435
        else if (len1 < len2)
 
436
                return -1;
 
437
 
 
438
        /* Fall back on byte-for-byte comparison */
 
439
        return strncmp(key->lexeme, VARDATA_ANY(t->element), len1);
 
440
}