Optimise searching for users using short queries

This optimises searching for users when using queries consisting out of
one or two characters such as "ab". We optimise such cases by searching
for `LOWER(name)` and `LOWER(username)` instead of using `ILIKE`. Using
`LOWER` produces a _much_ better performing query.

For example, when searching for all users matching the term "a" we'd
produce the following plan:

     Limit  (cost=637.69..637.74 rows=20 width=805) (actual time=41.983..41.995 rows=20 loops=1)
       Buffers: shared hit=8330
       ->  Sort  (cost=637.69..638.61 rows=368 width=805) (actual time=41.982..41.990 rows=20 loops=1)
             Sort Key: (CASE WHEN ((name)::text = 'a'::text) THEN 0 WHEN ((username)::text = 'a'::text) THEN 1 WHEN ((email)::text = 'a'::text) THEN 2 ELSE 3 END), name
             Sort Method: top-N heapsort  Memory: 35kB
             Buffers: shared hit=8330
             ->  Bitmap Heap Scan on users  (cost=75.47..627.89 rows=368 width=805) (actual time=9.452..41.305 rows=277 loops=1)
                   Recheck Cond: (((name)::text ~~* 'a'::text) OR ((username)::text ~~* 'a'::text) OR ((email)::text = 'a'::text))
                   Rows Removed by Index Recheck: 7601
                   Heap Blocks: exact=7636
                   Buffers: shared hit=8327
                   ->  BitmapOr  (cost=75.47..75.47 rows=368 width=0) (actual time=8.290..8.290 rows=0 loops=1)
                         Buffers: shared hit=691
                         ->  Bitmap Index Scan on index_users_on_name_trigram  (cost=0.00..38.85 rows=180 width=0) (actual time=4.369..4.369 rows=4071 loops=1)
                               Index Cond: ((name)::text ~~* 'a'::text)
                               Buffers: shared hit=360
                         ->  Bitmap Index Scan on index_users_on_username_trigram  (cost=0.00..34.41 rows=188 width=0) (actual time=3.896..3.896 rows=4140 loops=1)
                               Index Cond: ((username)::text ~~* 'a'::text)
                               Buffers: shared hit=328
                         ->  Bitmap Index Scan on users_email_key  (cost=0.00..1.94 rows=1 width=0) (actual time=0.022..0.022 rows=0 loops=1)
                               Index Cond: ((email)::text = 'a'::text)
                               Buffers: shared hit=3
     Planning time: 3.912 ms
     Execution time: 42.171 ms

With the changes in this commit we now produce the following plan
instead:

     Limit  (cost=13257.48..13257.53 rows=20 width=805) (actual time=1.567..1.579 rows=20 loops=1)
       Buffers: shared hit=287
       ->  Sort  (cost=13257.48..13280.93 rows=9379 width=805) (actual time=1.567..1.572 rows=20 loops=1)
             Sort Key: (CASE WHEN ((name)::text = 'a'::text) THEN 0 WHEN ((username)::text = 'a'::text) THEN 1 WHEN ((email)::text = 'a'::text) THEN 2 ELSE 3 END), name
             Sort Method: top-N heapsort  Memory: 35kB
             Buffers: shared hit=287
             ->  Bitmap Heap Scan on users  (cost=135.66..13007.91 rows=9379 width=805) (actual time=0.194..1.107 rows=277 loops=1)
                   Recheck Cond: ((lower((name)::text) = 'a'::text) OR (lower((username)::text) = 'a'::text) OR ((email)::text = 'a'::text))
                   Heap Blocks: exact=277
                   Buffers: shared hit=287
                   ->  BitmapOr  (cost=135.66..135.66 rows=9379 width=0) (actual time=0.152..0.152 rows=0 loops=1)
                         Buffers: shared hit=10
                         ->  Bitmap Index Scan on yorick_test_users  (cost=0.00..124.75 rows=9377 width=0) (actual time=0.101..0.101 rows=277 loops=1)
                               Index Cond: (lower((name)::text) = 'a'::text)
                               Buffers: shared hit=4
                         ->  Bitmap Index Scan on index_on_users_lower_username  (cost=0.00..1.94 rows=1 width=0) (actual time=0.035..0.035 rows=1 loops=1)
                               Index Cond: (lower((username)::text) = 'a'::text)
                               Buffers: shared hit=3
                         ->  Bitmap Index Scan on users_email_key  (cost=0.00..1.94 rows=1 width=0) (actual time=0.014..0.014 rows=0 loops=1)
                               Index Cond: ((email)::text = 'a'::text)
                               Buffers: shared hit=3
     Planning time: 0.303 ms
     Execution time: 1.687 ms

Here we can see the new query is 25 times faster compared to the old
query.

6 files changed, 54 insertions, 5 deletions

diff --git a/app/models/user.rb b/app/models/user.rb
index f5eeba27572..8610ca27b7f 100644
--- a/app/models/user.rb
+++ b/app/models/user.rb
@@ -327,8 +327,8 @@ class User < ActiveRecord::Base
       SQL
 
       where(
-        fuzzy_arel_match(:name, query)
-          .or(fuzzy_arel_match(:username, query))
+        fuzzy_arel_match(:name, query, lower_exact_match: true)
+          .or(fuzzy_arel_match(:username, query, lower_exact_match: true))
           .or(arel_table[:email].eq(query))
       ).reorder(order % { query: ActiveRecord::Base.connection.quote(query) }, :name)
     end
