Extremely slow when query uses GIST exclusion index - Mailing list pgsql-performance

Hi. My databases make heavy use of timestamp ranges, and they rely on GIST exclusion constraints to ensure that the ranges are disjoint. I've noticed that queries that hit the GIST indexes are EXTREMELY slow, and the queries run much faster if I make trivial changes to avoid the GIST indexes.

Here's the setup for a test case. (Timings were collected on PostgreSQL 9.5.4 on x86_64-pc-linux-gnu, Intel Xeon E5 in a VM with 3.5 GB RAM):

CREATE TABLE app (
  pk SERIAL PRIMARY KEY,
  group_id TEXT NOT NULL,
  app_time TIMESTAMPTZ NOT NULL
);

CREATE TABLE group_span (
  pk SERIAL PRIMARY KEY,
  group_id TEXT NOT NULL,
  valid_period TSTZRANGE NOT NULL,
  EXCLUDE USING GIST (group_id WITH =, valid_period WITH &&)
);

CREATE TABLE member_span (
  pk SERIAL PRIMARY KEY,
  member_id TEXT NOT NULL,
  group_id TEXT NOT NULL,
  valid_period TSTZRANGE NOT NULL,
  EXCLUDE USING GIST
    (member_id WITH =, group_id WITH =, valid_period WITH &&)
);

-- Fill tables with some random data

INSERT INTO app (group_id, app_time)
SELECT
  MD5(CONCAT(GENERATE_SERIES(1, 10000), RANDOM())),
  DATE_TRUNC('month', TIMESTAMPTZ '2000-01-01' +
             INTERVAL '3 years' * RANDOM());

-- Give groups a 1-year span, and give some groups a 2nd-year span:
INSERT INTO group_span (group_id, valid_period)
(SELECT
   group_id,
   TSTZRANGE(app_time, app_time + INTERVAL '1 year')
 FROM app)
UNION ALL
(SELECT
   group_id,
   TSTZRANGE(app_time + INTERVAL '1 year',
             app_time + INTERVAL '2 year')
 FROM app LIMIT 2000);

-- Create members with a random span within their group_span:
INSERT INTO member_span (member_id, group_id, valid_period)
SELECT
  MD5(RANDOM()::TEXT),
  group_id,
  TSTZRANGE(
    LOWER(valid_period),
    UPPER(valid_period) - DATE_TRUNC(
      'days',
      (UPPER(valid_period) - LOWER(valid_period)) * RANDOM()
    )
  )
FROM group_span;