Thread: Improve Seq scan performance

Dear List,

I would like to improve seq scan performance. :-)

I have many cols in a table. I use only 1 col for search on it.  It is
indexed with  btree with text_pattern_ops. The search method is: r like
'%aaa%'
When I make another table with only this col values, the search time is
better when the data is cached. But wronger when the data isn't in cache.

I think the following:
- When there is a big table with many cols, the seq search is read all
cols not only searched.
- If we use an index with full values of a col, it is possible to seq
scan over the index is make better performance (lower io with smaller data).

It is possible to make an index on the table, and make a seq index scan
on this values?

Thanks for helping.

Best Regards,
    Ferenc

Lutischán Ferenc wrote:

> It is possible to make an index on the table, and make a seq index scan
> on this values?

My understanding is that this isn't possible in PostgreSQL, because
indexes do not contain information about tuple visibility. Data read
from the index might refer to tuples that've been deleted as far as your
transaction is concerned, or to tuples that were created after your
snapshot was taken.

--
Craig Ringer

Vladimir Sitnikov wrote:
>> Lutischán Ferenc wrote:
>>
>>  It is possible to make an index on the table, and make a seq index scan on
>>> this values?
>>>
>> My understanding is that this isn't possible in PostgreSQL, because indexes
>> do not contain information about tuple visibility. Data read from the index
>> might refer to tuples that've been deleted as far as your transaction is
>> concerned, or to tuples that were created after your snapshot was taken.
>>
> My understanding is even though indices do not contain information on tuple
> visibility, index could be used to filter out records that is known to make
> no match.

Yes, that's what an index is for. As far as I know, if it's worth doing
that, it's worth doing an index scan instead of a seq scan.

Maybe there's some hybrid type possible where you can scan the index to
find large table regions that are known /not/ to contain tuples of
interest and seek over them in your scan. I wouldn't know, really, but
it sounds like it'd probably be more I/O than a pure seq scan (given the
reading of the index too) unless the table had the values of interest
rather neatly clustered. It'd also surely use more memory and CPU time
processing the whole index to find table regions without values of interest.

Is that what you meant, though?

> create table seq_test
>  as select cast(i as text) i, repeat('*', 500) padding from
> generate_series(1,10000) as s(i);
>
> create index i_ix on seq_test(i);
>
> vacuum analyze verbose seq_test;
> -- index "i_ix" now contains 10000 row versions in *30 *pages
> -- "seq_test": found 0 removable, 10000 nonremovable row versions in *667 *
> pages
>
> explain analyze select * from seq_test where i like '%123%';

A b-tree index cannot be used on a LIKE query with a leading wildcard.
See the FAQ.

In addition, if your database is not in the C locale you can't use an
ordinary index for LIKE queries. See the FAQ. You need to create a
text_pattern_ops index instead:

create index i_ix_txt on seq_test(i text_pattern_ops);

> set enable_seqscan=off
> -- Index Scan reads 2529 pages for some reason. I would expect *30 *(index
> size) + *20 *(number of matching entries) = 50 pages maximum, that is 10
> times better than with seq scan.
> Index Scan using i_ix on seq_test  (cost=0.00..1643.74 rows=356 width=508)
> (actual time=0.334..16.746 rows=*20 *loops=1 read_shared=2529(2529)
> read_local=0(0) flush=0 local_flush=0 file_read=0 file_write=0)
>   Filter: (i ~~ '%123%'::text)
> Total runtime: 16.863 ms

I think it's reading the whole index, because it can't do a prefix
search if there's a leading wildcard. I'm a bit confused, though, since
I thought in this case it couldn't actually execute the query w/o a
sequential scan, and would just use one irrespective of the
enable_seqscan param. That's what happens here.

Here's what I get:

test=# create table seq_test as select cast(i as text) AS i, repeat('*',
500) AS padding from generate_series(1,10000) as s(i);
SELECT
test=# create index i_ix on seq_test(i);
CREATE INDEX
test=# create index i_ix_txt on seq_test(i text_pattern_ops);
CREATE INDEX
test=# vacuum analyze verbose seq_test;
-- blah blah
INFO:  "seq_test": scanned 667 of 667 pages, containing 10000 live rows
and 0 dead rows; 3000 rows in sample, 10000 estimated total rows

test=# explain analyze select * from seq_test where i like '%123%';
                                                QUERY PLAN

---------------------------------------------------------------------------------------------------------
  Seq Scan on seq_test  (cost=0.00..792.00 rows=400 width=508) (actual
time=0.081..5.239 rows=20 loops=1)
    Filter: (i ~~ '%123%'::text)
  Total runtime: 5.281 ms