diff --git a/db/migrate/20180215181245_users_name_lower_index.rb b/db/migrate/20180215181245_users_name_lower_index.rb
new file mode 100644
index 00000000000..d3f68cb7d45
--- /dev/null
+++ b/db/migrate/20180215181245_users_name_lower_index.rb
@@ -0,0 +1,29 @@
+# See http://doc.gitlab.com/ce/development/migration_style_guide.html
+# for more information on how to write migrations for GitLab.
+
+class UsersNameLowerIndex < ActiveRecord::Migration
+  include Gitlab::Database::MigrationHelpers
+
+  # Set this constant to true if this migration requires downtime.
+  DOWNTIME = false
+  INDEX_NAME = 'index_on_users_name_lower'
+
+  disable_ddl_transaction!
+
+  def up
+    return unless Gitlab::Database.postgresql?
+
+    # On GitLab.com this produces an index with a size of roughly 60 MB.
+    execute "CREATE INDEX CONCURRENTLY #{INDEX_NAME} ON users (LOWER(name))"
+  end
+
+  def down
+    return unless Gitlab::Database.postgresql?
+
+    if supports_drop_index_concurrently?
+      execute "DROP INDEX CONCURRENTLY IF EXISTS #{INDEX_NAME}"
+    else
+      execute "DROP INDEX IF EXISTS #{INDEX_NAME}"
+    end
+  end
+end
diff --git a/db/schema.rb b/db/schema.rb
index 409d1ac7644..c0ce87302cf 100644
--- a/db/schema.rb
+++ b/db/schema.rb
@@ -11,7 +11,7 @@
 #
 # It's strongly recommended that you check this file into your version control system.
 
-ActiveRecord::Schema.define(version: 20180213131630) do
+ActiveRecord::Schema.define(version: 20180215181245) do
 
   # These are extensions that must be enabled in order to support this database
   enable_extension "plpgsql"
diff --git a/lib/gitlab/sql/pattern.rb b/lib/gitlab/sql/pattern.rb
index 5f0c98cb5a4..0e3a93aa236 100644
--- a/lib/gitlab/sql/pattern.rb
+++ b/lib/gitlab/sql/pattern.rb
@@ -25,7 +25,11 @@ module Gitlab
           query.length >= MIN_CHARS_FOR_PARTIAL_MATCHING
         end
 
-        def fuzzy_arel_match(column, query)
+        # column - The column name to search in.
+        # query - The text to search for.
+        # lower_exact_match - When set to `true` we'll fall back to using
+        #                     `LOWER(column) = query` instead of using `ILIKE`.
+        def fuzzy_arel_match(column, query, lower_exact_match: false)
           query = query.squish
           return nil unless query.present?
 
@@ -34,9 +38,17 @@ module Gitlab
           if words.any?
             words.map { |word| arel_table[column].matches(to_pattern(word)) }.reduce(:and)
           else
+            sanitized_query = sanitize_sql_like(query)
+
             # No words of at least 3 chars, but we can search for an exact
             # case insensitive match with the query as a whole
-            arel_table[column].matches(sanitize_sql_like(query))
+            if lower_exact_match
+              Arel::Nodes::NamedFunction
+                .new('LOWER', [arel_table[column]])
+                .eq(sanitized_query)
+            else
+              arel_table[column].matches(sanitized_query)
+            end
           end
         end
 
diff --git a/lib/tasks/migrate/setup_postgresql.rake b/lib/tasks/migrate/setup_postgresql.rake
index 31cbd651edb..1c7a8a90f5c 100644
--- a/lib/tasks/migrate/setup_postgresql.rake
+++ b/lib/tasks/migrate/setup_postgresql.rake
@@ -8,6 +8,7 @@ task setup_postgresql: :environment do
   require Rails.root.join('db/migrate/20170503185032_index_redirect_routes_path_for_like')
   require Rails.root.join('db/migrate/20171220191323_add_index_on_namespaces_lower_name.rb')
   require Rails.root.join('db/migrate/20180113220114_rework_redirect_routes_indexes.rb')
+  require Rails.root.join('db/migrate/20180215181245_users_name_lower_index.rb')
 
   NamespacesProjectsPathLowerIndexes.new.up
   AddUsersLowerUsernameEmailIndexes.new.up
@@ -17,4 +18,5 @@ task setup_postgresql: :environment do
   IndexRedirectRoutesPathForLike.new.up
   AddIndexOnNamespacesLowerName.new.up
   ReworkRedirectRoutesIndexes.new.up
+  UsersNameLowerIndex.new.up
 end
diff --git a/spec/lib/gitlab/sql/pattern_spec.rb b/spec/lib/gitlab/sql/pattern_spec.rb
index ef51e3cc8df..5b5052de372 100644
--- a/spec/lib/gitlab/sql/pattern_spec.rb
+++ b/spec/lib/gitlab/sql/pattern_spec.rb
@@ -154,6 +154,12 @@ describe Gitlab::SQL::Pattern do
       it 'returns a single equality condition' do
         expect(fuzzy_arel_match.to_sql).to match(/title.*I?LIKE 'fo'/)
       end
+
+      it 'uses LOWER instead of ILIKE when LOWER is enabled' do
+        rel = Issue.fuzzy_arel_match(:title, query, lower_exact_match: true)
+
+        expect(rel.to_sql).to match(/LOWER\(.*title.*\).*=.*'fo'/)
+      end
     end
 
     context 'with two words both equal to 3 chars' do