Here's an example, I'll use generated "names" which are actually numbers, which should work the same...
Note that if you want the search to ignore accents, like MySQL does, you'll need to replace lower() with a function that turns accented characters into non-accented ones. Since that function will probably be slow, it would be better to materialize the column.
If you want LIKE to use an index, don't forget to use the special index type text_pattern_ops !
create table test (a TEXT, b TEXT, c TEXT);
INSERT INTO test SELECT n, n*3, n*7 FROM generate_series( 1,100000 ) n;
create index test_a on test( lower( a ) text_pattern_ops );
create index test_b on test( lower( b ) text_pattern_ops );
create index test_c on test( lower( c ) text_pattern_ops );
EXPLAIN ANALYZE SELECT * FROM test WHERE lower(a) LIKE '12%' OR lower(b) LIKE '12%' OR lower(c) LIKE '12%' ORDER BY lower(a) LIMIT 10;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1081.12..1081.15 rows=10 width=17) (actual time=16.987..16.992 rows=10 loops=1)
-> Sort (cost=1081.12..1096.04 rows=5969 width=17) (actual time=16.986..16.986 rows=10 loops=1)
Sort Key: (lower(a))
Sort Method: top-N heapsort Memory: 25kB
-> Bitmap Heap Scan on test (cost=144.68..952.13 rows=5969 width=17) (actual time=1.107..13.261 rows=6405 loops=1)
Recheck Cond: ((lower(a) ~~ '12%'::text) OR (lower(b) ~~ '12%'::text) OR (lower(c) ~~ '12%'::text))
Filter: ((lower(a) ~~ '12%'::text) OR (lower(b) ~~ '12%'::text) OR (lower(c) ~~ '12%'::text))
-> BitmapOr (cost=144.68..144.68 rows=6341 width=0) (actual time=1.081..1.081 rows=0 loops=1)
-> Bitmap Index Scan on test_a (cost=0.00..22.95 rows=1068 width=0) (actual time=0.210..0.210 rows=1111 loops=1)
Index Cond: ((lower(a) ~>=~ '12'::text) AND (lower(a) ~<~ '13'::text))
-> Bitmap Index Scan on test_b (cost=0.00..81.85 rows=3758 width=0) (actual time=0.603..0.603 rows=3707 loops=1)
Index Cond: ((lower(b) ~>=~ '12'::text) AND (lower(b) ~<~ '13'::text))
-> Bitmap Index Scan on test_c (cost=0.00..35.42 rows=1515 width=0) (actual time=0.266..0.266 rows=1587 loops=1)
Index Cond: ((lower(c) ~>=~ '12'::text) AND (lower(c) ~<~ '13'::text))
Total runtime: 17.038 ms
Here the OR are turned into bitmap-OR index scans which are pretty fast. Note here, the first two "letters" are used, which gives a selectivity of 1%. If you use only one letter you might get pretty low selectivity and a huge result list which is unlikely to be useful, so better wait until the user types 2 chars before firing up that autocompletion.
Using UNION isn't faster.
But there is another hack ! Look :
select * from (values ('a'),('b'),('A'),('Â')) foo where column1 >= 'a' AND column1 < 'b';
column1
---------
a
A
Â
ok...
create index test_aa on test( a );
create index test_ba on test( b );
create index test_ca on test( c );
Here you'd need to take the string typed by the user (for instance, 'no'), remove accents and lowercase it, and increment the last character (which gives you 'np'). All names that start with 'no' have the property that name >= 'no' and name < 'np', because of collation rules, and it includes accents.
EXPLAIN ANALYZE
SELECT * FROM (SELECT * FROM test WHERE a >= '12' AND a < '13' ORDER BY a LIMIT 10) f1
UNION
SELECT * FROM (SELECT * FROM test WHERE b >= '12' AND b < '13' ORDER BY b LIMIT 10) f2
UNION
SELECT * FROM (SELECT * FROM test WHERE c >= '12' AND c < '13' ORDER BY c LIMIT 10) f3
ORDER BY a;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=27.20..27.27 rows=30 width=96) (actual time=0.451..0.456 rows=30 loops=1)
Sort Key: public.test.a
Sort Method: quicksort Memory: 27kB
-> HashAggregate (cost=26.16..26.46 rows=30 width=96) (actual time=0.399..0.404 rows=30 loops=1)
-> Append (cost=0.00..25.94 rows=30 width=96) (actual time=0.157..0.372 rows=30 loops=1)
-> Limit (cost=0.00..7.35 rows=10 width=17) (actual time=0.157..0.163 rows=10 loops=1)
-> Index Scan using test_aa on test (cost=0.00..784.85 rows=1068 width=17) (actual time=0.156..0.161 rows=10 loops=1)
Index Cond: ((a >= '12'::text) AND (a < '13'::text))
-> Limit (cost=0.00..6.96 rows=10 width=17) (actual time=0.122..0.133 rows=10 loops=1)
-> Index Scan using test_ba on test (cost=0.00..2614.31 rows=3758 width=17) (actual time=0.122..0.131 rows=10 loops=1)
Index Cond: ((b >= '12'::text) AND (b < '13'::text))
-> Limit (cost=0.00..11.03 rows=10 width=17) (actual time=0.066..0.072 rows=10 loops=1)
-> Index Scan using test_ca on test (cost=0.00..1671.03 rows=1515 width=17) (actual time=0.066..0.070 rows=10 loops=1)
Index Cond: ((c >= '12'::text) AND (c < '13'::text))
Total runtime: 0.527 ms
That's much, much faster, and it has some very useful properties.
Since the sorts are removed and an index-scan is used instead (because of the LIMIT 10) the query is extremely fast in all cases. It just doesn't return all the results.
If the user searches for names like 'a%' and gets 5000 results, this result is useless to the user, instead he'll just make a more precise query by adding a letter. So, the database resources expended to compute and return the 5000 results were spent uselessly. It is much better to make a quick, bounded time query like this one and display 'more results...' so the user knows he should enter a few more letters in the search box.