Из-за сложности и многообразия locale в постгресе запрещено использовать индекс
для запросов вида LIKE 'что%' для всех locale кроме 'C'. А что делать если хочется ?
В 8.01 стало возможным использовать operator class [1] !  Мы будем использовать varchar_pattern_ops, B-tree индекс
в этом случае, будет строиться без использования collation правил из locale, а на основе сравнения буквы с буквой.

   test=#  \d ru_words
       w      | text |
       Indexes:
          "w_idx" btree (lower(w) varchar_pattern_ops)

   test=# create index w_idx on ru_words (lower(w) varchar_pattern_ops);
      CREATE INDEX

   test=# vacuum analyze test;

   test=# explain analyze select w from ru_words where lower(w) like 'что%';

       Index Scan using w_idx on ru_words...
         Index Cond: ((lower(w) ~>=~ 'что'::character varying) AND (lower(w) ~<~ 'чтп'::character varying))
         Filter: (lower(w) ~~ 'что%'::text)

URL: http://www.sai.msu.su/~megera/oddmuse/index.cgi/pgsql_tips
Обсуждается: http://www.opennet.me/tips/info/830.shtml

• Как добиться, чтобы в запросах LIKE 'что%' использовался индекс ?,Остров, 16:13 , 23-Апр-05
• Как добиться, чтобы в запросах LIKE 'что%' использовался инд...,ku, 22:04 , 23-Ноя-11

Добавляйте в заголовок "PostgreSQL" иначе путаете многоих...

Создаю индекс так:
create unique index idx_username on usersfrontend using btree (lower(username) varchar_pattern_ops);

Итоговая таблица:
\d+ usersfrontend
                                           Table "public.usersfrontend"
   Column   |            Type             |                        Modifiers                        | Description
------------+-----------------------------+---------------------------------------------------------+-------------
id         | integer                     | not null default nextval('usersfrontend_seq'::regclass) |
username   | character varying(16)       | not null                                                |
Indexes:
    "idx_username" UNIQUE, btree (lower(username::text) varchar_pattern_ops)
    "idx_usersfrontend_uniq" UNIQUE, btree (id)
    "idx_username_password" btree (username, password)

Ну вот что в итоге:
explain analyze select username from usersfrontend where lower(username) like 'Dex%';                                              QUERY PLAN                                              
-------------------------------------------------------------------------------------------------------
Seq Scan on usersfrontend  (cost=0.00..2.39 rows=1 width=7) (actual time=0.085..0.085 rows=0 loops=1)
   Filter: (lower((username)::text) ~~ 'Dex%'::text)
Total runtime: 0.124 ms

Что не так?