pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
Techniques for quickly finding words in a phrase...
4+ messages / 4 participants
[nested] [flat]

* Techniques for quickly finding words in a phrase...
@ 2000-02-11 22:00  Saltsgaver, Scott <scottsa@aiinet.com>
  0 siblings, 1 reply; 4+ messages in thread

From: Saltsgaver, Scott @ 2000-02-11 22:00 UTC (permalink / raw)
  To: pgsql-sql

I have a large table where one of the columns is a text phrase (ex. "MARY
HAD A LITTLE LAMB").  I want to be able to search on that table with
the start of one or more words from that column ("LITT" and "LAMB").
I built a separate table whose foreign key maps back to my original table,
but also has a column with just the words from the phrase.

For example:

Table Phrase (indexed by id):
    id | phrase
    ---+-----------------------------
    1  | MARY HAD A LITTLE LAMB
    2  | WHOSE FLEECE WAS WHITE AS SNOW

Table PhraseWords (indexed by word):
    id | word
    ---+-------
    1  | MARY
    1  | HAD
    1  | A
    1  | LITTLE
    1  | LAMB
    2  | WHOSE
    2  | FLEECE
    2  | WAS
    2  | WHITE
    2  | AS
    2  | SNOW

The number of rows in the Prase table is ~225K, and the number of rows
in the PhraseWords table is ~1M.  And there are also some high-frequency
words in the PhraseWords table, such as "THE" which recur many times.
If the user attempts to search for the words "WAS WHIT SNOW" I generate
the following SQL:

SELECT p.id, phrase FROM Phrase AS p, PhraseWords AS pw
    WHERE
        ((p.id = pw.id) AND word LIKE 'WAS%')
        AND EXISTS (SELECT id FROM PhraseWords AS pw
                WHERE (p.id = pw.id) AND word LIKE 'WHIT%')
        AND EXISTS (SELECT id FROM PhraseWords AS pw
                WHERE (p.id = pw.id) AND word LIKE 'SNOW%');

My EXPLAIN for this is:

Nested Loop  (cost=8033.62 rows=172 width=48)
  ->  Index Scan using idx_phraseword on phraseword pw
      (cost=6256.27 rows=867 width=4)

  ->  Index Scan using phrase_pkey on phrase p
      (cost=2.05 rows=46669 width=44)

        SubPlan
          ->  Index Scan using idx_phraseword on phraseword pw
	      (cost=6256.27 rows=1 width=4)

          ->  Index Scan using idx_phraseword on phraseword pw
	      (cost=6256.27 rows=1 width=4)


For some reason, the select still takes > 1 minute on a fairly decent
sized Linux box (500Mhz, 128MB ram).  I was using IN clauses instead of
the EXISTS clauses, and was noticing the EXPLAIN telling me that it was
doing sequential table lookups.  I then found in the FAQ that this is a
known issue.  I was hoping that by using EXISTS I could do better.

So I guess my two questions are:

1) Is there a way to make this more efficient?
2) Is there another technique in general that will allow me to let
   my users search the table for words (or the start of words, in
   this case)?

Any help would be greatly appreciated!

Scott Saltsgaver





^ permalink  raw  reply  [nested|flat] 4+ messages in thread

* Re: [SQL] Techniques for quickly finding words in a phrase...
@ 2000-02-11 23:08  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Saltsgaver, Scott <scottsa@aiinet.com>
  0 siblings, 1 reply; 4+ messages in thread

From: Tom Lane @ 2000-02-11 23:08 UTC (permalink / raw)
  To: Saltsgaver, Scott <scottsa@aiinet.com>; +Cc: pgsql-sql

"Saltsgaver, Scott" <scottsa@aiinet.com> writes:
> SELECT p.id, phrase FROM Phrase AS p, PhraseWords AS pw
>     WHERE
>         ((p.id = pw.id) AND word LIKE 'WAS%')
>         AND EXISTS (SELECT id FROM PhraseWords AS pw
>                 WHERE (p.id = pw.id) AND word LIKE 'WHIT%')
>         AND EXISTS (SELECT id FROM PhraseWords AS pw
>                 WHERE (p.id = pw.id) AND word LIKE 'SNOW%');

> For some reason, the select still takes > 1 minute on a fairly decent
> sized Linux box (500Mhz, 128MB ram).

