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 a couple of questions regarding working of indexes in PostgreSQL. I have a Friends table with the following index:

   Friends ( user_id1 ,user_id2) 

user_id1 and user_id2 are foreign keys to user table

  1. Are these equivalent? If not then why?

    Index(user_id1,user_id2) and Index(user_id2,user_id1)
    
  2. If I create Primary Key(user_id1,user_id2), does it automatically create indexes for it and

    a) If the indexes in the first question are not equivalent, then which index is created on above primary key command?

Edit : Thanks to all the contributors for taking such an active role in explaining exactly how indexes may work in postgresql.

share|improve this question
1  
To the OP, I removed the third bit about how other RDBMs handle the indexes, to tighten up the focus of this particular question. –  Derek Downey Oct 5 '11 at 14:35
add comment

5 Answers

up vote 25 down vote accepted

Here are the results of querying a table on the second column of a multicolumn index.
The effects are easy to reproduce for anybody. Just try it at home.
I tested with PostgreSQL 9.0:

event=# SELECT version();
                                         version
-------------------------------------------------------------------------------------------
PostgreSQL 9.0.5 on x86_64-pc-linux-gnu, compiled by GCC gcc-4.4.real (Debian 4.4.5-8) 4.4.5, 64-bit

I used a medium sized table of a real-life database with 23322 rows. It implements the n:m relationship between the tables adr (address) and att (attribute), but that's not relevant here. Simplified schema:

CREATE TABLE ef.adratt
( adratt_id serial PRIMARY KEY,
  adr_id integer NOT NULL,
  att_id integer NOT NULL,
  log_up timestamp(0) without time zone NOT NULL DEFAULT (now())::timestamp(0) without time zone,
  CONSTRAINT adratt_uni UNIQUE (adr_id, att_id)
);

The UNIQUE constraint effectively implements a unique index. I repeated the test with a plain index to be sure and got identical results as expected.

CREATE INDEX adratt_idx ON ef.adratt(adr_id, att_id)

The table is clustered on the adratt_uni index and before the test I ran:

CLUSTER ef.adratt;
ANALYZE ef.adratt;

Sequential scans for queries on (adr_id, att_id) are as fast as they can possibly be. The multicolumn index will still be used for a query condition on the second index column alone.

I ran the queries a couple of times to populate the cache and the picked the best out of ten runs to get comparable results.


1) Query using both columns

SELECT *
FROM   ef.adratt
WHERE  att_id = 90
AND    adr_id = 10;

 adratt_id | adr_id | att_id |       log_up
-----------+--------+--------+---------------------
       123 |     10 |     90 | 2008-07-29 09:35:54
(1 row)

Output of EXPLAIN ANALYZE:

Index Scan using adratt_uni on adratt  (cost=0.00..3.48 rows=1 width=20) (actual time=0.022..0.025 rows=1 loops=1)
  Index Cond: ((adr_id = 10) AND (att_id = 90))
Total runtime: 0.067 ms

2) Query using first column

SELECT * FROM ef.adratt WHERE adr_id = 10

 adratt_id | adr_id | att_id |       log_up
-----------+--------+--------+---------------------
       126 |     10 |     10 | 2008-07-29 09:35:54
       125 |     10 |     13 | 2008-07-29 09:35:54
      4711 |     10 |     21 | 2008-07-29 09:35:54
     29322 |     10 |     22 | 2011-06-06 15:50:38
     29321 |     10 |     30 | 2011-06-06 15:47:17
       124 |     10 |     62 | 2008-07-29 09:35:54
     21913 |     10 |     78 | 2008-07-29 09:35:54
       123 |     10 |     90 | 2008-07-29 09:35:54
     28352 |     10 |    106 | 2010-11-22 12:37:50
(9 rows)

Output of EXPLAIN ANALYZE:

Index Scan using adratt_uni on adratt  (cost=0.00..8.23 rows=9 width=20) (actual time=0.007..0.023 rows=9 loops=1)
  Index Cond: (adr_id = 10)
Total runtime: 0.058 ms

3) Query using second column

SELECT * FROM ef.adratt WHERE att_id = 90

 adratt_id | adr_id | att_id |       log_up
-----------+--------+--------+---------------------
       123 |     10 |     90 | 2008-07-29 09:35:54
       180 |     39 |     90 | 2008-08-29 15:46:07
...
(83 rows)

Output of EXPLAIN ANALYZE:

