Speed up left-anchored query using indexes?

Question

I havea table with users in which I'll be having a lot of username searches, i.e.

WHERE username LIKE 'xxx%'

Here's the structure of my testing database:

CREATE TABLE usernames
(
  id serial NOT NULL,
  username character varying(64),
  name character varying(64)
)

I inserted one million different-ish names and usernames. I then tried to seach for a name and username without creating indexes for the two colums - the average times for the query:

SELECT * FROM usernames WHERE username LIKE 'xxx%'

is 650ms. After that I created an index for the username column using:

CREATE INDEX usernames_lower_idx
  ON usernames
  USING btree
  (lower(username::text)

And the times are again, on average 650ms. I tried with and without the lower function, same results. Any ideas how can I speed things up (without using an external search engine)? I am using PostgreSQL 9.2.

EDIT 1:

"Seq Scan on usernames  (cost=0.00..24437.47 rows=95 width=64) (actual time=609.796..609.796 rows=0 loops=1)"
"  Filter: ((username)::text ~~ 'asd%'::text)"
"  Rows Removed by Filter: 998358"
"Total runtime: 609.897 ms"

Answer 1

create index usernames_idx on usernames (username varchar_pattern_ops);

analyze usernames;