Autocompletion with full text search

Hi,

We implemented an autocompletion feature (case and accent insensitive)
using PostgreSQL full text search.
The query fetches patient ids matching the full text query that belong to a
given patient base (rows contain a pg_array with patient_base_ids).
Our table grew over time (6.2 million rows now) and the query got slower.
We are wondering if we have hit the limit or if there is still room for
performance improvement with better indexing or data partitioning for
instance.
Here is a link to the "explain (analyze, buffers)" results from such a
query run on one of our servers : http://explain.depesz.com/s/a5Q9
Running analyze on the table doesn't change the results and the table is
autovacuumed (last one was 2015-01-08 22:18).

You will find below additional information to bring context to my question.
Thank you in advance for your help.

Here is the schema of the table :

CREATE TABLE patients (
id integer NOT NULL,
first_name character varying(255),
last_name character varying(255),
regular_doctor_name character varying(255),
regular_doctor_city character varying(255),
email character varying(255),
phone_number character varying(255),
secondary_phone_number character varying(255),
gender boolean,
birthdate date,
zipcode character varying(255),
city character varying(255),
created_at timestamp without time zone,
updated_at timestamp without time zone,
imported_at timestamp without time zone,
import_error text,
import_identifier character varying(255),
address character varying(255),
deleted_at timestamp without time zone,
account_id integer,
main boolean DEFAULT false NOT NULL,
insurance_type character varying(255),
patient_base_ids_cache integer[] DEFAULT '{}'::integer[],
crucial_info character varying(255),
referrer character varying(255),
occupation character varying(255),
custom_fields_values hstore DEFAULT ''::hstore NOT NULL,
bounced_at timestamp without time zone,
merged_at timestamp without time zone,
maiden_name character varying(255)
);

Here is the dictionary definition we used for full text search :

CREATE TEXT SEARCH CONFIGURATION custom_name_search (
PARSER = pg_catalog."default" );

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR asciiword WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR word WITH unaccent, simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR numword WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR email WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR url WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR host WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR sfloat WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR version WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR hword_numpart WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR hword_part WITH unaccent, simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR hword_asciipart WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR numhword WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR asciihword WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR hword WITH unaccent, simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR url_path WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR file WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR "float" WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR "int" WITH simple;

ALTER TEXT SEARCH CONFIGURATION custom_name_search
ADD MAPPING FOR uint WITH simple;

Here are the indexes on the patients table :

CREATE INDEX index_patients_on_account_id ON patients USING btree
(account_id);
CREATE INDEX index_patients_on_import_identifier ON patients USING btree
(import_identifier);
CREATE INDEX index_patients_on_patient_base_ids_cache ON patients USING gin
(patient_base_ids_cache);
CREATE INDEX index_patients_on_phone_number ON patients USING btree
(phone_number);
CREATE INDEX patients_clean_secondary_phone_number_index ON patients USING
btree (replace((secondary_phone_number)::text, ' '::text, ''::text));
CREATE INDEX tsvector_on_patients ON patients USING gin
(to_tsvector('custom_name_search'::regconfig, (((COALESCE(last_name,
''::character varying))::text || ' '::text) || (COALESCE(first_name,
''::character varying))::text)));
CREATE INDEX tsvector_on_patients_and_patient_base_ids_cache ON patients
USING gin (to_tsvector('custom_name_search'::regconfig,
(((COALESCE(last_name, ''::character varying))::text || ' '::text) ||
(COALESCE(first_name, ''::character varying))::text)),
patient_base_ids_cache);
CREATE INDEX tsvector_on_patients_first_name ON patients USING gin
(to_tsvector('custom_name_search'::regconfig, (COALESCE(first_name,
''::character varying))::text));
CREATE INDEX tsvector_on_patients_first_name_and_patient_base_ids_cache ON
patients USING gin (to_tsvector('custom_name_search'::regconfig,
(COALESCE(first_name, ''::character varying))::text),
patient_base_ids_cache);
CREATE INDEX tsvector_on_patients_last_name_and_patient_base_ids_cache ON
patients USING gin (to_tsvector('custom_name_search'::regconfig,
(COALESCE(last_name, ''::character varying))::text),
patient_base_ids_cache);

