From: Peter Amstutz <peter.amstutz@curii.com>
Date: Fri, 1 May 2020 18:26:35 +0000 (-0400)
Subject: 16007: Use incremental updates instead of materialized view for permissions
X-Git-Tag: 2.1.0~193^2~14
X-Git-Url: https://git.arvados.org/arvados.git/commitdiff_plain/6ba9fdc006d023fe1a56cd28fb87a54dff5265d8

16007: Use incremental updates instead of materialized view for permissions

Separate 'trashed' from 'permissions' and remove 'trashed' from
permission computation.  Add postgres functions for computing trash
and update trashed_groups incrementally.  Make sure trash table gets
refreshed on database reset.  readable_by() now checks trash_at timestamp.

Drop materialized view and replace with a table that is updated
incrementally.  Add postgres functions for computing permissions.
Initialize materialized_permissions from search_permission_graph.
Call refresh_permissions in database_seeds.  Add index on
materialized_permissions.target_uuid.

Arvados-DCO-1.1-Signed-off-by: Peter Amstutz <peter.amstutz@curii.com>
---

diff --git a/services/api/app/controllers/database_controller.rb b/services/api/app/controllers/database_controller.rb
index d6045a5dcb..24c6cf5a79 100644
--- a/services/api/app/controllers/database_controller.rb
+++ b/services/api/app/controllers/database_controller.rb
@@ -78,6 +78,7 @@ class DatabaseController < ApplicationController
     require 'refresh_permission_view'
 
     refresh_permission_view
+    refresh_trashed
 
     # Done.
     send_json success: true
diff --git a/services/api/app/models/arvados_model.rb b/services/api/app/models/arvados_model.rb
index 816dbf4758..e168cc608e 100644
--- a/services/api/app/models/arvados_model.rb
+++ b/services/api/app/models/arvados_model.rb
@@ -287,8 +287,8 @@ class ArvadosModel < ApplicationRecord
 
     exclude_trashed_records = ""
     if !include_trash and (sql_table == "groups" or sql_table == "collections") then
-      # Only include records that are not explicitly trashed
-      exclude_trashed_records = "AND #{sql_table}.is_trashed = false"
+      # Only include records that are not trashed
+      exclude_trashed_records = "AND (#{sql_table}.trash_at is NULL or #{sql_table}.trash_at > statement_timestamp())"
     end
 
     if users_list.select { |u| u.is_admin }.any?
@@ -296,14 +296,14 @@ class ArvadosModel < ApplicationRecord
       if !include_trash
         if sql_table != "api_client_authorizations"
           # Only include records where the owner is not trashed
-          sql_conds = "#{sql_table}.owner_uuid NOT IN (SELECT target_uuid FROM #{PERMISSION_VIEW} "+
-                      "WHERE trashed = 1) #{exclude_trashed_records}"
+          sql_conds = "#{sql_table}.owner_uuid NOT IN (SELECT group_uuid FROM #{TRASHED_GROUPS} "+
+                      "where trash_at <= statement_timestamp()) #{exclude_trashed_records}"
         end
       end
     else
       trashed_check = ""
       if !include_trash then
-        trashed_check = "AND trashed = 0"
+        trashed_check = "AND target_uuid NOT IN (SELECT group_uuid FROM #{TRASHED_GROUPS} where trash_at <= statement_timestamp())"
       end
 
       # Note: it is possible to combine the direct_check and
@@ -322,7 +322,7 @@ class ArvadosModel < ApplicationRecord
       owner_check = ""
       if sql_table != "api_client_authorizations" and sql_table != "groups" then
         owner_check = "OR #{sql_table}.owner_uuid IN (SELECT target_uuid FROM #{PERMISSION_VIEW} "+
-          "WHERE user_uuid IN (:user_uuids) AND perm_level >= 1 #{trashed_check} AND target_owner_uuid IS NOT NULL) "
+          "WHERE user_uuid IN (:user_uuids) AND perm_level >= 1 #{trashed_check} AND traverse_owned) "
       end
 
       links_cond = ""
diff --git a/services/api/app/models/database_seeds.rb b/services/api/app/models/database_seeds.rb
index 6e7ab9b076..0fea2cf7b6 100644
--- a/services/api/app/models/database_seeds.rb
+++ b/services/api/app/models/database_seeds.rb
@@ -2,6 +2,8 @@
 #
 # SPDX-License-Identifier: AGPL-3.0
 
+require 'refresh_permission_view'
+
 class DatabaseSeeds
   extend CurrentApiClient
   def self.install
@@ -12,5 +14,7 @@ class DatabaseSeeds
     anonymous_group_read_permission
     anonymous_user
     empty_collection
+    refresh_permission_view
+    refresh_trashed
   end
 end
diff --git a/services/api/app/models/group.rb b/services/api/app/models/group.rb
index 1f2b0d8b77..9b8a9877e1 100644
--- a/services/api/app/models/group.rb
+++ b/services/api/app/models/group.rb
@@ -17,9 +17,15 @@ class Group < ArvadosModel
   attribute :properties, :jsonbHash, default: {}
 
   validate :ensure_filesystem_compatible_name
-  after_create :invalidate_permissions_cache
-  after_update :maybe_invalidate_permissions_cache
   before_create :assign_name
+  after_create :after_ownership_change
+  after_create :update_trash
+
+  before_update :before_ownership_change
+  after_update :after_ownership_change
+
+  after_update :update_trash
+  before_destroy :clear_permissions_and_trash
 
   api_accessible :user, extend: :common do |t|
     t.add :name
@@ -38,18 +44,58 @@ class Group < ArvadosModel
     super if group_class == 'project'
   end
 
