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 the following table and index definitions:

CREATE TABLE munkalap (
    munkalap_id serial PRIMARY KEY,
    ...
);

CREATE TABLE munkalap_lepes (
    munkalap_lepes_id serial PRIMARY KEY,
    munkalap_id integer REFERENCES munkalap (munkalap_id),
    ...
);

CREATE INDEX idx_munkalap_lepes_munkalap_id ON munkalap_lepes (munkalap_id);

Why are none of the indexes on munkalap_id used in the following query?

EXPLAIN ANALYZE SELECT ml.* FROM munkalap m JOIN munkalap_lepes ml USING (munkalap_id);

QUERY PLAN
Hash Join  (cost=119.17..2050.88 rows=38046 width=214) (actual time=0.824..18.011 rows=38046 loops=1)
  Hash Cond: (ml.munkalap_id = m.munkalap_id)
  ->  Seq Scan on munkalap_lepes ml  (cost=0.00..1313.46 rows=38046 width=214) (actual time=0.005..4.574 rows=38046 loops=1)
  ->  Hash  (cost=78.52..78.52 rows=3252 width=4) (actual time=0.810..0.810 rows=3253 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 115kB
        ->  Seq Scan on munkalap m  (cost=0.00..78.52 rows=3252 width=4) (actual time=0.003..0.398 rows=3253 loops=1)
Total runtime: 19.786 ms

It's the same even if I add a filter:

EXPLAIN ANALYZE SELECT ml.* FROM munkalap m JOIN munkalap_lepes ml USING (munkalap_id) WHERE NOT lezarva;

QUERY PLAN
Hash Join  (cost=79.60..1545.79 rows=1006 width=214) (actual time=0.616..10.824 rows=964 loops=1)
  Hash Cond: (ml.munkalap_id = m.munkalap_id)
  ->  Seq Scan on munkalap_lepes ml  (cost=0.00..1313.46 rows=38046 width=214) (actual time=0.007..5.061 rows=38046 loops=1)
  ->  Hash  (cost=78.52..78.52 rows=86 width=4) (actual time=0.587..0.587 rows=87 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 4kB
        ->  Seq Scan on munkalap m  (cost=0.00..78.52 rows=86 width=4) (actual time=0.014..0.560 rows=87 loops=1)
              Filter: (NOT lezarva)
Total runtime: 10.911 ms
share|improve this question

2 Answers 2

up vote 8 down vote accepted

Many people have heard guidance that "sequential scans are bad" and seek to eliminate them from their plans, but it isn't so simple. If a query is going to cover every row in a table, a sequential scan is the fastest way to get those rows. This is why your original join query used seq scan, because all rows in both tables were required.

When planning a query, Postgres's planner estimates the costs of various operations (computation, sequential, and random IO) under different possible schemes, and picks the plan it estimates as having the lowest cost. When doing IO from rotating storage (disks), random IO is usually substantially slower than sequential IO, the default pg configuration for random_page_cost and seq_page_cost estimate a 4:1 difference in cost.

These considerations come into play when considering a join or filter method which uses an index vs one which sequentially scans a table. When using an index, the plan may find a row quickly via the index, then have to account for a random block read to resolve the row data. In the case of your second query which added a filtering predicate WHERE NOT lezarva, you can see how this effected the planning estimates in the EXPLAIN ANALYZE results. The planner estimates 1006 rows resulting from the join (which pretty closely matches the actual result set of 964). Given that the larger table munkalap_lepes contains about 38K rows, the planner sees that the join is going to have to access about 1006/38046 or 1/38 of the rows in the table. It also knows the avg row width is 214 bytes and a block is 8K, so there's about 38 rows/block.

With these statistics, the planner considers it likely that the join will have to read all or most of the table's data blocks. Since the index lookups aren't free either, and the computation to scan a block evaluating a filter condition is very cheap relative to IO, the planner has chosen to sequentially scan the table and avoid index overhead and random reads as it calculates the seq scan will be faster.

In the real world, data is often available in memory via the OS page cache, and so not every block read requires IO. It can be quite hard to predict how effective a cache will be for a given query, but the Pg planner does use some simple heuristics. The configuration value effective_cache_size informs the planners estimates of the likelyhood of incurring actual IO costs. A larger value will cause it to estimate a lower cost to random IO and may thus bias it towards an index driven method over a sequential scan.

share|improve this answer
    
Thanks, this is so far the best (and most concise) description I've read. Clarified a few key points. –  dezso Apr 21 '12 at 7:03
1  
Excellent explanation. The calculation of rows / data page is a bit off, though. You have to factor in the page header (24 bytes) + 4 bytes for each per-row item pointer + the row header HeapTupleHeader (23 bytes per row) + NULL bitmask + alignment according to MAXALIGN. Finally, an unknown amount of padding due to data alignment depending on the data types of the columns and their sequence. All in all there are no more than 33 rows on an 8 kb page in this case. (Not taking TOAST into account.) –  Erwin Brandstetter Apr 30 '12 at 18:39
1  
@ErwinBrandstetter Thanks for filling in more exacting row size calculations. I had always assumed the row width estimate output by explain would include per-row considerations like the header and NULL-bitmask, but not page level overhead. –  dbenhur Apr 30 '12 at 23:10
1  
@dbenhur: You can run a quick EXPLAIN ANALYZE SELECT foo from bar with a basic dummy table to verify. Also, actual on-disc space depends on data alignment, which would be hard to factor in when only some rows are retrieved. The row width in EXPLAIN represents the basic space requirement for the retrieved set of columns. –  Erwin Brandstetter Apr 30 '12 at 23:42

You are retrieving all rows from both tables, so there is no real benefit by using an index scan. An index scan only makes sense if you are selecting only a few rows from a table (typically less than 10%-15%)

share|improve this answer
    
Yep, you are right :) I tried to clarify the situation with a more specific case, see the last query. –  dezso Apr 17 '12 at 12:31
    
@dezso: Same thing. If you have an index on (lezarva, munkalap_id) and it is selective enough, then it may be used. The NOT makes that less probable. –  ypercube Apr 17 '12 at 12:37
    
I added a partial index based on your suggestion and it is used, so half the problem is solved. But I wouldn't expect the index on the foreign key being useless given that I want to JOIN against only 87 values compared to the original 3252. –  dezso Apr 17 '12 at 12:49
1  
@dezso The rows avg 214 bytes wide so you'll have a little under 40 rows per 8K data block. The selectivity of the index is also about 1/40 (1006/38046). So, Pg figures that reading all the blocks sequentially is cheaper then the probable reading of about the same number of blocks randomly when using the index. These estimated tradoffs can be influenced by effective_cache_size and random_page_cost configuration values. –  dbenhur Apr 19 '12 at 22:02
    
@dbenhur: could you make your comment a proper answer? –  dezso Apr 20 '12 at 6:50

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.