Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have a big table ~15M records called entities. I want to find top 5 entities matching "hockey" in their name.

I have a Full text index built for that, which is used : gin_ix_entity_full_text_search_name, which indexes the name.

Query

 SELECT "entities".*,
         ts_rank(to_tsvector('english', "entities"."name"::text),
         to_tsquery('english', 'hockey'::text)) AS "rank0.48661998202865475"
    FROM "entities" 
         WHERE "entities"."place" = 'f' 
              AND (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'hockey'::text)) 
         ORDER BY "rank0.48661998202865475" DESC LIMIT 5

Duration 25,623 ms

Explain plan

1   Query plan  Limit  (cost=12666.89..12666.89 rows=5 width=3116)

2   Query plan    ->  Sort  (cost=12666.89..12670.18 rows=6571 width=3116)

3   Query plan          Sort Key: (ts_rank(to_tsvector('english'::regconfig, (name)::text), '''hockey'''::tsquery))

4   Query plan          ->  Bitmap Heap Scan on entities  (cost=124.06..12645.06 rows=6571 width=3116)

5   Query plan                Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''hockey'''::tsquery)

6   Query plan                Filter: (NOT place)

7   Query plan                ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..123.74 rows=6625 width=0)

8   Query plan                      Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''hockey'''::tsquery)

I do not understand why it verifies the index condition twice. (Query plan step 4 and 7). Is it because of my boolean condition (not Place?) If so, I should add it to my index and I should get a very fast query? Or is it the sorting condition which makes it very long?

Thanks helping me understand the Query plan and how to fix my 25 seconds query!

EDIT--------------------- Here's the explain analyze :

QUERY PLAN

  Limit  (cost=4447.28..4447.29 rows=5 width=3116) (actual time=18509.274..18509.282 rows=5 loops=1)
  ->  Sort  (cost=4447.28..4448.41 rows=2248 width=3116) (actual time=18509.271..18509.273 rows=5 loops=1)
         Sort Key: (ts_rank(to_tsvector('english'::regconfig, (name)::text), '''test'''::tsquery))
         Sort Method:  top-N heapsort  Memory: 19kB
     ->  Bitmap Heap Scan on entities  (cost=43.31..4439.82 rows=2248 width=3116) (actual time=119.003..18491.408 rows=2533 loops=1)
           Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''test'''::tsquery)
           Filter: (NOT place)
           ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..43.20 rows=2266 width=0) (actual time=74.093..74.093 rows=2593 loops=1)
                 Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''test'''::tsquery)
 Total runtime: 18509.381 ms
(10 rows)

Here are my DB parameters . It is an online DB hosted by Heroku, on Amazon services. They describe it as having 1.7GB of ram, 1 processing unit and a DB of max 1TB.

         name             |    current_setting                                                               

version                      | PostgreSQL 9.0.7 on i486-pc-linux-gnu, compiled by GCC gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3, 32-bit
archive_command              | test -f /etc/postgresql/9.0/main/wal-e.d/ARCHIVING_OFF ||     envdir /etc/postgresql/9.0/resource29857_heroku_com/wal-e.d/env wal-e wal-push %p
archive_mode                 | on
archive_timeout              | 1min
checkpoint_completion_target | 0.7
checkpoint_segments          | 40
client_min_messages          | notice
cpu_index_tuple_cost         | 0.001
cpu_operator_cost            | 0.0005
cpu_tuple_cost               | 0.003
effective_cache_size         | 1530000kB
hot_standby                  | on
lc_collate                   | en_US.UTF-8
lc_ctype                     | en_US.UTF-8
listen_addresses             | *
log_checkpoints              | on
log_destination              | syslog
log_line_prefix              | %u [YELLOW] 
log_min_duration_statement   | 50ms
log_min_messages             | notice
logging_collector            | on
maintenance_work_mem         | 64MB
max_connections              | 500
max_prepared_transactions    | 500
max_stack_depth              | 2MB
max_standby_archive_delay    | -1
max_standby_streaming_delay  | -1
max_wal_senders              | 10
port                         | 
random_page_cost             | 2
server_encoding              | UTF8
shared_buffers               | 415MB
ssl                          | on
syslog_ident                 | resource29857_heroku_com
TimeZone                     | UTC
wal_buffers                  | 8MB
wal_keep_segments            | 127
wal_level                    | hot_standby
work_mem                     | 100MB
(39 rows)

EDIT 2===========================

Looks like the ORDER BY is the slow part :

d6ifslbf0ugpu=> EXPLAIN ANALYZE SELECT "entities"."name",
     ts_rank(to_tsvector('english', "entities"."name"::text),
     to_tsquery('english', 'banana'::text)) AS "rank0.48661998202865475"
FROM "entities" 
     WHERE (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'banana'::text)) 
     LIMIT 5;

QUERY PLAN                                                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=43.31..53.07 rows=5 width=24) (actual time=76.583..103.623 rows=5 loops=1)
->  Bitmap Heap Scan on entities  (cost=43.31..4467.60 rows=2266 width=24) (actual time=76.581..103.613 rows=5 loops=1)
     Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
     ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..43.20 rows=2266 width=0) (actual time=53.592..53.592 rows=1495 loops=1)
           Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
 Total runtime: 103.680 ms
(6 rows)

VS with ORDER BY STATEMENT