-  def maybe_invalidate_permissions_cache
-    if uuid_changed? or owner_uuid_changed? or is_trashed_changed?
-      # This can change users' permissions on other groups as well as
-      # this one.
-      invalidate_permissions_cache
+  def update_trash
+    if trash_at_changed? or owner_uuid_changed?
+      # The group was added or removed from the trash.
+      #
+      # Strategy:
+      #   Compute project subtree, propagating trash_at to subprojects
+      #   Remove groups that don't belong from trash
+      #   Add/update groups that do belong in the trash
+
+      temptable = "group_subtree_#{rand(2**64).to_s(10)}"
+      ActiveRecord::Base.connection.exec_query %{
+create temporary table #{temptable} on commit drop
+as select * from project_subtree_with_trash_at($1, LEAST($2, $3)::timestamp)
+},
+                                               'Group.update_trash.select',
+                                               [[nil, self.uuid],
+                                                [nil, TrashedGroup.find_by_group_uuid(self.owner_uuid).andand.trash_at],
+                                                [nil, self.trash_at]]
+
+      ActiveRecord::Base.connection.exec_delete %{
+delete from trashed_groups where group_uuid in (select target_uuid from #{temptable} where trash_at is NULL);
+},
+                                            "Group.update_trash.delete"
+
+      ActiveRecord::Base.connection.exec_query %{
+insert into trashed_groups (group_uuid, trash_at)
+  select target_uuid as group_uuid, trash_at from #{temptable} where trash_at is not NULL
+on conflict (group_uuid) do update set trash_at=EXCLUDED.trash_at;
+},
+                                            "Group.update_trash.insert"
+    end
+  end
+
+  def before_ownership_change
+    if owner_uuid_changed? and !self.owner_uuid_was.nil?
+      MaterializedPermission.where(user_uuid: owner_uuid_was, target_uuid: uuid).delete_all
+      update_permissions self.owner_uuid, self.uuid, 0
+    end
+  end
+
+  def after_ownership_change
+    if owner_uuid_changed?
+      update_permissions self.owner_uuid, self.uuid, 3
     end
   end
 
-  def invalidate_permissions_cache
-    # Ensure a new group can be accessed by the appropriate users
-    # immediately after being created.
-    User.invalidate_permissions_cache self.async_permissions_update
+  def clear_permissions_and_trash
+    MaterializedPermission.where(target_uuid: uuid).delete_all
+    ActiveRecord::Base.connection.exec_delete %{
+delete from trashed_groups where group_uuid=$1
+}, "Group.clear_permissions_and_trash", [[nil, self.uuid]]
+
   end
 
   def assign_name
diff --git a/services/api/app/models/link.rb b/services/api/app/models/link.rb
index ad7800fe67..33e18b296b 100644
--- a/services/api/app/models/link.rb
+++ b/services/api/app/models/link.rb
@@ -11,12 +11,13 @@ class Link < ArvadosModel
   # already know how to properly treat them.
   attribute :properties, :jsonbHash, default: {}
 
+  validate :name_links_are_obsolete
   before_create :permission_to_attach_to_objects
   before_update :permission_to_attach_to_objects
-  after_update :maybe_invalidate_permissions_cache
-  after_create :maybe_invalidate_permissions_cache
-  after_destroy :maybe_invalidate_permissions_cache
-  validate :name_links_are_obsolete
+  after_update :call_update_permissions
+  after_create :call_update_permissions
+  before_destroy :clear_permissions
+  after_destroy :check_permissions
 
   api_accessible :user, extend: :common do |t|
     t.add :tail_uuid
@@ -64,15 +65,28 @@ class Link < ArvadosModel
     false
   end
 
-  def maybe_invalidate_permissions_cache
+  PERM_LEVEL = {
+    'can_read' => 1,
+    'can_login' => 1,
+    'can_write' => 2,
+    'can_manage' => 3,
+  }
+
+  def call_update_permissions
+    if self.link_class == 'permission'
+      update_permissions tail_uuid, head_uuid, PERM_LEVEL[name]
+    end
+  end
+
+  def clear_permissions
+    if self.link_class == 'permission'
+      update_permissions tail_uuid, head_uuid, 0
+    end
+  end
+
+  def check_permissions
     if self.link_class == 'permission'
-      # Clearing the entire permissions cache can generate many
-      # unnecessary queries if many active users are not affected by
-      # this change. In such cases it would be better to search cached
-      # permissions for head_uuid and tail_uuid, and invalidate the
-      # cache for only those users. (This would require a browseable
-      # cache.)
-      User.invalidate_permissions_cache
+      #check_permissions_against_full_refresh
     end
   end
 
diff --git a/services/api/app/models/materialized_permission.rb b/services/api/app/models/materialized_permission.rb
new file mode 100644
index 0000000000..24ba6737ae
--- /dev/null
+++ b/services/api/app/models/materialized_permission.rb
@@ -0,0 +1,6 @@
+# Copyright (C) The Arvados Authors. All rights reserved.
+#
+# SPDX-License-Identifier: AGPL-3.0
+
+class MaterializedPermission < ApplicationRecord
+end
diff --git a/services/api/app/models/trashed_group.rb b/services/api/app/models/trashed_group.rb
new file mode 100644
index 0000000000..5c85946bae
--- /dev/null
+++ b/services/api/app/models/trashed_group.rb
@@ -0,0 +1,6 @@
+# Copyright (C) The Arvados Authors. All rights reserved.
+#
+# SPDX-License-Identifier: AGPL-3.0
+
+class TrashedGroup < ApplicationRecord
+end
diff --git a/services/api/app/models/user.rb b/services/api/app/models/user.rb
index c3641b64e8..d48dde25a4 100644
--- a/services/api/app/models/user.rb
+++ b/services/api/app/models/user.rb
@@ -3,7 +3,6 @@
 # SPDX-License-Identifier: AGPL-3.0
 
 require 'can_be_an_owner'
-require 'refresh_permission_view'
 
 class User < ArvadosModel
   include HasUuid
@@ -28,25 +27,31 @@ class User < ArvadosModel
     user.username.nil? and user.username_changed?
   }
   before_update :setup_on_activate
+
   before_create :check_auto_admin
   before_create :set_initial_username, :if => Proc.new { |user|
     user.username.nil? and user.email
   }
+  after_create :after_ownership_change
   after_create :setup_on_activate
   after_create :add_system_group_permission_link
-  after_create :invalidate_permissions_cache
   after_create :auto_setup_new_user, :if => Proc.new { |user|
     Rails.configuration.Users.AutoSetupNewUsers and
     (user.uuid != system_user_uuid) and
     (user.uuid != anonymous_user_uuid)
   }
   after_create :send_admin_notifications
+
+  before_update :before_ownership_change
+  after_update :after_ownership_change
   after_update :send_profile_created_notification
   after_update :sync_repository_names, :if => Proc.new { |user|
     (user.uuid != system_user_uuid) and
     user.username_changed? and
     (not user.username_was.nil?)
   }
+  before_destroy :clear_permissions
+  after_destroy :check_permissions
 
   has_many :authorized_keys, :foreign_key => :authorized_user_uuid, :primary_key => :uuid
   has_many :repositories, foreign_key: :owner_uuid, primary_key: :uuid
@@ -77,6 +82,12 @@ class User < ArvadosModel
      {read: true, write: true},
      {read: true, write: true, manage: true}]
 
+  VAL_FOR_PERM =
+    {:read => 1,
+     :write => 2,
+     :manage => 3}
+
+
   def full_name
     "#{first_name} #{last_name}".strip
   end
@@ -88,7 +99,7 @@ class User < ArvadosModel
   end
 
   def groups_i_can(verb)
-    my_groups = self.group_permissions.select { |uuid, mask| mask[verb] }.keys
+    my_groups = self.group_permissions(VAL_FOR_PERM[verb]).keys
     if verb == :read
       my_groups << anonymous_group_uuid
     end
@@ -107,60 +118,61 @@ class User < ArvadosModel
         end
       end
       next if target_uuid == self.uuid
-      next if (group_permissions[target_uuid] and
-               group_permissions[target_uuid][action])
-      if target.respond_to? :owner_uuid
-        next if target.owner_uuid == self.uuid
-        next if (group_permissions[target.owner_uuid] and
-                 group_permissions[target.owner_uuid][action])
-      end
-      sufficient_perms = case action
-                         when :manage
-                           ['can_manage']
-                         when :write
-                           ['can_manage', 'can_write']
-                         when :read
-                           ['can_manage', 'can_write', 'can_read']
-                         else
-                           # (Skip this kind of permission opportunity
-                           # if action is an unknown permission type)
-                         end
-      if sufficient_perms
-        # Check permission links with head_uuid pointing directly at
-        # the target object. If target is a Group, this is redundant
-        # and will fail except [a] if permission caching is broken or
-        # [b] during a race condition, where a permission link has
-        # *just* been added.
-        if Link.where(link_class: 'permission',
-                      name: sufficient_perms,
-                      tail_uuid: groups_i_can(action) + [self.uuid],
-                      head_uuid: target_uuid).any?
-          next
-        end
+
+      target_owner_uuid = target.owner_uuid if target.respond_to? :owner_uuid
+
+      unless ActiveRecord::Base.connection.
+        exec_query(%{
+SELECT 1 FROM #{PERMISSION_VIEW}
+  WHERE user_uuid = $1 and
+        ((target_uuid = $2 and perm_level >= $3)
+         or (target_uuid = $4 and perm_level >= $3 and traverse_owned))
+},
+                  # "name" arg is a query label that appears in logs:
+                   "user_can_query",
+                   [[nil, self.uuid],
+                    [nil, target_uuid],
+                    [nil, VAL_FOR_PERM[action]],
+                    [nil, target_owner_uuid]]
+                  ).any?
+        return false
       end
-      return false
     end
     true
   end
 
-  def self.invalidate_permissions_cache(async=false)
-    refresh_permission_view(async)
+  def before_ownership_change
+    if owner_uuid_changed? and !self.owner_uuid_was.nil?
+      MaterializedPermission.where(user_uuid: owner_uuid_was, target_uuid: uuid).delete_all
+      update_permissions self.owner_uuid_was, self.uuid, 0
+    end
+  end
+
+  def after_ownership_change
+    if owner_uuid_changed?
+      update_permissions self.owner_uuid, self.uuid, 3
+    end
   end
 
