Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit78e73e8

Browse files
committed
Fix recently-introduced performance problem in ts_headline().
The new hlCover() algorithm that I introduced in commitc9b0c67turns out to potentially take O(N^2) or worse time on long documents,if there are many occurrences of individual query words but few or nosubstrings that actually satisfy the query. (One way to hit thisbehavior is with a "common_word & rare_word" type of query.) Thisseems unavoidable given the original goal of checking every substringof the document, so we have to back off that idea. Fortunately, itseems unlikely that anyone would really want headlines spanning all ofa long document, so we can avoid the worse-than-linear behavior byimposing a maximum length of substring that we'll consider.For now, just hard-wire that maximum length as a multiple of max_wordstimes max_fragments. Perhaps at some point somebody will argue forexposing it as a ts_headline parameter, but I'm hesitant to make sucha feature addition in a back-patched bug fix.I also noted that the hlFirstIndex() function I'd added in thatcommit was unnecessarily stupid: it really only needs to check whethera HeadlineWordEntry's item pointer is null or not. This wouldn't makeall that much difference in typical cases with queries having justa few terms, but a cycle shaved is a cycle earned.In addition, add a CHECK_FOR_INTERRUPTS call in TS_execute_recurse.This ensures that hlCover's loop is cancellable if it manages to takea long time, and it may protect some other TS_execute callers as well.Back-patch to 9.6 as the previous commit was. I also chose to add theCHECK_FOR_INTERRUPTS call to 9.5. The old hlCover() algorithm seemsto avoid the O(N^2) behavior, at least on the test case I tried, butnonetheless it's not very quick on a long document.Per report from Stephen Frost.Discussion:https://postgr.es/m/20200724160535.GW12375@tamriel.snowman.net
1 parent7be0449 commit78e73e8

File tree

2 files changed

+35
-25
lines changed

2 files changed

+35
-25
lines changed

‎src/backend/tsearch/wparser_def.c

Lines changed: 32 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -2003,33 +2003,29 @@ checkcondition_HL(void *opaque, QueryOperand *val, ExecPhraseData *data)
20032003
* Returns -1 if no such index
20042004
*/
20052005
staticint
2006-
hlFirstIndex(HeadlineParsedText*prs,TSQueryquery,intpos)
2006+
hlFirstIndex(HeadlineParsedText*prs,intpos)
20072007
{
20082008
inti;
20092009

2010-
/* For each word ... */
20112010
for (i=pos;i<prs->curwords;i++)
20122011
{
2013-
/* ... scan the query to see if this word matches any operand */
2014-
QueryItem*item=GETQUERY(query);
2015-
intj;
2016-
2017-
for (j=0;j<query->size;j++)
2018-
{
2019-
if (item->type==QI_VAL&&
2020-
prs->words[i].item==&item->qoperand)
2021-
returni;
2022-
item++;
2023-
}
2012+
if (prs->words[i].item!=NULL)
2013+
returni;
20242014
}
20252015
return-1;
20262016
}
20272017

