Received: from localhost (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id E6FD264FD2B for ; Mon, 10 Nov 2008 03:37:02 -0400 (AST) Received: from mail.postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 95015-01 for ; Mon, 10 Nov 2008 03:37:02 -0400 (AST) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from rv-out-0506.google.com (rv-out-0506.google.com [209.85.198.234]) by mail.postgresql.org (Postfix) with ESMTP id 06E4364FD29 for ; Mon, 10 Nov 2008 03:37:01 -0400 (AST) Received: by rv-out-0506.google.com with SMTP id b25so2211018rvf.43 for ; Sun, 09 Nov 2008 23:37:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:cc:in-reply-to:mime-version:content-type:references; bh=5+39i8462TdTQEK00txiZHVUGVU+7kwWRvMw9mJSmXk=; b=MfHamA3ybRGlUcQxLZwyWgTS10YnXwpDHmXXGOs1SyH88MOeeCzvtqUKnx6lbgg1hN 9UlApasHR8jsS9NNV0zFwwb3G9qwLx4scPivgJUOxyRCdSb5o7WDPHJC0/WD3iAr5XTe A92ne4dxDWJgKyjb150ts8KO7BXyAXPDDpFCg= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version :content-type:references; b=LXErEPH2sktuG/Dc67vAghQfsv8Y5CB4IPb6VK/MjiETgkUQSgdmzRtFV8gI5dhpUO AaEn9myfw5U0U5fSp/jUBayb+fAmpZAttnJo0tg7224IEEQkPKdGWkmUPBb8lILqcSN8 a5rfmNfZjpcttZQMxQiRlb3J2khUsYbe+/NWs= Received: by 10.142.193.13 with SMTP id q13mr2245696wff.109.1226302620843; Sun, 09 Nov 2008 23:37:00 -0800 (PST) Received: by 10.142.79.21 with HTTP; Sun, 9 Nov 2008 23:37:00 -0800 (PST) Message-ID: <1d709ecc0811092337q74fee9e7vc418eba9c798f3a4@mail.gmail.com> Date: Sun, 9 Nov 2008 23:37:00 -0800 From: "Vladimir Sitnikov" To: "Craig Ringer" Subject: Re: Improve Seq scan performance Cc: "=?ISO-8859-1?Q?Lutisch=E1n_Ferenc?=" , pgsql-performance@postgresql.org In-Reply-To: <4917DAFB.8000003@postnewspapers.com.au> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_109231_5011681.1226302620835" References: <4917D9C3.9060001@gmail.com> <4917DAFB.8000003@postnewspapers.com.au> X-Archive-Number: 200811/52 X-Sequence-Number: 31783 ------=_Part_109231_5011681.1226302620835 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline > Lutisch=E1n 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 index= es > do not contain information about tuple visibility. Data read from the ind= ex > 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 tup= le 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=3D0.00..792.00 rows=3D356 width=3D508) (actual time=3D0.129..9.071 rows=3D20 loops=3D1 read_shared=3D*667*(667) read_local= =3D0(0) flush=3D0 local_flush=3D0 file_read=3D0 file_write=3D0) Filter: (i ~~ '%123%'::text) Total runtime: 9.188 ms set enable_seqscan=3Doff -- Index Scan reads 2529 pages for some reason. I would expect *30 *(index size) + *20 *(number of matching entries) =3D 50 pages maximum, that is 10 times better than with seq scan. Index Scan using i_ix on seq_test (cost=3D0.00..1643.74 rows=3D356 width= =3D508) (actual time=3D0.334..16.746 rows=3D*20 *loops=3D1 read_shared=3D2529(2529) read_local=3D0(0) flush=3D0 local_flush=3D0 file_read=3D0 file_write=3D0) Filter: (i ~~ '%123%'::text) Total runtime: 16.863 ms Hopefully, there will be a clear distinction between filtering via index an= d filtering via table access. Regards, Vladimir Sitnikov ------=_Part_109231_5011681.1226302620835 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline
Lutisch=E1n 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 ind= exes do not contain information about tuple visibility. Data read from the = index might refer to tuples that've been deleted as far as your transac= tion is concerned, or to tuples that were created after your snapshot was t= aken.

My understanding is even though indices do not conta= in information on tuple visibility, index could be used to filter out recor= ds that is known to make no match. Since btree index stores exact values, P= ostgreSQL could scan through the index and skip those entries that do not c= ontain '%aaa%'. That will dramatically improve cases where the crit= eria 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 &= quot;performance bug" and add it to the "TODO" list:


create table seq_test
 as select cast(i as text) i, repeat('*', 500) padd= ing 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 co= ntains 10000 row versions in 30 pag= es
-- "seq_test"= : found 0 removable, 10000 nonremovable row versions in 667 pages

explain analyze select * from seq_test where i l= ike '%123%';
-- Seq Scan reads 667 p= ages (as expected)
= Seq Scan on seq_test&nb= sp; (cost=3D0.00..792.00 rows=3D356 width=3D508) (actual time=3D0.129..9.07= 1 rows=3D20 loops=3D1 read_shared=3D667(667) read_local=3D0(0) flush=3D0 local_flush=3D0 file_rea= d=3D0 file_write=3D0)
  Filter: (i ~~ &#= 39;%123%'::text)
Total runtime: 9.188 = ms

set enable_seqscan= =3Doff
-- Index Scan reads 2529 pages for= some reason. I would expect 30 <= /span>(index size) + 20 (number of matching entries) =3D 50 pages maximum, that is 10 times b= etter than with seq scan.
Index Scan using i_ix o= n seq_test  (cost=3D0.00..1643.74 rows=3D356 width=3D508) (actual time= =3D0.334..16.746 rows=3D20 loops=3D= 1 read_shared=3D2529(2529) read_local=3D0(0) flush=3D0 local_flush=3D0 file= _read=3D0 file_write=3D0)
  Filter: (i ~~ &#= 39;%123%'::text)
Total runtime: 16.863= ms

Hopefully, there will be a clear distinction between filtering via inde= x and filtering via table access.


Regards,
Vladimir Sitnikov<= br> ------=_Part_109231_5011681.1226302620835--