Best query to exclude existing friends from query
NOT IN is typically the slowest option. LEFT JOIN / IS NULL is more promising. Or NOT EXISTS:


Select rows where value of second column is not present in first column


Query

Just your query, formatted:

SELECT u.id_user, u.username
FROM   "user" u 
LEFT   JOIN friend_request fr ON fr.sent_to = u.id_user
                             AND fr.sent_from = 288
LEFT   JOIN friends f ON f.friend_to = u.id_user
                     AND f.friend_of = 288
WHERE  u.username LIKE '%tom%'
AND    fr.sent_to IS NULL
AND    f.friend_to IS NULL;


Or, a variant with NOT EXISTS anti-semi-joins:

SELECT u.id_user, u.username
FROM   "user" u
WHERE  NOT EXISTS (
   SELECT 1 FROM friend_request
   WHERE  sent_to = u.id_user
   AND    sent_from = 288
   ) 
AND    NOT EXISTS (
   SELECT 1 FROM friends
   WHERE  friend_to = u.id_user
   AND    friend_of = 288
   )
WHERE  u.username LIKE '%tom%';


Indexes

The most important factor for performance. An ideal setup would have:


A trigram GIN or GiST index on "user".username. You need the additional module pg_trgm. Instructions - and Gin or GiST?


How is LIKE implemented?


If index-only scans are possible, append the otherwise useless id_user. You need the additional module btree_gin (or btree_gist respectively):


Inner join using an array column


Then:

CREATE INDEX usr_trgm_idx ON "user" USING gin (username gin_trgm_ops, id_user);

Multicolumn indexes (or a UNIQUE / PK constraint) on (sent_from, sent_to) and (friend_of, friend_to) - with columns in that order. The reversed order would work, too, but not quite as good. Each query checks for a single friend_of combined with many different friend_to, which is faster with the suggested column order, because this way tuples are much rather localized on the same or a few index pages.


That said, the proof of the pudding is still in the eating.
Get the final verdict from EXPLAIN (BUFFERS, ANALYZE) in your production database.

Aside

Do not call your table user, that's a reserved word.