X-Git-Url: https://git.arvados.org/arvados.git/blobdiff_plain/b879b9cd18ddba6ba87b65f81eba676114478a06..1a599ec69ad8d533da1f12ad5d2c5789aa1c14e2:/services/api/db/structure.sql

diff --git a/services/api/db/structure.sql b/services/api/db/structure.sql
index eaa3d6299a..a8885f584a 100644
--- a/services/api/db/structure.sql
+++ b/services/api/db/structure.sql
@@ -45,7 +45,13 @@ CREATE EXTENSION IF NOT EXISTS pg_trgm WITH SCHEMA public;
 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 $$
-/* perm_origin_uuid: The object that 'gets' or 'has' the permission.
+
+/* The purpose of this function is to compute the permissions for a
+   subgraph of the database, starting from a given edge.  The newly
+   computed permissions are used to add and remove rows from the main
+   permissions table.
+
+   perm_origin_uuid: The object that 'gets' the permission.
 
    starting_uuid: The starting object the permission applies to.
 
@@ -53,103 +59,102 @@ CREATE FUNCTION public.compute_permission_subgraph(perm_origin_uuid character va
                   starting_uuid One of 1, 2, 3 for can_read,
                   can_write, can_manage respectively, or 0 to revoke
                   permissions.
-
-   This function is broken up into a number of clauses, described
-   below.
-
-   Note on query optimization:
-
-   Each clause in a "with" statement is called a "common table
-   expression" or CTE.
-
-   In Postgres, they are evaluated in sequence and results of each CTE
-   is stored in a temporary table.  This means Postgres does not
-   propagate constraints from later subqueries to earlier subqueries
-   when they are CTEs.
-
-   This is a problem if, for example, a later subquery chooses 10
-   items out of a set of 1000000 defined by an earlier subquery,
-   because it will always compute all 1000000 rows even if the query
-   on the 1000000 rows could have been constrained.  This is why
-   permission_graph_edges is a view -- views are inlined so and can be
-   optimized using external constraints.
-
-   The query optimizer does sort the temporary tables for later use in
-   joins.
-
-   Final note, this query would have been almost impossible to write
-   (and certainly impossible to read) without splitting it up using
-   SQL "with" but unfortunately it also stumbles into a frustrating
-   Postgres optimizer bug, see
-   lib/refresh_permission_view.rb#update_permissions
-   for details and a partial workaround.
 */
 with
-  /* Gets the initial set of objects potentially affected by the
-     permission change, using search_permission_graph.
+  /* Starting from starting_uuid, determine the set of objects that
+     could be affected by this permission change.
+
+     Note: We don't traverse users unless it is an "identity"
+     permission (permission origin is self).
   */
   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,
-                                   perm_origin_uuid,
-                                   starting_uuid,
-                                   starting_perm)),
-
-  /* Finds other inbound edges that grant permissions on the objects
-     in perm_from_start, and computes permissions that originate from
-     those.  This is required to handle the case where there is more
-     than one path through which a user gets permission to an object.
-     For example, a user owns a project and also shares it can_read
-     with a group the user belongs to, adding the can_read link must
-     not overwrite the existing can_manage permission granted by
-     ownership.
+    
+WITH RECURSIVE
+        traverse_graph(origin_uuid, target_uuid, val, traverse_owned, starting_set) as (
+            
+             values (perm_origin_uuid, starting_uuid, starting_perm,
+                    should_traverse_owned(starting_uuid, starting_perm),
+                    (perm_origin_uuid = starting_uuid or starting_uuid not like '_____-tpzed-_______________'))
+
+          union
+            (select traverse_graph.origin_uuid,
+                    edges.head_uuid,
+                      least(edges.val,
+                            traverse_graph.val
+                            ,
+                            case (edges.tail_uuid = perm_origin_uuid AND
+                                  edges.head_uuid = starting_uuid)
+                               when true then starting_perm
+                               else null
+                            end
+),
+                    should_traverse_owned(edges.head_uuid, edges.val),
+                    false
+             from permission_graph_edges as edges, traverse_graph
+             where traverse_graph.target_uuid = edges.tail_uuid
+             and (edges.tail_uuid like '_____-j7d0g-_______________' or
+                  traverse_graph.starting_set)))
+        select traverse_graph.origin_uuid, target_uuid, max(val) as val, bool_or(traverse_owned) as traverse_owned from traverse_graph
+        group by (traverse_graph.origin_uuid, target_uuid)
+),
+
+  /* Find other inbound edges that grant permissions to 'targets' in
+     perm_from_start, and compute permissions that originate from
+     those.
+
+     This is necessary for two reasons:
+
+       1) Other users may have access to a subset of the objects
+       through other permission links than the one we started from.
+       If we don't recompute them, their permission will get dropped.
+
+       2) There may be more than one path through which a user gets
+       permission to an object.  For example, a user owns a project
+       and also shares it can_read with a group the user belongs
+       to. adding the can_read link must not overwrite the existing
+       can_manage permission granted by ownership.
   */
   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,