Index Scan using adratt_uni on adratt  (cost=0.00..818.51 rows=83 width=20) (actual time=0.014..0.694 rows=83 loops=1)
  Index Cond: (att_id = 90)
Total runtime: 0.849 ms

4) Disable indexscan & bitmapscan

SET enable_indexscan = off;
SELECT * FROM ef.adratt WHERE att_id = 90

Output of EXPLAIN ANALYZE:

Bitmap Heap Scan on adratt  (cost=779.94..854.74 rows=83 width=20) (actual time=0.558..0.743 rows=83 loops=1)
  Recheck Cond: (att_id = 90)
  ->  Bitmap Index Scan on adratt_uni  (cost=0.00..779.86 rows=83 width=0) (actual time=0.544..0.544 rows=83 loops=1)
        Index Cond: (att_id = 90)
Total runtime: 0.894 ms 

SET enable_bitmapscan = off
SELECT * FROM ef.adratt WHERE att_id = 90

Output of EXPLAIN ANALYZE:

Seq Scan on adratt  (cost=0.00..1323.10 rows=83 width=20) (actual time=0.009..2.429 rows=83 loops=1)
  Filter: (att_id = 90)
Total runtime: 2.680 ms

Conclusion

As expected, the multi-column index is used for a query on the second column alone.
As expected, it is less effective, but the query is still 3x faster than without the index.
After disabling index scans, the query planner chooses a bitmap heap scan, which performs almost as fast. Only after disabling that, too, it falls back to a sequential scan.

share|improve this answer
    
Thanks for the detailed example. I wonder if this has something to do with the data distribution. I set up that table and filled adr_id, att_id with random values and my PostgreSQL 9.1 does not use the index for the WHERE clause on att_id (but I only created the plain index to make filling the table with random data easier). I need to try with different data sets. Thanks again for pointing this out and investing the time to show this! –  a_horse_with_no_name Nov 2 '11 at 0:04
1  
OK, after creating several different data sets I could finally see this on my computer as well. Thanks again, this is really interesting. –  a_horse_with_no_name Nov 2 '11 at 0:28
    
@Erwin all you are proving is that it is quicker to full scan an index than a larger table. The degree of the speedup will be very much related to the relative sizes of the table vs index - but you are doing a full index scan as you can see by turning on the 'buffers' option of explain analyze –  Jack Douglas Nov 2 '11 at 10:33
    
the fact you are clustering the underlying table is important too - scattered reads would impact on the cost of the index scan plus table lookup against a full scan of the table –  Jack Douglas Nov 2 '11 at 10:34
1  
@JackDouglas: I have given this some more thought. Clustering may help generally, because it is effectively also a vacuum full and a reindex. Other than that it will help index scans on the first or both leading columns a lot, but hurt queries on the second column. In a freshly clustered table, rows with the same value in the second column are spread out, so that a maximum of blocks will have to be read. –  Erwin Brandstetter Nov 5 '11 at 2:13
show 4 more comments

re 1) Yes and no.

For a query that uses both columns e.g. where (user_id1, user_id2) = (1,2) it doesn't matter which index is created.

For a query that has a condition on only one of the columns e.g. where user_id1 = 1 it does matter because usually only the "leading" columns can be used for a comparison by the optimizer. So where user_id1 = 1 would be able to use the index (user_id1, user_id2) but it would not be able to an index (user_id2, user_id1) for all cases.

After playing around with this (after Erwin so kindly showed us a setup where it works), it seems that this depends highly on the data distribution of the second column although I haven't yet found out which situation enables the optimizer to use trailing columns for a WHERE condition.

Oracle 11 which can also (sometimes) use columns that are not at the beginning of the index definition.

re 2) Yes it will create an index

Quote from the manual

Adding a primary key will automatically create a unique btree index on the column or group of columns used in the primary key.

re 2a) Primary Key (user_id1,user_id2) will create an index on (user_id1,user_id2) (which you can find out by yourself very easily by simply creating such a primary key)

I highly recommend that you read the chapter about indexes in the manual, it basically answers all the questions above:

http://www.postgresql.org/docs/current/static/indexes.html

share|improve this answer
5  
Additionally, I think this post does a good job explaining order on index columns and other index related topics: –  DrColossos Oct 4 '11 at 8:03
    
