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