-                                           perm_origin_uuid,
-                                           starting_uuid,
-                                           starting_perm) as ps
+    
+WITH RECURSIVE
+        traverse_graph(origin_uuid, target_uuid, val, traverse_owned, starting_set) as (
+            
+    select edges.tail_uuid as origin_uuid, edges.head_uuid as target_uuid, edges.val,
+           should_traverse_owned(edges.head_uuid, edges.val),
+           edges.head_uuid like '_____-j7d0g-_______________'
+      from permission_graph_edges as edges
       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)),
+                  edges.head_uuid = starting_uuid)) and
+            edges.tail_uuid not in (select target_uuid from perm_from_start where target_uuid like '_____-j7d0g-_______________') and
+            edges.head_uuid in (select target_uuid from perm_from_start)
 
-  /* Combines the permissions computed in the first two phases. */
-  partial_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+          union
+            (select traverse_graph.origin_uuid,
+                    edges.head_uuid,
+                      least(edges.val,
+                            traverse_graph.val
+                            ,
+                            case (edges.tail_uuid = perm_origin_uuid AND
+                                  edges.head_uuid = starting_uuid)
+                               when true then starting_perm
+                               else null
+                            end
+),
+                    should_traverse_owned(edges.head_uuid, edges.val),
+                    false
+             from permission_graph_edges as edges, traverse_graph
+             where traverse_graph.target_uuid = edges.tail_uuid
+             and (edges.tail_uuid like '_____-j7d0g-_______________' or
+                  traverse_graph.starting_set)))
+        select traverse_graph.origin_uuid, target_uuid, max(val) as val, bool_or(traverse_owned) as traverse_owned from traverse_graph
+        group by (traverse_graph.origin_uuid, target_uuid)
+),
+
+  /* Combine the permissions computed in the first two phases. */
+  all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
       select * from perm_from_start
     union all
       select * from additional_perms