-  def invalidate_permissions_cache
-    User.invalidate_permissions_cache
+  def clear_permissions
+    update_permissions self.owner_uuid, self.uuid, 0
+    MaterializedPermission.where("user_uuid = ? or target_uuid = ?", uuid, uuid).delete_all
+  end
+
+  def check_permissions
+    check_permissions_against_full_refresh
   end
 
   # Return a hash of {user_uuid: group_perms}
   def self.all_group_permissions
     all_perms = {}
     ActiveRecord::Base.connection.
-      exec_query("SELECT user_uuid, target_owner_uuid, perm_level, trashed
+      exec_query("SELECT user_uuid, target_uuid, perm_level
                   FROM #{PERMISSION_VIEW}
-                  WHERE target_owner_uuid IS NOT NULL",
+                  WHERE traverse_owned",
                   # "name" arg is a query label that appears in logs:
-                  "all_group_permissions",
-                  ).rows.each do |user_uuid, group_uuid, max_p_val, trashed|
+                 "all_group_permissions").
+      rows.each do |user_uuid, group_uuid, max_p_val|
       all_perms[user_uuid] ||= {}
       all_perms[user_uuid][group_uuid] = PERMS_FOR_VAL[max_p_val.to_i]
     end
@@ -170,18 +182,20 @@ class User < ArvadosModel
   # Return a hash of {group_uuid: perm_hash} where perm_hash[:read]
   # and perm_hash[:write] are true if this user can read and write
   # objects owned by group_uuid.
-  def group_permissions
-    group_perms = {self.uuid => {:read => true, :write => true, :manage => true}}
+  def group_permissions(level=1)
+    group_perms = {}
     ActiveRecord::Base.connection.
-      exec_query("SELECT target_owner_uuid, perm_level, trashed
-                  FROM #{PERMISSION_VIEW}
-                  WHERE user_uuid = $1
-                  AND target_owner_uuid IS NOT NULL",
+      exec_query(%{
+SELECT target_uuid, perm_level
+  FROM #{PERMISSION_VIEW}
+  WHERE user_uuid = $1 and perm_level >= $2
+},
                   # "name" arg is a query label that appears in logs:
-                  "group_permissions for #{uuid}",
+                  "group_permissions_for_user",
                   # "binds" arg is an array of [col_id, value] for '$1' vars:
-                  [[nil, uuid]],
-                ).rows.each do |group_uuid, max_p_val, trashed|
+                  [[nil, uuid],
+                   [nil, level]]).
+      rows.each do |group_uuid, max_p_val|
       group_perms[group_uuid] = PERMS_FOR_VAL[max_p_val.to_i]
     end
     group_perms
@@ -309,6 +323,18 @@ class User < ArvadosModel
       self.uuid = new_uuid
       save!(validate: false)
       change_all_uuid_refs(old_uuid: old_uuid, new_uuid: new_uuid)
+    ActiveRecord::Base.connection.exec_update %{
+update #{PERMISSION_VIEW} set user_uuid=$1 where user_uuid = $2
+},
+                                             'User.update_uuid.update_permissions_user_uuid',
+                                             [[nil, new_uuid],
+                                              [nil, old_uuid]]
+      ActiveRecord::Base.connection.exec_update %{
+update #{PERMISSION_VIEW} set target_uuid=$1 where target_uuid = $2
+},
+                                            'User.update_uuid.update_permissions_target_uuid',
+                                             [[nil, new_uuid],
+                                              [nil, old_uuid]]
     end
   end
 
@@ -334,6 +360,8 @@ class User < ArvadosModel
       raise "user does not exist" if !new_user
       raise "cannot merge to an already merged user" if new_user.redirect_to_user_uuid
 
+      self.clear_permissions
+
       # If 'self' is a remote user, don't transfer authorizations
       # (i.e. ability to access the account) to the new user, because
       # that gives the remote site the ability to access the 'new'
@@ -408,7 +436,8 @@ class User < ArvadosModel
       if redirect_to_new_user
         update_attributes!(redirect_to_user_uuid: new_user.uuid, username: nil)
       end
-      invalidate_permissions_cache
+      update_permissions self.owner_uuid, self.uuid, 3, false
+      update_permissions new_user.owner_uuid, new_user.uuid, 3
     end
   end
 
