Merge branch 'rework-authorizations-performance' into 'master'

Rework project authorizations and nested groups for better performance

See merge request !10885

63 files changed, 1198 insertions, 472 deletions

diff --git a/app/controllers/groups_controller.rb b/app/controllers/groups_controller.rb
index 3e921a1b1cb..18a2d69db29 100644
--- a/app/controllers/groups_controller.rb
+++ b/app/controllers/groups_controller.rb
@@ -64,6 +64,8 @@ class GroupsController < Groups::ApplicationController
   end
 
   def subgroups
+    return not_found unless Group.supports_nested_groups?
+
     @nested_groups = GroupsFinder.new(current_user, parent: group).execute
     @nested_groups = @nested_groups.search(params[:filter_groups]) if params[:filter_groups].present?
   end
diff --git a/app/models/concerns/routable.rb b/app/models/concerns/routable.rb
index c4463abdfe6..63d02b76f6b 100644
--- a/app/models/concerns/routable.rb
+++ b/app/models/concerns/routable.rb
@@ -84,89 +84,6 @@ module Routable
         joins(:route).where(wheres.join(' OR '))
       end
     end
-
-    # Builds a relation to find multiple objects that are nested under user membership
-    #
-    # Usage:
-    #
-    #     Klass.member_descendants(1)
-    #
-    # Returns an ActiveRecord::Relation.
-    def member_descendants(user_id)
-      joins(:route).
-        joins("INNER JOIN routes r2 ON routes.path LIKE CONCAT(r2.path, '/%')
-               INNER JOIN members ON members.source_id = r2.source_id
-               AND members.source_type = r2.source_type").
-        where('members.user_id = ?', user_id)
-    end
-
-    # Builds a relation to find multiple objects that are nested under user
-    # membership. Includes the parent, as opposed to `#member_descendants`
-    # which only includes the descendants.
-    #
-    # Usage:
-    #
-    #     Klass.member_self_and_descendants(1)
-    #
-    # Returns an ActiveRecord::Relation.
-    def member_self_and_descendants(user_id)
-      joins(:route).
-        joins("INNER JOIN routes r2 ON routes.path LIKE CONCAT(r2.path, '/%')
-               OR routes.path = r2.path
-               INNER JOIN members ON members.source_id = r2.source_id
-               AND members.source_type = r2.source_type").
-        where('members.user_id = ?', user_id)
-    end
-
-    # Returns all objects in a hierarchy, where any node in the hierarchy is
-    # under the user membership.
-    #
-    # Usage:
-    #
-    #     Klass.member_hierarchy(1)
-    #
-    # Examples:
-    #
-    #     Given the following group tree...
-    #
-    #            _______group_1_______
-    #           |                     |
-    #           |                     |
-    #     nested_group_1        nested_group_2
-    #           |                     |
-    #           |                     |
-    #     nested_group_1_1      nested_group_2_1
-    #
-    #
-    #     ... the following results are returned:
-    #
-    #     * the user is a member of group 1
-    #       => 'group_1',
-    #          'nested_group_1', nested_group_1_1',
-    #          'nested_group_2', 'nested_group_2_1'
-    #
-    #     * the user is a member of nested_group_2
-    #       => 'group1',
-    #          'nested_group_2', 'nested_group_2_1'
-    #
-    #     * the user is a member of nested_group_2_1
-    #       => 'group1',
-    #          'nested_group_2', 'nested_group_2_1'
-    #
-    # Returns an ActiveRecord::Relation.
-    def member_hierarchy(user_id)
-      paths = member_self_and_descendants(user_id).pluck('routes.path')
-
-      return none if paths.empty?
-
-      wheres = paths.map do |path|
-        "#{connection.quote(path)} = routes.path
-         OR
-         #{connection.quote(path)} LIKE CONCAT(routes.path, '/%')"
-      end
-
-      joins(:route).where(wheres.join(' OR '))
-    end
   end
 
   def full_name
diff --git a/app/models/concerns/select_for_project_authorization.rb b/app/models/concerns/select_for_project_authorization.rb
index 50a1d7fc3e1..58194b0ea13 100644
--- a/app/models/concerns/select_for_project_authorization.rb
+++ b/app/models/concerns/select_for_project_authorization.rb
@@ -3,7 +3,11 @@ module SelectForProjectAuthorization
 
   module ClassMethods
     def select_for_project_authorization
-      select("members.user_id, projects.id AS project_id, members.access_level")
+      select("projects.id AS project_id, members.access_level")
+    end
+
+    def select_as_master_for_project_authorization
+      select(["projects.id AS project_id", "#{Gitlab::Access::MASTER} AS access_level"])
     end
   end
 end
diff --git a/app/models/group.rb b/app/models/group.rb
index 6aab477f431..be944da5a67 100644
--- a/app/models/group.rb
+++ b/app/models/group.rb
@@ -38,6 +38,10 @@ class Group < Namespace
   after_save :update_two_factor_requirement
 
   class << self
+    def supports_nested_groups?
+      Gitlab::Database.postgresql?
+    end
+
     # Searches for groups matching the given query.
     #
     # This method uses ILIKE on PostgreSQL and LIKE on MySQL.
@@ -78,7 +82,7 @@ class Group < Namespace
       if current_scope.joins_values.include?(:shared_projects)
         joins('INNER JOIN namespaces project_namespace ON project_namespace.id = projects.namespace_id')
           .where('project_namespace.share_with_group_lock = ?',  false)
-          .select("members.user_id, projects.id AS project_id, LEAST(project_group_links.group_access, members.access_level) AS access_level")
+          .select("projects.id AS project_id, LEAST(project_group_links.group_access, members.access_level) AS access_level")
       else
         super
       end
diff --git a/app/models/namespace.rb b/app/models/namespace.rb
index 4d59267f71d..aebee06d560 100644
--- a/app/models/namespace.rb
+++ b/app/models/namespace.rb
@@ -176,26 +176,20 @@ class Namespace < ActiveRecord::Base
     projects.with_shared_runners.any?
   end
 
-  # Scopes the model on ancestors of the record
+  # Returns all the ancestors of the current namespaces.
   def ancestors
-    if parent_id
-      path = route ? route.path : full_path
-      paths = []
+    return self.class.none unless parent_id
 
-      until path.blank?
-        path = path.rpartition('/').first
-        paths << path
-      end
-
-      self.class.joins(:route).where('routes.path IN (?)', paths).reorder('routes.path ASC')
-    else
-      self.class.none
-    end
+    Gitlab::GroupHierarchy.
+      new(self.class.where(id: parent_id)).
+      base_and_ancestors
   end
 
-  # Scopes the model on direct and indirect children of the record
+  # Returns all the descendants of the current namespace.
   def descendants
-    self.class.joins(:route).merge(Route.inside_path(route.path)).reorder('routes.path ASC')
+    Gitlab::GroupHierarchy.
+      new(self.class.where(parent_id: id)).
+      base_and_descendants
   end
 
   def user_ids_for_project_authorizations
diff --git a/app/models/project_authorization.rb b/app/models/project_authorization.rb
index 4c7f4f5a429..def09675253 100644
--- a/app/models/project_authorization.rb
+++ b/app/models/project_authorization.rb
@@ -6,6 +6,12 @@ class ProjectAuthorization < ActiveRecord::Base
   validates :access_level, inclusion: { in: Gitlab::Access.all_values }, presence: true
   validates :user, uniqueness: { scope: [:project, :access_level] }, presence: true
 
+  def self.select_from_union(union)
+    select(['project_id', 'MAX(access_level) AS access_level']).
+      from("(#{union.to_sql}) #{ProjectAuthorization.table_name}").
+      group(:project_id)
+  end
+
   def self.insert_authorizations(rows, per_batch = 1000)
     rows.each_slice(per_batch) do |slice|
       tuples = slice.map do |tuple|
diff --git a/app/models/user.rb b/app/models/user.rb
index 625ba90002b..3f816a250c2 100644
--- a/app/models/user.rb
+++ b/app/models/user.rb
@@ -10,9 +10,12 @@ class User < ActiveRecord::Base
   include Sortable
   include CaseSensitivity
   include TokenAuthenticatable
+  include IgnorableColumn
 
   DEFAULT_NOTIFICATION_LEVEL = :participating
 
+  ignore_column :authorized_projects_populated
+
   add_authentication_token_field :authentication_token
   add_authentication_token_field :incoming_email_token
   add_authentication_token_field :rss_token
@@ -218,7 +221,6 @@ class User < ActiveRecord::Base
   scope :blocked, -> { with_states(:blocked, :ldap_blocked) }
   scope :external, -> { where(external: true) }
   scope :active, -> { with_state(:active).non_internal }
-  scope :not_in_project, ->(project) { project.users.present? ? where("id not in (:ids)", ids: project.users.map(&:id) ) : all }
   scope :without_projects, -> { where('id NOT IN (SELECT DISTINCT(user_id) FROM members WHERE user_id IS NOT NULL AND requested_at IS NULL)') }
   scope :todo_authors, ->(user_id, state) { where(id: Todo.where(user_id: user_id, state: state).select(:author_id)) }
   scope :order_recent_sign_in, -> { reorder(Gitlab::Database.nulls_last_order('last_sign_in_at', 'DESC')) }
@@ -510,23 +512,16 @@ class User < ActiveRecord::Base
     Group.where("namespaces.id IN (#{union.to_sql})")
   end
 
-  def nested_groups
-    Group.member_descendants(id)
-  end
-
+  # Returns a relation of groups the user has access to, including their parent
+  # and child groups (recursively).
   def all_expanded_groups
-    Group.member_hierarchy(id)
+    Gitlab::GroupHierarchy.new(groups).all_groups
   end
 
   def expanded_groups_requiring_two_factor_authentication
     all_expanded_groups.where(require_two_factor_authentication: true)
   end
 
-  def nested_groups_projects
-    Project.joins(:namespace).where('namespaces.parent_id IS NOT NULL').
-      member_descendants(id)
-  end
-
   def refresh_authorized_projects
     Users::RefreshAuthorizedProjectsService.new(self).execute
   end
@@ -535,18 +530,15 @@ class User < ActiveRecord::Base
     project_authorizations.where(project_id: project_ids).delete_all
   end
 
-  def set_authorized_projects_column
-    unless authorized_projects_populated
-      update_column(:authorized_projects_populated, true)
-    end
-  end
-
   def authorized_projects(min_access_level = nil)
-    refresh_authorized_projects unless authorized_projects_populated
-
-    # We're overriding an association, so explicitly call super with no arguments or it would be passed as `force_reload` to the association
+    # We're overriding an association, so explicitly call super with no
+    # arguments or it would be passed as `force_reload` to the association
     projects = super()
-    projects = projects.where('project_authorizations.access_level >= ?', min_access_level) if min_access_level
+
+    if min_access_level
+      projects = projects.
+        where('project_authorizations.access_level >= ?', min_access_level)
+    end
 
     projects
   end
diff --git a/app/services/users/refresh_authorized_projects_service.rb b/app/services/users/refresh_authorized_projects_service.rb
index 8f6f5b937c4..3e07b811027 100644
--- a/app/services/users/refresh_authorized_projects_service.rb
+++ b/app/services/users/refresh_authorized_projects_service.rb
@@ -73,12 +73,11 @@ module Users
     # remove - The IDs of the authorization rows to remove.
     # add - Rows to insert in the form `[user id, project id, access level]`
     def update_authorizations(remove = [], add = [])
-      return if remove.empty? && add.empty? && user.authorized_projects_populated
+      return if remove.empty? && add.empty?
 
       User.transaction do
         user.remove_project_authorizations(remove) unless remove.empty?
         ProjectAuthorization.insert_authorizations(add) unless add.empty?
-        user.set_authorized_projects_column
       end
 
       # Since we batch insert authorization rows, Rails' associations may get
@@ -101,38 +100,13 @@ module Users
     end
 
     def fresh_authorizations
-      ProjectAuthorization.
-        unscoped.
-        select('project_id, MAX(access_level) AS access_level').
-        from("(#{project_authorizations_union.to_sql}) #{ProjectAuthorization.table_name}").
-        group(:project_id)
-    end
-
-    private
-
-    # Returns a union query of projects that the user is authorized to access
-    def project_authorizations_union
-      relations = [
-        # Personal projects
-        user.personal_projects.select("#{user.id} AS user_id, projects.id AS project_id, #{Gitlab::Access::MASTER} AS access_level"),
-
-        # Projects the user is a member of
-        user.projects.select_for_project_authorization,
-
-        # Projects of groups the user is a member of
-        user.groups_projects.select_for_project_authorization,
-
-        # Projects of subgroups of groups the user is a member of
-        user.nested_groups_projects.select_for_project_authorization,
-
-        # Projects shared with groups the user is a member of
-        user.groups.joins(:shared_projects).select_for_project_authorization,
-
-        # Projects shared with subgroups of groups the user is a member of
-        user.nested_groups.joins(:shared_projects).select_for_project_authorization
-      ]
+      klass = if Group.supports_nested_groups?
+                Gitlab::ProjectAuthorizations::WithNestedGroups
+              else
+                Gitlab::ProjectAuthorizations::WithoutNestedGroups
+              end
 
-      Gitlab::SQL::Union.new(relations)
+      klass.new(user).calculate
     end
   end
 end
diff --git a/app/views/groups/_show_nav.html.haml b/app/views/groups/_show_nav.html.haml
index b2097e88741..35b75bc0923 100644
--- a/app/views/groups/_show_nav.html.haml
+++ b/app/views/groups/_show_nav.html.haml
@@ -2,6 +2,7 @@
   = nav_link(page: group_path(@group)) do
     = link_to group_path(@group) do
       Projects
-  = nav_link(page: subgroups_group_path(@group)) do
-    = link_to subgroups_group_path(@group) do
-      Subgroups
+  - if Group.supports_nested_groups?
+    = nav_link(page: subgroups_group_path(@group)) do
+      = link_to subgroups_group_path(@group) do
+        Subgroups
diff --git a/changelogs/unreleased/rework-authorizations-performance.yml b/changelogs/unreleased/rework-authorizations-performance.yml
new file mode 100644
index 00000000000..f64257a6f56
--- /dev/null
+++ b/changelogs/unreleased/rework-authorizations-performance.yml
@@ -0,0 +1,6 @@
+---
+title: >
+  Project authorizations are calculated much faster when using PostgreSQL, and
+  nested groups support for MySQL has been removed
+merge_request: 10885
+author:
diff --git a/config/initializers/postgresql_cte.rb b/config/initializers/postgresql_cte.rb
new file mode 100644
index 00000000000..7f0df8949db
--- /dev/null
+++ b/config/initializers/postgresql_cte.rb
@@ -0,0 +1,132 @@
+# Adds support for WITH statements when using PostgreSQL. The code here is taken
+# from https://github.com/shmay/ctes_in_my_pg which at the time of writing has
+# not been pushed to RubyGems. The license of this repository is as follows:
+#
+# The MIT License (MIT)
+#
+# Copyright (c) 2012 Dan McClain
+#
+# 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.
+
+module ActiveRecord
+  class Relation
+    class Merger # :nodoc:
+      def normal_values
+        NORMAL_VALUES + [:with]
+      end
+    end
+  end
+end
+
+module ActiveRecord::Querying
+  delegate :with, to: :all
+end
+
+module ActiveRecord
+  class Relation
+    # WithChain objects act as placeholder for queries in which #with does not have any parameter.
+    # In this case, #with must be chained with #recursive to return a new relation.
+    class WithChain
+      def initialize(scope)
+        @scope = scope
+      end
+
+      # Returns a new relation expressing WITH RECURSIVE
+      def recursive(*args)
+        @scope.with_values += args
+        @scope.recursive_value = true
+        @scope
+      end
+    end
+
+    def with_values
+      @values[:with] || []
+    end
+
+    def with_values=(values)
+      raise ImmutableRelation if @loaded
+      @values[:with] = values
+    end
+
+    def recursive_value=(value)
+      raise ImmutableRelation if @loaded
+      @values[:recursive] = value
+    end
+
+    def recursive_value
+      @values[:recursive]
+    end
+
+    def with(opts = :chain, *rest)
+      if opts == :chain
+        WithChain.new(spawn)
+      elsif opts.blank?
+        self
+      else
+        spawn.with!(opts, *rest)
+      end
+    end
+
+    def with!(opts = :chain, *rest) # :nodoc:
+      if opts == :chain
+        WithChain.new(self)
+      else
+        self.with_values += [opts] + rest
+        self
+      end
+    end
+
+    def build_arel
+      arel = super()
+
+      build_with(arel) if @values[:with]
+
+      arel
+    end
+
+    def build_with(arel)
+      with_statements = with_values.flat_map do |with_value|
+        case with_value
+        when String
+          with_value
+        when Hash
+          with_value.map  do |name, expression|
+            case expression
+            when String
+              select = Arel::Nodes::SqlLiteral.new "(#{expression})"
+            when ActiveRecord::Relation, Arel::SelectManager
+              select = Arel::Nodes::SqlLiteral.new "(#{expression.to_sql})"
+            end
+            Arel::Nodes::As.new Arel::Nodes::SqlLiteral.new("\"#{name}\""), select
+          end
+        when Arel::Nodes::As
+          with_value
+        end
+      end
+
+      unless with_statements.empty?
+        if recursive_value
+          arel.with :recursive, with_statements
+        else
+          arel.with with_statements
+        end
+      end
+    end
+  end
+end
diff --git a/db/migrate/20170503140201_reschedule_project_authorizations.rb b/db/migrate/20170503140201_reschedule_project_authorizations.rb
new file mode 100644
index 00000000000..fa45adadbae
--- /dev/null
+++ b/db/migrate/20170503140201_reschedule_project_authorizations.rb
@@ -0,0 +1,44 @@
+# See http://doc.gitlab.com/ce/development/migration_style_guide.html
+# for more information on how to write migrations for GitLab.
+
+class RescheduleProjectAuthorizations < ActiveRecord::Migration
+  include Gitlab::Database::MigrationHelpers
+
+  DOWNTIME = false
+
+  disable_ddl_transaction!
+
+  class User < ActiveRecord::Base
+    self.table_name = 'users'
+  end
+
+  def up
+    offset = 0
+    batch = 5000
+    start = Time.now
+
+    loop do
+      relation = User.where('id > ?', offset)
+      user_ids = relation.limit(batch).reorder(id: :asc).pluck(:id)
+
+      break if user_ids.empty?
+
+      offset = user_ids.last
+
+      # This will schedule each batch 5 minutes after the previous batch was
+      # scheduled. This smears out the load over time, instead of immediately
+      # scheduling a million jobs.
+      Sidekiq::Client.push_bulk(
+        'queue' => 'authorized_projects',
+        'args' => user_ids.zip,
+        'class' => 'AuthorizedProjectsWorker',
+        'at' => start.to_i
+      )
+
+      start += 5.minutes
+    end
+  end
+
+  def down
+  end
+end
diff --git a/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb b/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb
new file mode 100644
index 00000000000..c67690642c9
--- /dev/null
+++ b/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb
@@ -0,0 +1,123 @@
+# See http://doc.gitlab.com/ce/development/migration_style_guide.html
+# for more information on how to write migrations for GitLab.
+
+# This migration depends on code external to it. For example, it relies on
+# updating a namespace to also rename directories (uploads, GitLab pages, etc).
+# The alternative is to copy hundreds of lines of code into this migration,
+# adjust them where needed, etc; something which doesn't work well at all.
+class TurnNestedGroupsIntoRegularGroupsForMysql < ActiveRecord::Migration
+  include Gitlab::Database::MigrationHelpers
+
+  # Set this constant to true if this migration requires downtime.
+  DOWNTIME = false
+
+  def run_migration?
+    Gitlab::Database.mysql?
+  end
+
+  def up
+    return unless run_migration?
+
+    # For all sub-groups we need to give the right people access. We do this as
+    # follows:
+    #
+    # 1. Get all the ancestors for the current namespace
+    # 2. Get all the members of these namespaces, along with their higher access
+    #    level
+    # 3. Give these members access to the current namespace
+    Namespace.unscoped.where('parent_id IS NOT NULL').find_each do |namespace|
+      rows = []
+      existing = namespace.members.pluck(:user_id)
+
+      all_members_for(namespace).each do |member|
+        next if existing.include?(member[:user_id])
+
+        rows << {
+          access_level: member[:access_level],
+          source_id: namespace.id,
+          source_type: 'Namespace',
+          user_id: member[:user_id],
+          notification_level: 3, # global
+          type: 'GroupMember',
+          created_at: Time.current,
+          updated_at: Time.current
+        }
+      end
+
+      bulk_insert_members(rows)
+
+      # This method relies on the parent to determine the proper path.
+      # Because we reset "parent_id" this method will not return the right path
+      # when moving namespaces.
+      full_path_was = namespace.send(:full_path_was)
+
+      namespace.define_singleton_method(:full_path_was) { full_path_was }
+
+      namespace.update!(parent_id: nil, path: new_path_for(namespace))
+    end
+  end
+
+  def down
+    # There is no way to go back from regular groups to nested groups.
+  end
+
+  # Generates a new (unique) path for a namespace.
+  def new_path_for(namespace)
+    counter = 1
+    base = namespace.full_path.tr('/', '-')
+    new_path = base
+
+    while Namespace.unscoped.where(path: new_path).exists?
+      new_path = base + "-#{counter}"
+      counter += 1
+    end
+
+    new_path
+  end
+
+  # Returns an Array containing all the ancestors of the current namespace.
+  #
+  # This method is not particularly efficient, but it's probably still faster
+  # than using the "routes" table. Most importantly of all, it _only_ depends
+  # on the namespaces table and the "parent_id" column.
+  def ancestors_for(namespace)
+    ancestors = []
+    current = namespace
+
+    while current&.parent_id
+      # We're using find_by(id: ...) here to deal with cases where the
+      # parent_id may point to a missing row.
+      current = Namespace.unscoped.select([:id, :parent_id]).
+        find_by(id: current.parent_id)
+
+      ancestors << current.id if current
+    end
+
+    ancestors
+  end
+
+  # Returns a relation containing all the members that have access to any of
+  # the current namespace's parent namespaces.
+  def all_members_for(namespace)
+    Member.
+      unscoped.
+      select(['user_id', 'MAX(access_level) AS access_level']).
+      where(source_type: 'Namespace', source_id: ancestors_for(namespace)).
+      group(:user_id)
+  end
+
+  def bulk_insert_members(rows)
+    return if rows.empty?
+
+    keys = rows.first.keys
+
+    tuples = rows.map do |row|
+      row.map { |(_, value)| connection.quote(value) }
+    end
+
+    execute <<-EOF.strip_heredoc
+    INSERT INTO members (#{keys.join(', ')})
+    VALUES #{tuples.map { |tuple| "(#{tuple.join(', ')})" }.join(', ')}
+    EOF
+  end
+end
diff --git a/db/migrate/20170504182103_add_index_project_group_links_group_id.rb b/db/migrate/20170504182103_add_index_project_group_links_group_id.rb
new file mode 100644
index 00000000000..62bf641daa6
--- /dev/null
+++ b/db/migrate/20170504182103_add_index_project_group_links_group_id.rb
@@ -0,0 +1,19 @@
+# See http://doc.gitlab.com/ce/development/migration_style_guide.html
+# for more information on how to write migrations for GitLab.
+
+class AddIndexProjectGroupLinksGroupId < ActiveRecord::Migration
+  include Gitlab::Database::MigrationHelpers
+
+  # Set this constant to true if this migration requires downtime.
+  DOWNTIME = false
+
+  disable_ddl_transaction!
+
+  def up
+    add_concurrent_index :project_group_links, :group_id
+  end
+
+  def down
+    remove_concurrent_index :project_group_links, :group_id
+  end
+end
diff --git a/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb b/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb
new file mode 100644
index 00000000000..1b44334395f
--- /dev/null
+++ b/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb
@@ -0,0 +1,15 @@
+# See http://doc.gitlab.com/ce/development/migration_style_guide.html
+# for more information on how to write migrations for GitLab.
+
+class RemoveUsersAuthorizedProjectsPopulated < ActiveRecord::Migration
+  include Gitlab::Database::MigrationHelpers
+
+  # Set this constant to true if this migration requires downtime.
+  DOWNTIME = false
+
+  disable_ddl_transaction!
+
+  def change
+    remove_column :users, :authorized_projects_populated, :boolean
+  end
+end
diff --git a/db/schema.rb b/db/schema.rb
index f6b513a5725..4c73f74ef1f 100644
--- a/db/schema.rb
+++ b/db/schema.rb
@@ -928,6 +928,8 @@ ActiveRecord::Schema.define(version: 20170523091700) do
     t.date "expires_at"
   end
 
+  add_index "project_group_links", ["group_id"], name: "index_project_group_links_on_group_id", using: :btree
+
   create_table "project_import_data", force: :cascade do |t|
     t.integer "project_id"
     t.text "data"
@@ -1355,7 +1357,6 @@ ActiveRecord::Schema.define(version: 20170523091700) do
     t.boolean "external", default: false
     t.string "incoming_email_token"
     t.string "organization"
-    t.boolean "authorized_projects_populated"
     t.boolean "require_two_factor_authentication_from_group", default: false, null: false
     t.integer "two_factor_grace_period", default: 48, null: false
     t.boolean "ghost"
diff --git a/doc/user/group/subgroups/index.md b/doc/user/group/subgroups/index.md
index d5edf36f6b0..c4921c74a17 100644
--- a/doc/user/group/subgroups/index.md
+++ b/doc/user/group/subgroups/index.md
@@ -13,6 +13,15 @@ up to 20 levels of nested groups, which among other things can help you to:
 - **Make it easier to manage people and control visibility.** Give people
   different [permissions][] depending on their group [membership](#membership).
 
+## Database Requirements
+
+Nested groups are only supported when you use PostgreSQL. Supporting nested
+groups on MySQL in an efficient way is not possible due to MySQL's limitations.
+See the following links for more information:
+
+* <https://gitlab.com/gitlab-org/gitlab-ce/issues/30472>
+* <https://gitlab.com/gitlab-org/gitlab-ce/merge_requests/10885>
+
 ## Overview
 
 A group can have many subgroups inside it, and at the same time a group can have
diff --git a/lib/api/entities.rb b/lib/api/entities.rb
index cf4affe1758..8c5e5c91769 100644
--- a/lib/api/entities.rb
+++ b/lib/api/entities.rb
@@ -152,7 +152,10 @@ module API
       expose :web_url
       expose :request_access_enabled
       expose :full_name, :full_path
-      expose :parent_id
+
+      if ::Group.supports_nested_groups?
+        expose :parent_id
+      end
 
       expose :statistics, if: :statistics do
         with_options format_with: -> (value) { value.to_i } do
diff --git a/lib/api/groups.rb b/lib/api/groups.rb
index 3da7d735da8..ee85b777aff 100644
--- a/lib/api/groups.rb
+++ b/lib/api/groups.rb
@@ -70,7 +70,11 @@ module API
       params do
         requires :name, type: String, desc: 'The name of the group'
         requires :path, type: String, desc: 'The path of the group'
-        optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+
+        if ::Group.supports_nested_groups?
+          optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+        end
+
         use :optional_params
       end
       post do
diff --git a/lib/api/v3/entities.rb b/lib/api/v3/entities.rb
index 332f233bf5e..2e1b243c2db 100644
--- a/lib/api/v3/entities.rb
+++ b/lib/api/v3/entities.rb
@@ -137,7 +137,10 @@ module API
         expose :web_url
         expose :request_access_enabled
         expose :full_name, :full_path
-        expose :parent_id
+
+        if ::Group.supports_nested_groups?
+          expose :parent_id
+        end
 
         expose :statistics, if: :statistics do
           with_options format_with: -> (value) { value.to_i } do
diff --git a/lib/api/v3/groups.rb b/lib/api/v3/groups.rb
index 6187445fc8d..2c52d21fa1c 100644
--- a/lib/api/v3/groups.rb
+++ b/lib/api/v3/groups.rb
@@ -74,7 +74,11 @@ module API
         params do
           requires :name, type: String, desc: 'The name of the group'
           requires :path, type: String, desc: 'The path of the group'
-          optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+
+          if ::Group.supports_nested_groups?
+            optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+          end
+
           use :optional_params
         end
         post do
diff --git a/lib/gitlab/group_hierarchy.rb b/lib/gitlab/group_hierarchy.rb
new file mode 100644
index 00000000000..e9d5d52cabb
--- /dev/null
+++ b/lib/gitlab/group_hierarchy.rb
@@ -0,0 +1,104 @@
+module Gitlab
+  # Retrieving of parent or child groups based on a base ActiveRecord relation.
+  #
+  # This class uses recursive CTEs and as a result will only work on PostgreSQL.
+  class GroupHierarchy
+    attr_reader :base, :model
+
+    # base - An instance of ActiveRecord::Relation for which to get parent or
+    #        child groups.
+    def initialize(base)
+      @base = base
+      @model = base.model
+    end
+
+    # Returns a relation that includes the base set of groups and all their
+    # ancestors (recursively).
+    def base_and_ancestors
+      return model.none unless Group.supports_nested_groups?
+
+      base_and_ancestors_cte.apply_to(model.all)
+    end
+
+    # Returns a relation that includes the base set of groups and all their
+    # descendants (recursively).
+    def base_and_descendants
+      return model.none unless Group.supports_nested_groups?
+
+      base_and_descendants_cte.apply_to(model.all)
+    end
+
+    # Returns a relation that includes the base groups, their ancestors, and the
+    # descendants of the base groups.
+    #
+    # The resulting query will roughly look like the following:
+    #
+    #     WITH RECURSIVE ancestors AS ( ... ),
+    #       descendants AS ( ... )
+    #     SELECT *
+    #     FROM (
+    #       SELECT *
+    #       FROM ancestors namespaces
+    #
+    #       UNION
+    #
+    #       SELECT *
+    #       FROM descendants namespaces
+    #     ) groups;
+    #
+    # Using this approach allows us to further add criteria to the relation with
+    # Rails thinking it's selecting data the usual way.
+    def all_groups
+      return base unless Group.supports_nested_groups?
+
+      ancestors = base_and_ancestors_cte
+      descendants = base_and_descendants_cte
+
+      ancestors_table = ancestors.alias_to(groups_table)
+      descendants_table = descendants.alias_to(groups_table)
+
+      union = SQL::Union.new([model.unscoped.from(ancestors_table),
+                              model.unscoped.from(descendants_table)])
+
+      model.
+        unscoped.
+        with.
+        recursive(ancestors.to_arel, descendants.to_arel).
+        from("(#{union.to_sql}) #{model.table_name}")
+    end
+
+    private
+
+    def base_and_ancestors_cte
+      cte = SQL::RecursiveCTE.new(:base_and_ancestors)
+
+      cte << base.except(:order)
+
+      # Recursively get all the ancestors of the base set.
+      cte << model.
+        from([groups_table, cte.table]).
+        where(groups_table[:id].eq(cte.table[:parent_id])).
+        except(:order)
+
+      cte
+    end
+
+    def base_and_descendants_cte
+      cte = SQL::RecursiveCTE.new(:base_and_descendants)
+
+      cte << base.except(:order)
+
+      # Recursively get all the descendants of the base set.
+      cte << model.
+        from([groups_table, cte.table]).
+        where(groups_table[:parent_id].eq(cte.table[:id])).
+        except(:order)
+
+      cte
+    end
+
+    def groups_table
+      model.arel_table
+    end
+  end
+end
diff --git a/lib/gitlab/project_authorizations/with_nested_groups.rb b/lib/gitlab/project_authorizations/with_nested_groups.rb
new file mode 100644
index 00000000000..bb0df1e3dad
--- /dev/null
+++ b/lib/gitlab/project_authorizations/with_nested_groups.rb
@@ -0,0 +1,125 @@
+module Gitlab
+  module ProjectAuthorizations
+    # Calculating new project authorizations when supporting nested groups.
+    #
+    # This class relies on Common Table Expressions to efficiently get all data,
+    # including data for nested groups. As a result this class can only be used
+    # on PostgreSQL.
+    class WithNestedGroups
+      attr_reader :user
+
+      # user - The User object for which to calculate the authorizations.
+      def initialize(user)
+        @user = user
+      end
+
+      def calculate
+        cte = recursive_cte
+        cte_alias = cte.table.alias(Group.table_name)
+        projects = Project.arel_table
+        links = ProjectGroupLink.arel_table
+
+        relations = [
+          # The project a user has direct access to.
+          user.projects.select_for_project_authorization,
+
+          # The personal projects of the user.
+          user.personal_projects.select_as_master_for_project_authorization,
+
+          # Projects that belong directly to any of the groups the user has
+          # access to.
+          Namespace.
+            unscoped.
+            select([alias_as_column(projects[:id], 'project_id'),
+                    cte_alias[:access_level]]).
+            from(cte_alias).
+            joins(:projects),
+
+          # Projects shared with any of the namespaces the user has access to.
+          Namespace.
+            unscoped.
+            select([links[:project_id],
+                    least(cte_alias[:access_level],
+                          links[:group_access],
+                          'access_level')]).
+            from(cte_alias).
+            joins('INNER JOIN project_group_links ON project_group_links.group_id = namespaces.id').
+            joins('INNER JOIN projects ON projects.id = project_group_links.project_id').
+            joins('INNER JOIN namespaces p_ns ON p_ns.id = projects.namespace_id').
+            where('p_ns.share_with_group_lock IS FALSE')
+        ]
+
+        union = Gitlab::SQL::Union.new(relations)
+
+        ProjectAuthorization.
+          unscoped.
+          with.
+          recursive(cte.to_arel).
+          select_from_union(union)
+      end
+
+      private
+
+      # Builds a recursive CTE that gets all the groups the current user has
+      # access to, including any nested groups.
+      def recursive_cte
+        cte = Gitlab::SQL::RecursiveCTE.new(:namespaces_cte)
+        members = Member.arel_table
+        namespaces = Namespace.arel_table
+
+        # Namespaces the user is a member of.
+        cte << user.groups.
+          select([namespaces[:id], members[:access_level]]).
+          except(:order)
+
+        # Sub groups of any groups the user is a member of.
+        cte << Group.select([namespaces[:id],
+                             greatest(members[:access_level],
+                                      cte.table[:access_level], 'access_level')]).
+          joins(join_cte(cte)).
+          joins(join_members).
+          except(:order)
+
+        cte
+      end
+
+      # Builds a LEFT JOIN to join optional memberships onto the CTE.
+      def join_members
+        members = Member.arel_table
+        namespaces = Namespace.arel_table
+
+        cond = members[:source_id].
+          eq(namespaces[:id]).
+          and(members[:source_type].eq('Namespace')).
+          and(members[:requested_at].eq(nil)).
+          and(members[:user_id].eq(user.id))
+
+        Arel::Nodes::OuterJoin.new(members, Arel::Nodes::On.new(cond))
+      end
+
+      # Builds an INNER JOIN to join namespaces onto the CTE.
+      def join_cte(cte)
+        namespaces = Namespace.arel_table
+        cond = cte.table[:id].eq(namespaces[:parent_id])
+
+        Arel::Nodes::InnerJoin.new(cte.table, Arel::Nodes::On.new(cond))
+      end
+
+      def greatest(left, right, column_alias)
+        sql_function('GREATEST', [left, right], column_alias)
+      end
+
+      def least(left, right, column_alias)
+        sql_function('LEAST', [left, right], column_alias)
+      end
+
+      def sql_function(name, args, column_alias)
+        alias_as_column(Arel::Nodes::NamedFunction.new(name, args), column_alias)
+      end
+
+      def alias_as_column(value, alias_to)
+        Arel::Nodes::As.new(value, Arel::Nodes::SqlLiteral.new(alias_to))
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/project_authorizations/without_nested_groups.rb b/lib/gitlab/project_authorizations/without_nested_groups.rb
new file mode 100644
index 00000000000..627e8c5fba2
--- /dev/null
+++ b/lib/gitlab/project_authorizations/without_nested_groups.rb
@@ -0,0 +1,35 @@
+module Gitlab
+  module ProjectAuthorizations
+    # Calculating new project authorizations when not supporting nested groups.
+    class WithoutNestedGroups
+      attr_reader :user
+
+      # user - The User object for which to calculate the authorizations.
+      def initialize(user)
+        @user = user
+      end
+
+      def calculate
+        relations = [
+          # Projects the user is a direct member of
+          user.projects.select_for_project_authorization,
+
+          # Personal projects
+          user.personal_projects.select_as_master_for_project_authorization,
+
+          # Projects of groups the user is a member of
+          user.groups_projects.select_for_project_authorization,
+
+          # Projects shared with groups the user is a member of
+          user.groups.joins(:shared_projects).select_for_project_authorization
+        ]
+
+        union = Gitlab::SQL::Union.new(relations)
+
+        ProjectAuthorization.
+          unscoped.
+          select_from_union(union)
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/sql/recursive_cte.rb b/lib/gitlab/sql/recursive_cte.rb
new file mode 100644
index 00000000000..5b1b03820a3
--- /dev/null
+++ b/lib/gitlab/sql/recursive_cte.rb
@@ -0,0 +1,62 @@
+module Gitlab
+  module SQL
+    # Class for easily building recursive CTE statements.
+    #
+    # Example:
+    #
+    #     cte = RecursiveCTE.new(:my_cte_name)
+    #     ns = Arel::Table.new(:namespaces)
+    #
+    #     cte << Namespace.
+    #       where(ns[:parent_id].eq(some_namespace_id))
+    #
+    #     cte << Namespace.
+    #       from([ns, cte.table]).
+    #       where(ns[:parent_id].eq(cte.table[:id]))
+    #
+    #     Namespace.with.
+    #       recursive(cte.to_arel).
+    #       from(cte.alias_to(ns))
+    class RecursiveCTE
+      attr_reader :table
+
+      # name - The name of the CTE as a String or Symbol.
+      def initialize(name)
+        @table = Arel::Table.new(name)
+        @queries = []
+      end
+
+      # Adds a query to the body of the CTE.
+      #
+      # relation - The relation object to add to the body of the CTE.
+      def <<(relation)
+        @queries << relation
+      end
+
+      # Returns the Arel relation for this CTE.
+      def to_arel
+        sql = Arel::Nodes::SqlLiteral.new(Union.new(@queries).to_sql)
+
+        Arel::Nodes::As.new(table, Arel::Nodes::Grouping.new(sql))
+      end
+
+      # Returns an "AS" statement that aliases the CTE name as the given table
+      # name. This allows one to trick ActiveRecord into thinking it's selecting
+      # from an actual table, when in reality it's selecting from a CTE.
+      #
+      # alias_table - The Arel table to use as the alias.
+      def alias_to(alias_table)
+        Arel::Nodes::As.new(table, alias_table)
+      end
+
+      # Applies the CTE to the given relation, returning a new one that will
+      # query from it.
+      def apply_to(relation)
+        relation.except(:where).
+          with.
+          recursive(to_arel).
+          from(alias_to(relation.model.arel_table))
+      end
+    end
+  end
+end
diff --git a/spec/controllers/autocomplete_controller_spec.rb b/spec/controllers/autocomplete_controller_spec.rb
index 412d3643e94..2c9d1ffc9c2 100644
--- a/spec/controllers/autocomplete_controller_spec.rb
+++ b/spec/controllers/autocomplete_controller_spec.rb
@@ -22,7 +22,7 @@ describe AutocompleteController do
         let(:body) { JSON.parse(response.body) }
 
         it { expect(body).to be_kind_of(Array) }
-        it { expect(body.size).to eq 1 }
+        it { expect(body.size).to eq 2 }
         it { expect(body.map { |u| u["username"] }).to include(user.username) }
       end
 
@@ -80,8 +80,8 @@ describe AutocompleteController do
         end
 
         it { expect(body).to be_kind_of(Array) }
-        it { expect(body.size).to eq 2 }
-        it { expect(body.map { |u| u['username'] }).to match_array([user.username, non_member.username]) }
+        it { expect(body.size).to eq 3 }
+        it { expect(body.map { |u| u['username'] }).to include(user.username, non_member.username) }
       end
     end
 
@@ -122,7 +122,7 @@ describe AutocompleteController do
         end
 
         it { expect(body).to be_kind_of(Array) }
-        it { expect(body.size).to eq 1 }
+        it { expect(body.size).to eq 2 }
       end
 
       describe 'GET #users with project' do
diff --git a/spec/controllers/groups_controller_spec.rb b/spec/controllers/groups_controller_spec.rb
index 4626f1ebc29..b0b24b1de1b 100644
--- a/spec/controllers/groups_controller_spec.rb
+++ b/spec/controllers/groups_controller_spec.rb
@@ -26,7 +26,7 @@ describe GroupsController do
     end
   end
 
-  describe 'GET #subgroups' do
+  describe 'GET #subgroups', :nested_groups do
     let!(:public_subgroup) { create(:group, :public, parent: group) }
     let!(:private_subgroup) { create(:group, :private, parent: group) }
 
diff --git a/spec/controllers/projects/merge_requests_controller_spec.rb b/spec/controllers/projects/merge_requests_controller_spec.rb
index 587a5820c6f..08024a2148b 100644
--- a/spec/controllers/projects/merge_requests_controller_spec.rb
+++ b/spec/controllers/projects/merge_requests_controller_spec.rb
@@ -2,7 +2,7 @@ require 'spec_helper'
 
 describe Projects::MergeRequestsController do
   let(:project) { create(:project) }
-  let(:user)    { create(:user) }
+  let(:user)    { project.owner }
   let(:merge_request) { create(:merge_request_with_diffs, target_project: project, source_project: project) }
   let(:merge_request_with_conflicts) do
     create(:merge_request, source_branch: 'conflict-resolvable', target_branch: 'conflict-start', source_project: project) do |mr|
@@ -12,7 +12,6 @@ describe Projects::MergeRequestsController do
 
   before do
     sign_in(user)
-    project.team << [user, :master]
   end
 
   describe 'GET new' do
@@ -304,6 +303,8 @@ describe Projects::MergeRequestsController do
     end
 
     context 'when user cannot access' do
+      let(:user) { create(:user) }
+
       before do
         project.add_reporter(user)
         xhr :post, :merge, base_params
@@ -459,6 +460,8 @@ describe Projects::MergeRequestsController do
   end
 
   describe "DELETE destroy" do
+    let(:user) { create(:user) }
+
     it "denies access to users unless they're admin or project owner" do
       delete :destroy, namespace_id: project.namespace, project_id: project, id: merge_request.iid
 
diff --git a/spec/factories/projects.rb b/spec/factories/projects.rb
index 7a76f5f8afc..e8a9b688319 100644
--- a/spec/factories/projects.rb
+++ b/spec/factories/projects.rb
@@ -109,6 +109,18 @@ FactoryGirl.define do
           merge_requests_access_level: merge_requests_access_level,
           repository_access_level: evaluator.repository_access_level
         )
+
+      # Normally the class Projects::CreateService is used for creating
+      # projects, and this class takes care of making sure the owner and current
+      # user have access to the project. Our specs don't use said service class,
+      # thus we must manually refresh things here.
+      owner = project.owner
+
+      if owner && owner.is_a?(User) && !project.pending_delete
+        project.members.create!(user: owner, access_level: Gitlab::Access::MASTER)
+      end
+
+      project.group&.refresh_members_authorized_projects
     end
   end
 
diff --git a/spec/features/groups/group_name_toggle_spec.rb b/spec/features/groups/group_name_toggle_spec.rb
index 8a1d415c4f1..dfc3c84f29a 100644
--- a/spec/features/groups/group_name_toggle_spec.rb
+++ b/spec/features/groups/group_name_toggle_spec.rb
@@ -22,7 +22,7 @@ feature 'Group name toggle', feature: true, js: true do
     expect(page).not_to have_css('.group-name-toggle')
   end
 
-  it 'is present if the title is longer than the container' do
+  it 'is present if the title is longer than the container', :nested_groups do
     visit group_path(nested_group_3)
     title_width = page.evaluate_script("$('.title')[0].offsetWidth")
 
@@ -35,7 +35,7 @@ feature 'Group name toggle', feature: true, js: true do
     expect(title_width).to be > container_width
   end
 
-  it 'should show the full group namespace when toggled' do
+  it 'should show the full group namespace when toggled', :nested_groups do
     page_height = page.current_window.size[1]
     page.current_window.resize_to(SMALL_SCREEN, page_height)
     visit group_path(nested_group_3)
diff --git a/spec/features/groups/members/list_spec.rb b/spec/features/groups/members/list_spec.rb
index 543879bd21d..f654fa16a06 100644
--- a/spec/features/groups/members/list_spec.rb
+++ b/spec/features/groups/members/list_spec.rb
@@ -12,7 +12,7 @@ feature 'Groups members list', feature: true do
     login_as(user1)
   end
 
-  scenario 'show members from current group and parent' do
+  scenario 'show members from current group and parent', :nested_groups do
     group.add_developer(user1)
     nested_group.add_developer(user2)
 
@@ -22,7 +22,7 @@ feature 'Groups members list', feature: true do
     expect(second_row.text).to include(user2.name)
   end
 
-  scenario 'show user once if member of both current group and parent' do
+  scenario 'show user once if member of both current group and parent', :nested_groups do
     group.add_developer(user1)
     nested_group.add_developer(user1)
 
diff --git a/spec/features/groups_spec.rb b/spec/features/groups_spec.rb
index 3d32c47bf09..24ea7aba0cc 100644
--- a/spec/features/groups_spec.rb
+++ b/spec/features/groups_spec.rb
@@ -83,7 +83,7 @@ feature 'Group', feature: true do
     end
   end
 
-  describe 'create a nested group', js: true do
+  describe 'create a nested group', :nested_groups, js: true do
     let(:group) { create(:group, path: 'foo') }
 
     context 'as admin' do
@@ -196,7 +196,7 @@ feature 'Group', feature: true do
     end
   end
 
-  describe 'group page with nested groups', js: true do
+  describe 'group page with nested groups', :nested_groups, js: true do
     let!(:group) { create(:group) }
     let!(:nested_group) { create(:group, parent: group) }
     let!(:path)  { group_path(group) }
diff --git a/spec/features/issues/filtered_search/dropdown_assignee_spec.rb b/spec/features/issues/filtered_search/dropdown_assignee_spec.rb
index 0b573d7cef4..4d38df05928 100644
--- a/spec/features/issues/filtered_search/dropdown_assignee_spec.rb
+++ b/spec/features/issues/filtered_search/dropdown_assignee_spec.rb
@@ -58,7 +58,7 @@ describe 'Dropdown assignee', :feature, :js do
     it 'should load all the assignees when opened' do
       filtered_search.set('assignee:')
 
-      expect(dropdown_assignee_size).to eq(3)
+      expect(dropdown_assignee_size).to eq(4)
     end
 
     it 'shows current user at top of dropdown' do
diff --git a/spec/features/issues/filtered_search/dropdown_author_spec.rb b/spec/features/issues/filtered_search/dropdown_author_spec.rb
index b29177bed06..358b244fb5b 100644
--- a/spec/features/issues/filtered_search/dropdown_author_spec.rb
+++ b/spec/features/issues/filtered_search/dropdown_author_spec.rb
@@ -65,7 +65,7 @@ describe 'Dropdown author', js: true, feature: true do
     it 'should load all the authors when opened' do
       send_keys_to_filtered_search('author:')
 
-      expect(dropdown_author_size).to eq(3)
+      expect(dropdown_author_size).to eq(4)
     end
 
     it 'shows current user at top of dropdown' do
diff --git a/spec/features/projects/group_links_spec.rb b/spec/features/projects/group_links_spec.rb
index c969acc9140..4e5682c8636 100644
--- a/spec/features/projects/group_links_spec.rb
+++ b/spec/features/projects/group_links_spec.rb
@@ -40,7 +40,7 @@ feature 'Project group links', :feature, :js do
       another_group.add_master(master)
     end
 
-    it 'does not show ancestors' do
+    it 'does not show ancestors', :nested_groups do
       visit namespace_project_settings_members_path(project.namespace, project)
 
       click_link 'Search for a group'
diff --git a/spec/features/projects/members/sorting_spec.rb b/spec/features/projects/members/sorting_spec.rb
index b7ae5f0b925..d428f6fcf22 100644
--- a/spec/features/projects/members/sorting_spec.rb
+++ b/spec/features/projects/members/sorting_spec.rb
@@ -3,10 +3,9 @@ require 'spec_helper'
 feature 'Projects > Members > Sorting', feature: true do
   let(:master)    { create(:user, name: 'John Doe') }
   let(:developer) { create(:user, name: 'Mary Jane', last_sign_in_at: 5.days.ago) }
-  let(:project)   { create(:empty_project) }
+  let(:project)   { create(:empty_project, namespace: master.namespace, creator: master) }
 
   background do
-    create(:project_member, :master, user: master, project: project, created_at: 5.days.ago)
     create(:project_member, :developer, user: developer, project: project, created_at: 3.days.ago)
 
     login_as(master)
@@ -39,16 +38,16 @@ feature 'Projects > Members > Sorting', feature: true do
   scenario 'sorts by last joined' do
     visit_members_list(sort: :last_joined)
 
-    expect(first_member).to include(developer.name)
-    expect(second_member).to include(master.name)
+    expect(first_member).to include(master.name)
+    expect(second_member).to include(developer.name)
     expect(page).to have_css('.member-sort-dropdown .dropdown-toggle-text', text: 'Last joined')
   end
 
   scenario 'sorts by oldest joined' do
     visit_members_list(sort: :oldest_joined)
 
-    expect(first_member).to include(master.name)
-    expect(second_member).to include(developer.name)
+    expect(first_member).to include(developer.name)
+    expect(second_member).to include(master.name)
     expect(page).to have_css('.member-sort-dropdown .dropdown-toggle-text', text: 'Oldest joined')
   end
 
diff --git a/spec/features/projects/members/user_requests_access_spec.rb b/spec/features/projects/members/user_requests_access_spec.rb
index 1bf8f710b9f..ec48a4bd726 100644
--- a/spec/features/projects/members/user_requests_access_spec.rb
+++ b/spec/features/projects/members/user_requests_access_spec.rb
@@ -2,11 +2,10 @@ require 'spec_helper'
 
 feature 'Projects > Members > User requests access', feature: true do
   let(:user) { create(:user) }
-  let(:master) { create(:user) }
   let(:project) { create(:project, :public, :access_requestable) }
+  let(:master) { project.owner }
 
   background do
-    project.team << [master, :master]
     login_as(user)
     visit namespace_project_path(project.namespace, project)
   end
diff --git a/spec/finders/group_members_finder_spec.rb b/spec/finders/group_members_finder_spec.rb
index b762756f9ce..db3fcc23475 100644
--- a/spec/finders/group_members_finder_spec.rb
+++ b/spec/finders/group_members_finder_spec.rb
@@ -18,7 +18,7 @@ describe GroupMembersFinder, '#execute' do
     expect(result.to_a).to eq([member3, member2, member1])
   end
 
-  it 'returns members for nested group' do
+  it 'returns members for nested group', :nested_groups do
     group.add_master(user2)
     nested_group.request_access(user4)
     member1 = group.add_master(user1)
diff --git a/spec/finders/members_finder_spec.rb b/spec/finders/members_finder_spec.rb
index cf691cf684b..300ba8422e8 100644
--- a/spec/finders/members_finder_spec.rb
+++ b/spec/finders/members_finder_spec.rb
@@ -9,7 +9,7 @@ describe MembersFinder, '#execute' do
   let(:user3)        { create(:user) }
   let(:user4)        { create(:user) }
 
-  it 'returns members for project and parent groups' do
+  it 'returns members for project and parent groups', :nested_groups do
     nested_group.request_access(user1)
     member1 = group.add_master(user2)
     member2 = nested_group.add_master(user3)
diff --git a/spec/lib/gitlab/cache/ci/project_pipeline_status_spec.rb b/spec/lib/gitlab/cache/ci/project_pipeline_status_spec.rb
index b386852b196..cfb5cba054e 100644
--- a/spec/lib/gitlab/cache/ci/project_pipeline_status_spec.rb
+++ b/spec/lib/gitlab/cache/ci/project_pipeline_status_spec.rb
@@ -1,7 +1,7 @@
 require 'spec_helper'
 
 describe Gitlab::Cache::Ci::ProjectPipelineStatus, :redis do
-  let(:project) { create(:project) }
+  let!(:project) { create(:project) }
   let(:pipeline_status) { described_class.new(project) }
   let(:cache_key) { "projects/#{project.id}/pipeline_status" }
 
@@ -18,7 +18,7 @@ describe Gitlab::Cache::Ci::ProjectPipelineStatus, :redis do
     let(:sha) { '424d1b73bc0d3cb726eb7dc4ce17a4d48552f8c6' }
     let(:ref) { 'master' }
     let(:pipeline_info) { { sha: sha, status: status, ref: ref } }
-    let(:project_without_status) { create(:project) }
+    let!(:project_without_status) { create(:project) }
 
     describe '.load_in_batch_for_projects' do
       it 'preloads pipeline_status on projects' do
diff --git a/spec/lib/gitlab/group_hierarchy_spec.rb b/spec/lib/gitlab/group_hierarchy_spec.rb
new file mode 100644
index 00000000000..5d0ed1522b3
--- /dev/null
+++ b/spec/lib/gitlab/group_hierarchy_spec.rb
@@ -0,0 +1,53 @@
+require 'spec_helper'
+
+describe Gitlab::GroupHierarchy, :postgresql do
+  let!(:parent) { create(:group) }
+  let!(:child1) { create(:group, parent: parent) }
+  let!(:child2) { create(:group, parent: child1) }
+
+  describe '#base_and_ancestors' do
+    let(:relation) do
+      described_class.new(Group.where(id: child2.id)).base_and_ancestors
+    end
+
+    it 'includes the base rows' do
+      expect(relation).to include(child2)
+    end
+
+    it 'includes all of the ancestors' do
+      expect(relation).to include(parent, child1)
+    end
+  end
+
+  describe '#base_and_descendants' do
+    let(:relation) do
+      described_class.new(Group.where(id: parent.id)).base_and_descendants
+    end
+
+    it 'includes the base rows' do
+      expect(relation).to include(parent)
+    end
+
+    it 'includes all the descendants' do
+      expect(relation).to include(child1, child2)
+    end
+  end
+
+  describe '#all_groups' do
+    let(:relation) do
+      described_class.new(Group.where(id: child1.id)).all_groups
+    end
+
+    it 'includes the base rows' do
+      expect(relation).to include(child1)
+    end
+
+    it 'includes the ancestors' do
+      expect(relation).to include(parent)
+    end
+
+    it 'includes the descendants' do
+      expect(relation).to include(child2)
+    end
+  end
+end
diff --git a/spec/lib/gitlab/import_export/members_mapper_spec.rb b/spec/lib/gitlab/import_export/members_mapper_spec.rb
index b9d4e59e770..3e0291c9ae9 100644
--- a/spec/lib/gitlab/import_export/members_mapper_spec.rb
+++ b/spec/lib/gitlab/import_export/members_mapper_spec.rb
@@ -2,9 +2,9 @@ require 'spec_helper'
 
 describe Gitlab::ImportExport::MembersMapper, services: true do
   describe 'map members' do
-    let(:user) { create(:admin, authorized_projects_populated: true) }
+    let(:user) { create(:admin) }
     let(:project) { create(:empty_project, :public, name: 'searchable_project') }
-    let(:user2) { create(:user, authorized_projects_populated: true) }
+    let(:user2) { create(:user) }
     let(:exported_user_id) { 99 }
     let(:exported_members) do
       [{
@@ -74,7 +74,7 @@ describe Gitlab::ImportExport::MembersMapper, services: true do
     end
 
     context 'user is not an admin' do
-      let(:user) { create(:user, authorized_projects_populated: true) }
+      let(:user) { create(:user) }
 
       it 'does not map a project member' do
         expect(members_mapper.map[exported_user_id]).to eq(user.id)
@@ -94,7 +94,7 @@ describe Gitlab::ImportExport::MembersMapper, services: true do
     end
 
     context 'importer same as group member' do
-      let(:user2) { create(:admin, authorized_projects_populated: true) }
+      let(:user2) { create(:admin) }
       let(:group) { create(:group) }
       let(:project) { create(:empty_project, :public, name: 'searchable_project', namespace: group) }
       let(:members_mapper) do
diff --git a/spec/lib/gitlab/project_authorizations_spec.rb b/spec/lib/gitlab/project_authorizations_spec.rb
new file mode 100644
index 00000000000..67321f43710
--- /dev/null
+++ b/spec/lib/gitlab/project_authorizations_spec.rb
@@ -0,0 +1,73 @@
+require 'spec_helper'
+
+describe Gitlab::ProjectAuthorizations do
+  let(:group) { create(:group) }
+  let!(:owned_project) { create(:empty_project) }
+  let!(:other_project) { create(:empty_project) }
+  let!(:group_project) { create(:empty_project, namespace: group) }
+
+  let(:user) { owned_project.namespace.owner }
+
+  def map_access_levels(rows)
+    rows.each_with_object({}) do |row, hash|
+      hash[row.project_id] = row.access_level
+    end
+  end
+
+  before do
+    other_project.team << [user, :reporter]
+    group.add_developer(user)
+  end
+
+  let(:authorizations) do
+    klass = if Group.supports_nested_groups?
+              Gitlab::ProjectAuthorizations::WithNestedGroups
+            else
+              Gitlab::ProjectAuthorizations::WithoutNestedGroups
+            end
+
+    klass.new(user).calculate
+  end
+
+  it 'returns the correct number of authorizations' do
+    expect(authorizations.length).to eq(3)
+  end
+
+  it 'includes the correct projects' do
+    expect(authorizations.pluck(:project_id)).
+      to include(owned_project.id, other_project.id, group_project.id)
+  end
+
+  it 'includes the correct access levels' do
+    mapping = map_access_levels(authorizations)
+
+    expect(mapping[owned_project.id]).to eq(Gitlab::Access::MASTER)
+    expect(mapping[other_project.id]).to eq(Gitlab::Access::REPORTER)
+    expect(mapping[group_project.id]).to eq(Gitlab::Access::DEVELOPER)
+  end
+
+  if Group.supports_nested_groups?
+    context 'with nested groups' do
+      let!(:nested_group) { create(:group, parent: group) }
+      let!(:nested_project) { create(:empty_project, namespace: nested_group) }
+
+      it 'includes nested groups' do
+        expect(authorizations.pluck(:project_id)).to include(nested_project.id)
+      end
+
+      it 'inherits access levels when the user is not a member of a nested group' do
+        mapping = map_access_levels(authorizations)
+
+        expect(mapping[nested_project.id]).to eq(Gitlab::Access::DEVELOPER)
+      end
+
+      it 'uses the greatest access level when a user is a member of a nested group' do
+        nested_group.add_master(user)
+
+        mapping = map_access_levels(authorizations)
+
+        expect(mapping[nested_project.id]).to eq(Gitlab::Access::MASTER)
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/sql/recursive_cte_spec.rb b/spec/lib/gitlab/sql/recursive_cte_spec.rb
new file mode 100644
index 00000000000..25146860615
--- /dev/null
+++ b/spec/lib/gitlab/sql/recursive_cte_spec.rb
@@ -0,0 +1,49 @@
+require 'spec_helper'
+
+describe Gitlab::SQL::RecursiveCTE, :postgresql do
+  let(:cte) { described_class.new(:cte_name) }
+
+  describe '#to_arel' do
+    it 'generates an Arel relation for the CTE body' do
+      rel1 = User.where(id: 1)
+      rel2 = User.where(id: 2)
+
+      cte << rel1
+      cte << rel2
+
+      sql = cte.to_arel.to_sql
+      name = ActiveRecord::Base.connection.quote_table_name(:cte_name)
+
+      sql1, sql2 = ActiveRecord::Base.connection.unprepared_statement do
+        [rel1.except(:order).to_sql, rel2.except(:order).to_sql]
+      end
+
+      expect(sql).to eq("#{name} AS (#{sql1}\nUNION\n#{sql2})")
+    end
+  end
+
+  describe '#alias_to' do
+    it 'returns an alias for the CTE' do
+      table = Arel::Table.new(:kittens)
+
+      source_name = ActiveRecord::Base.connection.quote_table_name(:cte_name)
+      alias_name = ActiveRecord::Base.connection.quote_table_name(:kittens)
+
+      expect(cte.alias_to(table).to_sql).to eq("#{source_name} AS #{alias_name}")
+    end
+  end
+
+  describe '#apply_to' do
+    it 'applies a CTE to an ActiveRecord::Relation' do
+      user = create(:user)
+      cte = described_class.new(:cte_name)
+
+      cte << User.where(id: user.id)
+
+      relation = cte.apply_to(User.all)
+
+      expect(relation.to_sql).to match(/WITH RECURSIVE.+cte_name/)
+      expect(relation.to_a).to eq(User.where(id: user.id).to_a)
+    end
+  end
+end
diff --git a/spec/migrations/fill_authorized_projects_spec.rb b/spec/migrations/fill_authorized_projects_spec.rb
deleted file mode 100644
index 99dc4195818..00000000000
--- a/spec/migrations/fill_authorized_projects_spec.rb
+++ /dev/null
@@ -1,18 +0,0 @@
-require 'spec_helper'
-require Rails.root.join('db', 'post_migrate', '20170106142508_fill_authorized_projects.rb')
-
-describe FillAuthorizedProjects do
-  describe '#up' do
-    it 'schedules the jobs in batches' do
-      user1 = create(:user)
-      user2 = create(:user)
-
-      expect(Sidekiq::Client).to receive(:push_bulk).with(
-        'class' => 'AuthorizedProjectsWorker',
-        'args'  => [[user1.id], [user2.id]]
-      )
-
-      described_class.new.up
-    end
-  end
-end
diff --git a/spec/migrations/turn_nested_groups_into_regular_groups_for_mysql_spec.rb b/spec/migrations/turn_nested_groups_into_regular_groups_for_mysql_spec.rb
new file mode 100644
index 00000000000..175bf1876b2
--- /dev/null
+++ b/spec/migrations/turn_nested_groups_into_regular_groups_for_mysql_spec.rb
@@ -0,0 +1,66 @@
+require 'spec_helper'
+require Rails.root.join('db', 'migrate', '20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb')
+
+describe TurnNestedGroupsIntoRegularGroupsForMysql do
+  let!(:parent_group) { create(:group) }
+  let!(:child_group) { create(:group, parent: parent_group) }
+  let!(:project) { create(:project, :empty_repo, namespace: child_group) }
+  let!(:member) { create(:user) }
+  let(:migration) { described_class.new }
+
+  before do
+    parent_group.add_developer(member)
+
+    allow(migration).to receive(:run_migration?).and_return(true)
+    allow(migration).to receive(:verbose).and_return(false)
+  end
+
+  describe '#up' do
+    let(:updated_project) do
+      # path_with_namespace is memoized in an instance variable so we retrieve a
+      # new row here to work around that.
+      Project.find(project.id)
+    end
+
+    before do
+      migration.up
+    end
+
+    it 'unsets the parent_id column' do
+      expect(Namespace.where('parent_id IS NOT NULL').any?).to eq(false)
+    end
+
+    it 'adds members of parent groups as members to the migrated group' do
+      is_member = child_group.members.
+        where(user_id: member, access_level: Gitlab::Access::DEVELOPER).any?
+
+      expect(is_member).to eq(true)
+    end
+
+    it 'update the path of the nested group' do
+      child_group.reload
+
+      expect(child_group.path).to eq("#{parent_group.name}-#{child_group.name}")
+    end
+
+    it 'renames projects of the nested group' do
+      expect(updated_project.path_with_namespace).
+        to eq("#{parent_group.name}-#{child_group.name}/#{updated_project.path}")
+    end
+
+    it 'renames the repository of any projects' do
+      expect(updated_project.repository.path).
+        to end_with("#{parent_group.name}-#{child_group.name}/#{updated_project.path}.git")
+
+      expect(File.directory?(updated_project.repository.path)).to eq(true)
+    end
+
+    it 'creates a redirect route for renamed projects' do
+      exists = RedirectRoute.
+        where(source_type: 'Project', source_id: project.id).
+        any?
+
+      expect(exists).to eq(true)
+    end
+  end
+end
diff --git a/spec/models/concerns/routable_spec.rb b/spec/models/concerns/routable_spec.rb
index 49a4132f763..0e10d91836d 100644
--- a/spec/models/concerns/routable_spec.rb
+++ b/spec/models/concerns/routable_spec.rb
@@ -115,123 +115,6 @@ describe Group, 'Routable' do
     end
   end
 
-  describe '.member_descendants' do
-    let!(:user) { create(:user) }
-    let!(:nested_group) { create(:group, parent: group) }
-
-    before { group.add_owner(user) }
-    subject { described_class.member_descendants(user.id) }
-
-    it { is_expected.to eq([nested_group]) }
-  end
-
-  describe '.member_self_and_descendants' do
-    let!(:user) { create(:user) }
-    let!(:nested_group) { create(:group, parent: group) }
-
-    before { group.add_owner(user) }
-    subject { described_class.member_self_and_descendants(user.id) }
-
-    it { is_expected.to match_array [group, nested_group] }
-  end
-
-  describe '.member_hierarchy' do
-    # foo/bar would also match foo/barbaz instead of just foo/bar and foo/bar/baz
-    let!(:user) { create(:user) }
-
-    #                group
-    #        _______ (foo) _______
-    #       |                     |
-    #       |                     |
-    # nested_group_1        nested_group_2
-    # (bar)                 (barbaz)
-    #       |                     |
-    #       |                     |
-    # nested_group_1_1      nested_group_2_1
-    # (baz)                 (baz)
-    #
-    let!(:nested_group_1) { create :group, parent: group, name: 'bar' }
-    let!(:nested_group_1_1) { create :group, parent: nested_group_1, name: 'baz' }
-    let!(:nested_group_2) { create :group, parent: group, name: 'barbaz' }
-    let!(:nested_group_2_1) { create :group, parent: nested_group_2, name: 'baz' }
-
-    context 'user is not a member of any group' do
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns an empty array' do
-        is_expected.to eq []
-      end
-    end
-
-    context 'user is member of all groups' do
-      before do
-        group.add_owner(user)
-        nested_group_1.add_owner(user)
-        nested_group_1_1.add_owner(user)
-        nested_group_2.add_owner(user)
-        nested_group_2_1.add_owner(user)
-      end
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns all groups' do
-        is_expected.to match_array [
-          group,
-          nested_group_1, nested_group_1_1,
-          nested_group_2, nested_group_2_1
-        ]
-      end
-    end
-
-    context 'user is member of the top group' do
-      before { group.add_owner(user) }
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns all groups' do
-        is_expected.to match_array [
-          group,
-          nested_group_1, nested_group_1_1,
-          nested_group_2, nested_group_2_1
-        ]
-      end
-    end
-
-    context 'user is member of the first child (internal node), branch 1' do
-      before { nested_group_1.add_owner(user) }
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns the groups in the hierarchy' do
-        is_expected.to match_array [
-          group,
-          nested_group_1, nested_group_1_1
-        ]
-      end
-    end
-
-    context 'user is member of the first child (internal node), branch 2' do
-      before { nested_group_2.add_owner(user) }
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns the groups in the hierarchy' do
-        is_expected.to match_array [
-          group,
-          nested_group_2, nested_group_2_1
-        ]
-      end
-    end
-
-    context 'user is member of the last child (leaf node)' do
-      before { nested_group_1_1.add_owner(user) }
-      subject { described_class.member_hierarchy(user.id) }
-
-      it 'returns the groups in the hierarchy' do
-        is_expected.to match_array [
-          group,
-          nested_group_1, nested_group_1_1
-        ]
-      end
-    end
-  end
-
   describe '#full_path' do
     let(:group) { create(:group) }
     let(:nested_group) { create(:group, parent: group) }
diff --git a/spec/models/group_spec.rb b/spec/models/group_spec.rb
index 6ca1eb0374d..316bf153660 100644
--- a/spec/models/group_spec.rb
+++ b/spec/models/group_spec.rb
@@ -340,7 +340,7 @@ describe Group, models: true do
     it { expect(subject.parent).to be_kind_of(Group) }
   end
 
-  describe '#members_with_parents' do
+  describe '#members_with_parents', :nested_groups do
     let!(:group) { create(:group, :nested) }
     let!(:master) { group.parent.add_user(create(:user), GroupMember::MASTER) }
     let!(:developer) { group.add_user(create(:user), GroupMember::DEVELOPER) }
diff --git a/spec/models/members/project_member_spec.rb b/spec/models/members/project_member_spec.rb
index 87ea2e70680..cf9c701e8c5 100644
--- a/spec/models/members/project_member_spec.rb
+++ b/spec/models/members/project_member_spec.rb
@@ -22,16 +22,15 @@ describe ProjectMember, models: true do
   end
 
   describe '.add_user' do
-    context 'when called with the project owner' do
-      it 'adds the user as a member' do
-        project = create(:empty_project)
+    it 'adds the user as a member' do
+      user = create(:user)
+      project = create(:empty_project)
 
-        expect(project.users).not_to include(project.owner)
+      expect(project.users).not_to include(user)
 
-        described_class.add_user(project, project.owner, :master, current_user: project.owner)
+      described_class.add_user(project, user, :master, current_user: project.owner)
 
-        expect(project.users.reload).to include(project.owner)
-      end
+      expect(project.users.reload).to include(user)
     end
   end
 
diff --git a/spec/models/namespace_spec.rb b/spec/models/namespace_spec.rb
index ff5e7c350aa..0e74f1ab1bd 100644
--- a/spec/models/namespace_spec.rb
+++ b/spec/models/namespace_spec.rb
@@ -287,21 +287,21 @@ describe Namespace, models: true do
     end
   end
 
-  describe '#ancestors' do
+  describe '#ancestors', :nested_groups do
     let(:group) { create(:group) }
     let(:nested_group) { create(:group, parent: group) }
     let(:deep_nested_group) { create(:group, parent: nested_group) }
     let(:very_deep_nested_group) { create(:group, parent: deep_nested_group) }
 
     it 'returns the correct ancestors' do
-      expect(very_deep_nested_group.ancestors).to eq([group, nested_group, deep_nested_group])
-      expect(deep_nested_group.ancestors).to eq([group, nested_group])
-      expect(nested_group.ancestors).to eq([group])
+      expect(very_deep_nested_group.ancestors).to include(group, nested_group, deep_nested_group)
+      expect(deep_nested_group.ancestors).to include(group, nested_group)
+      expect(nested_group.ancestors).to include(group)
       expect(group.ancestors).to eq([])
     end
   end
 
-  describe '#descendants' do
+  describe '#descendants', :nested_groups do
     let!(:group) { create(:group, path: 'git_lab') }
     let!(:nested_group) { create(:group, parent: group) }
     let!(:deep_nested_group) { create(:group, parent: nested_group) }
@@ -311,9 +311,9 @@ describe Namespace, models: true do
 
     it 'returns the correct descendants' do
       expect(very_deep_nested_group.descendants.to_a).to eq([])
-      expect(deep_nested_group.descendants.to_a).to eq([very_deep_nested_group])
-      expect(nested_group.descendants.to_a).to eq([deep_nested_group, very_deep_nested_group])
-      expect(group.descendants.to_a).to eq([nested_group, deep_nested_group, very_deep_nested_group])
+      expect(deep_nested_group.descendants.to_a).to include(very_deep_nested_group)
+      expect(nested_group.descendants.to_a).to include(deep_nested_group, very_deep_nested_group)
+      expect(group.descendants.to_a).to include(nested_group, deep_nested_group, very_deep_nested_group)
     end
   end
 
diff --git a/spec/models/project_group_link_spec.rb b/spec/models/project_group_link_spec.rb
index 9b711bfc007..4161b9158b1 100644
--- a/spec/models/project_group_link_spec.rb
+++ b/spec/models/project_group_link_spec.rb
@@ -23,7 +23,7 @@ describe ProjectGroupLink do
       expect(project_group_link).not_to be_valid
     end
 
-    it "doesn't allow a project to be shared with an ancestor of the group it is in" do
+    it "doesn't allow a project to be shared with an ancestor of the group it is in", :nested_groups do
       project_group_link.group = parent_group
 
       expect(project_group_link).not_to be_valid
diff --git a/spec/models/project_team_spec.rb b/spec/models/project_team_spec.rb
index 942eeab251d..fb2d5f60009 100644
--- a/spec/models/project_team_spec.rb
+++ b/spec/models/project_team_spec.rb
@@ -81,7 +81,7 @@ describe ProjectTeam, models: true do
         user = create(:user)
         project.add_guest(user)
 
-        expect(project.team.members).to contain_exactly(user)
+        expect(project.team.members).to contain_exactly(user, project.owner)
       end
 
       it 'returns project members of a specified level' do
@@ -100,7 +100,8 @@ describe ProjectTeam, models: true do
           group_access: Gitlab::Access::GUEST
         )
 
-        expect(project.team.members).to contain_exactly(group_member.user)
+        expect(project.team.members).
+          to contain_exactly(group_member.user, project.owner)
       end
 
       it 'returns invited members of a group of a specified level' do
@@ -137,7 +138,10 @@ describe ProjectTeam, models: true do
 
   describe '#find_member' do
     context 'personal project' do
-      let(:project) { create(:empty_project, :public, :access_requestable) }
+      let(:project) do
+        create(:empty_project, :public, :access_requestable)
+      end
+
       let(:requester) { create(:user) }
 
       before do
@@ -200,7 +204,9 @@ describe ProjectTeam, models: true do
     let(:requester) { create(:user) }
 
     context 'personal project' do
-      let(:project) { create(:empty_project, :public, :access_requestable) }
+      let(:project) do
+        create(:empty_project, :public, :access_requestable)
+      end
 
       context 'when project is not shared with group' do
         before do
@@ -244,7 +250,9 @@ describe ProjectTeam, models: true do
 
     context 'group project' do
       let(:group) { create(:group, :access_requestable) }
-      let!(:project) { create(:empty_project, group: group) }
+      let!(:project) do
+        create(:empty_project, group: group)
+      end
 
       before do
         group.add_master(master)
@@ -265,8 +273,15 @@ describe ProjectTeam, models: true do
     let(:group) { create(:group) }
     let(:developer) { create(:user) }
     let(:master) { create(:user) }
-    let(:personal_project) { create(:empty_project, namespace: developer.namespace) }
-    let(:group_project) { create(:empty_project, namespace: group) }
+
+    let(:personal_project) do
+      create(:empty_project, namespace: developer.namespace)
+    end
+
+    let(:group_project) do
+      create(:empty_project, namespace: group)
+    end
+
     let(:members_project) { create(:empty_project) }
     let(:shared_project) { create(:empty_project) }
 
diff --git a/spec/models/user_spec.rb b/spec/models/user_spec.rb
index aabdac4bb75..9edf34b05ad 100644
--- a/spec/models/user_spec.rb
+++ b/spec/models/user_spec.rb
@@ -627,16 +627,6 @@ describe User, models: true do
     it { expect(User.without_projects).to include user_without_project2 }
   end
 
-  describe '.not_in_project' do
-    before do
-      User.delete_all
-      @user = create :user
-      @project = create(:empty_project)
-    end
-
-    it { expect(User.not_in_project(@project)).to include(@user, @project.owner) }
-  end
-
   describe 'user creation' do
     describe 'normal user' do
       let(:user) { create(:user, name: 'John Smith') }
@@ -1561,48 +1551,103 @@ describe User, models: true do
     end
   end
 
-  describe '#nested_groups' do
+  describe '#all_expanded_groups' do
+    # foo/bar would also match foo/barbaz instead of just foo/bar and foo/bar/baz
     let!(:user) { create(:user) }
-    let!(:group) { create(:group) }
-    let!(:nested_group) { create(:group, parent: group) }
 
-    before do
-      group.add_owner(user)
+    #                group
+    #        _______ (foo) _______
+    #       |                     |
+    #       |                     |
+    # nested_group_1        nested_group_2
+    # (bar)                 (barbaz)
+    #       |                     |
+    #       |                     |
+    # nested_group_1_1      nested_group_2_1
+    # (baz)                 (baz)
+    #
+    let!(:group) { create :group }
+    let!(:nested_group_1) { create :group, parent: group, name: 'bar' }
+    let!(:nested_group_1_1) { create :group, parent: nested_group_1, name: 'baz' }
+    let!(:nested_group_2) { create :group, parent: group, name: 'barbaz' }
+    let!(:nested_group_2_1) { create :group, parent: nested_group_2, name: 'baz' }
 
-      # Add more data to ensure method does not include wrong groups
-      create(:group).add_owner(create(:user))
+    subject { user.all_expanded_groups }
+
+    context 'user is not a member of any group' do
+      it 'returns an empty array' do
+        is_expected.to eq([])
+      end
     end
 
-    it { expect(user.nested_groups).to eq([nested_group]) }
-  end
+    context 'user is member of all groups' do
+      before do
+        group.add_owner(user)
+        nested_group_1.add_owner(user)
+        nested_group_1_1.add_owner(user)
+        nested_group_2.add_owner(user)
+        nested_group_2_1.add_owner(user)
+      end
 
-  describe '#all_expanded_groups' do
-    let!(:user) { create(:user) }
-    let!(:group) { create(:group) }
-    let!(:nested_group_1) { create(:group, parent: group) }
-    let!(:nested_group_2) { create(:group, parent: group) }
+      it 'returns all groups' do
+        is_expected.to match_array [
+          group,
+          nested_group_1, nested_group_1_1,
+          nested_group_2, nested_group_2_1
+        ]
+      end
+    end
 
-    before { nested_group_1.add_owner(user) }
+    context 'user is member of the top group' do
+      before { group.add_owner(user) }
 
-    it { expect(user.all_expanded_groups).to match_array [group, nested_group_1] }
-  end
+      if Group.supports_nested_groups?
+        it 'returns all groups' do
+          is_expected.to match_array [
+            group,
+            nested_group_1, nested_group_1_1,
+            nested_group_2, nested_group_2_1
+          ]
+        end
+      else
+        it 'returns the top-level groups' do
+          is_expected.to match_array [group]
+        end
+      end
+    end
 
-  describe '#nested_groups_projects' do
-    let!(:user) { create(:user) }
-    let!(:group) { create(:group) }
-    let!(:nested_group) { create(:group, parent: group) }
-    let!(:project) { create(:empty_project, namespace: group) }
-    let!(:nested_project) { create(:empty_project, namespace: nested_group) }
+    context 'user is member of the first child (internal node), branch 1', :nested_groups do
+      before { nested_group_1.add_owner(user) }
 
-    before do
-      group.add_owner(user)
+      it 'returns the groups in the hierarchy' do
+        is_expected.to match_array [
+          group,
+          nested_group_1, nested_group_1_1
+        ]
+      end
+    end
+
+    context 'user is member of the first child (internal node), branch 2', :nested_groups do
+      before { nested_group_2.add_owner(user) }
 
-      # Add more data to ensure method does not include wrong projects
-      other_project = create(:empty_project, namespace: create(:group, :nested))
-      other_project.add_developer(create(:user))
+      it 'returns the groups in the hierarchy' do
+        is_expected.to match_array [
+          group,
+          nested_group_2, nested_group_2_1
+        ]
+      end
     end
 
-    it { expect(user.nested_groups_projects).to eq([nested_project]) }
+    context 'user is member of the last child (leaf node)', :nested_groups do
+      before { nested_group_1_1.add_owner(user) }
+
+      it 'returns the groups in the hierarchy' do
+        is_expected.to match_array [
+          group,
+          nested_group_1, nested_group_1_1
+        ]
+      end
+    end
   end
 
   describe '#refresh_authorized_projects', redis: true do
@@ -1622,10 +1667,6 @@ describe User, models: true do
       expect(user.project_authorizations.count).to eq(2)
     end
 
-    it 'sets the authorized_projects_populated column' do
-      expect(user.authorized_projects_populated).to eq(true)
-    end
-
     it 'stores the correct access levels' do
       expect(user.project_authorizations.where(access_level: Gitlab::Access::GUEST).exists?).to eq(true)
       expect(user.project_authorizations.where(access_level: Gitlab::Access::REPORTER).exists?).to eq(true)
@@ -1735,7 +1776,7 @@ describe User, models: true do
       end
     end
 
-    context 'with 2FA requirement on nested parent group' do
+    context 'with 2FA requirement on nested parent group', :nested_groups do
       let!(:group1) { create :group, require_two_factor_authentication: true }
       let!(:group1a) { create :group, require_two_factor_authentication: false, parent: group1 }
 
@@ -1750,7 +1791,7 @@ describe User, models: true do
       end
     end
 
-    context 'with 2FA requirement on nested child group' do
+    context 'with 2FA requirement on nested child group', :nested_groups do
       let!(:group1) { create :group, require_two_factor_authentication: false }
       let!(:group1a) { create :group, require_two_factor_authentication: true, parent: group1 }
 
diff --git a/spec/policies/group_policy_spec.rb b/spec/policies/group_policy_spec.rb
index 2077c14ff7a..4c37a553227 100644
--- a/spec/policies/group_policy_spec.rb
+++ b/spec/policies/group_policy_spec.rb
@@ -107,7 +107,7 @@ describe GroupPolicy, models: true do
     end
   end
 
-  describe 'private nested group inherit permissions' do
+  describe 'private nested group inherit permissions', :nested_groups do
     let(:nested_group) { create(:group, :private, parent: group) }
 
     subject { described_class.abilities(current_user, nested_group).to_set }
diff --git a/spec/requests/api/commits_spec.rb b/spec/requests/api/commits_spec.rb
index 0b0e4c2b112..b84361d3abd 100644
--- a/spec/requests/api/commits_spec.rb
+++ b/spec/requests/api/commits_spec.rb
@@ -5,7 +5,6 @@ describe API::Commits do
   let(:user) { create(:user) }
   let(:user2) { create(:user) }
   let!(:project) { create(:project, :repository, creator: user, namespace: user.namespace) }
-  let!(:master) { create(:project_member, :master, user: user, project: project) }
   let!(:guest) { create(:project_member, :guest, user: user2, project: project) }
   let!(:note) { create(:note_on_commit, author: user, project: project, commit_id: project.repository.commit.id, note: 'a comment on a commit') }
   let!(:another_note) { create(:note_on_commit, author: user, project: project, commit_id: project.repository.commit.id, note: 'another comment on a commit') }
diff --git a/spec/requests/api/groups_spec.rb b/spec/requests/api/groups_spec.rb
index 90b36374ded..bb53796cbd7 100644
--- a/spec/requests/api/groups_spec.rb
+++ b/spec/requests/api/groups_spec.rb
@@ -429,7 +429,7 @@ describe API::Groups do
         expect(json_response["request_access_enabled"]).to eq(group[:request_access_enabled])
       end
 
-      it "creates a nested group" do
+      it "creates a nested group", :nested_groups do
         parent = create(:group)
         parent.add_owner(user3)
         group = attributes_for(:group, { parent_id: parent.id })
diff --git a/spec/requests/api/projects_spec.rb b/spec/requests/api/projects_spec.rb
index d5c3b5b34ad..f95a287a184 100644
--- a/spec/requests/api/projects_spec.rb
+++ b/spec/requests/api/projects_spec.rb
@@ -11,8 +11,7 @@ describe API::Projects do
   let(:project) { create(:empty_project, creator_id: user.id, namespace: user.namespace) }
   let(:project2) { create(:empty_project, path: 'project2', creator_id: user.id, namespace: user.namespace) }
   let(:snippet) { create(:project_snippet, :public, author: user, project: project, title: 'example') }
-  let(:project_member) { create(:project_member, :master, user: user, project: project) }
-  let(:project_member2) { create(:project_member, :developer, user: user3, project: project) }
+  let(:project_member) { create(:project_member, :developer, user: user3, project: project) }
   let(:user4) { create(:user) }
   let(:project3) do
     create(:project,
@@ -27,7 +26,7 @@ describe API::Projects do
     builds_enabled: false,
     snippets_enabled: false)
   end
-  let(:project_member3) do
+  let(:project_member2) do
     create(:project_member,
     user: user4,
     project: project3,
@@ -210,7 +209,7 @@ describe API::Projects do
         let(:public_project) { create(:empty_project, :public) }
 
         before do
-          project_member2
+          project_member
           user3.update_attributes(starred_projects: [project, project2, project3, public_project])
         end
 
@@ -784,19 +783,18 @@ describe API::Projects do
   describe 'GET /projects/:id/users' do
     shared_examples_for 'project users response' do
       it 'returns the project users' do
-        member = create(:user)
-        create(:project_member, :developer, user: member, project: project)
-
         get api("/projects/#{project.id}/users", current_user)
 
+        user = project.namespace.owner
+
         expect(response).to have_http_status(200)
         expect(response).to include_pagination_headers
         expect(json_response).to be_an Array
         expect(json_response.size).to eq(1)
 
         first_user = json_response.first
-        expect(first_user['username']).to eq(member.username)
-        expect(first_user['name']).to eq(member.name)
+        expect(first_user['username']).to eq(user.username)
+        expect(first_user['name']).to eq(user.name)
         expect(first_user.keys).to contain_exactly(*%w[name username id state avatar_url web_url])
       end
     end
@@ -1091,8 +1089,8 @@ describe API::Projects do
     before { user4 }
     before { project3 }
     before { project4 }
-    before { project_member3 }
     before { project_member2 }
+    before { project_member }
 
     it 'returns 400 when nothing sent' do
       project_param = {}
@@ -1573,7 +1571,7 @@ describe API::Projects do
 
     context 'when authenticated as developer' do
       before do
-        project_member2
+        project_member
       end
 
       it 'returns forbidden error' do
diff --git a/spec/requests/api/v3/commits_spec.rb b/spec/requests/api/v3/commits_spec.rb
index c2e8c3ae6f7..386f60065ad 100644
--- a/spec/requests/api/v3/commits_spec.rb
+++ b/spec/requests/api/v3/commits_spec.rb
@@ -5,7 +5,6 @@ describe API::V3::Commits do
   let(:user) { create(:user) }
   let(:user2) { create(:user) }
   let!(:project) { create(:project, :repository, creator: user, namespace: user.namespace) }
-  let!(:master) { create(:project_member, :master, user: user, project: project) }
   let!(:guest) { create(:project_member, :guest, user: user2, project: project) }
   let!(:note) { create(:note_on_commit, author: user, project: project, commit_id: project.repository.commit.id, note: 'a comment on a commit') }
   let!(:another_note) { create(:note_on_commit, author: user, project: project, commit_id: project.repository.commit.id, note: 'another comment on a commit') }
diff --git a/spec/requests/api/v3/groups_spec.rb b/spec/requests/api/v3/groups_spec.rb
index bc261b5e07c..98e8c954909 100644
--- a/spec/requests/api/v3/groups_spec.rb
+++ b/spec/requests/api/v3/groups_spec.rb
@@ -421,7 +421,7 @@ describe API::V3::Groups do
         expect(json_response["request_access_enabled"]).to eq(group[:request_access_enabled])
       end
 
-      it "creates a nested group" do
+      it "creates a nested group", :nested_groups do
         parent = create(:group)
         parent.add_owner(user3)
         group = attributes_for(:group, { parent_id: parent.id })
diff --git a/spec/requests/api/v3/projects_spec.rb b/spec/requests/api/v3/projects_spec.rb
index dc7c3d125b1..bc591b2eb37 100644
--- a/spec/requests/api/v3/projects_spec.rb
+++ b/spec/requests/api/v3/projects_spec.rb
@@ -10,8 +10,7 @@ describe API::V3::Projects do
   let(:project) { create(:empty_project, creator_id: user.id, namespace: user.namespace) }
   let(:project2) { create(:empty_project, path: 'project2', creator_id: user.id, namespace: user.namespace) }
   let(:snippet) { create(:project_snippet, :public, author: user, project: project, title: 'example') }
-  let(:project_member) { create(:project_member, :master, user: user, project: project) }
-  let(:project_member2) { create(:project_member, :developer, user: user3, project: project) }
+  let(:project_member) { create(:project_member, :developer, user: user3, project: project) }
   let(:user4) { create(:user) }
   let(:project3) do
     create(:project,
@@ -25,7 +24,7 @@ describe API::V3::Projects do
     issues_enabled: false, wiki_enabled: false,
     snippets_enabled: false)
   end
-  let(:project_member3) do
+  let(:project_member2) do
     create(:project_member,
     user: user4,
     project: project3,
@@ -286,7 +285,7 @@ describe API::V3::Projects do
     let(:public_project) { create(:empty_project, :public) }
 
     before do
-      project_member2
+      project_member
       user3.update_attributes(starred_projects: [project, project2, project3, public_project])
     end
 
@@ -622,7 +621,6 @@ describe API::V3::Projects do
     context 'when authenticated' do
       before do
         project
-        project_member
       end
 
       it 'returns a project by id' do
@@ -814,8 +812,7 @@ describe API::V3::Projects do
   describe 'GET /projects/:id/users' do
     shared_examples_for 'project users response' do
       it 'returns the project users' do
-        member = create(:user)
-        create(:project_member, :developer, user: member, project: project)
+        member = project.owner
 
         get v3_api("/projects/#{project.id}/users", current_user)
 
@@ -1163,8 +1160,8 @@ describe API::V3::Projects do
     before { user4 }
     before { project3 }
     before { project4 }
-    before { project_member3 }
     before { project_member2 }
+    before { project_member }
 
     context 'when unauthenticated' do
       it 'returns authentication error' do
diff --git a/spec/services/projects/destroy_service_spec.rb b/spec/services/projects/destroy_service_spec.rb
index 4b8589b2736..0d6dd28e332 100644
--- a/spec/services/projects/destroy_service_spec.rb
+++ b/spec/services/projects/destroy_service_spec.rb
@@ -70,7 +70,7 @@ describe Projects::DestroyService, services: true do
         end
       end
 
-      expect(project.team.members.count).to eq 1
+      expect(project.team.members.count).to eq 2
     end
   end
 
diff --git a/spec/services/users/refresh_authorized_projects_service_spec.rb b/spec/services/users/refresh_authorized_projects_service_spec.rb
index b19374ef1a2..8c40d25e00c 100644
--- a/spec/services/users/refresh_authorized_projects_service_spec.rb
+++ b/spec/services/users/refresh_authorized_projects_service_spec.rb
@@ -1,15 +1,13 @@
 require 'spec_helper'
 
 describe Users::RefreshAuthorizedProjectsService do
-  let(:project) { create(:empty_project) }
+  # We're using let! here so that any expectations for the service class are not
+  # triggered twice.
+  let!(:project) { create(:empty_project) }
+
   let(:user) { project.namespace.owner }
   let(:service) { described_class.new(user) }
 
-  def create_authorization(project, user, access_level = Gitlab::Access::MASTER)
-    ProjectAuthorization.
-      create!(project: project, user: user, access_level: access_level)
-  end
-
   describe '#execute', :redis do
     it 'refreshes the authorizations using a lease' do
       expect_any_instance_of(Gitlab::ExclusiveLease).to receive(:try_obtain).
@@ -31,7 +29,8 @@ describe Users::RefreshAuthorizedProjectsService do
 
     it 'updates the authorized projects of the user' do
       project2 = create(:empty_project)
-      to_remove = create_authorization(project2, user)
+      to_remove = user.project_authorizations.
+        create!(project: project2, access_level: Gitlab::Access::MASTER)
 
       expect(service).to receive(:update_authorizations).
         with([to_remove.project_id], [[user.id, project.id, Gitlab::Access::MASTER]])
@@ -40,7 +39,10 @@ describe Users::RefreshAuthorizedProjectsService do
     end
 
     it 'sets the access level of a project to the highest available level' do
-      to_remove = create_authorization(project, user, Gitlab::Access::DEVELOPER)
+      user.project_authorizations.delete_all
+
+      to_remove = user.project_authorizations.
+        create!(project: project, access_level: Gitlab::Access::DEVELOPER)
 
       expect(service).to receive(:update_authorizations).
         with([to_remove.project_id], [[user.id, project.id, Gitlab::Access::MASTER]])
@@ -61,34 +63,10 @@ describe Users::RefreshAuthorizedProjectsService do
 
         service.update_authorizations([], [])
       end
-
-      context 'when the authorized projects column is not set' do
-        before do
-          user.update!(authorized_projects_populated: nil)
-        end
-
-        it 'populates the authorized projects column' do
-          service.update_authorizations([], [])
-
-          expect(user.authorized_projects_populated).to eq true
-        end
-      end
-
-      context 'when the authorized projects column is set' do
-        before do
-          user.update!(authorized_projects_populated: true)
-        end
-
-        it 'does nothing' do
-          expect(user).not_to receive(:set_authorized_projects_column)
-
-          service.update_authorizations([], [])
-        end
-      end
     end
 
     it 'removes authorizations that should be removed' do
-      authorization = create_authorization(project, user)
+      authorization = user.project_authorizations.find_by(project_id: project.id)
 
       service.update_authorizations([authorization.project_id])
 
@@ -96,6 +74,8 @@ describe Users::RefreshAuthorizedProjectsService do
     end
 
     it 'inserts authorizations that should be added' do
+      user.project_authorizations.delete_all
+
       service.update_authorizations([], [[user.id, project.id, Gitlab::Access::MASTER]])
 
       authorizations = user.project_authorizations
@@ -105,16 +85,6 @@ describe Users::RefreshAuthorizedProjectsService do
       expect(authorizations[0].project_id).to eq(project.id)
       expect(authorizations[0].access_level).to eq(Gitlab::Access::MASTER)
     end
-
-    it 'populates the authorized projects column' do
-      # make sure we start with a nil value no matter what the default in the
-      # factory may be.
-      user.update!(authorized_projects_populated: nil)
-
-      service.update_authorizations([], [[user.id, project.id, Gitlab::Access::MASTER]])
-
-      expect(user.authorized_projects_populated).to eq(true)
-    end
   end
 
   describe '#fresh_access_levels_per_project' do
@@ -163,7 +133,7 @@ describe Users::RefreshAuthorizedProjectsService do
       end
     end
 
-    context 'projects of subgroups of groups the user is a member of' do
+    context 'projects of subgroups of groups the user is a member of', :nested_groups do
       let(:group) { create(:group) }
       let(:nested_group) { create(:group, parent: group) }
       let!(:other_project) { create(:empty_project, group: nested_group) }
@@ -191,7 +161,7 @@ describe Users::RefreshAuthorizedProjectsService do
       end
     end
 
-    context 'projects shared with subgroups of groups the user is a member of' do
+    context 'projects shared with subgroups of groups the user is a member of', :nested_groups do
       let(:group) { create(:group) }
       let(:nested_group) { create(:group, parent: group) }
       let(:other_project) { create(:empty_project) }
@@ -208,8 +178,6 @@ describe Users::RefreshAuthorizedProjectsService do
   end
 
   describe '#current_authorizations_per_project' do
-    before { create_authorization(project, user) }
-
     let(:hash) { service.current_authorizations_per_project }
 
     it 'returns a Hash' do
@@ -233,13 +201,13 @@ describe Users::RefreshAuthorizedProjectsService do
   describe '#current_authorizations' do
     context 'without authorizations' do
       it 'returns an empty list' do
+        user.project_authorizations.delete_all
+
         expect(service.current_authorizations.empty?).to eq(true)
       end
     end
 
     context 'with an authorization' do
-      before { create_authorization(project, user) }
-
       let(:row) { service.current_authorizations.take }
 
       it 'returns the currently authorized projects' do
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 51571ddebe9..4c2eba8fa46 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -92,6 +92,14 @@ RSpec.configure do |config|
     Gitlab::Redis.with(&:flushall)
     Sidekiq.redis(&:flushall)
   end
+
+  config.around(:each, :nested_groups) do |example|
+    example.run if Group.supports_nested_groups?
+  end
+
+  config.around(:each, :postgresql) do |example|
+    example.run if Gitlab::Database.postgresql?
+  end
 end
 
 FactoryGirl::SyntaxRunner.class_eval do