Обсуждение: bitmap-index-scan faster than seq-scan on full-table-scan (gin index)

Hi.

The test data a set of generated terms using this perl-script
http://shrek.krogh.cc/~jesper/build-test.pl
and http://shrek.krogh.cc/~jesper/words.txt

I have generated a test dataset with an average tsvector length of
around 250 and 200.000 tuples in the dataset.

Conceptually searching for the "full dataset" would always be fastest
solved by a seq-scan. The query planner enforces this so much, so not
even "enable_seqscan=off" can convince it to to something else. So in
the next two explain analyze I compare a query searching 99% of the
table up with a seqscan. The 98% case is enforced to be a 
"bitmap-index-scan"
I would expect the runtime of the seqscan to be shortest and the 
bitmap-index-scan
to be quite a lot larger, due to "random access" and the fact that the 
index-data
also needs to be read in from disk.

Bot runs are run with a freshly started postgresql backend and
"echo 3 > /proc/sys/vm/drop_caches" so the os caching should not come 
into play.

ftstest=# EXPLAIN ANALYZE select id from ftstest where body_fts @@ 
to_tsquery('commonterm98');                                                                 QUERY 
PLAN

--------------------------------------------------------------------------------------------------------------------------------------------
BitmapHeap Scan on ftstest  (cost=6579.81..992733.57 rows=195976 
 
width=4) (actual time=4813.258..7081.277 rows=195976 loops=1)   Recheck Cond: (body_fts @@
to_tsquery('commonterm98'::text))  ->  Bitmap Index Scan on ftstest_gist_idx  (cost=0.00..6530.82 
 
rows=195976 width=0) (actual time=4787.513..4787.513 rows=195976 loops=1)         Index Cond: (body_fts @@
to_tsquery('commonterm98'::text))Total runtime: 7389.346 ms
 
(5 rows)

ftstest=# set enable_bitmapscan = off;
WARNING:  terminating connection because of crash of another server process
DETAIL:  The postmaster has commanded this server process to roll back 
the current transaction and exit, because another server process exited 
abnormally and possibly corrupted shared memory.
HINT:  In a moment you should be able to reconnect to the database and 
repeat your command.
server closed the connection unexpectedly    This probably means the server terminated abnormally    before or while
processingthe request.
 
The connection to the server was lost. Attempting reset: Succeeded.
ftstest=# set enable_bitmapscan = off;
SET
ftstest=# EXPLAIN ANALYZE select id from ftstest where body_fts @@ 
to_tsquery('commonterm98');                                                      QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
SeqScan on ftstest  (cost=0.00..1006314.00 rows=195976 width=4) 
 
(actual time=96.077..60092.080 rows=195976 loops=1)   Filter: (body_fts @@ to_tsquery('commonterm98'::text)) Total
runtime:60436.556 ms
 
(3 rows)

So searching the full table via a bitmap-index-scan is actually 9 times
cheaper than a seq-scan.  (same on 9.0b1 and 8.4).

Digging more into it reveals that the body_fts tsvector is indeed needed for
the "filter" in the SeqScan. The tsvector data is stored in a TOAST 
table and
the in the bitmap-index-scan case it only needs to read in the main table
for checking visibillity. In the end it translates to reading in 1.4GB of
TOAST-data vs. reading in 34MB of table data.

Thinking a bit, then I dont think this is a particular rare case, 
allthough the
ratio between the tables may be a real cornercase. The ratio is not 1:33 
in the
dataset that looks like the production dataset, but more 1:10, but in 
all cases
in "production" there would be a much higher cache-hit ratio on the 
gin-index
and the main table pages than on the TOAST table, so even with a ratio 
of 1:1
there most likely would be a real-world benefit.

Would it be possible to implement the "Filtering" using the gin-index and
a subsequent visibillity-check as on the index-scan?

The same end up being the case for queries ordered by btree indexes and
"filtered" by gin-indexes.

Jesper
-- 
Jesper

Jesper Krogh <jesper@krogh.cc> writes:
> Conceptually searching for the "full dataset" would always be fastest
> solved by a seq-scan. The query planner enforces this so much, so not
> even "enable_seqscan=off" can convince it to to something else.
> ...
> Would it be possible to implement the "Filtering" using the gin-index and
> a subsequent visibillity-check as on the index-scan?

You're failing to make any sense whatsoever.  If you're reading the full
dataset, there is no filter condition.  If there is a potentially
indexable filter condition, the planner will certainly consider that.

Personally I think the issue here has got more to do with the
non-immutability of the single-argument form of to_tsquery, which means
it gets re-evaluated at every row during a seqscan.  Do your results
change if you work with to_tsquery('english', ...)  (or whatever your
default TS config is)?
        regards, tom lane

On 2010-05-31 22:09, Tom Lane wrote:
> Jesper Krogh<jesper@krogh.cc>  writes:
>    
>> Conceptually searching for the "full dataset" would always be fastest
>> solved by a seq-scan. The query planner enforces this so much, so not
>> even "enable_seqscan=off" can convince it to to something else.
>> ...
>> Would it be possible to implement the "Filtering" using the gin-index and
>> a subsequent visibillity-check as on the index-scan?
>>      
> You're failing to make any sense whatsoever.  If you're reading the full
> dataset, there is no filter condition.  If there is a potentially
> indexable filter condition, the planner will certainly consider that.
>    
Yes, you're totally right on that (about making sense).

But that is because of the "simplified" use-case described. A more elaborate
description ..
I have a table with has a set of colums attached to it typically
used for "sorting" these columns may also be inferred on the table
by a typical join condition and a document that is fts-indexed.
So the actual use-case is that people query for:

"give me the 1000 most recent documents matching <term>"

Term may in some cases be hugely trivial, only filtering away 0.001% of the
dataset resulting in a "index-scan on a btree date index" filtering on the
tsvector column for <term>".

Term may also be something really specific only returning a single
or a few documents and just pushing a post-sorting to get the ordering.

But in the case where the query-planner falls over to a "index-scan"
on one of the btree-indices it ends up reading over from the TOAST data.

Will the planner consider doing the index-scan(forward or backwards)
on a btree-index and filter using a gin-index instead of filtering directly
on the tuple-data?
(I haven't been able to enforce an query-plan that looks like that).

> Personally I think the issue here has got more to do with the
> non-immutability of the single-argument form of to_tsquery, which means
> it gets re-evaluated at every row during a seqscan.  Do your results
> change if you work with to_tsquery('english', ...)  (or whatever your
> default TS config is)?
>    

It is english..  and yes it did indeed change the results. So the 
expensive case
dropped from ~60s to ~28s and the cheap case from ~7.3s to ~4.3s, that
is quite surprising that such "small" change can have that huge impact. The
single-argument version should be forbidden.

But the performance ratio between the two cases is still the same.

The test was actually run with the preliminary gincostestimate-patch from
Oleg Bartunov so the actual cost estimates match way better now, but that
should not impact the actual runtime.

Thanks

-- 
Jesper