Merge branch 'trigram-index-searching' into 'master'

Refactor searching and use PostgreSQL trigram indexes for significantly
improved performance

Related issue: https://gitlab.com/gitlab-org/gitlab-ce/issues/13743.

Also fixes #12410

See merge request !2987

36 files changed, 926 insertions, 71 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 8917eebafda..d4554b96190 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -17,6 +17,7 @@ v 8.6.0 (unreleased)
   - Return empty array instead of 404 when commit has no statuses in commit status API
   - Decrease the font size and the padding of the `.anchor` icons used in the README (Roberto Dip)
   - Rewrite logo to simplify SVG code (Sean Lang)
+  - Refactor and greatly improve search performance
   - Add support for cross-project label references
   - Update documentation to reflect Guest role not being enforced on internal projects
   - Allow search for logged out users
diff --git a/app/finders/projects_finder.rb b/app/finders/projects_finder.rb
index 3b4e0362e04..2b8fba77bb1 100644
--- a/app/finders/projects_finder.rb
+++ b/app/finders/projects_finder.rb
@@ -52,7 +52,10 @@ class ProjectsFinder
 
   def all_projects(current_user)
     if current_user
-      [current_user.authorized_projects, public_and_internal_projects]
+      [
+        *current_user.project_relations,
+        public_and_internal_projects
+      ]
     else
       [Project.public_only]
     end
diff --git a/app/models/ci/runner.rb b/app/models/ci/runner.rb
index e725a6d468c..90349a07594 100644
--- a/app/models/ci/runner.rb
+++ b/app/models/ci/runner.rb
@@ -23,7 +23,7 @@ module Ci
 
     LAST_CONTACT_TIME = 5.minutes.ago
     AVAILABLE_SCOPES = ['specific', 'shared', 'active', 'paused', 'online']
-    
+
     has_many :builds, class_name: 'Ci::Build'
     has_many :runner_projects, dependent: :destroy, class_name: 'Ci::RunnerProject'
     has_many :projects, through: :runner_projects, class_name: '::Project', foreign_key: :gl_project_id
@@ -46,9 +46,23 @@ module Ci
 
     acts_as_taggable
 
+    # Searches for runners matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # This method performs a *partial* match on tokens, thus a query for "a"
+    # will match any runner where the token contains the letter "a". As a result
+    # you should *not* use this method for non-admin purposes as otherwise users
+    # might be able to query a list of all runners.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def self.search(query)
-      where('LOWER(ci_runners.token) LIKE :query OR LOWER(ci_runners.description) like :query',
-            query: "%#{query.try(:downcase)}%")
+      t = arel_table
+      pattern = "%#{query}%"
+
+      where(t[:token].matches(pattern).or(t[:description].matches(pattern)))
     end
 
     def set_default_values
diff --git a/app/models/concerns/issuable.rb b/app/models/concerns/issuable.rb
index 27b97944e38..3c42f582937 100644
--- a/app/models/concerns/issuable.rb
+++ b/app/models/concerns/issuable.rb
@@ -61,12 +61,29 @@ module Issuable
   end
 
   module ClassMethods
+    # Searches for records with a matching title.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      where("LOWER(title) like :query", query: "%#{query.downcase}%")
+      where(arel_table[:title].matches("%#{query}%"))
     end
 
+    # Searches for records with a matching title or description.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def full_search(query)
-      where("LOWER(title) like :query OR LOWER(description) like :query", query: "%#{query.downcase}%")
+      t = arel_table
+      pattern = "%#{query}%"
+
+      where(t[:title].matches(pattern).or(t[:description].matches(pattern)))
     end
 
     def sort(method)
diff --git a/app/models/group.rb b/app/models/group.rb
index 76042b3e3fd..afbc2922013 100644
--- a/app/models/group.rb
+++ b/app/models/group.rb
@@ -33,8 +33,18 @@ class Group < Namespace
   after_destroy :post_destroy_hook
 
   class << self
+    # Searches for groups matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      where("LOWER(namespaces.name) LIKE :query or LOWER(namespaces.path) LIKE :query", query: "%#{query.downcase}%")
+      table   = Namespace.arel_table
+      pattern = "%#{query}%"
+
+      where(table[:name].matches(pattern).or(table[:path].matches(pattern)))
     end
 
     def sort(method)
diff --git a/app/models/merge_request.rb b/app/models/merge_request.rb
index c1e18bb3cc5..188325045e2 100644
--- a/app/models/merge_request.rb
+++ b/app/models/merge_request.rb
@@ -135,7 +135,6 @@ class MergeRequest < ActiveRecord::Base
   scope :by_branch, ->(branch_name) { where("(source_branch LIKE :branch) OR (target_branch LIKE :branch)", branch: branch_name) }
   scope :cared, ->(user) { where('assignee_id = :user OR author_id = :user', user: user.id) }
   scope :by_milestone, ->(milestone) { where(milestone_id: milestone) }
-  scope :in_projects, ->(project_ids) { where("source_project_id in (:project_ids) OR target_project_id in (:project_ids)", project_ids: project_ids) }
   scope :of_projects, ->(ids) { where(target_project_id: ids) }
   scope :merged, -> { with_state(:merged) }
   scope :closed_and_merged, -> { with_states(:closed, :merged) }
@@ -161,6 +160,24 @@ class MergeRequest < ActiveRecord::Base
     super("merge_requests", /(?<merge_request>\d+)/)
   end
 
+  # Returns all the merge requests from an ActiveRecord:Relation.
+  #
+  # This method uses a UNION as it usually operates on the result of
+  # ProjectsFinder#execute. PostgreSQL in particular doesn't always like queries
+  # using multiple sub-queries especially when combined with an OR statement.
+  # UNIONs on the other hand perform much better in these cases.
+  #
+  # relation - An ActiveRecord::Relation that returns a list of Projects.
+  #
+  # Returns an ActiveRecord::Relation.
+  def self.in_projects(relation)
+    source = where(source_project_id: relation).select(:id)
+    target = where(target_project_id: relation).select(:id)
+    union  = Gitlab::SQL::Union.new([source, target])
+
+    where("merge_requests.id IN (#{union.to_sql})")
+  end
+
   def to_reference(from_project = nil)
     reference = "#{self.class.reference_prefix}#{iid}"
 
diff --git a/app/models/milestone.rb b/app/models/milestone.rb
index e3969f32dd6..e3b6c552f92 100644
--- a/app/models/milestone.rb
+++ b/app/models/milestone.rb
@@ -58,9 +58,18 @@ class Milestone < ActiveRecord::Base
   alias_attribute :name, :title
 
   class << self
+    # Searches for milestones matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      query = "%#{query}%"
-      where("title like ? or description like ?", query, query)
+      t = arel_table
+      pattern = "%#{query}%"
+
+      where(t[:title].matches(pattern).or(t[:description].matches(pattern)))
     end
   end
 
diff --git a/app/models/namespace.rb b/app/models/namespace.rb
index bdb33f37495..55842df1e2d 100644
--- a/app/models/namespace.rb
+++ b/app/models/namespace.rb
@@ -52,8 +52,18 @@ class Namespace < ActiveRecord::Base
       find_by("lower(path) = :path OR lower(name) = :path", path: path.downcase)
     end
 
+    # Searches for namespaces matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation
     def search(query)
-      where("name LIKE :query OR path LIKE :query", query: "%#{query}%")
+      t = arel_table
+      pattern = "%#{query}%"
+
+      where(t[:name].matches(pattern).or(t[:path].matches(pattern)))
     end
 
     def clean_path(path)
