Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * tsrank.c
4 : : * rank tsvector by tsquery
5 : : *
6 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 : : *
8 : : *
9 : : * IDENTIFICATION
10 : : * src/backend/utils/adt/tsrank.c
11 : : *
12 : : *-------------------------------------------------------------------------
13 : : */
14 : : #include "postgres.h"
15 : :
16 : : #include <limits.h>
17 : : #include <math.h>
18 : :
19 : : #include "miscadmin.h"
20 : : #include "tsearch/ts_utils.h"
21 : : #include "utils/array.h"
22 : : #include "utils/fmgrprotos.h"
23 : :
24 : : static const float weights[] = {0.1f, 0.2f, 0.4f, 1.0f};
25 : :
26 : : #define wpos(wep) ( w[ WEP_GETWEIGHT(wep) ] )
27 : :
28 : : #define RANK_NO_NORM 0x00
29 : : #define RANK_NORM_LOGLENGTH 0x01
30 : : #define RANK_NORM_LENGTH 0x02
31 : : #define RANK_NORM_EXTDIST 0x04
32 : : #define RANK_NORM_UNIQ 0x08
33 : : #define RANK_NORM_LOGUNIQ 0x10
34 : : #define RANK_NORM_RDIVRPLUS1 0x20
35 : : #define DEF_NORM_METHOD RANK_NO_NORM
36 : :
37 : : static float calc_rank_or(const float *w, TSVector t, TSQuery q);
38 : : static float calc_rank_and(const float *w, TSVector t, TSQuery q);
39 : :
40 : : /*
41 : : * Returns a weight of a word collocation
42 : : */
43 : : static float4
4311 peter_e@gmx.net 44 :CBC 9 : word_distance(int32 w)
45 : : {
6081 tgl@sss.pgh.pa.us 46 [ - + ]: 9 : if (w > 100)
6051 teodor@sigaev.ru 47 :UBC 0 : return 1e-30f;
48 : :
6081 tgl@sss.pgh.pa.us 49 :CBC 9 : return 1.0 / (1.005 + 0.05 * exp(((float4) w) / 1.5 - 2));
50 : : }
51 : :
52 : : static int
6081 tgl@sss.pgh.pa.us 53 :UBC 0 : cnt_length(TSVector t)
54 : : {
55 : 0 : WordEntry *ptr = ARRPTR(t),
56 : 0 : *end = (WordEntry *) STRPTR(t);
6060 teodor@sigaev.ru 57 : 0 : int len = 0;
58 : :
6081 tgl@sss.pgh.pa.us 59 [ # # ]: 0 : while (ptr < end)
60 : : {
5995 bruce@momjian.us 61 [ # # ]: 0 : int clen = POSDATALEN(t, ptr);
62 : :
6060 teodor@sigaev.ru 63 [ # # ]: 0 : if (clen == 0)
6081 tgl@sss.pgh.pa.us 64 : 0 : len += 1;
65 : : else
66 : 0 : len += clen;
67 : :
68 : 0 : ptr++;
69 : : }
70 : :
71 : 0 : return len;
72 : : }
73 : :
74 : :
75 : : #define WordECompareQueryItem(e,q,p,i,m) \
76 : : tsCompareString((q) + (i)->distance, (i)->length, \
77 : : (e) + (p)->pos, (p)->len, (m))
78 : :
79 : :
80 : : /*
81 : : * Returns a pointer to a WordEntry's array corresponding to 'item' from
82 : : * tsvector 't'. 'q' is the TSQuery containing 'item'.
83 : : * Returns NULL if not found.
84 : : */
85 : : static WordEntry *
5812 tgl@sss.pgh.pa.us 86 :CBC 213 : find_wordentry(TSVector t, TSQuery q, QueryOperand *item, int32 *nitem)
87 : : {
6081 88 : 213 : WordEntry *StopLow = ARRPTR(t);
89 : 213 : WordEntry *StopHigh = (WordEntry *) STRPTR(t);
5812 90 : 213 : WordEntry *StopMiddle = StopHigh;
91 : : int difference;
92 : :
5421 bruce@momjian.us 93 : 213 : *nitem = 0;
94 : :
95 : : /* Loop invariant: StopLow <= item < StopHigh */
6081 tgl@sss.pgh.pa.us 96 [ + + ]: 573 : while (StopLow < StopHigh)
97 : : {
98 : 549 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
5812 99 : 549 : difference = WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, false);
6081 100 [ + + ]: 549 : if (difference == 0)
101 : : {
5812 102 : 189 : StopHigh = StopMiddle;
5421 bruce@momjian.us 103 : 189 : *nitem = 1;
5812 tgl@sss.pgh.pa.us 104 : 189 : break;
105 : : }
106 [ + + ]: 360 : else if (difference > 0)
6081 107 : 126 : StopLow = StopMiddle + 1;
108 : : else
109 : 234 : StopHigh = StopMiddle;
110 : : }
111 : :
4900 rhaas@postgresql.org 112 [ + + ]: 213 : if (item->prefix)
113 : : {
5421 bruce@momjian.us 114 [ + - ]: 27 : if (StopLow >= StopHigh)
5812 tgl@sss.pgh.pa.us 115 : 27 : StopMiddle = StopHigh;
116 : :
5421 bruce@momjian.us 117 : 27 : *nitem = 0;
118 : :
119 [ + + + - ]: 111 : while (StopMiddle < (WordEntry *) STRPTR(t) &&
120 : 42 : WordECompareQueryItem(STRPTR(t), GETOPERAND(q), StopMiddle, item, true) == 0)
121 : : {
5812 tgl@sss.pgh.pa.us 122 : 42 : (*nitem)++;
123 : 42 : StopMiddle++;
124 : : }
125 : : }
126 : :
5421 bruce@momjian.us 127 [ + + ]: 213 : return (*nitem > 0) ? StopHigh : NULL;
128 : : }
129 : :
130 : :
131 : : /*
132 : : * sort QueryOperands by (length, word)
133 : : */
134 : : static int
6064 teodor@sigaev.ru 135 : 54 : compareQueryOperand(const void *a, const void *b, void *arg)
136 : : {
6081 tgl@sss.pgh.pa.us 137 : 54 : char *operand = (char *) arg;
4326 bruce@momjian.us 138 : 54 : QueryOperand *qa = (*(QueryOperand *const *) a);
139 : 54 : QueryOperand *qb = (*(QueryOperand *const *) b);
140 : :
5812 tgl@sss.pgh.pa.us 141 : 108 : return tsCompareString(operand + qa->distance, qa->length,
142 : 54 : operand + qb->distance, qb->length,
143 : : false);
144 : : }
145 : :
146 : : /*
147 : : * Returns a sorted, de-duplicated array of QueryOperands in a query.
148 : : * The returned QueryOperands are pointers to the original QueryOperands
149 : : * in the query.
150 : : *
151 : : * Length of the returned array is stored in *size
152 : : */
153 : : static QueryOperand **
6064 teodor@sigaev.ru 154 : 27 : SortAndUniqItems(TSQuery q, int *size)
155 : : {
5995 bruce@momjian.us 156 : 27 : char *operand = GETOPERAND(q);
157 : 27 : QueryItem *item = GETQUERY(q);
158 : : QueryOperand **res,
159 : : **ptr,
160 : : **prevptr;
161 : :
6064 teodor@sigaev.ru 162 : 27 : ptr = res = (QueryOperand **) palloc(sizeof(QueryOperand *) * *size);
163 : :
164 : : /* Collect all operands from the tree to res */
6081 tgl@sss.pgh.pa.us 165 [ + + ]: 108 : while ((*size)--)
166 : : {
6064 teodor@sigaev.ru 167 [ + + ]: 81 : if (item->type == QI_VAL)
168 : : {
169 : 54 : *ptr = (QueryOperand *) item;
6081 tgl@sss.pgh.pa.us 170 : 54 : ptr++;
171 : : }
172 : 81 : item++;
173 : : }
174 : :
175 : 27 : *size = ptr - res;
176 [ - + ]: 27 : if (*size < 2)
6081 tgl@sss.pgh.pa.us 177 :UBC 0 : return res;
178 : :
432 peter@eisentraut.org 179 :CBC 27 : qsort_arg(res, *size, sizeof(QueryOperand *), compareQueryOperand, operand);
180 : :
6081 tgl@sss.pgh.pa.us 181 : 27 : ptr = res + 1;
182 : 27 : prevptr = res;
183 : :
184 : : /* remove duplicates */
185 [ + + ]: 54 : while (ptr - res < *size)
186 : : {
6064 teodor@sigaev.ru 187 [ + - ]: 27 : if (compareQueryOperand((void *) ptr, (void *) prevptr, (void *) operand) != 0)
188 : : {
6081 tgl@sss.pgh.pa.us 189 : 27 : prevptr++;
190 : 27 : *prevptr = *ptr;
191 : : }
192 : 27 : ptr++;
193 : : }
194 : :
195 : 27 : *size = prevptr + 1 - res;
196 : 27 : return res;
197 : : }
198 : :
199 : : static float
3739 200 : 9 : calc_rank_and(const float *w, TSVector t, TSQuery q)
201 : : {
202 : : WordEntryPosVector **pos;
203 : : WordEntryPosVector1 posnull;
204 : : WordEntryPosVector *POSNULL;
205 : : int i,
206 : : k,
207 : : l,
208 : : p;
209 : : WordEntry *entry,
210 : : *firstentry;
211 : : WordEntryPos *post,
212 : : *ct;
213 : : int32 dimt,
214 : : lenct,
215 : : dist,
216 : : nitem;
6081 217 : 9 : float res = -1.0;
218 : : QueryOperand **item;
219 : 9 : int size = q->size;
220 : :
6064 teodor@sigaev.ru 221 : 9 : item = SortAndUniqItems(q, &size);
6081 tgl@sss.pgh.pa.us 222 [ - + ]: 9 : if (size < 2)
223 : : {
6081 tgl@sss.pgh.pa.us 224 :UBC 0 : pfree(item);
225 : 0 : return calc_rank_or(w, t, q);
226 : : }
6060 teodor@sigaev.ru 227 :CBC 9 : pos = (WordEntryPosVector **) palloc0(sizeof(WordEntryPosVector *) * q->size);
228 : :
229 : : /* A dummy WordEntryPos array to use when haspos is false */
3341 tgl@sss.pgh.pa.us 230 : 9 : posnull.npos = 1;
231 : 9 : posnull.pos[0] = 0;
232 : 9 : WEP_SETPOS(posnull.pos[0], MAXENTRYPOS - 1);
233 : 9 : POSNULL = (WordEntryPosVector *) &posnull;
234 : :
6081 235 [ + + ]: 27 : for (i = 0; i < size; i++)
236 : : {
5812 237 : 18 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
6081 238 [ - + ]: 18 : if (!entry)
6081 tgl@sss.pgh.pa.us 239 :UBC 0 : continue;
240 : :
5421 bruce@momjian.us 241 [ + + ]:CBC 36 : while (entry - firstentry < nitem)
242 : : {
5812 tgl@sss.pgh.pa.us 243 [ + - ]: 18 : if (entry->haspos)
244 : 18 : pos[i] = _POSVECPTR(t, entry);
245 : : else
3341 tgl@sss.pgh.pa.us 246 :UBC 0 : pos[i] = POSNULL;
247 : :
5812 tgl@sss.pgh.pa.us 248 :CBC 18 : dimt = pos[i]->npos;
249 : 18 : post = pos[i]->pos;
250 [ + + ]: 27 : for (k = 0; k < i; k++)
251 : : {
252 [ - + ]: 9 : if (!pos[k])
5812 tgl@sss.pgh.pa.us 253 :UBC 0 : continue;
5812 tgl@sss.pgh.pa.us 254 :CBC 9 : lenct = pos[k]->npos;
255 : 9 : ct = pos[k]->pos;
256 [ + + ]: 18 : for (l = 0; l < dimt; l++)
257 : : {
258 [ + + ]: 18 : for (p = 0; p < lenct; p++)
259 : : {
555 peter@eisentraut.org 260 : 9 : dist = abs((int) WEP_GETPOS(post[l]) - (int) WEP_GETPOS(ct[p]));
3341 tgl@sss.pgh.pa.us 261 [ - + - - : 9 : if (dist || (dist == 0 && (pos[i] == POSNULL || pos[k] == POSNULL)))
- - - - ]
262 : : {
263 : : float curw;
264 : :
5812 265 [ - + ]: 9 : if (!dist)
5812 tgl@sss.pgh.pa.us 266 :UBC 0 : dist = MAXENTRYPOS;
5812 tgl@sss.pgh.pa.us 267 :CBC 9 : curw = sqrt(wpos(post[l]) * wpos(ct[p]) * word_distance(dist));
268 [ + - ]: 9 : res = (res < 0) ? curw : 1.0 - (1.0 - res) * (1.0 - curw);
269 : : }
270 : : }
271 : : }
272 : : }
273 : :
274 : 18 : entry++;
275 : : }
276 : : }
6081 277 : 9 : pfree(pos);
278 : 9 : pfree(item);
279 : 9 : return res;
280 : : }
281 : :
282 : : static float
3739 283 : 18 : calc_rank_or(const float *w, TSVector t, TSQuery q)
284 : : {
285 : : WordEntry *entry,
286 : : *firstentry;
287 : : WordEntryPosVector1 posnull;
288 : : WordEntryPos *post;
289 : : int32 dimt,
290 : : j,
291 : : i,
292 : : nitem;
6081 293 : 18 : float res = 0.0;
294 : : QueryOperand **item;
295 : 18 : int size = q->size;
296 : :
297 : : /* A dummy WordEntryPos array to use when haspos is false */
3341 298 : 18 : posnull.npos = 1;
299 : 18 : posnull.pos[0] = 0;
300 : :
6064 teodor@sigaev.ru 301 : 18 : item = SortAndUniqItems(q, &size);
302 : :
6081 tgl@sss.pgh.pa.us 303 [ + + ]: 54 : for (i = 0; i < size; i++)
304 : : {
305 : : float resj,
306 : : wjm;
307 : : int32 jm;
308 : :
5812 309 : 36 : firstentry = entry = find_wordentry(t, q, item[i], &nitem);
6081 310 [ + + ]: 36 : if (!entry)
311 : 3 : continue;
312 : :
5421 bruce@momjian.us 313 [ + + ]: 66 : while (entry - firstentry < nitem)
314 : : {
5812 tgl@sss.pgh.pa.us 315 [ + - ]: 33 : if (entry->haspos)
316 : : {
317 [ + - ]: 33 : dimt = POSDATALEN(t, entry);
318 : 33 : post = POSDATAPTR(t, entry);
319 : : }
320 : : else
321 : : {
3341 tgl@sss.pgh.pa.us 322 :UBC 0 : dimt = posnull.npos;
323 : 0 : post = posnull.pos;
324 : : }
325 : :
5812 tgl@sss.pgh.pa.us 326 :CBC 33 : resj = 0.0;
327 : 33 : wjm = -1.0;
328 : 33 : jm = 0;
329 [ + + ]: 66 : for (j = 0; j < dimt; j++)
330 : : {
331 : 33 : resj = resj + wpos(post[j]) / ((j + 1) * (j + 1));
332 [ + - ]: 33 : if (wpos(post[j]) > wjm)
333 : : {
334 : 33 : wjm = wpos(post[j]);
335 : 33 : jm = j;
336 : : }
337 : : }
338 : : /*
339 : : limit (sum(1/i^2),i=1,inf) = pi^2/6
340 : : resj = sum(wi/i^2),i=1,noccurrence,
341 : : wi - should be sorted desc,
342 : : don't sort for now, just choose maximum weight. This should be corrected
343 : : Oleg Bartunov
344 : : */
345 : 33 : res = res + (wjm + resj - wjm / ((jm + 1) * (jm + 1))) / 1.64493406685;
346 : :
347 : 33 : entry++;
348 : : }
349 : : }
6081 350 [ + - ]: 18 : if (size > 0)
351 : 18 : res = res / size;
352 : 18 : pfree(item);
353 : 18 : return res;
354 : : }
355 : :
356 : : static float
3739 357 : 27 : calc_rank(const float *w, TSVector t, TSQuery q, int32 method)
358 : : {
6081 359 : 27 : QueryItem *item = GETQUERY(q);
360 : 27 : float res = 0.0;
361 : : int len;
362 : :
363 [ + - - + ]: 27 : if (!t->size || !q->size)
6081 tgl@sss.pgh.pa.us 364 :UBC 0 : return 0.0;
365 : :
366 : : /* XXX: What about NOT? */
2929 teodor@sigaev.ru 367 [ + + ]:CBC 27 : res = (item->type == QI_OPR && (item->qoperator.oper == OP_AND ||
368 [ - + ]: 18 : item->qoperator.oper == OP_PHRASE)) ?
2866 rhaas@postgresql.org 369 [ + - ]: 36 : calc_rank_and(w, t, q) :
370 : 18 : calc_rank_or(w, t, q);
371 : :
6081 tgl@sss.pgh.pa.us 372 [ - + ]: 27 : if (res < 0)
6051 teodor@sigaev.ru 373 :UBC 0 : res = 1e-20f;
374 : :
6081 tgl@sss.pgh.pa.us 375 [ - + - - ]:CBC 27 : if ((method & RANK_NORM_LOGLENGTH) && t->size > 0)
6081 tgl@sss.pgh.pa.us 376 :UBC 0 : res /= log((double) (cnt_length(t) + 1)) / log(2.0);
377 : :
6081 tgl@sss.pgh.pa.us 378 [ - + ]:CBC 27 : if (method & RANK_NORM_LENGTH)
379 : : {
6081 tgl@sss.pgh.pa.us 380 :UBC 0 : len = cnt_length(t);
381 [ # # ]: 0 : if (len > 0)
382 : 0 : res /= (float) len;
383 : : }
384 : :
385 : : /* RANK_NORM_EXTDIST not applicable */
386 : :
6081 tgl@sss.pgh.pa.us 387 [ - + - - ]:CBC 27 : if ((method & RANK_NORM_UNIQ) && t->size > 0)
6081 tgl@sss.pgh.pa.us 388 :UBC 0 : res /= (float) (t->size);
389 : :
6081 tgl@sss.pgh.pa.us 390 [ - + - - ]:CBC 27 : if ((method & RANK_NORM_LOGUNIQ) && t->size > 0)
6081 tgl@sss.pgh.pa.us 391 :UBC 0 : res /= log((double) (t->size + 1)) / log(2.0);
392 : :
5996 tgl@sss.pgh.pa.us 393 [ - + ]:CBC 27 : if (method & RANK_NORM_RDIVRPLUS1)
5996 tgl@sss.pgh.pa.us 394 :UBC 0 : res /= (res + 1);
395 : :
6081 tgl@sss.pgh.pa.us 396 :CBC 27 : return res;
397 : : }
398 : :
399 : : static const float *
400 : 105 : getWeights(ArrayType *win)
401 : : {
402 : : static float ws[lengthof(weights)];
403 : : int i;
404 : : float4 *arrdata;
405 : :
4916 406 [ + - ]: 105 : if (win == NULL)
6081 407 : 105 : return weights;
408 : :
6081 tgl@sss.pgh.pa.us 409 [ # # ]:UBC 0 : if (ARR_NDIM(win) != 1)
410 [ # # ]: 0 : ereport(ERROR,
411 : : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
412 : : errmsg("array of weight must be one-dimensional")));
413 : :
414 [ # # ]: 0 : if (ArrayGetNItems(ARR_NDIM(win), ARR_DIMS(win)) < lengthof(weights))
415 [ # # ]: 0 : ereport(ERROR,
416 : : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
417 : : errmsg("array of weight is too short")));
418 : :
4844 419 [ # # ]: 0 : if (array_contains_nulls(win))
6081 420 [ # # ]: 0 : ereport(ERROR,
421 : : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
422 : : errmsg("array of weight must not contain nulls")));
423 : :
424 [ # # ]: 0 : arrdata = (float4 *) ARR_DATA_PTR(win);
425 [ # # ]: 0 : for (i = 0; i < lengthof(weights); i++)
426 : : {
427 [ # # ]: 0 : ws[i] = (arrdata[i] >= 0) ? arrdata[i] : weights[i];
428 [ # # ]: 0 : if (ws[i] > 1.0)
429 [ # # ]: 0 : ereport(ERROR,
430 : : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
431 : : errmsg("weight out of range")));
432 : : }
433 : :
434 : 0 : return ws;
435 : : }
436 : :
437 : : Datum
438 : 0 : ts_rank_wttf(PG_FUNCTION_ARGS)
439 : : {
440 : 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
441 : 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
442 : 0 : TSQuery query = PG_GETARG_TSQUERY(2);
443 : 0 : int method = PG_GETARG_INT32(3);
444 : : float res;
445 : :
446 : 0 : res = calc_rank(getWeights(win), txt, query, method);
447 : :
448 [ # # ]: 0 : PG_FREE_IF_COPY(win, 0);
449 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 1);
450 [ # # ]: 0 : PG_FREE_IF_COPY(query, 2);
451 : 0 : PG_RETURN_FLOAT4(res);
452 : : }
453 : :
454 : : Datum
455 : 0 : ts_rank_wtt(PG_FUNCTION_ARGS)
456 : : {
457 : 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
458 : 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
459 : 0 : TSQuery query = PG_GETARG_TSQUERY(2);
460 : : float res;
461 : :
462 : 0 : res = calc_rank(getWeights(win), txt, query, DEF_NORM_METHOD);
463 : :
464 [ # # ]: 0 : PG_FREE_IF_COPY(win, 0);
465 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 1);
466 [ # # ]: 0 : PG_FREE_IF_COPY(query, 2);
467 : 0 : PG_RETURN_FLOAT4(res);
468 : : }
469 : :
470 : : Datum
471 : 0 : ts_rank_ttf(PG_FUNCTION_ARGS)
472 : : {
473 : 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
474 : 0 : TSQuery query = PG_GETARG_TSQUERY(1);
475 : 0 : int method = PG_GETARG_INT32(2);
476 : : float res;
477 : :
478 : 0 : res = calc_rank(getWeights(NULL), txt, query, method);
479 : :
480 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 0);
481 [ # # ]: 0 : PG_FREE_IF_COPY(query, 1);
482 : 0 : PG_RETURN_FLOAT4(res);
483 : : }
484 : :
485 : : Datum
6081 tgl@sss.pgh.pa.us 486 :CBC 27 : ts_rank_tt(PG_FUNCTION_ARGS)
487 : : {
488 : 27 : TSVector txt = PG_GETARG_TSVECTOR(0);
489 : 27 : TSQuery query = PG_GETARG_TSQUERY(1);
490 : : float res;
491 : :
492 : 27 : res = calc_rank(getWeights(NULL), txt, query, DEF_NORM_METHOD);
493 : :
494 [ - + ]: 27 : PG_FREE_IF_COPY(txt, 0);
495 [ - + ]: 27 : PG_FREE_IF_COPY(query, 1);
496 : 27 : PG_RETURN_FLOAT4(res);
497 : : }
498 : :
499 : : typedef struct
500 : : {
501 : : union
502 : : {
503 : : struct
504 : : { /* compiled doc representation */
505 : : QueryItem **items;
506 : : int16 nitem;
507 : : } query;
508 : : struct
509 : : { /* struct is used for preparing doc
510 : : * representation */
511 : : QueryItem *item;
512 : : WordEntry *entry;
513 : : } map;
514 : : } data;
515 : : WordEntryPos pos;
516 : : } DocRepresentation;
517 : :
518 : : static int
6060 teodor@sigaev.ru 519 : 174 : compareDocR(const void *va, const void *vb)
520 : : {
4599 peter_e@gmx.net 521 : 174 : const DocRepresentation *a = (const DocRepresentation *) va;
522 : 174 : const DocRepresentation *b = (const DocRepresentation *) vb;
523 : :
2929 teodor@sigaev.ru 524 [ + + ]: 174 : if (WEP_GETPOS(a->pos) == WEP_GETPOS(b->pos))
525 : : {
526 [ + + ]: 18 : if (WEP_GETWEIGHT(a->pos) == WEP_GETWEIGHT(b->pos))
527 : : {
528 [ + - ]: 3 : if (a->data.map.entry == b->data.map.entry)
529 : 3 : return 0;
530 : :
2929 teodor@sigaev.ru 531 [ # # ]:UBC 0 : return (a->data.map.entry > b->data.map.entry) ? 1 : -1;
532 : : }
533 : :
2929 teodor@sigaev.ru 534 [ + + ]:CBC 15 : return (WEP_GETWEIGHT(a->pos) > WEP_GETWEIGHT(b->pos)) ? 1 : -1;
535 : : }
536 : :
537 [ + + ]: 156 : return (WEP_GETPOS(a->pos) > WEP_GETPOS(b->pos)) ? 1 : -1;
538 : : }
539 : :
540 : : #define MAXQROPOS MAXENTRYPOS
541 : : typedef struct
542 : : {
543 : : bool operandexists;
544 : : bool reverseinsert; /* indicates insert order, true means
545 : : * descending order */
546 : : uint32 npos;
547 : : WordEntryPos pos[MAXQROPOS];
548 : : } QueryRepresentationOperand;
549 : :
550 : : typedef struct
551 : : {
552 : : TSQuery query;
553 : : QueryRepresentationOperand *operandData;
554 : : } QueryRepresentation;
555 : :
556 : : #define QR_GET_OPERAND_DATA(q, v) \
557 : : ( (q)->operandData + (((QueryItem*)(v)) - GETQUERY((q)->query)) )
558 : :
559 : : /*
560 : : * TS_execute callback for matching a tsquery operand to QueryRepresentation
561 : : */
562 : : static TSTernaryValue
1360 tgl@sss.pgh.pa.us 563 : 579 : checkcondition_QueryOperand(void *checkval, QueryOperand *val,
564 : : ExecPhraseData *data)
565 : : {
2866 rhaas@postgresql.org 566 : 579 : QueryRepresentation *qr = (QueryRepresentation *) checkval;
567 : 579 : QueryRepresentationOperand *opData = QR_GET_OPERAND_DATA(qr, val);
568 : :
2929 teodor@sigaev.ru 569 [ + + ]: 579 : if (!opData->operandexists)
1360 tgl@sss.pgh.pa.us 570 : 222 : return TS_NO;
571 : :
2929 teodor@sigaev.ru 572 [ + + ]: 357 : if (data)
573 : : {
574 : 174 : data->npos = opData->npos;
575 : 174 : data->pos = opData->pos;
576 [ + + ]: 174 : if (opData->reverseinsert)
577 : 54 : data->pos += MAXQROPOS - opData->npos;
578 : : }
579 : :
1360 tgl@sss.pgh.pa.us 580 : 357 : return TS_YES;
581 : : }
582 : :
583 : : typedef struct
584 : : {
585 : : int pos;
586 : : int p;
587 : : int q;
588 : : DocRepresentation *begin;
589 : : DocRepresentation *end;
590 : : } CoverExt;
591 : :
592 : : static void
2929 teodor@sigaev.ru 593 : 249 : resetQueryRepresentation(QueryRepresentation *qr, bool reverseinsert)
594 : : {
595 : : int i;
596 : :
2866 rhaas@postgresql.org 597 [ + + ]: 1008 : for (i = 0; i < qr->query->size; i++)
598 : : {
2929 teodor@sigaev.ru 599 : 759 : qr->operandData[i].operandexists = false;
600 : 759 : qr->operandData[i].reverseinsert = reverseinsert;
601 : 759 : qr->operandData[i].npos = 0;
602 : : }
603 : 249 : }
604 : :
605 : : static void
606 : 360 : fillQueryRepresentationData(QueryRepresentation *qr, DocRepresentation *entry)
607 : : {
608 : : int i;
609 : : int lastPos;
610 : : QueryRepresentationOperand *opData;
611 : :
612 [ + + ]: 723 : for (i = 0; i < entry->data.query.nitem; i++)
613 : : {
614 [ - + ]: 363 : if (entry->data.query.items[i]->type != QI_VAL)
2929 teodor@sigaev.ru 615 :UBC 0 : continue;
616 : :
2929 teodor@sigaev.ru 617 :CBC 363 : opData = QR_GET_OPERAND_DATA(qr, entry->data.query.items[i]);
618 : :
619 : 363 : opData->operandexists = true;
620 : :
621 [ + + ]: 363 : if (opData->npos == 0)
622 : : {
623 [ + + ]: 330 : lastPos = (opData->reverseinsert) ? (MAXQROPOS - 1) : 0;
624 : 330 : opData->pos[lastPos] = entry->pos;
625 : 330 : opData->npos++;
626 : 330 : continue;
627 : : }
628 : :
629 : 66 : lastPos = opData->reverseinsert ?
2866 rhaas@postgresql.org 630 [ - + ]: 33 : (MAXQROPOS - opData->npos) :
631 : 33 : (opData->npos - 1);
632 : :
2929 teodor@sigaev.ru 633 [ + + ]: 33 : if (WEP_GETPOS(opData->pos[lastPos]) != WEP_GETPOS(entry->pos))
634 : : {
635 : 42 : lastPos = opData->reverseinsert ?
2866 rhaas@postgresql.org 636 [ - + ]: 21 : (MAXQROPOS - 1 - opData->npos) :
637 : 21 : (opData->npos);
638 : :
2929 teodor@sigaev.ru 639 : 21 : opData->pos[lastPos] = entry->pos;
640 : 21 : opData->npos++;
641 : : }
642 : : }
643 : 360 : }
644 : :
645 : : static bool
3970 sfrost@snowman.net 646 : 162 : Cover(DocRepresentation *doc, int len, QueryRepresentation *qr, CoverExt *ext)
647 : : {
648 : : DocRepresentation *ptr;
2866 rhaas@postgresql.org 649 : 162 : int lastpos = ext->pos;
650 : 162 : bool found = false;
651 : :
652 : : /*
653 : : * since this function recurses, it could be driven to stack overflow.
654 : : * (though any decent compiler will optimize away the tail-recursion.
655 : : */
6064 teodor@sigaev.ru 656 : 162 : check_stack_depth();
657 : :
2929 658 : 162 : resetQueryRepresentation(qr, false);
659 : :
3308 andres@anarazel.de 660 : 162 : ext->p = INT_MAX;
6081 tgl@sss.pgh.pa.us 661 : 162 : ext->q = 0;
662 : 162 : ptr = doc + ext->pos;
663 : :
664 : : /* find upper bound of cover from current position, move up */
665 [ + + ]: 303 : while (ptr - doc < len)
666 : : {
2929 teodor@sigaev.ru 667 : 228 : fillQueryRepresentationData(qr, ptr);
668 : :
2848 669 [ + + ]: 228 : if (TS_execute(GETQUERY(qr->query), (void *) qr,
670 : : TS_EXEC_EMPTY, checkcondition_QueryOperand))
671 : : {
2929 672 [ + - ]: 87 : if (WEP_GETPOS(ptr->pos) > ext->q)
673 : : {
674 : 87 : ext->q = WEP_GETPOS(ptr->pos);
6081 tgl@sss.pgh.pa.us 675 : 87 : ext->end = ptr;
676 : 87 : lastpos = ptr - doc;
677 : 87 : found = true;
678 : : }
679 : 87 : break;
680 : : }
681 : 141 : ptr++;
682 : : }
683 : :
684 [ + + ]: 162 : if (!found)
685 : 75 : return false;
686 : :
2929 teodor@sigaev.ru 687 : 87 : resetQueryRepresentation(qr, true);
688 : :
6081 tgl@sss.pgh.pa.us 689 : 87 : ptr = doc + lastpos;
690 : :
691 : : /* find lower bound of cover from found upper bound, move down */
692 [ + - ]: 132 : while (ptr >= doc + ext->pos)
693 : : {
694 : : /*
695 : : * we scan doc from right to left, so pos info in reverse order!
696 : : */
2929 teodor@sigaev.ru 697 : 132 : fillQueryRepresentationData(qr, ptr);
698 : :
2848 699 [ + + ]: 132 : if (TS_execute(GETQUERY(qr->query), (void *) qr,
700 : : TS_EXEC_EMPTY, checkcondition_QueryOperand))
701 : : {
2929 702 [ + - ]: 87 : if (WEP_GETPOS(ptr->pos) < ext->p)
703 : : {
6081 tgl@sss.pgh.pa.us 704 : 87 : ext->begin = ptr;
2929 teodor@sigaev.ru 705 : 87 : ext->p = WEP_GETPOS(ptr->pos);
706 : : }
6081 tgl@sss.pgh.pa.us 707 : 87 : break;
708 : : }
709 : 45 : ptr--;
710 : : }
711 : :
712 [ + - ]: 87 : if (ext->p <= ext->q)
713 : : {
714 : : /*
715 : : * set position for next try to next lexeme after beginning of found
716 : : * cover
717 : : */
718 : 87 : ext->pos = (ptr - doc) + 1;
719 : 87 : return true;
720 : : }
721 : :
6081 tgl@sss.pgh.pa.us 722 :UBC 0 : ext->pos++;
6060 teodor@sigaev.ru 723 : 0 : return Cover(doc, len, qr, ext);
724 : : }
725 : :
726 : : static DocRepresentation *
5995 bruce@momjian.us 727 :CBC 78 : get_docrep(TSVector txt, QueryRepresentation *qr, int *doclen)
728 : : {
6060 teodor@sigaev.ru 729 : 78 : QueryItem *item = GETQUERY(qr->query);
730 : : WordEntry *entry,
731 : : *firstentry;
732 : : WordEntryPos *post;
733 : : int32 dimt, /* number of 'post' items */
734 : : j,
735 : : i,
736 : : nitem;
737 : 78 : int len = qr->query->size * 4,
6081 tgl@sss.pgh.pa.us 738 : 78 : cur = 0;
739 : : DocRepresentation *doc;
740 : :
741 : 78 : doc = (DocRepresentation *) palloc(sizeof(DocRepresentation) * len);
742 : :
743 : : /*
744 : : * Iterate through query to make DocRepresentation for words and it's
745 : : * entries satisfied by query
746 : : */
6060 teodor@sigaev.ru 747 [ + + ]: 318 : for (i = 0; i < qr->query->size; i++)
748 : : {
749 : : QueryOperand *curoperand;
750 : :
6064 751 [ + + ]: 240 : if (item[i].type != QI_VAL)
752 : 81 : continue;
753 : :
5386 peter_e@gmx.net 754 : 159 : curoperand = &item[i].qoperand;
755 : :
5812 tgl@sss.pgh.pa.us 756 : 159 : firstentry = entry = find_wordentry(txt, qr->query, curoperand, &nitem);
6081 757 [ + + ]: 159 : if (!entry)
758 : 3 : continue;
759 : :
760 : : /* iterations over entries in tsvector */
5421 bruce@momjian.us 761 [ + + ]: 327 : while (entry - firstentry < nitem)
762 : : {
5812 tgl@sss.pgh.pa.us 763 [ + + ]: 171 : if (entry->haspos)
764 : : {
765 [ + - ]: 165 : dimt = POSDATALEN(txt, entry);
766 : 165 : post = POSDATAPTR(txt, entry);
767 : : }
768 : : else
769 : : {
770 : : /* ignore words without positions */
3674 bruce@momjian.us 771 : 6 : entry++;
772 : 6 : continue;
773 : : }
774 : :
5812 tgl@sss.pgh.pa.us 775 [ - + ]: 165 : while (cur + dimt >= len)
776 : : {
5812 tgl@sss.pgh.pa.us 777 :UBC 0 : len *= 2;
778 : 0 : doc = (DocRepresentation *) repalloc(doc, sizeof(DocRepresentation) * len);
779 : : }
780 : :
781 : : /* iterations over entry's positions */
5812 tgl@sss.pgh.pa.us 782 [ + + ]:CBC 357 : for (j = 0; j < dimt; j++)
783 : : {
2929 teodor@sigaev.ru 784 [ + + ]: 192 : if (curoperand->weight == 0 ||
785 [ + + ]: 15 : curoperand->weight & (1 << WEP_GETWEIGHT(post[j])))
786 : : {
787 : 186 : doc[cur].pos = post[j];
788 : 186 : doc[cur].data.map.entry = entry;
789 : 186 : doc[cur].data.map.item = (QueryItem *) curoperand;
790 : 186 : cur++;
791 : : }
792 : : }
793 : :
5812 tgl@sss.pgh.pa.us 794 : 165 : entry++;
795 : : }
796 : : }
797 : :
6081 798 [ + + ]: 78 : if (cur > 0)
799 : : {
2866 rhaas@postgresql.org 800 : 75 : DocRepresentation *rptr = doc + 1,
801 : 75 : *wptr = doc,
802 : : storage;
803 : :
804 : : /*
805 : : * Sort representation in ascending order by pos and entry
806 : : */
432 peter@eisentraut.org 807 : 75 : qsort(doc, cur, sizeof(DocRepresentation), compareDocR);
808 : :
809 : : /*
810 : : * Join QueryItem per WordEntry and it's position
811 : : */
2929 teodor@sigaev.ru 812 : 75 : storage.pos = doc->pos;
813 : 75 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
814 : 75 : storage.data.query.items[0] = doc->data.map.item;
815 : 75 : storage.data.query.nitem = 1;
816 : :
817 [ + + ]: 186 : while (rptr - doc < cur)
818 : : {
2866 rhaas@postgresql.org 819 [ + + ]: 111 : if (rptr->pos == (rptr - 1)->pos &&
820 [ + - ]: 3 : rptr->data.map.entry == (rptr - 1)->data.map.entry)
821 : : {
2929 teodor@sigaev.ru 822 : 3 : storage.data.query.items[storage.data.query.nitem] = rptr->data.map.item;
823 : 3 : storage.data.query.nitem++;
824 : : }
825 : : else
826 : : {
827 : 108 : *wptr = storage;
828 : 108 : wptr++;
829 : 108 : storage.pos = rptr->pos;
830 : 108 : storage.data.query.items = palloc(sizeof(QueryItem *) * qr->query->size);
831 : 108 : storage.data.query.items[0] = rptr->data.map.item;
832 : 108 : storage.data.query.nitem = 1;
833 : : }
834 : :
835 : 111 : rptr++;
836 : : }
837 : :
838 : 75 : *wptr = storage;
839 : 75 : wptr++;
840 : :
841 : 75 : *doclen = wptr - doc;
6081 tgl@sss.pgh.pa.us 842 : 75 : return doc;
843 : : }
844 : :
845 : 3 : pfree(doc);
846 : 3 : return NULL;
847 : : }
848 : :
849 : : static float4
3739 850 : 78 : calc_rank_cd(const float4 *arrdata, TSVector txt, TSQuery query, int method)
851 : : {
852 : : DocRepresentation *doc;
853 : : int len,
854 : : i,
6081 855 : 78 : doclen = 0;
856 : : CoverExt ext;
857 : 78 : double Wdoc = 0.0;
858 : : double invws[lengthof(weights)];
859 : 78 : double SumDist = 0.0,
1317 860 : 78 : PrevExtPos = 0.0;
6081 861 : 78 : int NExtent = 0;
862 : : QueryRepresentation qr;
863 : :
864 : :
865 [ + + ]: 390 : for (i = 0; i < lengthof(weights); i++)
866 : : {
867 [ + - ]: 312 : invws[i] = ((double) ((arrdata[i] >= 0) ? arrdata[i] : weights[i]));
868 [ - + ]: 312 : if (invws[i] > 1.0)
6081 tgl@sss.pgh.pa.us 869 [ # # ]:UBC 0 : ereport(ERROR,
870 : : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
871 : : errmsg("weight out of range")));
6081 tgl@sss.pgh.pa.us 872 :CBC 312 : invws[i] = 1.0 / invws[i];
873 : : }
874 : :
6060 teodor@sigaev.ru 875 : 78 : qr.query = query;
2929 876 : 78 : qr.operandData = (QueryRepresentationOperand *)
2866 rhaas@postgresql.org 877 : 78 : palloc0(sizeof(QueryRepresentationOperand) * query->size);
878 : :
6060 teodor@sigaev.ru 879 : 78 : doc = get_docrep(txt, &qr, &doclen);
6081 tgl@sss.pgh.pa.us 880 [ + + ]: 78 : if (!doc)
881 : : {
2929 teodor@sigaev.ru 882 : 3 : pfree(qr.operandData);
6081 tgl@sss.pgh.pa.us 883 : 3 : return 0.0;
884 : : }
885 : :
3970 sfrost@snowman.net 886 [ + - + - : 375 : MemSet(&ext, 0, sizeof(CoverExt));
+ - + - +
+ ]
6060 teodor@sigaev.ru 887 [ + + ]: 162 : while (Cover(doc, doclen, &qr, &ext))
888 : : {
6081 tgl@sss.pgh.pa.us 889 : 87 : double Cpos = 0.0;
890 : 87 : double InvSum = 0.0;
891 : : double CurExtPos;
892 : : int nNoise;
893 : 87 : DocRepresentation *ptr = ext.begin;
894 : :
895 [ + + ]: 219 : while (ptr <= ext.end)
896 : : {
2929 teodor@sigaev.ru 897 : 132 : InvSum += invws[WEP_GETWEIGHT(ptr->pos)];
6081 tgl@sss.pgh.pa.us 898 : 132 : ptr++;
899 : : }
900 : :
901 : 87 : Cpos = ((double) (ext.end - ext.begin + 1)) / InvSum;
902 : :
903 : : /*
904 : : * if doc are big enough then ext.q may be equal to ext.p due to limit
905 : : * of positional information. In this case we approximate number of
906 : : * noise word as half cover's length
907 : : */
908 : 87 : nNoise = (ext.q - ext.p) - (ext.end - ext.begin);
909 [ - + ]: 87 : if (nNoise < 0)
6081 tgl@sss.pgh.pa.us 910 :UBC 0 : nNoise = (ext.end - ext.begin) / 2;
6081 tgl@sss.pgh.pa.us 911 :CBC 87 : Wdoc += Cpos / ((double) (1 + nNoise));
912 : :
913 : 87 : CurExtPos = ((double) (ext.q + ext.p)) / 2.0;
2489 914 [ + + + - ]: 87 : if (NExtent > 0 && CurExtPos > PrevExtPos /* prevent division by
915 : : * zero in a case of
916 : : * multiple lexize */ )
6081 917 : 21 : SumDist += 1.0 / (CurExtPos - PrevExtPos);
918 : :
919 : 87 : PrevExtPos = CurExtPos;
920 : 87 : NExtent++;
921 : : }
922 : :
923 [ - + - - ]: 75 : if ((method & RANK_NORM_LOGLENGTH) && txt->size > 0)
6081 tgl@sss.pgh.pa.us 924 :UBC 0 : Wdoc /= log((double) (cnt_length(txt) + 1));
925 : :
6081 tgl@sss.pgh.pa.us 926 [ - + ]:CBC 75 : if (method & RANK_NORM_LENGTH)
927 : : {
6081 tgl@sss.pgh.pa.us 928 :UBC 0 : len = cnt_length(txt);
929 [ # # ]: 0 : if (len > 0)
930 : 0 : Wdoc /= (double) len;
931 : : }
932 : :
5996 tgl@sss.pgh.pa.us 933 [ - + - - :CBC 75 : if ((method & RANK_NORM_EXTDIST) && NExtent > 0 && SumDist > 0)
- - ]
6081 tgl@sss.pgh.pa.us 934 :UBC 0 : Wdoc /= ((double) NExtent) / SumDist;
935 : :
6081 tgl@sss.pgh.pa.us 936 [ - + - - ]:CBC 75 : if ((method & RANK_NORM_UNIQ) && txt->size > 0)
6081 tgl@sss.pgh.pa.us 937 :UBC 0 : Wdoc /= (double) (txt->size);
938 : :
6081 tgl@sss.pgh.pa.us 939 [ - + - - ]:CBC 75 : if ((method & RANK_NORM_LOGUNIQ) && txt->size > 0)
6081 tgl@sss.pgh.pa.us 940 :UBC 0 : Wdoc /= log((double) (txt->size + 1)) / log(2.0);
941 : :
5996 tgl@sss.pgh.pa.us 942 [ - + ]:CBC 75 : if (method & RANK_NORM_RDIVRPLUS1)
5996 tgl@sss.pgh.pa.us 943 :UBC 0 : Wdoc /= (Wdoc + 1);
944 : :
6081 tgl@sss.pgh.pa.us 945 :CBC 75 : pfree(doc);
946 : :
2929 teodor@sigaev.ru 947 : 75 : pfree(qr.operandData);
948 : :
6081 tgl@sss.pgh.pa.us 949 : 75 : return (float4) Wdoc;
950 : : }
951 : :
952 : : Datum
6081 tgl@sss.pgh.pa.us 953 :UBC 0 : ts_rankcd_wttf(PG_FUNCTION_ARGS)
954 : : {
955 : 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
956 : 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
6060 teodor@sigaev.ru 957 : 0 : TSQuery query = PG_GETARG_TSQUERY(2);
6081 tgl@sss.pgh.pa.us 958 : 0 : int method = PG_GETARG_INT32(3);
959 : : float res;
960 : :
961 : 0 : res = calc_rank_cd(getWeights(win), txt, query, method);
962 : :
963 [ # # ]: 0 : PG_FREE_IF_COPY(win, 0);
964 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 1);
965 [ # # ]: 0 : PG_FREE_IF_COPY(query, 2);
966 : 0 : PG_RETURN_FLOAT4(res);
967 : : }
968 : :
969 : : Datum
970 : 0 : ts_rankcd_wtt(PG_FUNCTION_ARGS)
971 : : {
972 : 0 : ArrayType *win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
973 : 0 : TSVector txt = PG_GETARG_TSVECTOR(1);
6060 teodor@sigaev.ru 974 : 0 : TSQuery query = PG_GETARG_TSQUERY(2);
975 : : float res;
976 : :
6081 tgl@sss.pgh.pa.us 977 : 0 : res = calc_rank_cd(getWeights(win), txt, query, DEF_NORM_METHOD);
978 : :
979 [ # # ]: 0 : PG_FREE_IF_COPY(win, 0);
980 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 1);
981 [ # # ]: 0 : PG_FREE_IF_COPY(query, 2);
982 : 0 : PG_RETURN_FLOAT4(res);
983 : : }
984 : :
985 : : Datum
986 : 0 : ts_rankcd_ttf(PG_FUNCTION_ARGS)
987 : : {
988 : 0 : TSVector txt = PG_GETARG_TSVECTOR(0);
6060 teodor@sigaev.ru 989 : 0 : TSQuery query = PG_GETARG_TSQUERY(1);
6081 tgl@sss.pgh.pa.us 990 : 0 : int method = PG_GETARG_INT32(2);
991 : : float res;
992 : :
993 : 0 : res = calc_rank_cd(getWeights(NULL), txt, query, method);
994 : :
995 [ # # ]: 0 : PG_FREE_IF_COPY(txt, 0);
996 [ # # ]: 0 : PG_FREE_IF_COPY(query, 1);
997 : 0 : PG_RETURN_FLOAT4(res);
998 : : }
999 : :
1000 : : Datum
6081 tgl@sss.pgh.pa.us 1001 :CBC 78 : ts_rankcd_tt(PG_FUNCTION_ARGS)
1002 : : {
1003 : 78 : TSVector txt = PG_GETARG_TSVECTOR(0);
6060 teodor@sigaev.ru 1004 : 78 : TSQuery query = PG_GETARG_TSQUERY(1);
1005 : : float res;
1006 : :
6081 tgl@sss.pgh.pa.us 1007 : 78 : res = calc_rank_cd(getWeights(NULL), txt, query, DEF_NORM_METHOD);
1008 : :
1009 [ - + ]: 78 : PG_FREE_IF_COPY(txt, 0);
1010 [ - + ]: 78 : PG_FREE_IF_COPY(query, 1);
1011 : 78 : PG_RETURN_FLOAT4(res);
1012 : : }
|
