BUG #15111: c between x and x gives bad planning

The following bug has been logged on the website:

Bug reference: 15111
Logged by: Alex Pires de Camargo
Email address: acamargo(at)gmail(dot)com
PostgreSQL version: 9.5.12
Operating system: Linux
Description:

Scenario: A table with columns a,b,c. Btree index on a,c. Gist index on b,c.
A query with a clause a = y and c between x and x uses the gist index b,c
instead of a,c, with very worst execution time than when c between x and z,
even with small deltas (x,z), when the btree (a,c) is used. Below a script
with sample data and results.

There is a discussion in
https://dba.stackexchange.com/questions/198967/postgresql-planner-choosing-btree-or-gist-index-for-few-result-rows

Script:

show default_statistics_target ;
show random_page_cost;
drop table if exists sampledata2;
create table sampledata2 as (with a as (select generate_series(1,50) as
id) select id, md5(random()::text) rand, generate_series (timestamptz
'2004-03-07', timestamptz '2004-03-17', interval '1 minute') ts from a);
select * from sampledata2 limit 3;
create index idx_idTs_btree on sampledata2 using btree(id, ts);
create index idx_randTs_gist on sampledata2 using gist(rand, ts);
analyze sampledata2;
explain analyze select * from sampledata2 where id=42 and ts between
'2004-03-07 00:22:00-03' and '2004-03-07 00:22:00-03';
explain analyze select * from sampledata2 where id=42 and ts between
'2004-03-07 00:22:00-03' and '2004-03-07 00:23:00-03';
alter table sampledata2 alter column id set statistics 10000;
alter table sampledata2 alter column rand set statistics 10000;
alter table sampledata2 alter column ts set statistics 10000;
analyze sampledata2;
explain analyze select * from sampledata2 where id=42 and ts between
'2004-03-07 00:22:00-03' and '2004-03-07 00:22:00-03';
explain analyze select * from sampledata2 where id=42 and ts between
'2004-03-07 00:22:00-03' and '2004-03-07 00:23:00-03';

Results:

default_statistics_target
---------------------------
100
(1 row)

Time: 0.662 ms
random_page_cost
------------------
4
(1 row)

Time: 0.156 ms
DROP TABLE
Time: 31.960 ms
SELECT 720050
Time: 1677.838 ms (00:01.678)
id | rand | ts
----+----------------------------------+------------------------
1 | d75c0c826c3b0e225925330b301f1a0f | 2004-03-07 00:00:00-03
1 | d6f6e5ba4759fce0ff20bbe41ddcfd26 | 2004-03-07 00:01:00-03
1 | c108cad91b852f768b7eddf962fe08a0 | 2004-03-07 00:02:00-03
(3 rows)

Time: 0.707 ms
CREATE INDEX
Time: 565.309 ms
CREATE INDEX
Time: 30686.707 ms (00:30.687)
ANALYZE
Time: 124.453 ms
QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_randts_gist on sampledata2 (cost=0.41..8.43 rows=1
width=45) (actual time=9.344..14.270 rows=1 loops=1)
Index Cond: ((ts >= '2004-03-07 00:22:00-03'::timestamp with time zone)
AND (ts <= '2004-03-07 00:22:00-03'::timestamp with time zone))
Filter: (id = 42)
Rows Removed by Filter: 49
Planning time: 0.149 ms
Execution time: 14.300 ms
(6 rows)

Time: 14.788 ms
QUERY
PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_idts_btree on sampledata2 (cost=0.42..8.45 rows=1
width=45) (actual time=0.048..0.048 rows=2 loops=1)
Index Cond: ((id = 42) AND (ts >= '2004-03-07 00:22:00-03'::timestamp
with time zone) AND (ts <= '2004-03-07 00:23:00-03'::timestamp with time
zone))
Planning time: 0.109 ms
Execution time: 0.068 ms
(4 rows)

Time: 0.394 ms
ALTER TABLE
Time: 0.960 ms
ALTER TABLE
Time: 0.810 ms
ALTER TABLE
Time: 0.814 ms
ANALYZE
Time: 2632.346 ms (00:02.632)
QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_randts_gist on sampledata2 (cost=0.41..8.43 rows=1
width=45) (actual time=9.619..14.368 rows=1 loops=1)
Index Cond: ((ts >= '2004-03-07 00:22:00-03'::timestamp with time zone)
AND (ts <= '2004-03-07 00:22:00-03'::timestamp with time zone))
Filter: (id = 42)
Rows Removed by Filter: 49
Planning time: 0.729 ms
Execution time: 14.393 ms
(6 rows)

Time: 15.404 ms
QUERY
PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_idts_btree on sampledata2 (cost=0.42..8.45 rows=1
width=45) (actual time=0.011..0.012 rows=2 loops=1)
Index Cond: ((id = 42) AND (ts >= '2004-03-07 00:22:00-03'::timestamp
with time zone) AND (ts <= '2004-03-07 00:23:00-03'::timestamp with time
zone))
Planning time: 0.408 ms
Execution time: 0.027 ms
(4 rows)

Time: 0.584 ms

PostgreSQL 9.5.12 on x86_64-pc-linux-gnu (Ubuntu 9.5.12-1.pgdg16.04+1),
compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609, 64-bit