Subselects are pretty inefficient in Postgres at present.  Try rewriting
it as a join:

SELECT p.id, phrase FROM Phrase AS p, PhraseWords AS pw1,
	PhraseWords AS pw2, PhraseWords AS pw3
WHERE p.id = pw1.id AND pw1.word LIKE 'WAS%'
	AND p.id = pw2.id AND pw2.word LIKE 'WHIT%'
	AND p.id = pw3.id AND pw3.word LIKE 'SNOW%';

(with the obvious adjustments depending on how many words in your
search phrase).

If you are using search phrases with more than half a dozen words,
you will probably need to enable GEQO planning to avoid spending
an unreasonable amount of time in planning the query.  (If 'explain'
itself starts to take a long time, you are seeing excessive plan time.)

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 4+ messages in thread

* Re: [SQL] Techniques for quickly finding words in a phrase...
@ 2000-02-12 08:30  om <o@mueschke.de>
  parent: Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 4+ messages in thread

From: om @ 2000-02-12 08:30 UTC (permalink / raw)
  To: Saltsgaver, Scott <scottsa@aiinet.com>; +Cc: pgsql-sql

On Fri, Feb 11, 2000 at 06:08:43PM -0500, Tom Lane wrote:
> "Saltsgaver, Scott" <scottsa@aiinet.com> writes:
> > SELECT p.id, phrase FROM Phrase AS p, PhraseWords AS pw
> >     WHERE
> >         ((p.id = pw.id) AND word LIKE 'WAS%')
> >         AND EXISTS (SELECT id FROM PhraseWords AS pw
> >                 WHERE (p.id = pw.id) AND word LIKE 'WHIT%')
> >         AND EXISTS (SELECT id FROM PhraseWords AS pw
> >                 WHERE (p.id = pw.id) AND word LIKE 'SNOW%');
> 
> > For some reason, the select still takes > 1 minute on a fairly decent
> > sized Linux box (500Mhz, 128MB ram).
> 
> Subselects are pretty inefficient in Postgres at present.  Try rewriting
> it as a join:
> 
> SELECT p.id, phrase FROM Phrase AS p, PhraseWords AS pw1,
> 	PhraseWords AS pw2, PhraseWords AS pw3
> WHERE p.id = pw1.id AND pw1.word LIKE 'WAS%'
> 	AND p.id = pw2.id AND pw2.word LIKE 'WHIT%'
> 	AND p.id = pw3.id AND pw3.word LIKE 'SNOW%';

another approach would leave the PhraseWords table aside and use regular
expressions to find matches in table Phrase. of course, this couldn't take
advantage of indices, but maybe the fact that it avoids the join (or
subselect) helps performance.

SELECT id, phrase FROM Phrase
WHERE  phrase ~* '[[:<:]]was'
   AND phrase ~* '[[:<:]]whit'
   AND phrase ~* '[[:<:]]snow';


-- oliver




^ permalink  raw  reply  [nested|flat] 4+ messages in thread

* Techniques for quickly finding words in a phrase...
@ 2000-02-15 17:08  Carl Flansbaum <carl@planetcpub.com>
  0 siblings, 0 replies; 4+ messages in thread

From: Carl Flansbaum @ 2000-02-15 17:08 UTC (permalink / raw)
  To: pgsql-sql

Hello,

Ok, can anyone help with the following...

I'm also looking to write a SQL query to find a specific string in a target
of words.

the field contains values like 1234 2456 1234a etc.

The problem is that the string must be exact, so while using


WHERE foo ~ '1234';

or

WHERE foo LIKE '1234';

or

WHERE foo ~* '[[:<:]]1234';

will work, it also brings up results with the 1234a value in the field.

I've tried a wide variety of pattern matching with no luck.

any advice?

thanks

carl




^ permalink  raw  reply  [nested|flat] 4+ messages in thread


end of thread, other threads:[~2000-02-15 17:08 UTC | newest]

Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2000-02-11 22:00 Techniques for quickly finding words in a phrase... Saltsgaver, Scott <scottsa@aiinet.com>
2000-02-11 23:08 ` Tom Lane <tgl@sss.pgh.pa.us>
2000-02-12 08:30   ` om <o@mueschke.de>
2000-02-15 17:08 Techniques for quickly finding words in a phrase... Carl Flansbaum <carl@planetcpub.com>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox