How can one optimize a query involving a sort and a LIKE? Here is the query:

EXPLAIN ANALYZE SELECT
    *
FROM
    "Users" AS "User"
WHERE
    "User"."name" LIKE 'garr%'
AND "User"."id" NOT IN (2449214)
AND "User"."hellbanned" IS NULL
AND "User"."hellbanPostsAfterDate" IS NULL
ORDER BY
    "followerCount" DESC NULLS LAST
LIMIT 3;


Which yields:

Limit  (cost=0.43..3662.92 rows=3 width=1711) (actual time=181.935..2158.898 rows=3 loops=1)
  -&gt;  Index Scan using users_search_followercount_index on "Users" "User"  (cost=0.43..280791.25 rows=230 width=1711) (actual time=181.933..2158.891 rows=3 loops=1)
        Filter: (((name)::text ~~ 'garr%'::text) AND (id &lt;&gt; 2449214))
        Rows Removed by Filter: 29434
Total runtime: 2158.951 ms


The index used is the most optimal I could build:

CREATE INDEX users_search_followercount_index ON "Users" ("followerCount" DESC NULLS LAST) WHERE "hellbanned" IS NULL AND "hellbanPostsAfterDate" IS NULL;


I also tried these:

-- CREATE UNIQUE INDEX users_name_unique_index ON "Users" ("name");
-- CREATE INDEX users_followerCount_index ON "Users" ("followerCount" DESC NULLS LAST);
-- CREATE UNIQUE INDEX users_search_name_followercount_unique_index ON "Users" ("name", "followerCount" DESC NULLS LAST) WHERE "hellbanned" IS NULL AND "hellbanPostsAfterDate" IS NULL; -- N/A
-- CREATE UNIQUE INDEX users_search_followercount_name_unique_index ON "Users" ("followerCount" DESC NULLS LAST, "name") WHERE "hellbanned" IS NULL AND "hellbanPostsAfterDate" IS NULL; -- 5422
-- CREATE INDEX users_name_unique_index ON "Users" ("name") WHERE "hellbanned" IS NULL AND "hellbanPostsAfterDate" IS NULL; -- 5422


But none speed it up.
Your index attempts are still futile, since the predicate

u."name" LIKE 'garr%'


is obviously the most selective one but cannot use a basic (default) b-tree index unless you are operating with the "C" locale (which is uncommon). 

SELECT *
FROM   "Users"
WHERE  name LIKE 'garr%'
AND    id &lt;&gt; 2449214
AND    hellbanned IS NULL
AND    "hellbanPostsAfterDate" IS NULL
ORDER  BY "followerCount" DESC NULLS LAST
LIMIT  3;


There are several options (also depending on the missing table definition and other information), this index should work:

CREATE INDEX "Users_whatever_idx"
ON     "Users" (name text_pattern_ops, "followerCount" DESC NULLS LAST) 
WHERE  hellbanned IS NULL
AND   "hellbanPostsAfterDate" IS NULL;


The conditions on hellbanned and "hellbanPostsAfterDate" are only useful if they exclude more than a few rows. Else, a complete index might be the better choice, since it can be used for more different queries.

Also, there is a chance the second column in the index "followerCount" won't help, since there are typically multiple different matches for the first and Postgres has to sort after all. Test a couple of typical queries with and without the second column in the index.

Details for indexes and pattern matching, including an explanation for the operator class text_pattern_ops:


Pattern matching with LIKE, SIMILAR TO or regular expressions in PostgreSQL


Aside: My standing advise is to use unquoted, legal, lower-case identifiers exclusively in Postgres.