SELECT COUNT(id) FROM patients;

count

---------

6219569

(1 row)

SELECT version();

version

------------------------------------------------------------------------------------------------------------

PostgreSQL 9.3.5 on x86_64-unknown-linux-gnu, compiled by gcc
(Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3, 64-bit

(1 row)

=> SELECT name, current_setting(name), source

-> FROM pg_settings

-> WHERE source NOT IN ('default', 'override');

name |
current_setting |
source

--------------------------------+-------------------------------------------------------------------------------------------------------+----------------------

application_name | psql
| client

archive_command | test -f
/etc/postgresql/wal-e.d/ARCHIVING_OFF || envdir /etc/postgresql/wal-e.d/env
wal-e wal-push %p | configuration file

archive_mode | on
| configuration
file

archive_timeout | 1min
| configuration
file

bytea_output | escape
| user

checkpoint_completion_target | 0.7
| configuration
file

checkpoint_segments | 40
| configuration
file

checkpoint_timeout | 10min
| configuration
file

client_encoding | UTF8
| client

client_min_messages | notice
| configuration
file

cpu_index_tuple_cost | 0.001
| configuration
file

cpu_operator_cost | 0.0005
| configuration
file

cpu_tuple_cost | 0.003
| configuration
file

DateStyle | ISO, MDY
| configuration
file

default_text_search_config | pg_catalog.english
| configuration
file

effective_cache_size | 10800000kB
| configuration
file

hot_standby | on
| configuration
file

hot_standby_feedback | on
| configuration
file

lc_messages | en_US.UTF-8
| configuration
file

lc_monetary | en_US.UTF-8
| configuration
file

lc_numeric | en_US.UTF-8
| configuration
file

lc_time | en_US.UTF-8
| configuration
file

listen_addresses | *
| configuration
file

local_preload_libraries | pgextwlist
| configuration
file

log_checkpoints | on
| configuration
file

log_connections | on
| configuration
file

log_destination | stderr
| configuration
file

log_line_prefix | %m %p %u [PINK]
| configuration
file

log_lock_waits | on
| configuration
file

log_min_duration_statement | 2s
| configuration
file

log_min_messages | notice
| configuration
file

log_rotation_age | 1d
| configuration
file

log_rotation_size | 100MB
| configuration
file

log_statement | ddl
| configuration
file

log_temp_files | 10MB
| configuration
file

log_timezone | UTC
| configuration
file

log_truncate_on_rotation | off
| configuration
file

logfebe.identity | c671acf1-c82e-4c2d-a3b3-f815580b6db5
| configuration
file

logfebe.unix_socket |
/tmp/pg_logplexcollector/pg_logplexcollector.sock
| configuration file

logging_collector | on
| configuration
file

maintenance_work_mem | 1700MB
| configuration
file

max_connections | 500
| configuration
file

max_prepared_transactions | 0
| configuration
file

max_stack_depth | 2MB
| environment
variable

max_standby_archive_delay | -1
| configuration
file

max_standby_streaming_delay | -1
| configuration
file

max_wal_senders | 20
| configuration
file

port | 5432
| configuration
file

random_page_cost | 2
| configuration
file

shared_buffers | 2929MB
| configuration
file

ssl | on
| configuration
file

ssl_renegotiation_limit | 0
| configuration
file

superuser_reserved_connections | 3
| configuration
file

synchronous_commit | local
| configuration
file

synchronous_standby_names | follower
| configuration
file

temp_tablespaces | ephemeral
| database

TimeZone | UTC
| configuration
file

track_io_timing | on
| configuration
file

wal_keep_segments | 61
| configuration
file

wal_level | hot_standby
| configuration
file

work_mem | 100MB
| configuration
file

(61 rows)