(3 rows)

-- Now, note lack of leading wildcard:
test=# explain analyze select * from seq_test where i like '123%';
                                                     QUERY PLAN

-------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on seq_test  (cost=4.35..40.81 rows=10 width=508)
(actual time=0.062..0.081 rows=11 loops=1)
    Filter: (i ~~ '123%'::text)
    ->  Bitmap Index Scan on i_ix_txt  (cost=0.00..4.35 rows=10 width=0)
(actual time=0.048..0.048 rows=11 loops=1)
          Index Cond: ((i ~>=~ '123'::text) AND (i ~<~ '124'::text))
  Total runtime: 0.121 ms
(5 rows)

test=# set enable_seqscan=off;
SET
test=# explain analyze select * from seq_test where i like '%123%';
                                                       QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------
  Seq Scan on seq_test  (cost=100000000.00..100000792.00 rows=400
width=508) (actual time=0.088..5.666 rows=20 loops=1)
    Filter: (i ~~ '%123%'::text)
  Total runtime: 5.702 ms
(3 rows)

--
Craig Ringer

Vladimir Sitnikov wrote:

> Suppose you want to find all the values that contain '%123%'. Currently
> PostgreSQL will do a sec scan, while the better option might be (and it is)
> to loop through all the items in the index (it will cost 30 I/O), find
> records that truly contain %123% (it will find 20 of them) and do 20 I/O to
> check tuple visiblity. That is 50 I/O versus 667 for seq scan.

That does make sense. The 20 visibility checks/tuple reads have a higher
cost than you've accounted for given that they require seeks. Assuming
Pg's random_page_cost assumption is right and that every tuple of
interest is on a different page it'd cost the equivalent of 80
sequential page reads, which still brings the total to only 110.

Anyway, sorry I've bothered you about this. I misunderstood the point
you were at in investigating this and hadn't realised you were very
familiar with Pg and its innards, so I tried to bring up some points
that might help someone who's facing typical issues like "why doesn't it
use an index for %thing%".

> Please, follow the case carefully:  the index is only 30 pages long. Why is
> PostgreSQL doing 2529 I/O? It drives me crazy.

I certainly can't help you there, though I'm interested myself...

--
Craig Ringer

Dear Vladimir,

Thanks for clear description of the problem. :-)
Please report it to the bug list.
I hope it will be accepted as a "performance bug" and will be solved.

Best Regards,
    Ferenc

Vladimir Sitnikov wrotte:
>
> As far as I understand, it is discouraged to implement/suggest patches
> during Commitfest, however, I would love to treat the following case
> as a "performance bug" and add it to the "TODO" list:
>
>
> create table seq_test
>  as select cast(i as text) i, repeat('*', 500) padding from
> generate_series(1,10000) as s(i);
>
> create index i_ix on seq_test(i);
>
> vacuum analyze verbose seq_test;
> -- index "i_ix" now contains 10000 row versions in *30 *pages
> -- "seq_test": found 0 removable, 10000 nonremovable row versions in
> *667 *pages
>
> explain analyze select * from seq_test where i like '%123%';
> -- Seq Scan reads 667 pages (as expected)
> Seq Scan on seq_test  (cost=0.00..792.00 rows=356 width=508) (actual
> time=0.129..9.071 rows=20 loops=1 read_shared=*667*(667)
> read_local=0(0) flush=0 local_flush=0 file_read=0 file_write=0)
>   Filter: (i ~~ '%123%'::text)
> Total runtime: 9.188 ms
>
> set enable_seqscan=off
> -- Index Scan reads 2529 pages for some reason. I would expect *30
> *(index size) + *20 *(number of matching entries) = 50 pages maximum,
> that is 10 times better than with seq scan.
> Index Scan using i_ix on seq_test  (cost=0.00..1643.74 rows=356
> width=508) (actual time=0.334..16.746 rows=*20 *loops=1
> read_shared=2529(2529) read_local=0(0) flush=0 local_flush=0
> file_read=0 file_write=0)
>   Filter: (i ~~ '%123%'::text)
> Total runtime: 16.863 ms
>
> Hopefully, there will be a clear distinction between filtering via
> index and filtering via table access.

> Dear List,
>
> I would like to improve seq scan performance. :-)
>
> I have many cols in a table. I use only 1 col for search on it.  It is
> indexed with  btree with text_pattern_ops. The search method is: r like
> '%aaa%'
> When I make another table with only this col values, the search time is
> better when the data is cached. But wronger when the data isn't in cache.
>
> I think the following:
> - When there is a big table with many cols, the seq search is read all
> cols not only searched.
> - If we use an index with full values of a col, it is possible to seq
> scan over the index is make better performance (lower io with smaller
> data).
>
> It is possible to make an index on the table, and make a seq index scan
> on this values?

    You can fake this (as a test) by creating a separate table with just your