diff --git a/services/api/db/migrate/20200501150153_permission_table.rb b/services/api/db/migrate/20200501150153_permission_table.rb
new file mode 100644
index 0000000000..51216b9c23
--- /dev/null
+++ b/services/api/db/migrate/20200501150153_permission_table.rb
@@ -0,0 +1,263 @@
+# Copyright (C) The Arvados Authors. All rights reserved.
+#
+# SPDX-License-Identifier: AGPL-3.0
+
+class PermissionTable < ActiveRecord::Migration[5.0]
+  def up
+    ActiveRecord::Base.connection.execute "DROP MATERIALIZED VIEW IF EXISTS materialized_permission_view;"
+    drop_table :permission_refresh_lock
+
+    create_table :materialized_permissions, :id => false do |t|
+      t.string :user_uuid
+      t.string :target_uuid
+      t.integer :perm_level
+      t.boolean :traverse_owned
+    end
+    add_index :materialized_permissions, [:user_uuid, :target_uuid], unique: true, name: 'permission_user_target'
+    add_index :materialized_permissions, [:target_uuid], unique: false, name: 'permission_target'
+
+    ActiveRecord::Base.connection.execute %{
+create or replace function project_subtree_with_trash_at (starting_uuid varchar(27), starting_trash_at timestamp)
+returns table (target_uuid varchar(27), trash_at timestamp)
+STABLE
+language SQL
+as $$
+WITH RECURSIVE
+        project_subtree(uuid, trash_at) as (
+        values (starting_uuid, starting_trash_at)
+        union
+        select groups.uuid, LEAST(project_subtree.trash_at, groups.trash_at)
+          from groups join project_subtree on (groups.owner_uuid = project_subtree.uuid)
+        )
+        select uuid, trash_at from project_subtree;
+$$;
+}
+
+    create_table :trashed_groups, :id => false do |t|
+      t.string :group_uuid
+      t.datetime :trash_at
+    end
+    add_index :trashed_groups, :group_uuid, :unique => true
+
+    ActiveRecord::Base.connection.execute %{
+create or replace function compute_trashed ()
+returns table (uuid varchar(27), trash_at timestamp)
+STABLE
+language SQL
+as $$
+select ps.target_uuid as group_uuid, ps.trash_at from groups,
+  lateral project_subtree_with_trash_at(groups.uuid, groups.trash_at) ps
+  where groups.owner_uuid like '_____-tpzed-_______________'
+$$;
+}
+
+    ActiveRecord::Base.connection.execute("INSERT INTO trashed_groups select * from compute_trashed()")
+
+    ActiveRecord::Base.connection.execute %{
+create or replace function should_traverse_owned (starting_uuid varchar(27),
+                                                  starting_perm integer)
+  returns bool
+STABLE
+language SQL
+as $$
+select starting_uuid like '_____-j7d0g-_______________' or
+       (starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3);
+$$;
+}
+
+    ActiveRecord::Base.connection.execute %{
+create view permission_graph_edges as
+  select groups.owner_uuid as tail_uuid, groups.uuid as head_uuid, (3) as val from groups
+union all
+  select users.owner_uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users
+union all
+  select links.tail_uuid,
+         links.head_uuid,
+         CASE
+           WHEN links.name = 'can_read'   THEN 1
+           WHEN links.name = 'can_login'  THEN 1
+           WHEN links.name = 'can_write'  THEN 2
+           WHEN links.name = 'can_manage' THEN 3
+          END as val
+      from links
+      where links.link_class='permission'
+}
+
+        # Get a set of permission by searching the graph and following
+        # ownership and permission links.
+        #
+        # edges() - a subselect with the union of ownership and permission links
+        #
+        # traverse_graph() - recursive query, from the starting node,
+        # self-join with edges to find outgoing permissions.
+        # Re-runs the query on new rows until there are no more results.
+        # This accomplishes a breadth-first search of the permission graph.
+        #
+    ActiveRecord::Base.connection.execute %{
+create or replace function search_permission_graph (starting_uuid varchar(27),
+                                                    starting_perm integer)
+  returns table (target_uuid varchar(27), val integer, traverse_owned bool)
+STABLE
+language SQL
+as $$
+WITH RECURSIVE
+        traverse_graph(target_uuid, val, traverse_owned) as (
+            values (starting_uuid, starting_perm,
+                    should_traverse_owned(starting_uuid, starting_perm))
+          union
+            (select edges.head_uuid,
+                    least(edges.val, traverse_graph.val,
+                          case traverse_graph.traverse_owned
+                            when true then null
+                            else 0
+                          end),
+                    should_traverse_owned(edges.head_uuid, edges.val)
+             from permission_graph_edges as edges, traverse_graph
+             where traverse_graph.target_uuid = edges.tail_uuid))
+        select target_uuid, max(val), bool_or(traverse_owned) from traverse_graph
+        group by (target_uuid);
+$$;
+}
+
+    ActiveRecord::Base.connection.execute %{
+create or replace function compute_permission_subgraph (perm_origin_uuid varchar(27),
+                                                        starting_uuid varchar(27),
+                                                        starting_perm integer)
+returns table (user_uuid varchar(27), target_uuid varchar(27), val integer, traverse_owned bool)
+STABLE
+language SQL
+as $$
+with
+perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+  select perm_origin_uuid, target_uuid, val, traverse_owned
+    from search_permission_graph(starting_uuid, starting_perm)),
+
+  additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+    select edges.tail_uuid as perm_origin_uuid, ps.target_uuid, ps.val,
+           should_traverse_owned(ps.target_uuid, ps.val)
+      from permission_graph_edges as edges, lateral search_permission_graph(edges.head_uuid, edges.val) as ps
+      where (not (edges.tail_uuid = perm_origin_uuid and
+                 edges.head_uuid = starting_uuid)) and
+            edges.tail_uuid not in (select target_uuid from perm_from_start) and
+            edges.head_uuid in (select target_uuid from perm_from_start)),
+
+  partial_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+      select * from perm_from_start
+    union all
+      select * from additional_perms
+  ),
+
+  user_identity_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+    select users.uuid as perm_origin_uuid, ps.target_uuid, ps.val, ps.traverse_owned
+      from users, lateral search_permission_graph(users.uuid, 3) as ps
+      where (users.owner_uuid not in (select target_uuid from partial_perms) or
+             users.owner_uuid = users.uuid) and
+      users.uuid in (select target_uuid from partial_perms)
+  ),
+
+  all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+      select * from partial_perms
+    union
+      select * from user_identity_perms
+  )
+
+  select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
+    (select m.user_uuid,
+         u.target_uuid,
+         least(u.val, m.perm_level) as perm_level,
+         u.traverse_owned
+      from all_perms as u, materialized_permissions as m
+           where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
+    union all
+      select perm_origin_uuid as user_uuid, target_uuid, val as perm_level, traverse_owned
+        from all_perms
+        where all_perms.perm_origin_uuid like '_____-tpzed-_______________') as v
+    group by v.user_uuid, v.target_uuid
+$$;
+     }
+
+    ActiveRecord::Base.connection.execute %{
+INSERT INTO materialized_permissions
+select users.uuid, g.target_uuid, g.val, g.traverse_owned
+from users, lateral search_permission_graph(users.uuid, 3) as g where g.val > 0
+}
+  end
+
+  def down
+    drop_table :materialized_permissions
+    drop_table :trashed_groups
+
+    ActiveRecord::Base.connection.execute "DROP function project_subtree_with_trash_at (varchar, timestamp);"
+    ActiveRecord::Base.connection.execute "DROP function compute_trashed ();"
+    ActiveRecord::Base.connection.execute "DROP function search_permission_graph(varchar, integer);"
+    ActiveRecord::Base.connection.execute "DROP function compute_permission_subgraph (varchar, varchar, integer);"
+    ActiveRecord::Base.connection.execute "DROP function should_traverse_owned(varchar, integer);"
+    ActiveRecord::Base.connection.execute "DROP view permission_graph_edges;"
+
+    ActiveRecord::Base.connection.execute(%{
+CREATE MATERIALIZED VIEW materialized_permission_view AS
+ WITH RECURSIVE perm_value(name, val) AS (
+         VALUES ('can_read'::text,(1)::smallint), ('can_login'::text,1), ('can_write'::text,2), ('can_manage'::text,3)
+        ), perm_edges(tail_uuid, head_uuid, val, follow, trashed) AS (
+         SELECT links.tail_uuid,
+            links.head_uuid,
+            pv.val,
+            ((pv.val = 3) OR (groups.uuid IS NOT NULL)) AS follow,
+            (0)::smallint AS trashed,
+            (0)::smallint AS followtrash
+           FROM ((public.links
+             LEFT JOIN perm_value pv ON ((pv.name = (links.name)::text)))
+             LEFT JOIN public.groups ON (((pv.val < 3) AND ((groups.uuid)::text = (links.head_uuid)::text))))
+          WHERE ((links.link_class)::text = 'permission'::text)
+        UNION ALL
+         SELECT groups.owner_uuid,
+            groups.uuid,
+            3,
+            true AS bool,
+                CASE
+                    WHEN ((groups.trash_at IS NOT NULL) AND (groups.trash_at < clock_timestamp())) THEN 1
+                    ELSE 0
+                END AS "case",
+            1
+           FROM public.groups
+        ), perm(val, follow, user_uuid, target_uuid, trashed) AS (
+         SELECT (3)::smallint AS val,
+            true AS follow,
+            (users.uuid)::character varying(32) AS user_uuid,
+            (users.uuid)::character varying(32) AS target_uuid,
+            (0)::smallint AS trashed
+           FROM public.users
+        UNION
+         SELECT (LEAST((perm_1.val)::integer, edges.val))::smallint AS val,
+            edges.follow,
+            perm_1.user_uuid,
+            (edges.head_uuid)::character varying(32) AS target_uuid,
+            ((GREATEST((perm_1.trashed)::integer, edges.trashed) * edges.followtrash))::smallint AS trashed
+           FROM (perm perm_1
+             JOIN perm_edges edges ON ((perm_1.follow AND ((edges.tail_uuid)::text = (perm_1.target_uuid)::text))))
+        )
+ SELECT perm.user_uuid,
+    perm.target_uuid,
+    max(perm.val) AS perm_level,
+        CASE perm.follow
+            WHEN true THEN perm.target_uuid
+            ELSE NULL::character varying
+        END AS target_owner_uuid,
+    max(perm.trashed) AS trashed
+   FROM perm
+  GROUP BY perm.user_uuid, perm.target_uuid,
+        CASE perm.follow
+            WHEN true THEN perm.target_uuid
+            ELSE NULL::character varying
+        END
+  WITH NO DATA;
+}
+    )
+
+    add_index :materialized_permission_view, [:trashed, :target_uuid], name: 'permission_target_trashed'
+    add_index :materialized_permission_view, [:user_uuid, :trashed, :perm_level], name: 'permission_target_user_trashed_level'
+    create_table :permission_refresh_lock
+
+    ActiveRecord::Base.connection.execute 'REFRESH MATERIALIZED VIEW materialized_permission_view;'
+  end
+end
diff --git a/services/api/db/structure.sql b/services/api/db/structure.sql
index 88cd0baa2f..5f71554ffd 100644
--- a/services/api/db/structure.sql
+++ b/services/api/db/structure.sql
@@ -38,6 +38,131 @@ CREATE EXTENSION IF NOT EXISTS pg_trgm WITH SCHEMA public;
 -- COMMENT ON EXTENSION pg_trgm IS 'text similarity measurement and index searching based on trigrams';
 
 