diff --git a/app/models/note.rb b/app/models/note.rb
index 3b20d5d22b6..8b0610ff77e 100644
--- a/app/models/note.rb
+++ b/app/models/note.rb
@@ -105,8 +105,18 @@ class Note < ActiveRecord::Base
       [:discussion, type.try(:underscore), id, line_code].join("-").to_sym
     end
 
+    # Searches for notes matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String.
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      where("LOWER(note) like :query", query: "%#{query.downcase}%")
+      table   = arel_table
+      pattern = "%#{query}%"
+
+      where(table[:note].matches(pattern))
     end
 
     def grouped_awards
diff --git a/app/models/project.rb b/app/models/project.rb
index 65829bec77a..ce103398a9a 100644
--- a/app/models/project.rb
+++ b/app/models/project.rb
@@ -266,13 +266,31 @@ class Project < ActiveRecord::Base
       joins(:issues, :notes, :merge_requests).order('issues.created_at, notes.created_at, merge_requests.created_at DESC')
     end
 
+    # Searches for a list of projects based on the query given in `query`.
+    #
+    # On PostgreSQL this method uses "ILIKE" to perform a case-insensitive
+    # search. On MySQL a regular "LIKE" is used as it's already
+    # case-insensitive.
+    #
+    # query - The search query as a String.
     def search(query)
-      joins(:namespace).
-        where('LOWER(projects.name) LIKE :query OR
-              LOWER(projects.path) LIKE :query OR
-              LOWER(namespaces.name) LIKE :query OR
-              LOWER(projects.description) LIKE :query',
-              query: "%#{query.try(:downcase)}%")
+      ptable  = arel_table
+      ntable  = Namespace.arel_table
+      pattern = "%#{query}%"
+
+      projects = select(:id).where(
+        ptable[:path].matches(pattern).
+          or(ptable[:name].matches(pattern)).
+          or(ptable[:description].matches(pattern))
+      )
+
+      namespaces = select(:id).
+        joins(:namespace).
+        where(ntable[:name].matches(pattern))
+
+      union = Gitlab::SQL::Union.new([projects, namespaces])
+
+      where("projects.id IN (#{union.to_sql})")
     end
 
     def search_by_visibility(level)
@@ -280,7 +298,10 @@ class Project < ActiveRecord::Base
     end
 
     def search_by_title(query)
-      non_archived.where('LOWER(projects.name) LIKE :query', query: "%#{query.downcase}%")
+      pattern = "%#{query}%"
+      table   = Project.arel_table
+
+      non_archived.where(table[:name].matches(pattern))
     end
 
     def find_with_namespace(id)
diff --git a/app/models/snippet.rb b/app/models/snippet.rb
index dd3925c7a7d..b9e835a4486 100644
--- a/app/models/snippet.rb
+++ b/app/models/snippet.rb
@@ -113,12 +113,32 @@ class Snippet < ActiveRecord::Base
   end
 
   class << self
+    # Searches for snippets with a matching title or file name.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String.
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      where('(title LIKE :query OR file_name LIKE :query)', query: "%#{query}%")
+      t = arel_table
+      pattern = "%#{query}%"
+
+      where(t[:title].matches(pattern).or(t[:file_name].matches(pattern)))
     end
 
+    # Searches for snippets with matching content.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String.
+    #
+    # Returns an ActiveRecord::Relation.
     def search_code(query)
-      where('(content LIKE :query)', query: "%#{query}%")
+      table   = Snippet.arel_table
+      pattern = "%#{query}%"
+
+      where(table[:content].matches(pattern))
     end
 
     def accessible_to(user)
diff --git a/app/models/user.rb b/app/models/user.rb
index 505a547d8ec..101303e1f1f 100644
--- a/app/models/user.rb
+++ b/app/models/user.rb
@@ -286,8 +286,22 @@ class User < ActiveRecord::Base
       end
     end
 
+    # Searches users matching the given query.
+    #
+    # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
+    #
+    # query - The search query as a String
+    #
+    # Returns an ActiveRecord::Relation.
     def search(query)
-      where("lower(name) LIKE :query OR lower(email) LIKE :query OR lower(username) LIKE :query", query: "%#{query.downcase}%")
+      table   = arel_table
+      pattern = "%#{query}%"
+
+      where(
+        table[:name].matches(pattern).
+          or(table[:email].matches(pattern)).
+          or(table[:username].matches(pattern))
+      )
     end
 
     def by_login(login)
@@ -428,6 +442,11 @@ class User < ActiveRecord::Base
     Project.where("projects.id IN (#{projects_union.to_sql})")
   end
 