d6ifslbf0ugpu=> EXPLAIN ANALYZE SELECT "entities"."name",
     ts_rank(to_tsvector('english', "entities"."name"::text),
     to_tsquery('english', 'banana'::text)) AS "rank0.48661998202865475"
FROM "entities" 
     WHERE (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'banana'::text)) 
     ORDER BY "rank0.48661998202865475" DESC LIMIT 5;


QUERY PLAN                                                                           
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit  (cost=4475.12..4475.13 rows=5 width=24) (actual time=15013.735..15013.741 rows=5 loops=1)
->  Sort  (cost=4475.12..4476.26 rows=2266 width=24) (actual time=15013.732..15013.735 rows=5 loops=1)
     Sort Key: (ts_rank(to_tsvector('english'::regconfig, (name)::text), '''banana'''::tsquery))
     Sort Method:  top-N heapsort  Memory: 17kB
     ->  Bitmap Heap Scan on entities  (cost=43.31..4467.60 rows=2266 width=24) (actual time=0.872..15006.763 rows=1495 loops=1)
           Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
           ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..43.20 rows=2266 width=0) (actual time=0.549..0.549 rows=1495 loops=1)
                 Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
 Total runtime: 15013.805 ms
(9 rows)

What I still don't understand, is why this is slower. Looks like it's fetching the same amount of rows from Bitmap Heap Scan , but takes so much longer.

share|improve this question
    
If increasing work_mem doesn't provide enough of a performance boost, please show the results of EXPLAIN ANALYZE instead of just EXPLAIN. It also helps to show the results of running the the query on this page: wiki.postgresql.org/wiki/Server_Configuration A brief description of the hardware helps, too. –  kgrittn Apr 12 '12 at 17:24
    
Here's another EXPLAIN ANALYZE : (see edit in my above post) –  xlash Apr 13 '12 at 1:38
    
I should point out that the PostgreSQL configuration you show is not likely to be anywhere close to optimal. That's far enough off-topic that it should probably be addressed in a separate question, though. I recommend you do so. –  kgrittn Apr 15 '12 at 22:31
    
If you are having trouble understanding your EXPLAIN ANALYZE output, there is a Wiki page that should help: wiki.postgresql.org/wiki/Using_EXPLAIN A lot of people find the explain.depesz.com page helpful; you might want to poke around the help and give it a try. –  kgrittn Apr 15 '12 at 23:49

3 Answers 3

A bitmap scan works like this: The index is scanned to find the locations of the tuples matching the index conditions. The bitmap might go through logical combination with the results of other bitmap scans, using boolean logic on the bits. Then the pages holding the data are accessed in page number order, to reduce disk access and hopefully turn some random reads into sequential reads.

A bitmap index scan may need to become "lossy" to fit in memory -- it reduces its accuracy from the tuple level to the page level. If you increase work_mem (at least for this one query), you might avoid that. It's not going to be able to skip the bitmap heap scan on line 4 or the filter on line 6, but it might be able to skip the recheck on line 5.

share|improve this answer
    
Increased from 100MB to 650MB, gave no performance difference. (work_mem) –  xlash Apr 13 '12 at 2:19

What I still don't understand, is why this is slower.

That sorting the rows will cost something is obvious. But why so much?
Without ORDER BY rank0... Postgres can just

  • pick the first 5 rows it finds and stop fetching rows as soon as it has 5.

    Bitmap Heap Scan on entities ... rows=5 ...

  • then compute ts_rank() for just 5 rows.
In the second case, Postgres has to

  • fetch all (1495 according to your query plan) rows that qualify.

    Bitmap Heap Scan on entities ... rows=1495 ...

  • compute ts_rank() for all of them.
  • sort all of them to find the first 5 according to the calculated value.
Try ORDER BY name just to see the cost of computing to_tsquery('english', 'hockey'::text)) for the superfluous rows and how much remains for fetching more rows and sorting.

share|improve this answer
    
Caching comes in the way... it roughly gives a performance as bad. 10secs 1500 rows. I understand your explanation. It makes sense. But while doing a text search.... any way to build my index for proper quality sorting without extracting everything? –  xlash Apr 14 '12 at 18:51

Since the edited question makes it look like the goal is to pick a few of the top matches, rather that a list of everything which matches, I'm posting a separate answer for that, since it is a rather different problem.

You might want to consider a KNN-GiST (for K Nearest Neighbor -- Generalized Search Tree) index, which can pull right from the index in order of similarity -- so you don't need to randomly read all those heap tuples and sort them down to find the K best matches.

To date I don't think anyone has implemented KNN-GIST support for tsearch queries (although I've been assured it can be done, it's just a matter of someone taking the time to do it), but maybe the trigram support (which is done) will work for your application. The main difference is that trigram searches don't use dictionaries for stemming and synonyms the way tsearch does; you'll only find exact word matches.

To try trigrams for your example, you probably want to index "name" like this:

CREATE INDEX entities_name_trgm ON entities USING gist (name gist_trgm_ops);

Then you can search like this:

SELECT
    *,
    name <-> 'banana' AS sim
  FROM entities 
  WHERE name % 'banana'
  ORDER BY sim DESC
  LIMIT 5;

Note the operators used and the ORDER BY using the alias of the "similarity" column. I wouldn't stray too far from this pattern when trying it out. The index on the tsvector is not used for this search.

Barring problems with your current configuration (which could easily throw your whole VM into hopeless paging from memory overcommit), you will probably really like the performance of this. Whether it has the behavior you want is what I don't know.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.