BUG #10189: Limit in 9.3.4 no longer works when ordering using a composite multi-type index

The following bug has been logged on the website:

Bug reference: 10189
Logged by: Nick Rupley
Email address: nickr(at)mirth(dot)com
PostgreSQL version: 9.3.4
Operating system: CentOS
Description:

It would appear that when you order on a column such that the query plan
scans across a composite, multi-type index (say, bigint and integer), and
the plan runs through an Index Cond, doing all that AND a LIMIT clause no
longer works. And by "no longer works" I mean the query does not return any
results when it should.

Assuming that the column being ordered on falls within the index composite,
no SORT or SEQ SCAN is done, because the result set is already ordered by
virtue of the BTREE. No sorting is needed. So it's just a simple Limit ->
Index Scan, Index Cond, Filter. In 9.0.13 this works perfectly, but in 9.3.4
no rows are returned by the query (though a COUNT still works as expected).
It also seems that the data distribution matters, because it only appears to
happen when the expected result set is small (that is, less than a couple
hundred records).

Let me see if I can provide enough information to "prove" that it's a bug...
Here's the table description:

mirthdb=# \d d_mm100
Table "public.d_mm100"
Column | Type | Modifiers
----------------+--------------------------+--------------------
id | integer | not null
message_id | bigint | not null
server_id | character varying(36) | not null
received_date | timestamp with time zone |
status | character(1) | not null
connector_name | text |
send_attempts | integer | not null default 0
send_date | timestamp with time zone |
response_date | timestamp with time zone |
error_code | integer | not null default 0
chain_id | integer | not null
order_id | integer | not null
Indexes:
"d_mm100_pkey" PRIMARY KEY, btree (message_id, id)
"d_mm100_fki" btree (message_id)
"d_mm100_index1" btree (message_id, id, status)
"d_mm100_index2" btree (message_id, server_id, id)
Foreign-key constraints:
"d_mm100_fkey" FOREIGN KEY (message_id) REFERENCES d_m100(id) ON DELETE
CASCADE
Referenced by:
TABLE "d_mc100" CONSTRAINT "d_mc100_fkey" FOREIGN KEY (message_id,
metadata_id) REFERENCES d_mm100(message_id, id) ON DELETE CASCADE
TABLE "d_mcm100" CONSTRAINT "d_mcm100_fkey" FOREIGN KEY (message_id,
metadata_id) REFERENCES d_mm100(message_id, id) ON DELETE CASCADE

mirthdb=# select version();
version
--------------------------------------------------------------------------------------------------------------------
PostgreSQL 9.0.13 on x86_64-unknown-linux-gnu, compiled by GCC gcc (GCC)
4.1.2 20080704 (Red Hat 4.1.2-44), 64-bit
(1 row)

Here's the explain/analyze and the actual queries being done in 9.0.13:

# /opt/pgsql/bin/psql -U postgres -d mirthdb
psql (9.0.13)
Type "help" for help.

mirthdb=# explain analyze select * from d_mm100 where ID = 0 AND status =
'R' AND server_id = '2f9d9557-e260-45ee-92a3-b3069422cce9' order by
(message_id) limit 7 offset 0;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..54319.46 rows=1 width=100) (actual time=193.292..193.292
rows=0 loops=1)
-> Index Scan using d_mm100_index1 on d_mm100 (cost=0.00..54319.46
rows=1 width=100) (actual time=193.281..193.281 rows=0 loops=1)
Index Cond: ((id = 0) AND (status = 'R'::bpchar))
Filter: ((server_id)::text =
'2f9d9557-e260-45ee-92a3-b3069422cce9'::text)
Total runtime: 193.370 ms
(5 rows)

mirthdb=# select * from d_mm100 where ID = 0 AND status = 'R' AND server_id
= '2f9d9557-e260-45ee-92a3-b3069422cce9' order by (message_id) limit 7
offset 0;
id | message_id | server_id |
received_date | status | connector_name | send_attempts | send_date |
response_date | error_code | chain_id | o
rder_id
----+------------+--------------------------------------+---------------------------+--------+----------------+---------------+-----------+---------------+------------+----------+--
--------
0 | 2439985 | 2f9d9557-e260-45ee-92a3-b3069422cce9 | 2014-04-30
15:00:11.13-06 | R | Source | 0 | |
| 0 | 0 |
0
(1 row)

mirthdb=# select count(*) from d_mm100 where ID = 0 AND status = 'R' AND
server_id = '2f9d9557-e260-45ee-92a3-b3069422cce9';
count
-------
1
(1 row)

