Slow index scan backward.

I have a single table with 45 columns and 6.5 million records with a roughly random distribution of data of a variety of types. I am trying to implement a data table with pagination in a web user interface, where the data table can be filtered in a very flexible way on pretty much any combination of columns. I have indexes covering the most frequently filtered columns. The data table shows 30 records at a time, sorted to put the most recent records first. The database version is 9.3.5.

The problem occurs if I have a filter which results in less than 30 records, or where the 30 records that are returned are distributed through the dataset (it's OK if the page of 30 records are found in the relatively recent records). Basically, because of the ORDER BY id DESC LIMIT 30 the query planner is opting to use an index scan backward on the primary key, applying a filter to each record, until it finds 30 records. If it finds these relatively quickly then all is good. However sometimes the filter results in < 30 records in the final result set, in which case the index scan runs through the whole table and takes several minutes. A better plan in these cases would be to use the indexes available on the other fields to limit the results set, then filter, sort and limit. But, the planner is presumably not able to work this out because the statistics aren't detailed enough.

Here's the table schema:

-- Table: cache_occurrences_functional

-- DROP TABLE cache_occurrences_functional;

CREATE TABLE cache_occurrences_functional

(

  id integer NOT NULL,

  sample_id integer,

  website_id integer,

  survey_id integer,

  input_form character varying,

  location_id integer,

  location_name character varying,

  public_geom geometry(Geometry,900913),

  map_sq_1km_id integer,

  map_sq_2km_id integer,

  map_sq_10km_id integer,

  date_start date,

  date_end date,

  date_type character varying(2),

  created_on timestamp without time zone,

  updated_on timestamp without time zone,

  verified_on timestamp without time zone,

  created_by_id integer,

  group_id integer,

  taxa_taxon_list_id integer,

  preferred_taxa_taxon_list_id integer,

  taxon_meaning_id integer,

  taxa_taxon_list_external_key character varying(50),

  family_taxa_taxon_list_id integer,

  taxon_group_id integer,

  taxon_rank_sort_order integer,

  record_status character(1),

  record_substatus smallint,

  certainty character(1),

  query character(1),

  sensitive boolean,

  release_status character(1),

  marine_flag boolean,

  data_cleaner_result boolean,

  media_count integer DEFAULT 0,

  training boolean NOT NULL DEFAULT false,

  zero_abundance boolean,

  licence_id integer,

  location_id_vice_county integer,

  location_id_lrc_boundary integer,

  location_id_country integer,

  identification_difficulty integer, -- Identification difficulty assigned by the data_cleaner module, on a scale from 1 (easy) to 5 (difficult)

  import_guid character varying, -- Globally unique identifier of the import batch.

  confidential boolean DEFAULT false,

  external_key character varying,

  CONSTRAINT pk_cache_occurrences_functional PRIMARY KEY (id)

)

WITH (

  OIDS=FALSE

);

ALTER TABLE cache_occurrences_functional

  OWNER TO indicia_user;

GRANT ALL ON TABLE cache_occurrences_functional TO indicia_user;

GRANT SELECT ON TABLE cache_occurrences_functional TO indicia_report_user;

GRANT SELECT ON TABLE cache_occurrences_functional TO naturespot;

GRANT SELECT ON TABLE cache_occurrences_functional TO brc_read_only;

COMMENT ON COLUMN cache_occurrences_functional.identification_difficulty IS 'Identification difficulty assigned by the data_cleaner module, on a scale from 1 (easy) to 5 (difficult)';

COMMENT ON COLUMN cache_occurrences_functional.import_guid IS 'Globally unique identifier of the import batch.';

-- Index: ix_cache_occurrences_functional_created_by_id

-- DROP INDEX ix_cache_occurrences_functional_created_by_id;

CREATE INDEX ix_cache_occurrences_functional_created_by_id

  ON cache_occurrences_functional

  USING btree

  (created_by_id);

-- Index: ix_cache_occurrences_functional_date_end

-- DROP INDEX ix_cache_occurrences_functional_date_end;

CREATE INDEX ix_cache_occurrences_functional_date_end

  ON cache_occurrences_functional

  USING btree

  (date_end);

-- Index: ix_cache_occurrences_functional_date_start

-- DROP INDEX ix_cache_occurrences_functional_date_start;

CREATE INDEX ix_cache_occurrences_functional_date_start

  ON cache_occurrences_functional

  USING btree

  (date_start);

-- Index: ix_cache_occurrences_functional_family_taxa_taxon_list_id

-- DROP INDEX ix_cache_occurrences_functional_family_taxa_taxon_list_id;

CREATE INDEX ix_cache_occurrences_functional_family_taxa_taxon_list_id

  ON cache_occurrences_functional

  USING btree

  (family_taxa_taxon_list_id);

-- Index: ix_cache_occurrences_functional_group_id

-- DROP INDEX ix_cache_occurrences_functional_group_id;

CREATE INDEX ix_cache_occurrences_functional_group_id

  ON cache_occurrences_functional

  USING btree

  (group_id);

-- Index: ix_cache_occurrences_functional_location_id

-- DROP INDEX ix_cache_occurrences_functional_location_id;

CREATE INDEX ix_cache_occurrences_functional_location_id

  ON cache_occurrences_functional

  USING btree

  (location_id);

-- Index: ix_cache_occurrences_functional_location_id_country

-- DROP INDEX ix_cache_occurrences_functional_location_id_country;

CREATE INDEX ix_cache_occurrences_functional_location_id_country

  ON cache_occurrences_functional

  USING btree

  (location_id_country);

-- Index: ix_cache_occurrences_functional_location_id_lrc_boundary

-- DROP INDEX ix_cache_occurrences_functional_location_id_lrc_boundary;

CREATE INDEX ix_cache_occurrences_functional_location_id_lrc_boundary

  ON cache_occurrences_functional

  USING btree

  (location_id_lrc_boundary);

-- Index: ix_cache_occurrences_functional_location_id_vice_county

-- DROP INDEX ix_cache_occurrences_functional_location_id_vice_county;

CREATE INDEX ix_cache_occurrences_functional_location_id_vice_county

  ON cache_occurrences_functional

  USING btree

  (location_id_vice_county);

-- Index: ix_cache_occurrences_functional_map_sq_10km_id

-- DROP INDEX ix_cache_occurrences_functional_map_sq_10km_id;

CREATE INDEX ix_cache_occurrences_functional_map_sq_10km_id

  ON cache_occurrences_functional

  USING btree

  (map_sq_10km_id);

-- Index: ix_cache_occurrences_functional_map_sq_1km_id

-- DROP INDEX ix_cache_occurrences_functional_map_sq_1km_id;

CREATE INDEX ix_cache_occurrences_functional_map_sq_1km_id

  ON cache_occurrences_functional

  USING btree

  (map_sq_1km_id);

-- Index: ix_cache_occurrences_functional_map_sq_2km_id

-- DROP INDEX ix_cache_occurrences_functional_map_sq_2km_id;

CREATE INDEX ix_cache_occurrences_functional_map_sq_2km_id

  ON cache_occurrences_functional

  USING btree

  (map_sq_2km_id);

-- Index: ix_cache_occurrences_functional_public_geom

-- DROP INDEX ix_cache_occurrences_functional_public_geom;

CREATE INDEX ix_cache_occurrences_functional_public_geom

  ON cache_occurrences_functional

  USING gist

  (public_geom);

-- Index: ix_cache_occurrences_functional_status

-- DROP INDEX ix_cache_occurrences_functional_status;

CREATE INDEX ix_cache_occurrences_functional_status

  ON cache_occurrences_functional

  USING btree

  (record_status COLLATE pg_catalog."default", record_substatus);

-- Index: ix_cache_occurrences_functional_submission

-- DROP INDEX ix_cache_occurrences_functional_submission;

CREATE INDEX ix_cache_occurrences_functional_submission

  ON cache_occurrences_functional

  USING btree

  (website_id, survey_id, sample_id);

ALTER TABLE cache_occurrences_functional CLUSTER ON ix_cache_occurrences_functional_submission;

-- Index: ix_cache_occurrences_functional_taxa_taxon_list_external_key

-- DROP INDEX ix_cache_occurrences_functional_taxa_taxon_list_external_key;

CREATE INDEX ix_cache_occurrences_functional_taxa_taxon_list_external_key

  ON cache_occurrences_functional

  USING btree

  (taxa_taxon_list_external_key COLLATE pg_catalog."default");

-- Index: ix_cache_occurrences_functional_taxon_group_id

-- DROP INDEX ix_cache_occurrences_functional_taxon_group_id;

CREATE INDEX ix_cache_occurrences_functional_taxon_group_id

  ON cache_occurrences_functional

  USING btree

  (taxon_group_id);

-- Index: ix_cache_occurrences_functional_updated_on

-- DROP INDEX ix_cache_occurrences_functional_updated_on;

CREATE INDEX ix_cache_occurrences_functional_updated_on

  ON cache_occurrences_functional

  USING btree

  (updated_on);

-- Index: ix_cache_occurrences_functional_verified_on

-- DROP INDEX ix_cache_occurrences_functional_verified_on;

CREATE INDEX ix_cache_occurrences_functional_verified_on

  ON cache_occurrences_functional

  USING btree

  (verified_on);

Here's an example query:

SELECT o.id

  FROM cache_occurrences_functional o

  WHERE o.website_id in (101,12,24,14,8,6,17,25,11,3,7,30,40,16,27,34,5,43,13,41,29,33,44,32,42,47,54,28,51,49,59,65,68,73,75,9,71,83,87,72,97,69,23,10)

AND o.record_status='C' and o.record_substatus is null and (o.query<>'Q' or o.query is null)

AND o.taxa_taxon_list_external_key in ('NBNSYS0000008324')

AND o.media_count>0

ORDER BY o.id DESC LIMIT 30

and a link to a query plan:

https://explain.depesz.com/s/LuK7

Interestingly if I deliberately prevent the index being scanned by sorting by o.id+0, then I get good performance because the planner uses the column indexes to filter first:

SELECT o.id

  FROM cache_occurrences_functional o

  WHERE o.website_id in (101,12,24,14,8,6,17,25,11,3,7,30,40,16,27,34,5,43,13,41,29,33,44,32,42,47,54,28,51,49,59,65,68,73,75,9,71,83,87,72,97,69,23,10)

AND o.record_status='C' and o.record_substatus is null and (o.query<>'Q' or o.query is null)

AND o.taxa_taxon_list_external_key in ('NBNSYS0000008324')

AND o.media_count>0

ORDER BY o.id+0 DESC LIMIT 30

The "fixed" plan:

https://explain.depesz.com/s/7KAy

Unfortunately this way of hacking the query to prevent the index scan backward makes other filters with more than 30 records in the results set much slower so it is not an option.

Any ideas on indexing strategies or ways of restructuring the database schema to cope with this scenario would be much appreciated.

Regards

John