@DrColossos - fantastic link, and I didn't know about partial indexes until reading about them in the article - that will be very helpful to me, thanks –  Jack Douglas Oct 4 '11 at 19:05
1  
This claim is wrong "So where user_id1 = 1 would be able to use the index (user_id1, user_id2) but not (user_id2, user_id1)." Just try for yourself and see. –  Erwin Brandstetter Oct 31 '11 at 18:24
1  
@Erwin please note I'm in no way suggesting anything you wrote is incorrect - and I admire your attention to detail and willingness to evidence your claims. –  Jack Douglas Nov 2 '11 at 11:01
1  
you might find this discussion interesting... –  Jack Douglas Nov 2 '11 at 12:11
show 5 more comments

Ad 1)
There are limitations in PostgreSQL like @a_horse_with_no_name describes. Up until version 8.0 it could use multi-column indexes only for queries on the first column(s). This has been improved decisively in version 8.1. The current manual claims:

A multicolumn B-tree index can be used with query conditions that involve any subset of the index's columns, but the index is most efficient when there are constraints on the leading (leftmost) columns.

Emphasis mine. I can confirm that from experience.

share|improve this answer
    
-1 this is really a misleading quote (not wrong, just misleading) - postgres does nothing at all like Oracle's "skip scans", but can use indexes to filter to "save visits to the table proper, but they do not reduce the portion of the index that has to be scanned" –  Jack Douglas Oct 3 '11 at 11:36
2  
How is that misleading? It is a direct quote from the docs, it is correct and effective in real life in that it speeds up queries. It is nothing but true. What "Oracle does" is orthogonal to the question. –  Erwin Brandstetter Oct 3 '11 at 12:23
    
It is true as you say, but the way the indexes are "used" in this case is really of incidental importance compared to the Oracle functionality a_horse mentions. "The limitations in PostgreSQL that @a_horse_with_no_name describe" are still the case in 9.1 if I understand his answer correctly, which is about "reducing the portion of the index that has to be scanned". Note that my quote is from your link to the postgres docs. –  Jack Douglas Oct 3 '11 at 12:38
1  
Just in case you missed this great link posted by DrColossos –  Jack Douglas Oct 4 '11 at 19:06
1  
Here you go - now with link to guide through the many answers. –  Erwin Brandstetter Nov 3 '11 at 16:56
show 5 more comments
  1. Are these equivalent? If not then why?

    Index(user_id1,user_id2) and Index(user_id2,user_id1)

These are not equivalent and generally speaking index(bar,baz) will not be efficient for queries of the form select * from foo where baz=?

Erwin has demonstrated that such indexes can indeed speed up a query but this effect is limited and not of the same order as you generally expect an index to improve a lookup - it relies on the fact that a 'full scan' of an index is often quicker than a 'full scan' of the indexed table due to the extra columns in the table that don't appear in the index.

Summary: indexes can help queries even on non-leading columns, but in one of two secondary and relatively minor ways and not in the dramatic way you normally expect an index to help due to it's btree structure

nb the two ways the index can help are if a full scan of the index is significantly cheaper than a full scan of the table and either: 1. the table lookups are cheap (because there are few of them or they are clustered), or 2. the index is covering so there are no table lookups at all oops, see Erwins comments here

testbed:

create table foo(bar integer not null, baz integer not null, qux text not null);

insert into foo(bar, baz, qux)
select random()*100, random()*100, 'some random text '||g from generate_series(1,10000) g;

query 1 (no index, hitting 74 buffers):

explain (buffers, analyze, verbose) select max(qux) from foo where baz=0;
                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=181.41..181.42 rows=1 width=32) (actual time=3.301..3.302 rows=1 loops=1)
   Output: max(qux)
   Buffers: shared hit=74
   ->  Seq Scan on stack.foo  (cost=0.00..181.30 rows=43 width=32) (actual time=0.043..3.228 rows=52 loops=1)
         Output: bar, baz, qux
         Filter: (foo.baz = 0)
         Buffers: shared hit=74
 Total runtime: 3.335 ms

query 2 (with index - the optimizer ignores the index - hitting 74 buffers again):

create index bar_baz on foo(bar, baz);

explain (buffers, analyze, verbose) select max(qux) from foo where baz=0;
                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=199.12..199.13 rows=1 width=32) (actual time=3.277..3.277 rows=1 loops=1)
   Output: max(qux)
   Buffers: shared hit=74
   ->  Seq Scan on stack.foo  (cost=0.00..199.00 rows=50 width=32) (actual time=0.043..3.210 rows=52 loops=1)
         Output: bar, baz, qux
         Filter: (foo.baz = 0)
         Buffers: shared hit=74
 Total runtime: 3.311 ms