column of interest and the row id (primary key), updated via triggers, and
seq scan this table. Seq scanning this small table should be fast. Of
course if you have several column conditions it will get more complex.

    Note that btrees cannot optimize '%aaa%'. You could use trigrams.

OK, I see your problem. Try this :

read this : http://www.postgresql.org/docs/current/static/pgtrgm.html
locate and \i the pg_trgm.sql file

CREATE TABLE dict( s TEXT );

I loaded the english - german dictionary in a test table. I didn't parse
it, so it's just a bunch of 418552 strings, english and german mixed.

test=> EXPLAIN ANALYZE SELECT * FROM dict WHERE s LIKE '%tation%';
                                                QUERY PLAN
--------------------------------------------------------------------------------------------------------
  Seq Scan on dict  (cost=0.00..7445.90 rows=133 width=13) (actual
time=0.102..217.155 rows=802 loops=1)
    Filter: (s ~~ '%tation%'::text)
  Total runtime: 217.451 ms
(3 lignes)

Temps : 217,846 ms

Since this data does not change very often, let's use a gin index.

CREATE INDEX trgm_idx ON dict USING gin (s gin_trgm_ops);

With trigrams we can search by similarity. So, we can issue this :

EXPLAIN ANALYZE SELECT s, similarity(s, 'tation') AS sml FROM dict WHERE s
% 'tation' ORDER BY sml DESC, s;
                                                             QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------
  Sort  (cost=1114.44..1115.49 rows=419 width=13) (actual
time=190.778..190.980 rows=500 loops=1)
    Sort Key: (similarity(s, 'tation'::text)), s
    Sort Method:  quicksort  Memory: 37kB
    ->  Bitmap Heap Scan on dict  (cost=35.80..1096.19 rows=419 width=13)
(actual time=113.486..188.825 rows=500 loops=1)
          Filter: (s % 'tation'::text)
          ->  Bitmap Index Scan on trgm_idx  (cost=0.00..35.69 rows=419
width=0) (actual time=112.011..112.011 rows=15891 loops=1)
                Index Cond: (s % 'tation'::text)
  Total runtime: 191.189 ms

It is not much faster than the seq scan, but it can give you useful
results, correct spelling errors, etc.
Perhaps it's faster when data is not cached.
Sample of returns :

  taxation                |      0.6
  station                 |      0.5
  tabulation              |      0.5
  taction                 |      0.5
  Taxation {f}            |      0.5
  Taxation {f}            |      0.5

If you do not want to correct for spelling errors, you can do like this :

EXPLAIN ANALYZE SELECT s FROM dict WHERE s LIKE '%tation%' AND s %
'tation';
                                                         QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on dict  (cost=35.70..1096.09 rows=1 width=13) (actual
time=66.583..80.980 rows=306 loops=1)
    Filter: ((s ~~ '%tation%'::text) AND (s % 'tation'::text))
    ->  Bitmap Index Scan on trgm_idx  (cost=0.00..35.69 rows=419 width=0)
(actual time=65.799..65.799 rows=15891 loops=1)
          Index Cond: (s % 'tation'::text)
  Total runtime: 81.140 ms
(5 lignes)

Temps : 81,652 ms

In this case the trigram index is used to narrow the search, and the LIKE
to get only exact matches.

Careful though, it might not always match, for instance if you search
"rat" you won't find "consideration", because the search string is too
small.

Anyway, I would suggest to change your strategy.

You could try preloading everything into an in-memory array of strings.
This would be much faster.
You could also try to build a list of unique words from your dictionary,
which contains lots of expressions. Then, when the user enters a query,
get the words that contain the entered text, and use a full-text index to
search your dictionary.

> I tested first only some words. And later with '%a%', '%b% etc. When I
> re-query the table with the used term (e.g. 1.'%a%' -slow, 2. '%b%'-
> slow, '%a%' - fast), it is faster than the old method.

When the user enters a very short string like 'a' or 'is', I don't think
it is relevant to display all entries that contain this, because that
could be most of your dictionary. Instead, why not display all unique
words which start with this string ? Much less results, faster, and
probably more useful too. Then the user can select an longer word and use
this.

Also, pagination is overrated. If there are 50 pages of results, the user
will never click on them anyway. They are more likely to refine their
query instead. So, just display the first 100 results and be done with it
;)