Now in 9.3.4, here are the same explain/analyze and queries:

# /opt/pgsql/bin/psql -U postgres -d mirthdb
psql (9.3.4)
Type "help" for help.

mirthdb=# explain analyze select * from d_mm65 where ID = 0 AND status = 'R'
AND server_id = '4e2ae77d-480f-4df0-af32-7d140982813a' order by (message_id)
limit 7 offset 0;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.42..504.59 rows=7 width=115) (actual time=273.808..273.808
rows=0 loops=1)
-> Index Scan using d_mm65_index1 on d_mm65 (cost=0.42..38100.94
rows=529 width=115) (actual time=273.801..273.801 rows=0 loops=1)
Index Cond: ((id = 0) AND (status = 'R'::bpchar))
Filter: ((server_id)::text =
'4e2ae77d-480f-4df0-af32-7d140982813a'::text)
Total runtime: 273.939 ms
(5 rows)

mirthdb=# select * from d_mm65 where ID = 0 AND status = 'R' AND server_id
= '4e2ae77d-480f-4df0-af32-7d140982813a' order by (message_id) limit 7
offset 0;
id | message_id | server_id | received_date | status | connector_name |
send_attempts | send_date | response_date | error_code | chain_id |
order_id
----+------------+-----------+---------------+--------+----------------+---------------+-----------+---------------+------------+----------+----------
(0 rows)

mirthdb=# select count(*) from d_mm65 where ID = 0 AND status = 'R' AND
server_id = '4e2ae77d-480f-4df0-af32-7d140982813a';
count
-------
8
(1 row)

And just to confirm, here's the table description, which is exactly the
same:

mirthdb=# \d d_mm65
Table "public.d_mm65"
Column | Type | Modifiers
----------------+--------------------------+--------------------
id | integer | not null
message_id | bigint | not null
server_id | character varying(36) | not null
received_date | timestamp with time zone |
status | character(1) | not null
connector_name | text |
send_attempts | integer | not null default 0
send_date | timestamp with time zone |
response_date | timestamp with time zone |
error_code | integer | not null default 0
chain_id | integer | not null
order_id | integer | not null
Indexes:
"d_mm65_pkey" PRIMARY KEY, btree (message_id, id)
"d_mm65_fki" btree (message_id)
"d_mm65_index1" btree (message_id, id, status)
"d_mm65_index2" btree (message_id, server_id, id)
Foreign-key constraints:
"d_mm65_fkey" FOREIGN KEY (message_id) REFERENCES d_m65(id) ON DELETE
CASCADE
Referenced by:
TABLE "d_mc65" CONSTRAINT "d_mc65_fkey" FOREIGN KEY (message_id,
metadata_id) REFERENCES d_mm65(message_id, id) ON DELETE CASCADE
TABLE "d_mcm65" CONSTRAINT "d_mcm65_fkey" FOREIGN KEY (message_id,
metadata_id) REFERENCES d_mm65(message_id, id) ON DELETE CASCADE

mirthdb=# select version();
version
---------------------------------------------------------------------------------------------------------------
PostgreSQL 9.3.4 on x86_64-unknown-linux-gnu, compiled by gcc (GCC) 4.1.2
20080704 (Red Hat 4.1.2-44), 64-bit
(1 row)

At one point I was even able to isolate the LIMIT clause to a "tipping
point". For example this returned 0 records:

select * from d_mm65 where id = 0 and d_mm65.status = 'R' and server_id =
'4e2ae77d-480f-4df0-af32-7d140982813a'
order by message_id
limit 519 offset 0

However this returned the 8 rows as expected:

select * from d_mm65 where id = 0 and d_mm65.status = 'R' and server_id =
'4e2ae77d-480f-4df0-af32-7d140982813a'
order by message_id
limit 520 offset 0

The query plan goes from this:

Limit (cost=0.42..37386.88 rows=519 width=115)
-> Index Scan using d_mm65_index1 on d_mm65 (cost=0.42..38107.23
rows=529 width=115)
Index Cond: ((id = 0) AND (status = 'R'::bpchar))
Filter: ((server_id)::text =
'4e2ae77d-480f-4df0-af32-7d140982813a'::text)

To this:

Limit (cost=37417.10..37418.40 rows=520 width=115)
-> Sort (cost=37417.10..37418.42 rows=529 width=115)
Sort Key: message_id
-> Seq Scan on d_mm65 (cost=0.00..37393.17 rows=529 width=115)
Filter: ((id = 0) AND (status = 'R'::bpchar) AND
((server_id)::text = '4e2ae77d-480f-4df0-af32-7d140982813a'::text))