+  # Returns all the project relations
+  def project_relations
+    [personal_projects, groups_projects, projects]
+  end
+
   def owned_projects
     @owned_projects ||=
       Project.where('namespace_id IN (?) OR namespace_id = ?',
@@ -816,9 +835,7 @@ class User < ActiveRecord::Base
   private
 
   def projects_union
-    Gitlab::SQL::Union.new([personal_projects.select(:id),
-                            groups_projects.select(:id),
-                            projects.select(:id)])
+    Gitlab::SQL::Union.new(project_relations.map { |r| r.select(:id) })
   end
 
   def ci_projects_union
diff --git a/app/services/search/global_service.rb b/app/services/search/global_service.rb
index e904cb6c6fc..e1e94c5cc38 100644
--- a/app/services/search/global_service.rb
+++ b/app/services/search/global_service.rb
@@ -10,9 +10,8 @@ module Search
       group = Group.find_by(id: params[:group_id]) if params[:group_id].present?
       projects = ProjectsFinder.new.execute(current_user)
       projects = projects.in_namespace(group.id) if group
-      project_ids = projects.pluck(:id)
 
-      Gitlab::SearchResults.new(project_ids, params[:search])
+      Gitlab::SearchResults.new(projects, params[:search])
     end
   end
 end
diff --git a/app/services/search/project_service.rb b/app/services/search/project_service.rb
index f630c0a3790..c08881dce4b 100644
--- a/app/services/search/project_service.rb
+++ b/app/services/search/project_service.rb
@@ -7,7 +7,7 @@ module Search
     end
 
     def execute
-      Gitlab::ProjectSearchResults.new(project.id,
+      Gitlab::ProjectSearchResults.new(project,
                                        params[:search],
                                        params[:repository_ref])
     end
diff --git a/app/services/search/snippet_service.rb b/app/services/search/snippet_service.rb
index 8ca0877321d..0b3e713e220 100644
--- a/app/services/search/snippet_service.rb
+++ b/app/services/search/snippet_service.rb
@@ -7,8 +7,9 @@ module Search
     end
 
     def execute
-      snippet_ids = Snippet.accessible_to(current_user).pluck(:id)
-      Gitlab::SnippetSearchResults.new(snippet_ids, params[:search])
+      snippets = Snippet.accessible_to(current_user)
+
+      Gitlab::SnippetSearchResults.new(snippets, params[:search])
     end
   end
 end
diff --git a/config/initializers/mysql_ignore_postgresql_options.rb b/config/initializers/mysql_ignore_postgresql_options.rb
new file mode 100644
index 00000000000..835f3ec5574
--- /dev/null
+++ b/config/initializers/mysql_ignore_postgresql_options.rb
@@ -0,0 +1,49 @@
+# This patches ActiveRecord so indexes created using the MySQL adapter ignore
+# any PostgreSQL specific options (e.g. `using: :gin`).
+#
+# These patches do the following for MySQL:
+#
+# 1. Indexes created using the :opclasses option are ignored (as they serve no
+#    purpose on MySQL).
+# 2. When creating an index with `using: :gin` the `using` option is discarded
+#    as :gin is not a valid value for MySQL.
+# 3. The `:opclasses` option is stripped from add_index_options in case it's
+#    used anywhere other than in the add_index methods.
+
+if defined?(ActiveRecord::ConnectionAdapters::Mysql2Adapter)
+  module ActiveRecord
+    module ConnectionAdapters
+      class Mysql2Adapter < AbstractMysqlAdapter
+        alias_method :__gitlab_add_index, :add_index
+        alias_method :__gitlab_add_index_sql, :add_index_sql
+        alias_method :__gitlab_add_index_options, :add_index_options
+
+        def add_index(table_name, column_name, options = {})
+          unless options[:opclasses]
+            __gitlab_add_index(table_name, column_name, options)
+          end
+        end
+
+        def add_index_sql(table_name, column_name, options = {})
+          unless options[:opclasses]
+            __gitlab_add_index_sql(table_name, column_name, options)
+          end
+        end
+
+        def add_index_options(table_name, column_name, options = {})
+          if options[:using] and options[:using] == :gin
+            options = options.dup
+            options.delete(:using)
+          end
+
+          if options[:opclasses]
+            options = options.dup
+            options.delete(:opclasses)
+          end
+
+          __gitlab_add_index_options(table_name, column_name, options)
+        end
+      end
+    end
+  end
+end
diff --git a/config/initializers/postgresql_opclasses_support.rb b/config/initializers/postgresql_opclasses_support.rb
new file mode 100644
index 00000000000..820cc89ef57
--- /dev/null
+++ b/config/initializers/postgresql_opclasses_support.rb
@@ -0,0 +1,188 @@
+# rubocop:disable all
+
+# These changes add support for PostgreSQL operator classes when creating
+# indexes and dumping/loading schemas. Taken from Rails pull request
+# https://github.com/rails/rails/pull/19090.
+#
+# License:
+#
+# Copyright (c) 2004-2016 David Heinemeier Hansson
+#
+# Permission is hereby granted, free of charge, to any person obtaining
+# a copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be
+# included in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+require 'date'
+require 'set'
+require 'bigdecimal'
+require 'bigdecimal/util'
+
+# As the Struct definition is changed in this PR/patch we have to first remove
+# the existing one.
+ActiveRecord::ConnectionAdapters.send(:remove_const, :IndexDefinition)
+
+module ActiveRecord
+  module ConnectionAdapters #:nodoc:
+    # Abstract representation of an index definition on a table. Instances of
+    # this type are typically created and returned by methods in database
+    # adapters. e.g. ActiveRecord::ConnectionAdapters::AbstractMysqlAdapter#indexes
+    class IndexDefinition < Struct.new(:table, :name, :unique, :columns, :lengths, :orders, :where, :type, :using, :opclasses) #:nodoc:
+    end
+  end
+end
+
+
+module ActiveRecord
+  module ConnectionAdapters # :nodoc:
+    module SchemaStatements
+      def add_index_options(table_name, column_name, options = {}) #:nodoc:
+        column_names = Array(column_name)
+        index_name   = index_name(table_name, column: column_names)
+
+        options.assert_valid_keys(:unique, :order, :name, :where, :length, :internal, :using, :algorithm, :type, :opclasses)
+
+        index_type = options[:unique] ? "UNIQUE" : ""
+        index_type = options[:type].to_s if options.key?(:type)
+        index_name = options[:name].to_s if options.key?(:name)
+        max_index_length = options.fetch(:internal, false) ? index_name_length : allowed_index_name_length
+
+        if options.key?(:algorithm)
+          algorithm = index_algorithms.fetch(options[:algorithm]) {
+            raise ArgumentError.new("Algorithm must be one of the following: #{index_algorithms.keys.map(&:inspect).join(', ')}")
+          }
+        end
+
+        using = "USING #{options[:using]}" if options[:using].present?
+
+        if supports_partial_index?
+          index_options = options[:where] ? " WHERE #{options[:where]}" : ""
+        end
+
+        if index_name.length > max_index_length
+          raise ArgumentError, "Index name '#{index_name}' on table '#{table_name}' is too long; the limit is #{max_index_length} characters"
+        end
+        if table_exists?(table_name) && index_name_exists?(table_name, index_name, false)
+          raise ArgumentError, "Index name '#{index_name}' on table '#{table_name}' already exists"
+        end
+        index_columns = quoted_columns_for_index(column_names, options).join(", ")
+
+        [index_name, index_type, index_columns, index_options, algorithm, using]
+      end
+    end
+  end
+end
+
+module ActiveRecord
+  module ConnectionAdapters
+    module PostgreSQL
+      module SchemaStatements
+        # Returns an array of indexes for the given table.
+        def indexes(table_name, name = nil)
+           result = query(<<-SQL, 'SCHEMA')
+             SELECT distinct i.relname, d.indisunique, d.indkey, pg_get_indexdef(d.indexrelid), t.oid
+             FROM pg_class t
+             INNER JOIN pg_index d ON t.oid = d.indrelid
+             INNER JOIN pg_class i ON d.indexrelid = i.oid
+             WHERE i.relkind = 'i'
+               AND d.indisprimary = 'f'
+               AND t.relname = '#{table_name}'
+               AND i.relnamespace IN (SELECT oid FROM pg_namespace WHERE nspname = ANY (current_schemas(false)) )
+            ORDER BY i.relname
+          SQL
+
+          result.map do |row|
+            index_name = row[0]
+            unique = row[1] == 't'
+            indkey = row[2].split(" ")
+            inddef = row[3]
+            oid = row[4]
+
+            columns = Hash[query(<<-SQL, "SCHEMA")]
+            SELECT a.attnum, a.attname
+            FROM pg_attribute a
+            WHERE a.attrelid = #{oid}
+            AND a.attnum IN (#{indkey.join(",")})
+            SQL
+
+            column_names = columns.values_at(*indkey).compact
+
+            unless column_names.empty?
+              # add info on sort order for columns (only desc order is explicitly specified, asc is the default)
+              desc_order_columns = inddef.scan(/(\w+) DESC/).flatten
+              orders = desc_order_columns.any? ? Hash[desc_order_columns.map {|order_column| [order_column, :desc]}] : {}
+              where = inddef.scan(/WHERE (.+)$/).flatten[0]
+              using = inddef.scan(/USING (.+?) /).flatten[0].to_sym
+              opclasses = Hash[inddef.scan(/\((.+)\)$/).flatten[0].split(',').map do |column_and_opclass|
+                                 column, opclass = column_and_opclass.split(' ').map(&:strip)
+                                 [column, opclass] if opclass
+                               end.compact]
+
+              IndexDefinition.new(table_name, index_name, unique, column_names, [], orders, where, nil, using, opclasses)
+            end
+          end.compact
+        end
+
+        def add_index(table_name, column_name, options = {}) #:nodoc:
+          index_name, index_type, index_columns_and_opclasses, index_options, index_algorithm, index_using = add_index_options(table_name, column_name, options)
+          execute "CREATE #{index_type} INDEX #{index_algorithm} #{quote_column_name(index_name)} ON #{quote_table_name(table_name)} #{index_using} (#{index_columns_and_opclasses})#{index_options}"
+        end
+
+        protected
+
+          def quoted_columns_for_index(column_names, options = {})
+            column_opclasses = options[:opclasses] || {}
+            column_names.map {|name| "#{quote_column_name(name)} #{column_opclasses[name]}"}
+          end
+      end
+    end
+  end
+end
+
+module ActiveRecord
+  class SchemaDumper
+    private
+
+      def indexes(table, stream)
+        if (indexes = @connection.indexes(table)).any?
+          add_index_statements = indexes.map do |index|
+            statement_parts = [
+              "add_index #{remove_prefix_and_suffix(index.table).inspect}",
+              index.columns.inspect,
+              "name: #{index.name.inspect}",
+            ]
+            statement_parts << 'unique: true' if index.unique
+
+            index_lengths = (index.lengths || []).compact
+            statement_parts << "length: #{Hash[index.columns.zip(index.lengths)].inspect}" if index_lengths.any?
+
+            index_orders = index.orders || {}
+            statement_parts << "order: #{index.orders.inspect}" if index_orders.any?
+            statement_parts << "where: #{index.where.inspect}" if index.where
+            statement_parts << "using: #{index.using.inspect}" if index.using
+            statement_parts << "type: #{index.type.inspect}" if index.type
+            statement_parts << "opclasses: #{index.opclasses}" if index.opclasses.present?
+
+            "  #{statement_parts.join(', ')}"
+          end
+
+          stream.puts add_index_statements.sort.join("\n")
+          stream.puts
+        end
+      end
+  end
+end
diff --git a/db/migrate/20160226114608_add_trigram_indexes_for_searching.rb b/db/migrate/20160226114608_add_trigram_indexes_for_searching.rb
new file mode 100644
index 00000000000..003169c13c6
--- /dev/null
+++ b/db/migrate/20160226114608_add_trigram_indexes_for_searching.rb
@@ -0,0 +1,53 @@
+class AddTrigramIndexesForSearching < ActiveRecord::Migration
+  disable_ddl_transaction!
+
+  def up
+    return unless Gitlab::Database.postgresql?
+
+    unless trigrams_enabled?
+      raise 'You must enable the pg_trgm extension. You can do so by running ' \
+        '"CREATE EXTENSION pg_trgm;" as a PostgreSQL super user, this must be ' \
+        'done for every GitLab database. For more information see ' \
+        'http://www.postgresql.org/docs/current/static/sql-createextension.html'
+    end
+
+    # trigram indexes are case-insensitive so we can just index the column
+    # instead of indexing lower(column)
+    to_index.each do |table, columns|
+      columns.each do |column|
+        execute "CREATE INDEX CONCURRENTLY index_#{table}_on_#{column}_trigram ON #{table} USING gin(#{column} gin_trgm_ops);"
+      end
+    end
+  end
+
+  def down
+    return unless Gitlab::Database.postgresql?
+
+    to_index.each do |table, columns|
+      columns.each do |column|
+        remove_index table, name: "index_#{table}_on_#{column}_trigram"
+      end
+    end
+  end
+
+  def trigrams_enabled?
+    res = execute("SELECT true AS enabled FROM pg_available_extensions WHERE name = 'pg_trgm' AND installed_version IS NOT NULL;")
+    row = res.first
+
+    row && row['enabled'] == 't' ? true : false
+  end
+
+  def to_index
+    {
+      ci_runners:     [:token, :description],
+      issues:         [:title, :description],
+      merge_requests: [:title, :description],
+      milestones:     [:title, :description],
+      namespaces:     [:name, :path],
+      notes:          [:note],
+      projects:       [:name, :path, :description],
+      snippets:       [:title, :file_name],
+      users:          [:username, :name, :email]
+    }
+  end
+end
diff --git a/db/schema.rb b/db/schema.rb
index a74b86d8e2f..3ac6203632d 100644
--- a/db/schema.rb
+++ b/db/schema.rb
@@ -15,6 +15,7 @@ ActiveRecord::Schema.define(version: 20160309140734) do
 
   # These are extensions that must be enabled in order to support this database
   enable_extension "plpgsql"
+  enable_extension "pg_trgm"
 
   create_table "abuse_reports", force: :cascade do |t|
     t.integer  "reporter_id"
@@ -258,6 +259,9 @@ ActiveRecord::Schema.define(version: 20160309140734) do
     t.string   "architecture"
   end
 
+  add_index "ci_runners", ["description"], name: "index_ci_runners_on_description_trigram", using: :gin, opclasses: {"description"=>"gin_trgm_ops"}
+  add_index "ci_runners", ["token"], name: "index_ci_runners_on_token_trigram", using: :gin, opclasses: {"token"=>"gin_trgm_ops"}
+
   create_table "ci_services", force: :cascade do |t|
     t.string   "type"
     t.string   "title"
@@ -417,11 +421,13 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "issues", ["author_id"], name: "index_issues_on_author_id", using: :btree
   add_index "issues", ["created_at", "id"], name: "index_issues_on_created_at_and_id", using: :btree
   add_index "issues", ["created_at"], name: "index_issues_on_created_at", using: :btree
+  add_index "issues", ["description"], name: "index_issues_on_description_trigram", using: :gin, opclasses: {"description"=>"gin_trgm_ops"}
   add_index "issues", ["milestone_id"], name: "index_issues_on_milestone_id", using: :btree
   add_index "issues", ["project_id", "iid"], name: "index_issues_on_project_id_and_iid", unique: true, using: :btree
   add_index "issues", ["project_id"], name: "index_issues_on_project_id", using: :btree
   add_index "issues", ["state"], name: "index_issues_on_state", using: :btree
   add_index "issues", ["title"], name: "index_issues_on_title", using: :btree
+  add_index "issues", ["title"], name: "index_issues_on_title_trigram", using: :gin, opclasses: {"title"=>"gin_trgm_ops"}
 
   create_table "keys", force: :cascade do |t|
     t.integer  "user_id"
@@ -543,12 +549,14 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "merge_requests", ["author_id"], name: "index_merge_requests_on_author_id", using: :btree
   add_index "merge_requests", ["created_at", "id"], name: "index_merge_requests_on_created_at_and_id", using: :btree
   add_index "merge_requests", ["created_at"], name: "index_merge_requests_on_created_at", using: :btree
+  add_index "merge_requests", ["description"], name: "index_merge_requests_on_description_trigram", using: :gin, opclasses: {"description"=>"gin_trgm_ops"}
   add_index "merge_requests", ["milestone_id"], name: "index_merge_requests_on_milestone_id", using: :btree
   add_index "merge_requests", ["source_branch"], name: "index_merge_requests_on_source_branch", using: :btree
   add_index "merge_requests", ["source_project_id"], name: "index_merge_requests_on_source_project_id", using: :btree
   add_index "merge_requests", ["target_branch"], name: "index_merge_requests_on_target_branch", using: :btree
   add_index "merge_requests", ["target_project_id", "iid"], name: "index_merge_requests_on_target_project_id_and_iid", unique: true, using: :btree
   add_index "merge_requests", ["title"], name: "index_merge_requests_on_title", using: :btree
+  add_index "merge_requests", ["title"], name: "index_merge_requests_on_title_trigram", using: :gin, opclasses: {"title"=>"gin_trgm_ops"}
 
   create_table "milestones", force: :cascade do |t|
     t.string   "title",       null: false
@@ -562,10 +570,12 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   end
 
   add_index "milestones", ["created_at", "id"], name: "index_milestones_on_created_at_and_id", using: :btree
+  add_index "milestones", ["description"], name: "index_milestones_on_description_trigram", using: :gin, opclasses: {"description"=>"gin_trgm_ops"}
   add_index "milestones", ["due_date"], name: "index_milestones_on_due_date", using: :btree
   add_index "milestones", ["project_id", "iid"], name: "index_milestones_on_project_id_and_iid", unique: true, using: :btree
   add_index "milestones", ["project_id"], name: "index_milestones_on_project_id", using: :btree
   add_index "milestones", ["title"], name: "index_milestones_on_title", using: :btree
+  add_index "milestones", ["title"], name: "index_milestones_on_title_trigram", using: :gin, opclasses: {"title"=>"gin_trgm_ops"}
 
   create_table "namespaces", force: :cascade do |t|
     t.string   "name",                     null: false
@@ -580,8 +590,10 @@ ActiveRecord::Schema.define(version: 20160309140734) do
 
   add_index "namespaces", ["created_at", "id"], name: "index_namespaces_on_created_at_and_id", using: :btree
   add_index "namespaces", ["name"], name: "index_namespaces_on_name", unique: true, using: :btree
+  add_index "namespaces", ["name"], name: "index_namespaces_on_name_trigram", using: :gin, opclasses: {"name"=>"gin_trgm_ops"}
   add_index "namespaces", ["owner_id"], name: "index_namespaces_on_owner_id", using: :btree
   add_index "namespaces", ["path"], name: "index_namespaces_on_path", unique: true, using: :btree
+  add_index "namespaces", ["path"], name: "index_namespaces_on_path_trigram", using: :gin, opclasses: {"path"=>"gin_trgm_ops"}
   add_index "namespaces", ["type"], name: "index_namespaces_on_type", using: :btree
 
   create_table "notes", force: :cascade do |t|
@@ -607,6 +619,7 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "notes", ["created_at"], name: "index_notes_on_created_at", using: :btree
   add_index "notes", ["is_award"], name: "index_notes_on_is_award", using: :btree
   add_index "notes", ["line_code"], name: "index_notes_on_line_code", using: :btree
+  add_index "notes", ["note"], name: "index_notes_on_note_trigram", using: :gin, opclasses: {"note"=>"gin_trgm_ops"}
   add_index "notes", ["noteable_id", "noteable_type"], name: "index_notes_on_noteable_id_and_noteable_type", using: :btree
   add_index "notes", ["noteable_type"], name: "index_notes_on_noteable_type", using: :btree
   add_index "notes", ["project_id", "noteable_type"], name: "index_notes_on_project_id_and_noteable_type", using: :btree
@@ -705,9 +718,12 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "projects", ["ci_id"], name: "index_projects_on_ci_id", using: :btree
   add_index "projects", ["created_at", "id"], name: "index_projects_on_created_at_and_id", using: :btree
   add_index "projects", ["creator_id"], name: "index_projects_on_creator_id", using: :btree
+  add_index "projects", ["description"], name: "index_projects_on_description_trigram", using: :gin, opclasses: {"description"=>"gin_trgm_ops"}
   add_index "projects", ["last_activity_at"], name: "index_projects_on_last_activity_at", using: :btree
+  add_index "projects", ["name"], name: "index_projects_on_name_trigram", using: :gin, opclasses: {"name"=>"gin_trgm_ops"}
   add_index "projects", ["namespace_id"], name: "index_projects_on_namespace_id", using: :btree
   add_index "projects", ["path"], name: "index_projects_on_path", using: :btree
+  add_index "projects", ["path"], name: "index_projects_on_path_trigram", using: :gin, opclasses: {"path"=>"gin_trgm_ops"}
   add_index "projects", ["runners_token"], name: "index_projects_on_runners_token", using: :btree
   add_index "projects", ["star_count"], name: "index_projects_on_star_count", using: :btree
   add_index "projects", ["visibility_level"], name: "index_projects_on_visibility_level", using: :btree
@@ -785,7 +801,9 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "snippets", ["author_id"], name: "index_snippets_on_author_id", using: :btree
   add_index "snippets", ["created_at", "id"], name: "index_snippets_on_created_at_and_id", using: :btree
   add_index "snippets", ["created_at"], name: "index_snippets_on_created_at", using: :btree
+  add_index "snippets", ["file_name"], name: "index_snippets_on_file_name_trigram", using: :gin, opclasses: {"file_name"=>"gin_trgm_ops"}
   add_index "snippets", ["project_id"], name: "index_snippets_on_project_id", using: :btree
+  add_index "snippets", ["title"], name: "index_snippets_on_title_trigram", using: :gin, opclasses: {"title"=>"gin_trgm_ops"}
   add_index "snippets", ["updated_at"], name: "index_snippets_on_updated_at", using: :btree
   add_index "snippets", ["visibility_level"], name: "index_snippets_on_visibility_level", using: :btree
 
@@ -919,9 +937,12 @@ ActiveRecord::Schema.define(version: 20160309140734) do
   add_index "users", ["created_at", "id"], name: "index_users_on_created_at_and_id", using: :btree
   add_index "users", ["current_sign_in_at"], name: "index_users_on_current_sign_in_at", using: :btree
   add_index "users", ["email"], name: "index_users_on_email", unique: true, using: :btree
+  add_index "users", ["email"], name: "index_users_on_email_trigram", using: :gin, opclasses: {"email"=>"gin_trgm_ops"}
   add_index "users", ["name"], name: "index_users_on_name", using: :btree
+  add_index "users", ["name"], name: "index_users_on_name_trigram", using: :gin, opclasses: {"name"=>"gin_trgm_ops"}
   add_index "users", ["reset_password_token"], name: "index_users_on_reset_password_token", unique: true, using: :btree
   add_index "users", ["username"], name: "index_users_on_username", using: :btree
+  add_index "users", ["username"], name: "index_users_on_username_trigram", using: :gin, opclasses: {"username"=>"gin_trgm_ops"}
 
   create_table "users_star_projects", force: :cascade do |t|
     t.integer  "project_id", null: false
diff --git a/doc/install/requirements.md b/doc/install/requirements.md
index 8df142c531b..d59b7f0e84d 100644
--- a/doc/install/requirements.md
+++ b/doc/install/requirements.md
@@ -97,6 +97,17 @@ To change the Unicorn workers when you have the Omnibus package please see [the
 
 If you want to run the database separately expect a size of about 1 MB per user.
 
+### PostgreSQL Requirements
+
+Users using PostgreSQL must ensure the `pg_trgm` extension is loaded into every
+GitLab database. This extension can be enabled (using a PostgreSQL super user)
+by running the following query for every database:
+
+    CREATE EXTENSION pg_trgm;
+
+On some systems you may need to install an additional package (e.g.
+`postgresql-contrib`) for this extension to become available.
+
 ## Redis and Sidekiq
 
 Redis stores all user sessions and the background task queue.
diff --git a/lib/gitlab/project_search_results.rb b/lib/gitlab/project_search_results.rb
index 70de6a74e76..0607a8b9592 100644
--- a/lib/gitlab/project_search_results.rb
+++ b/lib/gitlab/project_search_results.rb
@@ -2,8 +2,8 @@ module Gitlab
   class ProjectSearchResults < SearchResults
     attr_reader :project, :repository_ref
 
-    def initialize(project_id, query, repository_ref = nil)
-      @project = Project.find(project_id)
+    def initialize(project, query, repository_ref = nil)
+      @project = project
       @repository_ref = if repository_ref.present?
                           repository_ref
                         else
@@ -73,7 +73,7 @@ module Gitlab
     end
 
     def notes
-      Note.where(project_id: limit_project_ids).user.search(query).order('updated_at DESC')
+      project.notes.user.search(query).order('updated_at DESC')
     end
 
     def commits
@@ -84,8 +84,8 @@ module Gitlab
       end
     end
 
-    def limit_project_ids
-      [project.id]
+    def project_ids_relation
+      project
     end
   end
 end
diff --git a/lib/gitlab/search_results.rb b/lib/gitlab/search_results.rb
index 2ab2d4af797..f13528a2eea 100644
--- a/lib/gitlab/search_results.rb
+++ b/lib/gitlab/search_results.rb
@@ -2,12 +2,12 @@ module Gitlab
   class SearchResults
     attr_reader :query
 
-    # Limit search results by passed project ids
+    # Limit search results by passed projects
     # It allows us to search only for projects user has access to
-    attr_reader :limit_project_ids
+    attr_reader :limit_projects
 
-    def initialize(limit_project_ids, query)
-      @limit_project_ids = limit_project_ids || Project.all
+    def initialize(limit_projects, query)
+      @limit_projects = limit_projects || Project.all
       @query = Shellwords.shellescape(query) if query.present?
     end
 
@@ -27,7 +27,8 @@ module Gitlab
     end
 
     def total_count
-      @total_count ||= projects_count + issues_count + merge_requests_count + milestones_count
+      @total_count ||= projects_count + issues_count + merge_requests_count +
+        milestones_count
     end
 
     def projects_count
@@ -53,27 +54,29 @@ module Gitlab
     private
 
     def projects
-      Project.where(id: limit_project_ids).search(query)
+      limit_projects.search(query)
     end
 
     def issues
-      issues = Issue.where(project_id: limit_project_ids)
+      issues = Issue.where(project_id: project_ids_relation)
+
       if query =~ /#(\d+)\z/
         issues = issues.where(iid: $1)
       else
         issues = issues.full_search(query)
       end
+
       issues.order('updated_at DESC')
     end
 
     def milestones
-      milestones = Milestone.where(project_id: limit_project_ids)
+      milestones = Milestone.where(project_id: project_ids_relation)
       milestones = milestones.search(query)
       milestones.order('updated_at DESC')
     end
 
     def merge_requests
-      merge_requests = MergeRequest.in_projects(limit_project_ids)
+      merge_requests = MergeRequest.in_projects(project_ids_relation)
       if query =~ /[#!](\d+)\z/
         merge_requests = merge_requests.where(iid: $1)
       else
@@ -89,5 +92,9 @@ module Gitlab
     def per_page
       20
     end
+
+    def project_ids_relation
+      limit_projects.select(:id).reorder(nil)
+    end
   end
 end
diff --git a/lib/gitlab/snippet_search_results.rb b/lib/gitlab/snippet_search_results.rb
index addda95be2b..e0e74ff8359 100644
--- a/lib/gitlab/snippet_search_results.rb
+++ b/lib/gitlab/snippet_search_results.rb
@@ -2,10 +2,10 @@ module Gitlab
   class SnippetSearchResults < SearchResults
     include SnippetsHelper
 
-    attr_reader :limit_snippet_ids
+    attr_reader :limit_snippets
 
-    def initialize(limit_snippet_ids, query)
-      @limit_snippet_ids = limit_snippet_ids
+    def initialize(limit_snippets, query)
+      @limit_snippets = limit_snippets
       @query = query
     end
 
@@ -35,11 +35,11 @@ module Gitlab
     private
 
     def snippet_titles
-      Snippet.where(id: limit_snippet_ids).search(query).order('updated_at DESC')
+      limit_snippets.search(query).order('updated_at DESC')
     end
 
     def snippet_blobs
-      Snippet.where(id: limit_snippet_ids).search_code(query).order('updated_at DESC')
+      limit_snippets.search_code(query).order('updated_at DESC')
     end
 
     def default_scope
diff --git a/spec/lib/gitlab/project_search_results_spec.rb b/spec/lib/gitlab/project_search_results_spec.rb
index efc2e5f4ef1..09adbc07dcb 100644
--- a/spec/lib/gitlab/project_search_results_spec.rb
+++ b/spec/lib/gitlab/project_search_results_spec.rb
@@ -5,7 +5,7 @@ describe Gitlab::ProjectSearchResults, lib: true do
   let(:query) { 'hello world' }
 
   describe 'initialize with empty ref' do
-    let(:results) { Gitlab::ProjectSearchResults.new(project.id, query, '') }
+    let(:results) { Gitlab::ProjectSearchResults.new(project, query, '') }
 
     it { expect(results.project).to eq(project) }
     it { expect(results.repository_ref).to be_nil }
@@ -14,7 +14,7 @@ describe Gitlab::ProjectSearchResults, lib: true do
 
   describe 'initialize with ref' do
     let(:ref) { 'refs/heads/test' }
-    let(:results) { Gitlab::ProjectSearchResults.new(project.id, query, ref) }
+    let(:results) { Gitlab::ProjectSearchResults.new(project, query, ref) }
 
     it { expect(results.project).to eq(project) }
     it { expect(results.repository_ref).to eq(ref) }
diff --git a/spec/lib/gitlab/search_results_spec.rb b/spec/lib/gitlab/search_results_spec.rb
new file mode 100644
index 00000000000..bb18f417858
--- /dev/null
+++ b/spec/lib/gitlab/search_results_spec.rb
@@ -0,0 +1,55 @@
+require 'spec_helper'
+
+describe Gitlab::SearchResults do
+  let!(:project) { create(:project, name: 'foo') }
+  let!(:issue) { create(:issue, project: project, title: 'foo') }
+
+  let!(:merge_request) do
+    create(:merge_request, source_project: project, title: 'foo')
+  end
+
+  let!(:milestone) { create(:milestone, project: project, title: 'foo') }
+  let(:results) { described_class.new(Project.all, 'foo') }
+
+  describe '#total_count' do
+    it 'returns the total amount of search hits' do
+      expect(results.total_count).to eq(4)
+    end
+  end
+
+  describe '#projects_count' do
+    it 'returns the total amount of projects' do
+      expect(results.projects_count).to eq(1)
+    end
+  end
+
+  describe '#issues_count' do
+    it 'returns the total amount of issues' do
+      expect(results.issues_count).to eq(1)
+    end
+  end
+
+  describe '#merge_requests_count' do
+    it 'returns the total amount of merge requests' do
+      expect(results.merge_requests_count).to eq(1)
+    end
+  end
+
+  describe '#milestones_count' do
+    it 'returns the total amount of milestones' do
+      expect(results.milestones_count).to eq(1)
+    end
+  end
+
+  describe '#empty?' do
+    it 'returns true when there are no search results' do
+      allow(results).to receive(:total_count).and_return(0)
+
+      expect(results.empty?).to eq(true)
+    end
+
+    it 'returns false when there are search results' do
+      expect(results.empty?).to eq(false)
+    end
+  end
+end
diff --git a/spec/lib/gitlab/snippet_search_results_spec.rb b/spec/lib/gitlab/snippet_search_results_spec.rb
new file mode 100644
index 00000000000..e86b9ef6a63
--- /dev/null
+++ b/spec/lib/gitlab/snippet_search_results_spec.rb
@@ -0,0 +1,25 @@
+require 'spec_helper'
+
+describe Gitlab::SnippetSearchResults do
+  let!(:snippet) { create(:snippet, content: 'foo', file_name: 'foo') }
+
+  let(:results) { described_class.new(Snippet.all, 'foo') }
+
+  describe '#total_count' do
+    it 'returns the total amount of search hits' do
+      expect(results.total_count).to eq(2)
+    end
+  end
+
+  describe '#snippet_titles_count' do
+    it 'returns the amount of matched snippet titles' do
+      expect(results.snippet_titles_count).to eq(1)
+    end
+  end
+
+  describe '#snippet_blobs_count' do
+    it 'returns the amount of matched snippet blobs' do
+      expect(results.snippet_blobs_count).to eq(1)
+    end
+  end
+end
diff --git a/spec/models/ci/runner_spec.rb b/spec/models/ci/runner_spec.rb
index e891838672e..25e9e5eca48 100644
--- a/spec/models/ci/runner_spec.rb
+++ b/spec/models/ci/runner_spec.rb
@@ -132,4 +132,32 @@ describe Ci::Runner, models: true do
       expect(runner.belongs_to_one_project?).to be_truthy
     end
   end
+
+  describe '#search' do
+    let(:runner) { create(:ci_runner, token: '123abc') }
+
+    it 'returns runners with a matching token' do
+      expect(described_class.search(runner.token)).to eq([runner])
+    end
+
+    it 'returns runners with a partially matching token' do
+      expect(described_class.search(runner.token[0..2])).to eq([runner])
+    end
+
+    it 'returns runners with a matching token regardless of the casing' do
+      expect(described_class.search(runner.token.upcase)).to eq([runner])
+    end
+
+    it 'returns runners with a matching description' do
+      expect(described_class.search(runner.description)).to eq([runner])
+    end
+
+    it 'returns runners with a partially matching description' do
+      expect(described_class.search(runner.description[0..2])).to eq([runner])
+    end
+
+    it 'returns runners with a matching description regardless of the casing' do
+      expect(described_class.search(runner.description.upcase)).to eq([runner])
+    end
+  end
 end
diff --git a/spec/models/concerns/issuable_spec.rb b/spec/models/concerns/issuable_spec.rb
index 600089802b2..aff384c2949 100644
--- a/spec/models/concerns/issuable_spec.rb
+++ b/spec/models/concerns/issuable_spec.rb
@@ -32,9 +32,54 @@ describe Issue, "Issuable" do
   describe ".search" do
     let!(:searchable_issue) { create(:issue, title: "Searchable issue") }
 
-    it "matches by title" do
+    it 'returns notes with a matching title' do
+      expect(described_class.search(searchable_issue.title)).
+        to eq([searchable_issue])
+    end
+
+    it 'returns notes with a partially matching title' do
       expect(described_class.search('able')).to eq([searchable_issue])
     end
+
+    it 'returns notes with a matching title regardless of the casing' do
+      expect(described_class.search(searchable_issue.title.upcase)).
+        to eq([searchable_issue])
+    end
+  end
+
+  describe ".full_search" do
+    let!(:searchable_issue) do
+      create(:issue, title: "Searchable issue", description: 'kittens')
+    end
+
+    it 'returns notes with a matching title' do
+      expect(described_class.full_search(searchable_issue.title)).
+        to eq([searchable_issue])
+    end
+
+    it 'returns notes with a partially matching title' do
+      expect(described_class.full_search('able')).to eq([searchable_issue])
+    end
+
+    it 'returns notes with a matching title regardless of the casing' do
+      expect(described_class.full_search(searchable_issue.title.upcase)).
+        to eq([searchable_issue])
+    end
+
+    it 'returns notes with a matching description' do
+      expect(described_class.full_search(searchable_issue.description)).
+        to eq([searchable_issue])
+    end
+
+    it 'returns notes with a partially matching description' do
+      expect(described_class.full_search(searchable_issue.description)).
+        to eq([searchable_issue])
+    end
+
+    it 'returns notes with a matching description regardless of the casing' do
+      expect(described_class.full_search(searchable_issue.description.upcase)).
+        to eq([searchable_issue])
+    end
   end
 
   describe "#today?" do
diff --git a/spec/models/group_spec.rb b/spec/models/group_spec.rb
index 3c995053eec..c9245fc9535 100644
--- a/spec/models/group_spec.rb
+++ b/spec/models/group_spec.rb
@@ -103,4 +103,30 @@ describe Group, models: true do
       expect(group.avatar_type).to eq(["only images allowed"])
     end
   end
+
+  describe '.search' do
+    it 'returns groups with a matching name' do
+      expect(described_class.search(group.name)).to eq([group])
+    end
+
+    it 'returns groups with a partially matching name' do
+      expect(described_class.search(group.name[0..2])).to eq([group])
+    end
+
+    it 'returns groups with a matching name regardless of the casing' do
+      expect(described_class.search(group.name.upcase)).to eq([group])
+    end
+
+    it 'returns groups with a matching path' do
+      expect(described_class.search(group.path)).to eq([group])
+    end
+
+    it 'returns groups with a partially matching path' do
+      expect(described_class.search(group.path[0..2])).to eq([group])
+    end
+
+    it 'returns groups with a matching path regardless of the casing' do
+      expect(described_class.search(group.path.upcase)).to eq([group])
+    end
+  end
 end
diff --git a/spec/models/merge_request_spec.rb b/spec/models/merge_request_spec.rb
index 59c40922abb..8bf68013fd2 100644
--- a/spec/models/merge_request_spec.rb
+++ b/spec/models/merge_request_spec.rb
@@ -80,6 +80,12 @@ describe MergeRequest, models: true do
     it { is_expected.to respond_to(:merge_when_build_succeeds) }
   end
 
+  describe '.in_projects' do
+    it 'returns the merge requests for a set of projects' do
+      expect(described_class.in_projects(Project.all)).to eq([subject])
+    end
+  end
+
   describe '#to_reference' do
     it 'returns a String reference to the object' do
       expect(subject.to_reference).to eq "!#{subject.iid}"
diff --git a/spec/models/milestone_spec.rb b/spec/models/milestone_spec.rb
index 28f13100d15..de1757bf67a 100644
--- a/spec/models/milestone_spec.rb
+++ b/spec/models/milestone_spec.rb
@@ -181,4 +181,34 @@ describe Milestone, models: true do
       expect(issue4.position).to eq(42)
     end
   end
+
+  describe '.search' do
+    let(:milestone) { create(:milestone, title: 'foo', description: 'bar') }
+
+    it 'returns milestones with a matching title' do
+      expect(described_class.search(milestone.title)).to eq([milestone])
+    end
+
+    it 'returns milestones with a partially matching title' do
+      expect(described_class.search(milestone.title[0..2])).to eq([milestone])
+    end
+
+    it 'returns milestones with a matching title regardless of the casing' do
+      expect(described_class.search(milestone.title.upcase)).to eq([milestone])
+    end
+
+    it 'returns milestones with a matching description' do
+      expect(described_class.search(milestone.description)).to eq([milestone])
+    end
+
+    it 'returns milestones with a partially matching description' do
+      expect(described_class.search(milestone.description[0..2])).
+        to eq([milestone])
+    end
+
+    it 'returns milestones with a matching description regardless of the casing' do
+      expect(described_class.search(milestone.description.upcase)).
+        to eq([milestone])
+    end
+  end
 end
diff --git a/spec/models/namespace_spec.rb b/spec/models/namespace_spec.rb
index e0b3290e416..3c3a580942a 100644
--- a/spec/models/namespace_spec.rb
+++ b/spec/models/namespace_spec.rb
@@ -41,13 +41,32 @@ describe Namespace, models: true do
     it { expect(namespace.human_name).to eq(namespace.owner_name) }
   end
 
-  describe :search do
-    before do
-      @namespace = create :namespace
+  describe '.search' do
+    let(:namespace) { create(:namespace) }
+
+    it 'returns namespaces with a matching name' do
+      expect(described_class.search(namespace.name)).to eq([namespace])
+    end
+
+    it 'returns namespaces with a partially matching name' do
+      expect(described_class.search(namespace.name[0..2])).to eq([namespace])
+    end
+
+    it 'returns namespaces with a matching name regardless of the casing' do
+      expect(described_class.search(namespace.name.upcase)).to eq([namespace])
+    end
+
+    it 'returns namespaces with a matching path' do
+      expect(described_class.search(namespace.path)).to eq([namespace])
     end
 
-    it { expect(Namespace.search(@namespace.path)).to eq([@namespace]) }
-    it { expect(Namespace.search('unknown')).to eq([]) }
+    it 'returns namespaces with a partially matching path' do
+      expect(described_class.search(namespace.path[0..2])).to eq([namespace])
+    end
+
+    it 'returns namespaces with a matching path regardless of the casing' do
+      expect(described_class.search(namespace.path.upcase)).to eq([namespace])
+    end
   end
 
   describe :move_dir do
diff --git a/spec/models/note_spec.rb b/spec/models/note_spec.rb
index 33085dac4ea..cd620ea5440 100644
--- a/spec/models/note_spec.rb
+++ b/spec/models/note_spec.rb
@@ -140,10 +140,16 @@ describe Note, models: true do
     end
   end
 
-  describe :search do
-    let!(:note) { create(:note, note: "WoW") }
+  describe '.search' do
+    let(:note) { create(:note, note: 'WoW') }
 
-    it { expect(Note.search('wow')).to include(note) }
+    it 'returns notes with matching content' do
+      expect(described_class.search(note.note)).to eq([note])
+    end
+
+    it 'returns notes with matching content regardless of the casing' do
+      expect(described_class.search('WOW')).to eq([note])
+    end
   end
 
   describe :grouped_awards do
diff --git a/spec/models/project_spec.rb b/spec/models/project_spec.rb
index 2fa38a5d3d3..59c5ffa6b9c 100644
--- a/spec/models/project_spec.rb
+++ b/spec/models/project_spec.rb
@@ -582,7 +582,58 @@ describe Project, models: true do
       it { expect(forked_project.visibility_level_allowed?(Gitlab::VisibilityLevel::INTERNAL)).to be_truthy }
       it { expect(forked_project.visibility_level_allowed?(Gitlab::VisibilityLevel::PUBLIC)).to be_falsey }
     end
+  end
+
+  describe '.search' do
+    let(:project) { create(:project, description: 'kitten mittens') }
 
+    it 'returns projects with a matching name' do
+      expect(described_class.search(project.name)).to eq([project])
+    end
+
+    it 'returns projects with a partially matching name' do
+      expect(described_class.search(project.name[0..2])).to eq([project])
+    end
+
+    it 'returns projects with a matching name regardless of the casing' do
+      expect(described_class.search(project.name.upcase)).to eq([project])
+    end
+
+    it 'returns projects with a matching description' do
+      expect(described_class.search(project.description)).to eq([project])
+    end
+
+    it 'returns projects with a partially matching description' do
+      expect(described_class.search('kitten')).to eq([project])
+    end
+
+    it 'returns projects with a matching description regardless of the casing' do
+      expect(described_class.search('KITTEN')).to eq([project])
+    end
+
+    it 'returns projects with a matching path' do
+      expect(described_class.search(project.path)).to eq([project])
+    end
+
+    it 'returns projects with a partially matching path' do
+      expect(described_class.search(project.path[0..2])).to eq([project])
+    end
+
+    it 'returns projects with a matching path regardless of the casing' do
+      expect(described_class.search(project.path.upcase)).to eq([project])
+    end
+
+    it 'returns projects with a matching namespace name' do
+      expect(described_class.search(project.namespace.name)).to eq([project])
+    end
+
+    it 'returns projects with a partially matching namespace name' do
+      expect(described_class.search(project.namespace.name[0..2])).to eq([project])
+    end
+
+    it 'returns projects with a matching namespace name regardless of the casing' do
+      expect(described_class.search(project.namespace.name.upcase)).to eq([project])
+    end
   end
 
   describe '#rename_repo' do
@@ -647,4 +698,20 @@ describe Project, models: true do
       project.expire_caches_before_rename('foo')
     end
   end
+
+  describe '.search_by_title' do
+    let(:project) { create(:project, name: 'kittens') }
+
+    it 'returns projects with a matching name' do
+      expect(described_class.search_by_title(project.name)).to eq([project])
+    end
+
+    it 'returns projects with a partially matching name' do
+      expect(described_class.search_by_title('kitten')).to eq([project])
+    end
+
+    it 'returns projects with a matching name regardless of the casing' do
+      expect(described_class.search_by_title('KITTENS')).to eq([project])
+    end
+  end
 end
diff --git a/spec/models/snippet_spec.rb b/spec/models/snippet_spec.rb
index 7e5b5499aea..5077ac7b62b 100644
--- a/spec/models/snippet_spec.rb
+++ b/spec/models/snippet_spec.rb
@@ -59,4 +59,48 @@ describe Snippet, models: true do
       expect(snippet.to_reference(cross)).to eq "#{project.to_reference}$#{snippet.id}"
     end
   end
+
+  describe '.search' do
+    let(:snippet) { create(:snippet) }
+
+    it 'returns snippets with a matching title' do
+      expect(described_class.search(snippet.title)).to eq([snippet])
+    end
+
+    it 'returns snippets with a partially matching title' do
+      expect(described_class.search(snippet.title[0..2])).to eq([snippet])
+    end
+
+    it 'returns snippets with a matching title regardless of the casing' do
+      expect(described_class.search(snippet.title.upcase)).to eq([snippet])
+    end
+
+    it 'returns snippets with a matching file name' do
+      expect(described_class.search(snippet.file_name)).to eq([snippet])
+    end
+
+    it 'returns snippets with a partially matching file name' do
+      expect(described_class.search(snippet.file_name[0..2])).to eq([snippet])
+    end
+
+    it 'returns snippets with a matching file name regardless of the casing' do
+      expect(described_class.search(snippet.file_name.upcase)).to eq([snippet])
+    end
+  end
+
+  describe '#search_code' do
+    let(:snippet) { create(:snippet, content: 'class Foo; end') }
+
+    it 'returns snippets with matching content' do
+      expect(described_class.search_code(snippet.content)).to eq([snippet])
+    end
+
+    it 'returns snippets with partially matching content' do
+      expect(described_class.search_code('class')).to eq([snippet])
+    end
+
+    it 'returns snippets with matching content regardless of the casing' do
+      expect(described_class.search_code('FOO')).to eq([snippet])
+    end
+  end
 end
diff --git a/spec/models/user_spec.rb b/spec/models/user_spec.rb
index 412101ac9f9..909b6796591 100644
--- a/spec/models/user_spec.rb
+++ b/spec/models/user_spec.rb
@@ -463,17 +463,43 @@ describe User, models: true do
     end
   end
 
-  describe 'search' do
-    let(:user1) { create(:user, username: 'James', email: 'james@testing.com') }
-    let(:user2) { create(:user, username: 'jameson', email: 'jameson@example.com') }
-
-    it "should be case insensitive" do
-      expect(User.search(user1.username.upcase).to_a).to eq([user1])
-      expect(User.search(user1.username.downcase).to_a).to eq([user1])
-      expect(User.search(user2.username.upcase).to_a).to eq([user2])
-      expect(User.search(user2.username.downcase).to_a).to eq([user2])
-      expect(User.search(user1.username.downcase).to_a.size).to eq(2)
-      expect(User.search(user2.username.downcase).to_a.size).to eq(1)
+  describe '.search' do
+    let(:user) { create(:user) }
+
+    it 'returns users with a matching name' do
+      expect(described_class.search(user.name)).to eq([user])
+    end
+
+    it 'returns users with a partially matching name' do
+      expect(described_class.search(user.name[0..2])).to eq([user])
+    end
+
+    it 'returns users with a matching name regardless of the casing' do
+      expect(described_class.search(user.name.upcase)).to eq([user])
+    end
+
+    it 'returns users with a matching Email' do
+      expect(described_class.search(user.email)).to eq([user])
+    end
+
+    it 'returns users with a partially matching Email' do
+      expect(described_class.search(user.email[0..2])).to eq([user])
+    end
+
+    it 'returns users with a matching Email regardless of the casing' do
+      expect(described_class.search(user.email.upcase)).to eq([user])
+    end
+
+    it 'returns users with a matching username' do
+      expect(described_class.search(user.username)).to eq([user])
+    end
+
+    it 'returns users with a partially matching username' do
+      expect(described_class.search(user.username[0..2])).to eq([user])
+    end
+
+    it 'returns users with a matching username regardless of the casing' do
+      expect(described_class.search(user.username.upcase)).to eq([user])
     end
   end