Can I do better than this heapscan and sort?

I have two tables node and relationship. Each relationship record connects two nodes and has an application keys (unfortunately named) that can be used by the application to look-up a relationship and get from one node to the other.

My query uses a node id and a description of a relationship from the node, and must find the "next" relationship that the node has. It does this by finding all the relationships that could be "next", ordering them and then getting the first.

Details are below but I end up with 6896 candidates for "next".

If I'm reading the output correctly it takes 13.509 ms to apply the filter and another 7 ms or so to do the sort of the remaining 6896 nodes.

Have tried many index combinations to try and improve the results. I suspect that with so many nodes to sort, postgresql will opt for heap scan rather than index. But why does it not use the IDX_order_sort_down_2 index for the sort?

Thanks,
Andy


Details..........

Version
-------
PostgreSQL 9.1.2 on x86_64-unknown-linux-gnu, compiled by gcc (GCC) 4.5.2, 64-bit

Tables
------
CREATE TABLE node (
node_id bigint NOT NULL,
node_type int4 NOT NULL,
c_state int4 NOT NULL,
d_state int4 NOT NULL,
sort_key bigint NOT NULL,
permissions bytea NOT NULL,
audit bytea NOT NULL,
pkg_id bytea NULL,
created timestamp NOT NULL
);

CREATE TABLE relationship (
rel_id bigint NOT NULL,
rel_type integer NOT NULL,
s_t_n bigint NOT NULL,
t_s_n bigint NOT NULL,
state integer NOT NULL,
control integer NOT NULL,
sort_key bigint NOT NULL,
prime_key bytea NULL,
prime_key_len integer NOT NULL,
sec_key bytea NULL,
sec_key_len integer NOT NULL,
up_sort_key bigint NOT NULL,
up_prime_key bytea NULL,
up_prime_key_len integer NOT NULL,
up_sec_key bytea NULL,
up_sec_key_len integer NOT NULL,
permissions bytea NOT NULL,
t_s_n_type integer NOT NULL,
created timestamp NOT NULL
);

Constraints
-----------
-- Primary keys
ALTER TABLE node ADD CONSTRAINT PK_node PRIMARY KEY (node_id);

ALTER TABLE relationship ADD CONSTRAINT PK_relationship PRIMARY KEY (rel_id);

-- Foreign keys
ALTER TABLE relationship ADD CONSTRAINT FK_node_s FOREIGN KEY (s_t_n) REFERENCES node (node_id);

ALTER TABLE relationship ADD CONSTRAINT FK_node_n FOREIGN KEY (t_s_n) REFERENCES node (node_id);

Indexes
-------
CREATE INDEX IDX_node_type ON node (node_type ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_node_sort_key ON node (sort_key ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_s_t_n ON relationship (s_t_n ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_t_s_n ON relationship (t_s_n ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_type ON relationship (rel_type ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_prime_key ON relationship (prime_key ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_u_prime_key ON relationship (up_prime_key ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_relationship_sec_key ON relationship (sec_key ASC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_order_first ON node(sort_key DESC, node_id DESC) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_order_sort_down_1 ON relationship(sort_key DESC, prime_key ASC NULLS FIRST, sec_key ASC NULLS FIRST) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_order_sort_down_2 ON relationship(sort_key DESC, prime_key ASC NULLS FIRST, sec_key DESC NULLS FIRST) TABLESPACE ds_appex_ts_10
;
CREATE INDEX IDX_order_sort_up ON relationship(up_sort_key DESC, up_prime_key ASC NULLS FIRST, up_sec_key ASC NULLS FIRST) TABLESPACE ds_appex_ts_10
;

Query
-----
CREATE OR REPLACE FUNCTION sp_get_rel_sort_dup_sec_desc(in_rel_type1 integer, in_rel_type2 integer, in_node_type integer, in_own_guid bigint, in_prev_prime_key bytea, in_prev_prime_key_len integer, in_prev_sec_key bytea, in_prev_sec_key_len integer, in_prev_sort_key bigint, in_ctrl integer) RETURNS select_rel_holder AS
'
declare
h select_rel_holder%rowtype;

begin
SELECT INTO h r.rel_id, r.t_s_n, r.rel_type, r.sort_key,
r.state,r.permissions, r.control,
r.prime_key, r.prime_key_len, r.sec_key, r.sec_key_len,
r.up_prime_key, r.up_prime_key_len, r.up_sec_key, r.up_sec_key_len
FROM relationship r
WHERE r.s_t_n = in_own_guid AND (r.rel_type = in_rel_type1 OR r.rel_type = in_rel_type2)
AND
(
(
(
r.prime_key > in_prev_prime_key
OR
( r.prime_key = in_prev_prime_key AND r.sec_key < in_prev_sec_key)
)
AND
r.sort_key = in_prev_sort_key
)

OR
r.sort_key < in_prev_sort_key
)
AND t_s_n_type = in_node_type
AND r.control >= in_ctrl
ORDER BY sort_key DESC, prime_key ASC NULLS FIRST, sec_key DESC NULLS FIRST LIMIT 1;
RETURN h;
end
'
language 'plpgsql' STABLE;


EXPLAIN ANALYZE output
-------------------------------
Limit (cost=48.90..48.90 rows=1 width=89) (actual time=21.480..21.480 rows=1 loops=1)
Output: rel_id, t_s_n, rel_type, sort_key, state, permissions, control, prime_key, prime_key_len, sec_key, sec_key_len, up_prime_key, up_prime_key_l
en, up_sec_key, up_sec_key_len

-> Sort (cost=48.90..48.90 rows=1 width=89) (actual time=21.479..21.479 rows=1 loops=1)
Output: rel_id, t_s_n, rel_type, sort_key, state, permissions, control, prime_key, prime_key_len, sec_key, sec_key_len, up_prime_key, up_prime
_key_len, up_sec_key, up_sec_key_len
Sort Key: r.sort_key, r.prime_key, r.sec_key
Sort Method: top-N heapsort Memory: 25kB

-> Bitmap Heap Scan on public.relationship r (cost=3.39..48.89 rows=1 width=89) (actual time=1.034..13.509 rows=6986 loops=1)
Output: rel_id, t_s_n, rel_type, sort_key, state, permissions, control, prime_key, prime_key_len, sec_key, sec_key_len, up_prime_key, up
_prime_key_len, up_sec_key, up_sec_key_len
Recheck Cond: (r.s_t_n = $4)
Filter: ((r.control >= $10) AND (r.t_s_n_type = $3) AND ((r.rel_type = $1) OR (r.rel_type = $2)) AND ((((r.prime_key > $5) OR ((r.prime_
key = $5) AND (r.sec_key < $7))) AND (r.sort_key = $9)) OR (r.sort_key < $9)))

-> Bitmap Index Scan on idx_relationship_s_t_n (cost=0.00..3.39 rows=18 width=0) (actual time=0.951..0.951 rows=6989 loops=1)
Index Cond: (r.s_t_n = $4)