query 2 (with index - and we trick the optimizer to use it):

explain (buffers, analyze, verbose) select max(qux) from foo where bar>-1000 and baz=0;
                                                       QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=115.56..115.57 rows=1 width=32) (actual time=1.495..1.495 rows=1 loops=1)
   Output: max(qux)
   Buffers: shared hit=36 read=30
   ->  Bitmap Heap Scan on stack.foo  (cost=73.59..115.52 rows=17 width=32) (actual time=1.370..1.428 rows=52 loops=1)
         Output: bar, baz, qux
         Recheck Cond: ((foo.bar > (-1000)) AND (foo.baz = 0))
         Buffers: shared hit=36 read=30
         ->  Bitmap Index Scan on bar_baz  (cost=0.00..73.58 rows=17 width=0) (actual time=1.356..1.356 rows=52 loops=1)
               Index Cond: ((foo.bar > (-1000)) AND (foo.baz = 0))
               Buffers: shared read=30
 Total runtime: 1.535 ms

So access via the index is twice as fast in this case hitting 30 buffers - which in terms of indexing is 'slightly faster'!, and YMMV depending on the relative size of table and index, along with the number of filtered rows and clustering characteristics of the data in the table

By contrast, queries on the leading column make use of the btree structure of the index - in this case hitting 2 buffers:

explain (buffers, analyze, verbose) select max(qux) from foo where bar=0;
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=75.70..75.71 rows=1 width=32) (actual time=0.172..0.173 rows=1 loops=1)
   Output: max(qux)
   Buffers: shared hit=38
   ->  Bitmap Heap Scan on stack.foo  (cost=4.64..75.57 rows=50 width=32) (actual time=0.036..0.097 rows=59 loops=1)
         Output: bar, baz, qux
         Recheck Cond: (foo.bar = 0)
         Buffers: shared hit=38
         ->  Bitmap Index Scan on bar_baz  (cost=0.00..4.63 rows=50 width=0) (actual time=0.024..0.024 rows=59 loops=1)
               Index Cond: (foo.bar = 0)
               Buffers: shared hit=2
 Total runtime: 0.209 ms
share|improve this answer
    
+1 for very informative answer. I still have a few issues with it that won't fit into a comment. I wrote another answer. –  Erwin Brandstetter Nov 2 '11 at 20:26
1  
Thanks for the excellent corrective. I would very much like to know what other effects are in play here. I may try and scale up some tests and try and eliminate caching by rebooting to see if that reveals anything. –  Jack Douglas Nov 2 '11 at 22:25
add comment

This is in answer to Jack's answer. A comment wouldn't do.

There are no covering indexes in PostgreSQL, yet. Due to the MVCC model, every tuple in the result set has to be visited to check visibility. You may be be thinking of Oracle. Read here.

PostgreSQL developers talk about "index-only scans". In fact, the feature has been committed a few weeks ago and is planned for version 9.2. Read the commit message.
Depesz (also active on SO) wrote a very informative Blog post.

This is a bit off, too:

it relies on the fact that a 'full scan' of an index is often quicker than a 'full scan' of the indexed table due to the extra columns in the table that don't appear in the index.

As reported in comments on my other answer I have also run tests with a table of two integers and nothing else. The index holds the same columns as the table. The size of a btree index is around 2/3 that of the table. Not enough to explain a speedup of factor 3. I ran more test, based on your setup, simplified to two columns and with a 100000 rows. On my PostgreSQL 9.0 installation the results were consistent.

If the table has additional columns, the speedup with index becomes more substantial, but that is certainly not the only factor here.

To sum up the major points:

  • Multi-column indexes can be used with queries on non-leading columns, but the speedup is only around factor 3 for selective criteria (small percentage of rows in the result). Higher for larger tuples, lower for larger portions of the table in the result set.
  • Create an additional index on those columns if performance is important.
  • If all your resulting columns are included in an index, expect performance improvements with version 9.2 where "index-only scans" (covering indexes) are introduced.
share|improve this answer
1  
The "index-only scans" feature just made it into beta. h-online.com/open/news/item/… –  Ben Atkin May 15 '12 at 15:06
    
Ben Atkin was referring to PostgreSQL 9.2 beta - so since 9.2 this feature is released. –  RichVel Sep 1 '13 at 13:08
add comment

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.