Slow functional indexes?

I would like to understand what causes some of my indexes to be slower to
use than others with PostgreSQL 8.1. On a particular table, I have an int4
primary key, an indexed unique text 'name' column and a functional index of
type text. The function (person_sort_key()) is declared IMMUTABLE and
RETURNS NULL ON NULL INPUT.

A simple query ordering by each of these columns generates nearly identical
query plans, however runtime differences are significantly slower using the
functional index. If I add a new column to the table containing the result
of the function, index it and query ordering by this new column then the
runtime is nearly an order of magnitude faster than using the functional
index (and again, query plans are nearly identical).

(The following log is also at
http://rafb.net/paste/results/vKVuyi47.nln.html if that is more readable)

demo=# vacuum full analyze person;
VACUUM
demo=# reindex table person;
REINDEX
demo=# cluster person_pkey on person;
CLUSTER
demo=# explain analyze select * from person order by id offset 527000 limit 50;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=37039.09..37042.61 rows=50 width=531) (actual
time=1870.393..1870.643 rows=50 loops=1)
-> Index Scan using person_pkey on person (cost=0.00..37093.42
rows=527773 width=531) (actual time=0.077..1133.659 rows=527050 loops=1)
Total runtime: 1870.792 ms
(3 rows)

demo=# cluster person_name_key on person;
CLUSTER
demo=# explain analyze select * from person order by name offset 527000
limit 50;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=63727.87..63733.91 rows=50 width=531) (actual
time=1865.769..1866.028 rows=50 loops=1)
-> Index Scan using person_name_key on person (cost=0.00..63821.34
rows=527773 width=531) (actual time=0.068..1138.649 rows=527050 loops=1)
Total runtime: 1866.153 ms
(3 rows)

demo=# cluster person_sorting_idx on person;
CLUSTER
demo=# explain analyze select * from person order by
person_sort_key(displayname,name) offset 527000 limit 50;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=65806.62..65812.86 rows=50 width=531) (actual
time=13846.677..13848.102 rows=50 loops=1)
-> Index Scan using person_sorting_idx on person (cost=0.00..65903.14
rows=527773 width=531) (actual time=0.214..13093.090 rows=527050 loops=1)
Total runtime: 13848.254 ms
(3 rows)

demo=# alter table person add column sort_key text;
ALTER TABLE
demo=# update person set sort_key=person_sort_key(displayname,name);
UPDATE 527773
demo=# create index person_sort_key_idx on person(sort_key);
CREATE INDEX
demo=# vacuum analyze person;
VACUUM
demo=# cluster person_sort_key_idx on person;
CLUSTER
demo=# explain analyze select * from person order by sort_key offset 527000
limit 50;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=41069.28..41073.18 rows=50 width=553) (actual
time=1999.456..1999.724 rows=50 loops=1)
-> Index Scan using person_sort_key_idx on person (cost=0.00..41129.52
rows=527773 width=553) (actual time=0.079..1274.952 rows=527050 loops=1)
Total runtime: 1999.858 ms
(3 rows)

--
Stuart Bishop <stuart(dot)bishop(at)canonical(dot)com> http://www.canonical.com/
Canonical Ltd. http://www.ubuntu.com/