Faster query with pattern-matching on multiple text fields
For your kind of pattern matching you best use a trigram index. Read this first:


How is LIKE implemented?


I assume there's a typo in your expression (first_name || '' || last_name), which makes no sense with an empty string, and you really want (first_name || ' ' || last_name) - with a space character.

Assuming that either column can be NULL, you would need NULL-safe concatenation, the simple solution is concat_ws():


Combine two columns and add into one new column


But that function is not IMMUTABLE (explanation in the linked answer), so you cannot use it directly in an index expression. You could use an IMMUTABLE function wrapper:

CREATE OR REPLACE FUNCTION f_immutable_concat_ws(s text, t1 text, t2 text)
  RETURNS text AS
$func$
SELECT concat_ws(s, t1, t2)
$func$ LANGUAGE sql IMMUTABLE;


The wrapper can be IMMUTABLE because it only takes text parameters.
Either way, this is more verbose but has less internal overhead and is considerably faster:

CREATE OR REPLACE FUNCTION f_immutable_concat_ws1(s text, t1 text, t2 text)
  RETURNS text AS
$func$
SELECT CASE
         WHEN t1 IS NULL THEN t2
         WHEN t2 IS NULL THEN t1
         ELSE t1 || s || t2
       END
$func$ LANGUAGE sql IMMUTABLE;


Or, with hard-coded space character:

CREATE OR REPLACE FUNCTION f_concat_space(t1 text, t2 text)
  RETURNS text AS
$func$
SELECT CASE
         WHEN t1 IS NULL THEN t2
         WHEN t2 IS NULL THEN t1
         ELSE t1 || ' ' || t2
       END
$func$ LANGUAGE sql IMMUTABLE;


Basing the index on this function, I suggest:

CREATE INDEX people_special_gin_trgm_idx ON people
USING gin (f_concat_space(first_name, last_name) gin_trgm_ops, email gin_trgm_ops);


I added email as second index column for several considerations.

Creating the index will take a while for 20M rows, best not during top load, or maybe use CREATE INDEX CONCURRENTLY .... A GIN index is considerably bigger than a plain btree index and also more expensive to maintain. Be sure to run the latest version of Postgres, there have been major improvements for GIN indexes in recent versions.

Then your slightly adapted and simplified query should be fast and correct:

SELECT *
FROM   people
WHERE  f_concat_space(first_name, last_name) ILIKE '%bat%man%' OR
       email ILIKE '%bat%man%'
LIMIT  25;


You only need the one index for this query.

Basics for pattern matching:


Pattern matching with LIKE, SIMILAR TO or regular expressions in PostgreSQL
How to create an index to speed up an aggregate LIKE query on an expression?