20282018
/*
20292019
* hlCover: try to find a substring of prs' word list that satisfies query
20302020
*
2031-
* At entry, *p must be the first word index to consider (initialize this to
2032-
* zero, or to the next index after a previous successful search).
2021+
* At entry, *p must be the first word index to consider (initialize this
2022+
* to zero, or to the next index after a previous successful search).
2023+
* We will consider all substrings starting at or after that word, and
2024+
* containing no more than max_cover words. (We need a length limit to
2025+
* keep this from taking O(N^2) time for a long document with many query
2026+
* words but few complete matches. Actually, since checkcondition_HL is
2027+
* roughly O(N) in the length of the substring being checked, it's even
2028+
* worse than that.)
20332029
*
20342030
* On success, sets *p to first word index and *q to last word index of the
20352031
* cover substring, and returns true.
@@ -2038,7 +2034,8 @@ hlFirstIndex(HeadlineParsedText *prs, TSQuery query, int pos)
20382034
* words used in the query.
20392035
*/
20402036
staticbool
2041-
hlCover(HeadlineParsedText*prs,TSQueryquery,int*p,int*q)
2037+
hlCover(HeadlineParsedText*prs,TSQueryquery,intmax_cover,
2038+
int*p,int*q)
20422039
{
20432040
intpmin,
20442041
pmax,
@@ -2052,7 +2049,7 @@ hlCover(HeadlineParsedText *prs, TSQuery query, int *p, int *q)
20522049
* appearing in the query; there's no point in trying endpoints in between
20532050
* such points.
20542051
*/
2055-
pmin=hlFirstIndex(prs,query,*p);
2052+
pmin=hlFirstIndex(prs,*p);
20562053
while (pmin >=0)
20572054
{
20582055
/* This useless assignment just keeps stupider compilers quiet */
@@ -2073,7 +2070,7 @@ hlCover(HeadlineParsedText *prs, TSQuery query, int *p, int *q)
20732070
return true;
20742071
}
20752072
/* Nope, so advance pmax to next feasible endpoint */
2076-
nextpmax=hlFirstIndex(prs,query,pmax+1);
2073+
nextpmax=hlFirstIndex(prs,pmax+1);
20772074

20782075
/*
20792076
* If this is our first advance past pmin, then the result is also
@@ -2084,7 +2081,7 @@ hlCover(HeadlineParsedText *prs, TSQuery query, int *p, int *q)
20842081
nextpmin=nextpmax;
20852082
pmax=nextpmax;
20862083
}
2087-
while (pmax >=0);
2084+
while (pmax >=0&&pmax-pmin<max_cover);
20882085
/* No luck here, so try next feasible startpoint */
20892086
pmin=nextpmin;
20902087
}
@@ -2186,7 +2183,7 @@ get_next_fragment(HeadlineParsedText *prs, int *startpos, int *endpos,
21862183
staticvoid
21872184
mark_hl_fragments(HeadlineParsedText*prs,TSQueryquery,boolhighlightall,
21882185
intshortword,intmin_words,
2189-
intmax_words,intmax_fragments)
2186+
intmax_words,intmax_fragments,intmax_cover)
21902187
{
21912188
int32poslen,
21922189
curlen,
@@ -2213,7 +2210,7 @@ mark_hl_fragments(HeadlineParsedText *prs, TSQuery query, bool highlightall,
22132210
covers=palloc(maxcovers*sizeof(CoverPos));
22142211

22152212
/* get all covers */
2216-
while (hlCover(prs,query,&p,&q))
2213+
while (hlCover(prs,query,max_cover,&p,&q))
22172214
{
22182215
startpos=p;
22192216
endpos=q;
@@ -2368,7 +2365,7 @@ mark_hl_fragments(HeadlineParsedText *prs, TSQuery query, bool highlightall,
23682365
*/
23692366
staticvoid
23702367
mark_hl_words(HeadlineParsedText*prs,TSQueryquery,boolhighlightall,
2371-
intshortword,intmin_words,intmax_words)
2368+
intshortword,intmin_words,intmax_words,intmax_cover)
23722369
{
23732370
intp=0,
23742371
q=0;
@@ -2386,7 +2383,7 @@ mark_hl_words(HeadlineParsedText *prs, TSQuery query, bool highlightall,
23862383
if (!highlightall)
23872384
{
23882385
/* examine all covers, select a headline using the best one */
2389-
while (hlCover(prs,query,&p,&q))
2386+
while (hlCover(prs,query,max_cover,&p,&q))
23902387
{
23912388
/*
23922389
* Count words (curlen) and interesting words (poslen) within
@@ -2542,6 +2539,7 @@ prsd_headline(PG_FUNCTION_ARGS)
25422539
intshortword=3;
25432540
intmax_fragments=0;
25442541
boolhighlightall= false;
2542+
intmax_cover;
25452543
ListCell*l;
25462544

25472545
/* Extract configuration option values */
@@ -2581,6 +2579,15 @@ prsd_headline(PG_FUNCTION_ARGS)
25812579
defel->defname)));
25822580
}
25832581

2582+
/*
2583+
* We might eventually make max_cover a user-settable parameter, but for
2584+
* now, just compute a reasonable value based on max_words and
2585+
* max_fragments.
2586+
*/
2587+
max_cover=Max(max_words*10,100);
2588+
if (max_fragments>0)
2589+
max_cover *=max_fragments;
2590+
25842591
/* in HighlightAll mode these parameters are ignored */
25852592
if (!highlightall)
25862593
{
@@ -2605,10 +2612,10 @@ prsd_headline(PG_FUNCTION_ARGS)
26052612
/* Apply appropriate headline selector */
26062613
if (max_fragments==0)
26072614
mark_hl_words(prs,query,highlightall,shortword,
2608-
min_words,max_words);
2615+
min_words,max_words,max_cover);
26092616
else
26102617
mark_hl_fragments(prs,query,highlightall,shortword,
2611-
min_words,max_words,max_fragments);
2618+
min_words,max_words,max_fragments,max_cover);
26122619

26132620
/* Fill in default values for string options */
26142621
if (!prs->startsel)

‎src/backend/utils/adt/tsvector_op.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1868,6 +1868,9 @@ TS_execute_recurse(QueryItem *curitem, void *arg, uint32 flags,
18681868
/* since this function recurses, it could be driven to stack overflow */
18691869
check_stack_depth();
18701870

1871+
/* ... and let's check for query cancel while we're at it */
1872+
CHECK_FOR_INTERRUPTS();
1873+
18711874
if (curitem->type==QI_VAL)
18721875
returnchkcond(arg, (QueryOperand*)curitem,
18731876
NULL/* don't need position info */ );

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp