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@gmail.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