pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedImprove Seq scan performance
9+ messages / 4 participants
[nested] [flat]
* Improve Seq scan performance
@ 2008-11-10 06:50 Lutischán Ferenc <lutischanf@gmail.com>
0 siblings, 2 replies; 9+ messages in thread
From: Lutischán Ferenc @ 2008-11-10 06:50 UTC (permalink / raw)
To: pgsql-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
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 06:55 Craig Ringer <craig@postnewspapers.com.au>
parent: Lutischán Ferenc <lutischanf@gmail.com>
1 sibling, 1 reply; 9+ messages in thread
From: Craig Ringer @ 2008-11-10 06:55 UTC (permalink / raw)
To: Lutischán Ferenc <lutischanf@gmail.com>; +Cc: pgsql-performance
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
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 07:37 Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
parent: Craig Ringer <craig@postnewspapers.com.au>
0 siblings, 2 replies; 9+ messages in thread
From: Vladimir Sitnikov @ 2008-11-10 07:37 UTC (permalink / raw)
To: Craig Ringer <craig@postnewspapers.com.au>; +Cc: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-performance
> 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. Since btree index stores exact values, PostgreSQL could scan
through the index and skip those entries that do not contain '%aaa%'. That
will dramatically improve cases where the criteria has good selectivity,
since index has much more compact structure than table.
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.
Regards,
Vladimir Sitnikov
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 07:59 Craig Ringer <craig@postnewspapers.com.au>
parent: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
1 sibling, 1 reply; 9+ messages in thread
From: Craig Ringer @ 2008-11-10 07:59 UTC (permalink / raw)
To: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>; +Cc: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-performance
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
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 08:18 Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
parent: Craig Ringer <craig@postnewspapers.com.au>
0 siblings, 1 reply; 9+ messages in thread
From: Vladimir Sitnikov @ 2008-11-10 08:18 UTC (permalink / raw)
To: Craig Ringer <craig@postnewspapers.com.au>; +Cc: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-performance
>
> 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?
Not exactly. I mean the following: there are cases when index scan even
over non-clustered values is a complete win (basically, it is a win when the
number of returned values is relatively small no matter is it due to
selectivity or due to limit clause).
The test case that I have provided creates a 667 pages long table and 30
pages long index thus a complete scan of the index is 22 times faster in
terms of I/O.
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.
> A b-tree index cannot be used on a LIKE query with a leading wildcard. See
> the FAQ.
Unfortunately it is true. I would love to improve that particular case.
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);
Good catch. However, that does not change the results. PostgresSQL does the
same amount of 2529 I/O for index scan on '%123%' for some unknown reason.
>
>
> 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.
Please, follow the case carefully: the index is only 30 pages long. Why is
PostgreSQL doing 2529 I/O? It drives me crazy.
Regards,
Vladimir Sitnikov
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 08:41 Craig Ringer <craig@postnewspapers.com.au>
parent: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
0 siblings, 0 replies; 9+ messages in thread
From: Craig Ringer @ 2008-11-10 08:41 UTC (permalink / raw)
To: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>; +Cc: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-performance
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
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-10 16:19 Lutischán Ferenc <lutischanf@gmail.com>
parent: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
1 sibling, 0 replies; 9+ messages in thread
From: Lutischán Ferenc @ 2008-11-10 16:19 UTC (permalink / raw)
To: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>; +Cc: Craig Ringer <craig@postnewspapers.com.au>; pgsql-performance
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.
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-16 14:54 PFC <lists@peufeu.com>
parent: Lutischán Ferenc <lutischanf@gmail.com>
1 sibling, 1 reply; 9+ messages in thread
From: PFC @ 2008-11-16 14:54 UTC (permalink / raw)
To: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-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?
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.
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Improve Seq scan performance
@ 2008-11-17 10:51 PFC <lists@peufeu.com>
parent: PFC <lists@peufeu.com>
0 siblings, 0 replies; 9+ messages in thread
From: PFC @ 2008-11-17 10:51 UTC (permalink / raw)
To: Lutischán Ferenc <lutischanf@gmail.com>; pgsql-performance
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
;)
^ permalink raw reply [nested|flat] 9+ messages in thread
end of thread, other threads:[~2008-11-17 10:51 UTC | newest]
Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2008-11-10 06:50 Improve Seq scan performance Lutischán Ferenc <lutischanf@gmail.com>
2008-11-10 06:55 ` Craig Ringer <craig@postnewspapers.com.au>
2008-11-10 07:37 ` Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
2008-11-10 07:59 ` Craig Ringer <craig@postnewspapers.com.au>
2008-11-10 08:18 ` Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
2008-11-10 08:41 ` Craig Ringer <craig@postnewspapers.com.au>
2008-11-10 16:19 ` Lutischán Ferenc <lutischanf@gmail.com>
2008-11-16 14:54 ` PFC <lists@peufeu.com>
2008-11-17 10:51 ` PFC <lists@peufeu.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