+--
+-- Name: compute_permission_subgraph(character varying, character varying, integer); Type: FUNCTION; Schema: public; Owner: -
+--
+
+CREATE FUNCTION public.compute_permission_subgraph(perm_origin_uuid character varying, starting_uuid character varying, starting_perm integer) RETURNS TABLE(user_uuid character varying, target_uuid character varying, val integer, traverse_owned boolean)
+    LANGUAGE sql STABLE
+    AS $$
+with
+perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+  select perm_origin_uuid, target_uuid, val, traverse_owned
+    from search_permission_graph(starting_uuid, starting_perm)),
+
+  additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+    select edges.tail_uuid as perm_origin_uuid, ps.target_uuid, ps.val,
+           should_traverse_owned(ps.target_uuid, ps.val)
+      from permission_graph_edges as edges, lateral search_permission_graph(edges.head_uuid, edges.val) as ps
+      where (not (edges.tail_uuid = perm_origin_uuid and
+                 edges.head_uuid = starting_uuid)) and
+            edges.tail_uuid not in (select target_uuid from perm_from_start) and
+            edges.head_uuid in (select target_uuid from perm_from_start)),
+
+  partial_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+      select * from perm_from_start
+    union all
+      select * from additional_perms
+  ),
+
+  user_identity_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+    select users.uuid as perm_origin_uuid, ps.target_uuid, ps.val, ps.traverse_owned
+      from users, lateral search_permission_graph(users.uuid, 3) as ps
+      where (users.owner_uuid not in (select target_uuid from partial_perms) or
+             users.owner_uuid = users.uuid) and
+      users.uuid in (select target_uuid from partial_perms)
+  ),
+
+  all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+      select * from partial_perms
+    union
+      select * from user_identity_perms
+  )
+
+  select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
+    (select m.user_uuid,
+         u.target_uuid,
+         least(u.val, m.perm_level) as perm_level,
+         u.traverse_owned
+      from all_perms as u, materialized_permissions as m
+           where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
+    union all
+      select perm_origin_uuid as user_uuid, target_uuid, val as perm_level, traverse_owned
+        from all_perms
+        where all_perms.perm_origin_uuid like '_____-tpzed-_______________') as v
+    group by v.user_uuid, v.target_uuid
+$$;
+
+
+--
+-- Name: compute_trashed(); Type: FUNCTION; Schema: public; Owner: -
+--
+
+CREATE FUNCTION public.compute_trashed() RETURNS TABLE(uuid character varying, trash_at timestamp without time zone)
+    LANGUAGE sql STABLE
+    AS $$
+select ps.target_uuid as group_uuid, ps.trash_at from groups,
+  lateral project_subtree_with_trash_at(groups.uuid, groups.trash_at) ps
+  where groups.owner_uuid like '_____-tpzed-_______________'
+$$;
+
+
+--
+-- Name: project_subtree_with_trash_at(character varying, timestamp without time zone); Type: FUNCTION; Schema: public; Owner: -
+--
+
+CREATE FUNCTION public.project_subtree_with_trash_at(starting_uuid character varying, starting_trash_at timestamp without time zone) RETURNS TABLE(target_uuid character varying, trash_at timestamp without time zone)
+    LANGUAGE sql STABLE
+    AS $$
+WITH RECURSIVE
+        project_subtree(uuid, trash_at) as (
+        values (starting_uuid, starting_trash_at)
+        union
+        select groups.uuid, LEAST(project_subtree.trash_at, groups.trash_at)
+          from groups join project_subtree on (groups.owner_uuid = project_subtree.uuid)
+        )
+        select uuid, trash_at from project_subtree;
+$$;
+
+
+--
+-- Name: search_permission_graph(character varying, integer); Type: FUNCTION; Schema: public; Owner: -
+--
+
+CREATE FUNCTION public.search_permission_graph(starting_uuid character varying, starting_perm integer) RETURNS TABLE(target_uuid character varying, val integer, traverse_owned boolean)
+    LANGUAGE sql STABLE
+    AS $$
+WITH RECURSIVE
+        traverse_graph(target_uuid, val, traverse_owned) as (
+            values (starting_uuid, starting_perm,
+                    should_traverse_owned(starting_uuid, starting_perm))
+          union
+            (select edges.head_uuid,
+                    least(edges.val, traverse_graph.val,
+                          case traverse_graph.traverse_owned
+                            when true then null
+                            else 0
+                          end),
+                    should_traverse_owned(edges.head_uuid, edges.val)
+             from permission_graph_edges as edges, traverse_graph
+             where traverse_graph.target_uuid = edges.tail_uuid))
+        select target_uuid, max(val), bool_or(traverse_owned) from traverse_graph
+        group by (target_uuid);
+$$;
+
+
+--
+-- Name: should_traverse_owned(character varying, integer); Type: FUNCTION; Schema: public; Owner: -
+--
+
+CREATE FUNCTION public.should_traverse_owned(starting_uuid character varying, starting_perm integer) RETURNS boolean
+    LANGUAGE sql STABLE
+    AS $$
+select starting_uuid like '_____-j7d0g-_______________' or
+       (starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3);
+$$;
+
+
 SET default_tablespace = '';
 
 SET default_with_oids = false;
@@ -719,93 +844,17 @@ ALTER SEQUENCE public.logs_id_seq OWNED BY public.logs.id;
 
 
 --
--- Name: users; Type: TABLE; Schema: public; Owner: -
+-- Name: materialized_permissions; Type: TABLE; Schema: public; Owner: -
 --
 