-  ),
-
-  /* If there are any users in the set of potentially affected objects
-     and the user's owner was not traversed, recompute permissions for
-     that user.  This is required because users always have permission
-     to themselves (identity property) which would be missing from the
-     permission set if the user was traversed while computing
-     permissions for another object.
-  */
-  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,
-                                                  perm_origin_uuid,
-                                                  starting_uuid,
-                                                  starting_perm) 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)
-  ),
-
-  /* Combines all the computed permissions into one table. */
-  all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
-      select * from partial_perms
-    union
-      select * from user_identity_perms
   )
 
   /* The actual query that produces rows to be added or removed
@@ -158,30 +163,27 @@ with
 
      Key insights:
 
-     * Permissions are transitive (with some special cases involving
-       users, this is controlled by the traverse_owned flag).
+     * For every group, the materialized_permissions lists all users
+       that can access to that group.
+
+     * The all_perms subquery has computed permissions on on a set of
+       objects for all inbound "origins", which are users or groups.
 
-     * A user object can only gain permissions via an inbound edge,
-       or appearing in the graph.
+     * Permissions through groups are transitive.
 
-     * The materialized_permissions table includes the permission
-       each user has on the tail end of each inbound edge.
+     We can infer:
 
-     * The all_perms subquery has permissions for each object in the
-       subgraph reachable from certain origin (tail end of an edge).
+     1) The materialized_permissions table declares that user X has permission N on group Y
+     2) The all_perms result has determined group Y has permission M on object Z
+     3) Therefore, user X has permission min(N, M) on object Z
 
-     * Therefore, for each user, we can compute user permissions on
-       each object in subgraph by determining the permission the user
-       has on each origin (tail end of an edge), joining that with the
-       perm_origin_uuid column of all_perms, and taking the least() of
-       the origin edge or all_perms val (because of the "least
-       permission on the path" rule).  If an object was reachable by
-       more than one path (appears with more than one origin), we take
-       the max() of the computed permissions.
+     This allows us to efficiently determine the set of users that
+     have permissions on the subset of objects, without having to
+     follow the chain of permission back up to find those users.
 
-     * Finally, because users always have permission on themselves, the
-       query also makes sure those permission rows are always
-       returned.
+     In addition, because users always have permission on themselves, this
+     query also makes sure those permission rows are always
+     returned.
   */
   select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
     (select m.user_uuid,
@@ -190,31 +192,15 @@ with
          u.traverse_owned
       from all_perms as u, materialized_permissions as m
            where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
+           AND (m.user_uuid = m.target_uuid or m.target_uuid not like '_____-tpzed-_______________')
     union all
-      select perm_origin_uuid as user_uuid, target_uuid, val as perm_level, traverse_owned
+      select target_uuid as user_uuid, target_uuid, 3, true
         from all_perms
-        where all_perms.perm_origin_uuid like '_____-tpzed-_______________') as v
+        where all_perms.target_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 $$
-/* Helper function to populate trashed_groups table. This starts with
-   each group owned by a user and computes the subtree under that
-   group to find any groups that are trashed.
-*/
-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: -
 --
@@ -242,63 +228,6 @@ WITH RECURSIVE
 $$;
 
 
---
--- Name: search_permission_graph(character varying, integer, character varying, character varying, integer); Type: FUNCTION; Schema: public; Owner: -
---
-
-CREATE FUNCTION public.search_permission_graph(starting_uuid character varying, starting_perm integer, override_edge_tail character varying DEFAULT NULL::character varying, override_edge_head character varying DEFAULT NULL::character varying, override_edge_perm integer DEFAULT NULL::integer) RETURNS TABLE(target_uuid character varying, val integer, traverse_owned boolean)
-    LANGUAGE sql STABLE
-    AS $$
-/*
-  From starting_uuid, perform a recursive self-join on the edges
-  to follow chains of permissions.  This is a breadth-first search
-  of the permission graph.  Permission is propagated across edges,
-  which may narrow the permission for subsequent links (eg I start
-  at can_manage but when traversing a can_read link everything
-  touched through that link will only be can_read).
-
-  When revoking a permission, we follow the chain of permissions but
-  with a permissions level of 0.  The update on the permissions table
-  has to happen _before_ the permission is actually removed, because
-  we need to be able to traverse the edge before it goes away.  When
-  we do that, we also need to traverse it at the _new_ permission
-  level - this is what override_edge_tail/head/perm are for.
-
-  Yields the set of objects that are potentially affected, and
-  their permission levels granted by having starting_perm on
-  starting_uuid.
-
-  If starting_uuid is a user, this computes the entire set of
-  permissions for that user (because it returns everything that is
-  reachable by that user).
-
-  Used by the compute_permission_subgraph function.
-*/
-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,
-                            case (edges.tail_uuid = override_edge_tail AND
-                                  edges.head_uuid = override_edge_head)
-                               when true then override_edge_perm
-                               else null
-                            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: -
 --
@@ -1092,6 +1021,11 @@ UNION ALL
     users.uuid AS head_uuid,
     3 AS val
    FROM public.users
+UNION ALL
+ SELECT users.uuid AS tail_uuid,
+    users.uuid AS head_uuid,
+    3 AS val
+   FROM public.users
 UNION ALL
  SELECT links.tail_uuid,
     links.head_uuid,
@@ -1100,7 +1034,7 @@ UNION ALL
             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
+            ELSE 0
         END AS val
    FROM public.links
   WHERE ((links.link_class)::text = 'permission'::text);