-CREATE TABLE public.users (
-    id integer NOT NULL,
-    uuid character varying(255),
-    owner_uuid character varying(255) NOT NULL,
-    created_at timestamp without time zone NOT NULL,
-    modified_by_client_uuid character varying(255),
-    modified_by_user_uuid character varying(255),
-    modified_at timestamp without time zone,
-    email character varying(255),
-    first_name character varying(255),
-    last_name character varying(255),
-    identity_url character varying(255),
-    is_admin boolean,
-    prefs text,
-    updated_at timestamp without time zone NOT NULL,
-    default_owner_uuid character varying(255),
-    is_active boolean DEFAULT false,
-    username character varying(255),
-    redirect_to_user_uuid character varying
+CREATE TABLE public.materialized_permissions (
+    user_uuid character varying,
+    target_uuid character varying,
+    perm_level integer,
+    traverse_owned boolean
 );
 
 
---
--- Name: materialized_permission_view; Type: MATERIALIZED VIEW; Schema: public; Owner: -
---
-
-CREATE MATERIALIZED VIEW public.materialized_permission_view AS
- WITH RECURSIVE perm_value(name, val) AS (
-         VALUES ('can_read'::text,(1)::smallint), ('can_login'::text,1), ('can_write'::text,2), ('can_manage'::text,3)
-        ), perm_edges(tail_uuid, head_uuid, val, follow, trashed) AS (
-         SELECT links.tail_uuid,
-            links.head_uuid,
-            pv.val,
-            ((pv.val = 3) OR (groups.uuid IS NOT NULL)) AS follow,
-            (0)::smallint AS trashed,
-            (0)::smallint AS followtrash
-           FROM ((public.links
-             LEFT JOIN perm_value pv ON ((pv.name = (links.name)::text)))
-             LEFT JOIN public.groups ON (((pv.val < 3) AND ((groups.uuid)::text = (links.head_uuid)::text))))
-          WHERE ((links.link_class)::text = 'permission'::text)
-        UNION ALL
-         SELECT groups.owner_uuid,
-            groups.uuid,
-            3,
-            true AS bool,
-                CASE
-                    WHEN ((groups.trash_at IS NOT NULL) AND (groups.trash_at < clock_timestamp())) THEN 1
-                    ELSE 0
-                END AS "case",
-            1
-           FROM public.groups
-        ), perm(val, follow, user_uuid, target_uuid, trashed) AS (
-         SELECT (3)::smallint AS val,
-            true AS follow,
-            (users.uuid)::character varying(32) AS user_uuid,
-            (users.uuid)::character varying(32) AS target_uuid,
-            (0)::smallint AS trashed
-           FROM public.users
-        UNION
-         SELECT (LEAST((perm_1.val)::integer, edges.val))::smallint AS val,
-            edges.follow,
-            perm_1.user_uuid,
-            (edges.head_uuid)::character varying(32) AS target_uuid,
-            ((GREATEST((perm_1.trashed)::integer, edges.trashed) * edges.followtrash))::smallint AS trashed
-           FROM (perm perm_1
-             JOIN perm_edges edges ON ((perm_1.follow AND ((edges.tail_uuid)::text = (perm_1.target_uuid)::text))))
-        )
- SELECT perm.user_uuid,
-    perm.target_uuid,
-    max(perm.val) AS perm_level,
-        CASE perm.follow
-            WHEN true THEN perm.target_uuid
-            ELSE NULL::character varying
-        END AS target_owner_uuid,
-    max(perm.trashed) AS trashed
-   FROM perm
-  GROUP BY perm.user_uuid, perm.target_uuid,
-        CASE perm.follow
-            WHEN true THEN perm.target_uuid
-            ELSE NULL::character varying
-        END
-  WITH NO DATA;
-
-
 --
 -- Name: nodes; Type: TABLE; Schema: public; Owner: -
 --
@@ -851,31 +900,57 @@ ALTER SEQUENCE public.nodes_id_seq OWNED BY public.nodes.id;
 
 
 --
--- Name: permission_refresh_lock; Type: TABLE; Schema: public; Owner: -
+-- Name: users; Type: TABLE; Schema: public; Owner: -
 --
 
-CREATE TABLE public.permission_refresh_lock (
-    id integer NOT NULL
+CREATE TABLE public.users (
+    id integer NOT NULL,
+    uuid character varying(255),
+    owner_uuid character varying(255) NOT NULL,
+    created_at timestamp without time zone NOT NULL,
+    modified_by_client_uuid character varying(255),
+    modified_by_user_uuid character varying(255),
+    modified_at timestamp without time zone,
+    email character varying(255),
+    first_name character varying(255),
+    last_name character varying(255),
+    identity_url character varying(255),
+    is_admin boolean,
+    prefs text,
+    updated_at timestamp without time zone NOT NULL,
+    default_owner_uuid character varying(255),
+    is_active boolean DEFAULT false,
+    username character varying(255),
+    redirect_to_user_uuid character varying
 );
 
 
 --
--- Name: permission_refresh_lock_id_seq; Type: SEQUENCE; Schema: public; Owner: -
---
-
-CREATE SEQUENCE public.permission_refresh_lock_id_seq
-    START WITH 1
-    INCREMENT BY 1
-    NO MINVALUE
-    NO MAXVALUE
-    CACHE 1;
-
-
---
--- Name: permission_refresh_lock_id_seq; Type: SEQUENCE OWNED BY; Schema: public; Owner: -
+-- Name: permission_graph_edges; Type: VIEW; Schema: public; Owner: -
 --
 
-ALTER SEQUENCE public.permission_refresh_lock_id_seq OWNED BY public.permission_refresh_lock.id;
+CREATE VIEW public.permission_graph_edges AS
+ SELECT groups.owner_uuid AS tail_uuid,
+    groups.uuid AS head_uuid,
+    3 AS val
+   FROM public.groups
+UNION ALL
+ SELECT users.owner_uuid AS tail_uuid,
+    users.uuid AS head_uuid,
+    3 AS val
+   FROM public.users
+UNION ALL
+ SELECT links.tail_uuid,
+    links.head_uuid,
+        CASE
+            WHEN ((links.name)::text = 'can_read'::text) THEN 1
+            WHEN ((links.name)::text = 'can_login'::text) THEN 1
+            WHEN ((links.name)::text = 'can_write'::text) THEN 2
+            WHEN ((links.name)::text = 'can_manage'::text) THEN 3
+            ELSE NULL::integer
+        END AS val
+   FROM public.links
+  WHERE ((links.link_class)::text = 'permission'::text);
 
 
 --
@@ -1079,6 +1154,16 @@ CREATE SEQUENCE public.traits_id_seq
 ALTER SEQUENCE public.traits_id_seq OWNED BY public.traits.id;
 
 
+--
+-- Name: trashed_groups; Type: TABLE; Schema: public; Owner: -
+--
+
+CREATE TABLE public.trashed_groups (
+    group_uuid character varying,
+    trash_at timestamp without time zone
+);
+
+
 --
 -- Name: users_id_seq; Type: SEQUENCE; Schema: public; Owner: -
 --
@@ -1277,13 +1362,6 @@ ALTER TABLE ONLY public.logs ALTER COLUMN id SET DEFAULT nextval('public.logs_id
 ALTER TABLE ONLY public.nodes ALTER COLUMN id SET DEFAULT nextval('public.nodes_id_seq'::regclass);
 
 
---
--- Name: permission_refresh_lock id; Type: DEFAULT; Schema: public; Owner: -
---
-
-ALTER TABLE ONLY public.permission_refresh_lock ALTER COLUMN id SET DEFAULT nextval('public.permission_refresh_lock_id_seq'::regclass);
-
-
 --
 -- Name: pipeline_instances id; Type: DEFAULT; Schema: public; Owner: -
 --
@@ -1468,14 +1546,6 @@ ALTER TABLE ONLY public.nodes
     ADD CONSTRAINT nodes_pkey PRIMARY KEY (id);
 
 
---
--- Name: permission_refresh_lock permission_refresh_lock_pkey; Type: CONSTRAINT; Schema: public; Owner: -
---
-
-ALTER TABLE ONLY public.permission_refresh_lock
-    ADD CONSTRAINT permission_refresh_lock_pkey PRIMARY KEY (id);
-
-
 --
 -- Name: pipeline_instances pipeline_instances_pkey; Type: CONSTRAINT; Schema: public; Owner: -
 --
@@ -2513,6 +2583,13 @@ CREATE INDEX index_traits_on_owner_uuid ON public.traits USING btree (owner_uuid
 CREATE UNIQUE INDEX index_traits_on_uuid ON public.traits USING btree (uuid);
 
 
+--
+-- Name: index_trashed_groups_on_group_uuid; Type: INDEX; Schema: public; Owner: -
+--
+
+CREATE UNIQUE INDEX index_trashed_groups_on_group_uuid ON public.trashed_groups USING btree (group_uuid);
+
+
 --
 -- Name: index_users_on_created_at; Type: INDEX; Schema: public; Owner: -
 --
@@ -2703,17 +2780,17 @@ CREATE INDEX nodes_search_index ON public.nodes USING btree (uuid, owner_uuid, m
 
 
 --
--- Name: permission_target_trashed; Type: INDEX; Schema: public; Owner: -
+-- Name: permission_target; Type: INDEX; Schema: public; Owner: -
 --
 
-CREATE INDEX permission_target_trashed ON public.materialized_permission_view USING btree (trashed, target_uuid);
+CREATE INDEX permission_target ON public.materialized_permissions USING btree (target_uuid);
 
 
 --
--- Name: permission_target_user_trashed_level; Type: INDEX; Schema: public; Owner: -
+-- Name: permission_user_target; Type: INDEX; Schema: public; Owner: -
 --
 
-CREATE INDEX permission_target_user_trashed_level ON public.materialized_permission_view USING btree (user_uuid, trashed, perm_level);
+CREATE UNIQUE INDEX permission_user_target ON public.materialized_permissions USING btree (user_uuid, target_uuid);
 
 
 --
@@ -3024,6 +3101,7 @@ INSERT INTO "schema_migrations" (version) VALUES
 ('20190523180148'),
 ('20190808145904'),
 ('20190809135453'),
-('20190905151603');
+('20190905151603'),
+('20200501150153');
 
 
diff --git a/services/api/lib/refresh_permission_view.rb b/services/api/lib/refresh_permission_view.rb
index 5d6081f262..3901a1f220 100644
--- a/services/api/lib/refresh_permission_view.rb
+++ b/services/api/lib/refresh_permission_view.rb
@@ -2,39 +2,118 @@
 #
 # SPDX-License-Identifier: AGPL-3.0
 
-PERMISSION_VIEW = "materialized_permission_view"
+PERMISSION_VIEW = "materialized_permissions"
+TRASHED_GROUPS = "trashed_groups"
 
-def do_refresh_permission_view
+def refresh_permission_view
   ActiveRecord::Base.transaction do
-    ActiveRecord::Base.connection.execute("LOCK TABLE permission_refresh_lock")
-    ActiveRecord::Base.connection.execute("REFRESH MATERIALIZED VIEW #{PERMISSION_VIEW}")
+    ActiveRecord::Base.connection.execute("LOCK TABLE #{PERMISSION_VIEW}")
+    ActiveRecord::Base.connection.execute("DELETE FROM #{PERMISSION_VIEW}")
+    ActiveRecord::Base.connection.execute %{
+INSERT INTO #{PERMISSION_VIEW}
+select users.uuid, g.target_uuid, g.val, g.traverse_owned
+from users, lateral search_permission_graph(users.uuid, 3) as g where g.val > 0
+},
+                                          "refresh_permission_view.do"
   end
 end
 
-def refresh_permission_view(async=false)
-  if async and Rails.configuration.API.AsyncPermissionsUpdateInterval > 0
-    exp = Rails.configuration.API.AsyncPermissionsUpdateInterval.seconds
-    need = false
-    Rails.cache.fetch('AsyncRefreshPermissionView', expires_in: exp) do
-      need = true
-    end
-    if need
-      # Schedule a new permission update and return immediately
-      Thread.new do
-        Thread.current.abort_on_exception = false
-        begin
-          sleep(exp)
-          Rails.cache.delete('AsyncRefreshPermissionView')
-          do_refresh_permission_view
-        rescue => e
-          Rails.logger.error "Updating permission view: #{e}\n#{e.backtrace.join("\n\t")}"
-        ensure
-          ActiveRecord::Base.connection.close
-        end
+def refresh_trashed
+  ActiveRecord::Base.connection.execute("DELETE FROM #{TRASHED_GROUPS}")
+  ActiveRecord::Base.connection.execute("INSERT INTO #{TRASHED_GROUPS} select * from compute_trashed()")
+end
+
+def update_permissions perm_origin_uuid, starting_uuid, perm_level, check=false
+  # Update a subset of the permission graph
+  # perm_level is the inherited permission
+  # perm_level is a number from 0-3
+  #   can_read=1
+  #   can_write=2
+  #   can_manage=3
+  #   call with perm_level=0 to revoke permissions
+  #
+  # 1. Compute set (group, permission) implied by traversing
+  #    graph starting at this group
+  # 2. Find links from outside the graph that point inside
+  # 3. For each starting uuid, get the set of permissions from the
+  #    materialized permission table
+  # 3. Delete permissions from table not in our computed subset.
+  # 4. Upsert each permission in our subset (user, group, val)
+
+  ActiveRecord::Base.connection.execute "LOCK TABLE #{PERMISSION_VIEW} in SHARE MODE"
+
+  ActiveRecord::Base.connection.exec_query "SET LOCAL enable_mergejoin to false;"
+
+  temptable_perms = "temp_perms_#{rand(2**64).to_s(10)}"
+  ActiveRecord::Base.connection.exec_query %{
+create temporary table #{temptable_perms} on commit drop
+as select * from compute_permission_subgraph($1, $2, $3)
+},
+                                           'update_permissions.select',
+                                           [[nil, perm_origin_uuid],
+                                            [nil, starting_uuid],
+                                            [nil, perm_level]]
+
+  ActiveRecord::Base.connection.exec_query "SET LOCAL enable_mergejoin to true;"
+
+  ActiveRecord::Base.connection.exec_delete %{
+delete from #{PERMISSION_VIEW} where
+  target_uuid in (select target_uuid from #{temptable_perms}) and
+  not exists (select 1 from #{temptable_perms}
+              where target_uuid=#{PERMISSION_VIEW}.target_uuid and
+                    user_uuid=#{PERMISSION_VIEW}.user_uuid and
+                    val>0)
+},
+                                        "update_permissions.delete"
+
+  ActiveRecord::Base.connection.exec_query %{
+insert into #{PERMISSION_VIEW} (user_uuid, target_uuid, perm_level, traverse_owned)
+  select user_uuid, target_uuid, val as perm_level, traverse_owned from #{temptable_perms} where val>0
+on conflict (user_uuid, target_uuid) do update set perm_level=EXCLUDED.perm_level, traverse_owned=EXCLUDED.traverse_owned;
+},
+                                           "update_permissions.insert"
+
+  if check and perm_level>0
+    check_permissions_against_full_refresh
+  end
+end
+
+
+def check_permissions_against_full_refresh
+  #
+  # For debugging, this checks contents of the
+  # incrementally-updated 'materialized_permission' against a
+  # from-scratch permission refresh.
+  #
+
+  q1 = ActiveRecord::Base.connection.exec_query %{
+select user_uuid, target_uuid, perm_level, traverse_owned from #{PERMISSION_VIEW}
+order by user_uuid, target_uuid
+}, "check_permissions_against_full_refresh.permission_table"
+
+  q2 = ActiveRecord::Base.connection.exec_query %{
+select users.uuid as user_uuid, g.target_uuid, g.val as perm_level, g.traverse_owned
+from users, lateral search_permission_graph(users.uuid, 3) as g where g.val > 0
+order by users.uuid, target_uuid
+}, "check_permissions_against_full_refresh.full_recompute"
+
+  if q1.count != q2.count
+    puts "Didn't match incremental+: #{q1.count} != full refresh-: #{q2.count}"
+  end
+
+  if q1.count > q2.count
+    q1.each_with_index do |r, i|
+      if r != q2[i]
+        puts "+#{r}\n-#{q2[i]}"
+        raise "Didn't match"
       end
-      true
     end
   else
-    do_refresh_permission_view
+    q2.each_with_index do |r, i|
+      if r != q1[i]
+        puts "+#{q1[i]}\n-#{r}"
+        raise "Didn't match"
+      end
+    end
   end
 end
diff --git a/services/api/test/fixtures/groups.yml b/services/api/test/fixtures/groups.yml
index 92a1ced528..22c999ecd7 100644
--- a/services/api/test/fixtures/groups.yml
+++ b/services/api/test/fixtures/groups.yml
@@ -60,6 +60,7 @@ testusergroup_admins:
   uuid: zzzzz-j7d0g-48foin4vonvc2at
   owner_uuid: zzzzz-tpzed-000000000000000
   name: Administrators of a subset of users
+  group_class: role
 
 aproject:
   uuid: zzzzz-j7d0g-v955i6s2oi1cbso
@@ -143,6 +144,7 @@ active_user_has_can_manage:
   uuid: zzzzz-j7d0g-ptt1ou6a9lxrv07
   owner_uuid: zzzzz-tpzed-d9tiejq69daie8f
   name: Active user has can_manage
+  group_class: project
 
 # Group for testing granting permission between users who share a group.
 group_for_sharing_tests:
@@ -343,4 +345,4 @@ trashed_on_next_sweep:
   trash_at: 2001-01-01T00:00:00Z
   delete_at: 2038-03-01T00:00:00Z
   is_trashed: false
-  modified_at: 2001-01-01T00:00:00Z
\ No newline at end of file
+  modified_at: 2001-01-01T00:00:00Z
diff --git a/services/api/test/fixtures/users.yml b/services/api/test/fixtures/users.yml
index 57633a3120..14630d9efa 100644
--- a/services/api/test/fixtures/users.yml
+++ b/services/api/test/fixtures/users.yml
@@ -418,3 +418,17 @@ double_redirects_to_active:
       organization: example.com
       role: Computational biologist
     getting_started_shown: 2015-03-26 12:34:56.789000000 Z
+
+has_can_login_permission:
+  owner_uuid: zzzzz-tpzed-000000000000000
+  uuid: zzzzz-tpzed-xabcdjxw79nv3jz
+  email: can-login-user@arvados.local
+  modified_by_client_uuid: zzzzz-ozdt8-teyxzyd8qllg11h
+  modified_by_user_uuid: zzzzz-tpzed-xurymjxw79nv3jz
+  first_name: Can_login
+  last_name: User
+  identity_url: https://can-login-user.openid.local
+  is_active: true
+  is_admin: false
+  modified_at: 2015-03-26 12:34:56.789000000 Z
+  username: can-login-user
diff --git a/services/api/test/functional/arvados/v1/groups_controller_test.rb b/services/api/test/functional/arvados/v1/groups_controller_test.rb
index 30ab89c7e2..2b5e8d5a9d 100644
--- a/services/api/test/functional/arvados/v1/groups_controller_test.rb
+++ b/services/api/test/functional/arvados/v1/groups_controller_test.rb
@@ -505,9 +505,19 @@ class Arvados::V1::GroupsControllerTest < ActionController::TestCase
 
   ### trashed project tests ###
 
-  [:active, :admin].each do |auth|
+  #
+  # The structure is
+  #
+  # trashed_project         (zzzzz-j7d0g-trashedproject1)
+  #   trashed_subproject    (zzzzz-j7d0g-trashedproject2)
+  #   trashed_subproject3   (zzzzz-j7d0g-trashedproject3)
+  #   zzzzz-xvhdp-cr5trashedcontr
+
+  [:active,
+   :admin].each do |auth|
     # project: to query,    to untrash,    is visible, parent contents listing success
-    [[:trashed_project,     [],                 false, true],
+    [
+     [:trashed_project,     [],                 false, true],
      [:trashed_project,     [:trashed_project], true,  true],
      [:trashed_subproject,  [],                 false, false],
      [:trashed_subproject,  [:trashed_project], true,  true],
diff --git a/services/api/test/integration/groups_test.rb b/services/api/test/integration/groups_test.rb
index eb97fc1f49..445670a3d5 100644
--- a/services/api/test/integration/groups_test.rb
+++ b/services/api/test/integration/groups_test.rb
@@ -193,11 +193,15 @@ class NonTransactionalGroupsTest < ActionDispatch::IntegrationTest
     assert_response :success
   end
 
-  test "create request with async=true defers permissions update" do
+  test "create request with async=true does not defer permissions update" do
     Rails.configuration.API.AsyncPermissionsUpdateInterval = 1 # second
     name = "Random group #{rand(1000)}"
     assert_equal nil, Group.find_by_name(name)
 
+    # Following the implementation of incremental permission updates
+    # (#16007) the async flag is now a no-op.  Permission changes are
+    # visible immediately.
+
     # Trigger the asynchronous permission update by using async=true parameter.
     post "/arvados/v1/groups",
       params: {
@@ -209,7 +213,7 @@ class NonTransactionalGroupsTest < ActionDispatch::IntegrationTest
       headers: auth(:active)
     assert_response 202
 
-    # The group exists on the database, but it's not accessible yet.
+    # The group exists in the database
     assert_not_nil Group.find_by_name(name)
     get "/arvados/v1/groups",
       params: {
@@ -218,7 +222,7 @@ class NonTransactionalGroupsTest < ActionDispatch::IntegrationTest
       },
       headers: auth(:active)
     assert_response 200
-    assert_equal 0, json_response['items_available']
+    assert_equal 1, json_response['items_available']
 
     # Wait a bit and try again.
     sleep(1)
diff --git a/services/api/test/performance/permission_test.rb b/services/api/test/performance/permission_test.rb
index a0605f97e7..0fea3b1350 100644
--- a/services/api/test/performance/permission_test.rb
+++ b/services/api/test/performance/permission_test.rb
@@ -40,7 +40,7 @@ class PermissionPerfTest < ActionDispatch::IntegrationTest
                    end
                  end
                end
-               User.invalidate_permissions_cache
+               refresh_permission_view
              end
            end)
     end
diff --git a/services/api/test/test_helper.rb b/services/api/test/test_helper.rb
index 5747a85cf5..12f729e338 100644
--- a/services/api/test/test_helper.rb
+++ b/services/api/test/test_helper.rb
@@ -2,6 +2,8 @@
 #
 # SPDX-License-Identifier: AGPL-3.0
 
+require 'refresh_permission_view'
+
 ENV["RAILS_ENV"] = "test"
 unless ENV["NO_COVERAGE_TEST"]
   begin
@@ -207,4 +209,5 @@ class ActionDispatch::IntegrationTest
 end
 
 # Ensure permissions are computed from the test fixtures.
-User.invalidate_permissions_cache
+refresh_permission_view
+refresh_trashed
diff --git a/services/api/test/unit/collection_test.rb b/services/api/test/unit/collection_test.rb
index bf1ba517eb..addea83062 100644
--- a/services/api/test/unit/collection_test.rb
+++ b/services/api/test/unit/collection_test.rb
@@ -1000,6 +1000,19 @@ class CollectionTest < ActiveSupport::TestCase
   test "delete referring links in SweepTrashedObjects" do
     uuid = collections(:trashed_on_next_sweep).uuid
     act_as_system_user do
+      assert_raises ActiveRecord::RecordInvalid do
+        # Cannot create because :trashed_on_next_sweep is already trashed
+        Link.create!(head_uuid: uuid,
+                     tail_uuid: system_user_uuid,
+                     link_class: 'whatever',
+                     name: 'something')
+      end
+
+      # Bump trash_at to now + 1 minute
+      Collection.where(uuid: uuid).
+        update(trash_at: db_current_time + (1).minute)
+
+      # Not considered trashed now
       Link.create!(head_uuid: uuid,
                    tail_uuid: system_user_uuid,
                    link_class: 'whatever',
diff --git a/services/api/test/unit/owner_test.rb b/services/api/test/unit/owner_test.rb
index 528c6d253f..2bdc198a35 100644
--- a/services/api/test/unit/owner_test.rb
+++ b/services/api/test/unit/owner_test.rb
@@ -70,8 +70,12 @@ class OwnerTest < ActiveSupport::TestCase
              "new #{o_class} should really be in DB")
       old_uuid = o.uuid
       new_uuid = o.uuid.sub(/..........$/, rand(2**256).to_s(36)[0..9])
-      assert(o.update_attributes(uuid: new_uuid),
-             "should change #{o_class} uuid from #{old_uuid} to #{new_uuid}")
+      if o.respond_to? :update_uuid
+        o.update_uuid(new_uuid: new_uuid)
+      else
+        assert(o.update_attributes(uuid: new_uuid),
+               "should change #{o_class} uuid from #{old_uuid} to #{new_uuid}")
+      end
       assert_equal(false, o_class.where(uuid: old_uuid).any?,
                    "#{old_uuid} should disappear when renamed to #{new_uuid}")
     end
@@ -116,8 +120,8 @@ class OwnerTest < ActiveSupport::TestCase
                  "setting owner to self should work")
     old_uuid = o.uuid
     new_uuid = o.uuid.sub(/..........$/, rand(2**256).to_s(36)[0..9])
-    assert(o.update_attributes(uuid: new_uuid),
-           "should change uuid of User that owns self")
+    o.update_uuid(new_uuid: new_uuid)
+    o = User.find_by_uuid(new_uuid)
     assert_equal(false, User.where(uuid: old_uuid).any?,
                  "#{old_uuid} should not be in DB after deleting")
     assert_equal(true, User.where(uuid: new_uuid).any?,
diff --git a/services/api/test/unit/user_test.rb b/services/api/test/unit/user_test.rb
index 260795c12f..5d25361eda 100644
--- a/services/api/test/unit/user_test.rb
+++ b/services/api/test/unit/user_test.rb
@@ -165,7 +165,12 @@ class UserTest < ActiveSupport::TestCase
 
       if auto_admin_first_user_config
         # This test requires no admin users exist (except for the system user)
-        users(:admin).delete
+        act_as_system_user do
+          users(:admin).update_attributes!(is_admin: false)
+        end
+        # need to manually call clear_permissions because we used 'delete' instead of 'destory'
+        # we use delete here because 'destroy' will throw an error
+        #users(:admin).clear_permissions
         @all_users = User.where("uuid not like '%-000000000000000'").where(:is_admin => true)
         assert_equal 0, @all_users.count, "No admin users should exist (except for the system user)"
       end