Some observations on the scalability of the OpenACS 4 Permissions system

One of the key components of the OpenACS 4 toolkit is the general permissions facility. The permissions facility provides an extremely flexible and easy to use mechanism for controlling user actions on objects.

However experience has shown that checking to see if a user has permission to perform a particular action on a particular object rapidly becomes extremely expensive as the number of users and objects in the system becomes moderately large. This is exacerbated if groups and relational segments (subsets of groups) are used to grant permissions to sets of users based on group membership.

This document provides some hard data that shows how poorly the current general permissions system performs when non-trivial amounts of data are involved.

It also provides encouraging data demonstrating that we may be able to increase the performance of permissions to acceptable levels.

I've included results for both the PostgreSQL and Oracle versions.

Platform

laptop with a 500 MHz Celeron, 389 MB SDRAM, 4200 RPM disk
RedHat 6.2
PostgreSQL 7.2.3
OpenACS 4.6 core

Data

I wrote a small "populate" package that allows one to easily fill an OpenACS 4 instance with large amounts of test data. The pertinent numbers:

Table Rows (PostgreSQL) Rows (Oracle)

acs_objects 39,069 48,744

users 1,102 921

groups 292 278

rel_segments 703 539

average users per rel_segment 50 50

fs_files 2,030 3870

acs_privileges 16 6

acs_permissions 12,601 14387

party_member_map 33,432 46199

Table	Rows (PostgreSQL)	Rows (Oracle)
acs_objects	39,069	48,744
users	1,102	921
groups	292	278
rel_segments	703	539
average users per rel_segment	50	50
fs_files	2,030	3870
acs_privileges	16	6
acs_permissions	12,601	14387
party_member_map	33,432	46199

I didn't bother to set up the same dataset for Oracle and PostgreSQL, mostly because I populated the two databases while fine-tuning my "populate" package and generating large amounts of content is a relatively slow process I didn't care to repeat.

PostgreSQL results

Here is a sample query from file storage which grabs 100 files from folder 13164:

select fc.*
from (select fs_objects.object_id,
        fs_objects.name,
        fs_objects.live_revision,
        fs_objects.type,
        to_char(fs_objects.last_modified, 'YYYY-MM-DD HH24:MI:SS') as last_modified,
        fs_objects.content_size,
        fs_objects.url,
        fs_objects.key,
        fs_objects.sort_key,
        fs_objects.file_upload_name,
        case when fs_objects.last_modified >= (now() - interval '99999 days') then 1 else 0 end as new_p,
        acs_permission__permission_p(fs_objects.object_id, 2741, 'admin') as admin_p,
        acs_permission__permission_p(fs_objects.object_id, 2741, 'delete') as delete_p,
        acs_permission__permission_p(fs_objects.object_id, 2741, 'write') as write_p
      from fs_objects
      where fs_objects.parent_id = 13164) fc
where acs_permission__permission_p(fc.object_id, 2741, 'read')
order by fc.sort_key, fc.name;

Note that users might be granted privileges on a file or one of its parent folders directly, or that they might indirectly have a privilege on a file by virtue of belonging to a group which has been granted that privilege. The current implementation of acs_permission__permission_p checks for direct permissions first as these are faster, as can be seen in the data table which follows.

As an experiment I expanded the party_member_map view into a table, then created an index on the (party_id, member_id) pair. I then rewrote acs_permission__permission_p to use that table rather than individually check the group membership map and the relational segment membership map.

This version of acs_permission__permission_p is labelled "rewrite #1" in the data table below. As can be seen this slows down the case where a user has been granted a privilege slightly, but the case where a user is granted the privilege by virtue of group or relational segment membership is about 2.5 times faster.

I then rewrote further, causing the code to query the acs_permission_hierarchy_index and the acs_object_context_index tables directly. As implemented in the PostgreSQL version today, the acs_permission_hierarchy_index doesn't quite contain what we need but it is close enough for benchmarking purposes.

This version is labelled "rewrite #2" below. As can be seen the improvement over the current implementation seems to be quite dramatic. Comparing the query plan for my experimental approach vs. the OpenACS 4.6 approach the experimental approach would appear to scale much better as well.

Add to this the fact that expanding the party_member_map means we can eliminate the acs_object_party_privilege_map and all_object_party_privilege_map views. Before we can reimplement on this basis there are some problems to be solved, in particular how to map user 0 and privileges granted to "the world" (group -1).

The data in the table's been adjusted for the raw query overhead measured by removing the permissions checks altogether.

acs_permission__permission_p version	User gets privilege	Execution time (in seconds)	Time per permission check (in milliseconds)
N/A (raw query time)	N/A	0.4	N/A
OpenACS 4.6	Directly	7.2	18
Rewrite #1	Directly	7.9	19.75
Rewrite #2	Directly	2.5	6.25
OpenACS 4.6	Indirectly	33.1	83.5
Rewrite #1	Indirectly	13.4	33.5
Rewrite #2	Indirectly	4.4	11

Here's the query used in my second rewrite ("foo" is my index table generated from the party_member_map view):

explain
select exists (
  select 1
  from acs_permissions p,  acs_privilege_hierarchy_index h, foo f, acs_object_context_index c
  where p.object_id = c.ancestor_id
    and c.object_id = 13213
    and f.member_id = 2741
    and h.child_privilege = 'read'
    and p.privilege = h.privilege
    and p.grantee_id = f.party_id);

QUERY PLAN:

Result  (cost=0.00..0.01 rows=1 width=0)
  InitPlan
    ->  Nested Loop  (cost=1.29..163.96 rows=2 width=35)
          ->  Hash Join  (cost=1.29..129.94 rows=6 width=31)
                ->  Nested Loop  (cost=0.00..128.09 rows=28 width=20)
                      ->  Index Scan using acs_object_context_index_pk on acs_object_context_index c  (cost=0.00..18.93 rows=6 width=4)
                      ->  Index Scan using acs_permissions_pk on acs_permissions p  (cost=0.00..19.60 rows=5 width=16)
                ->  Hash  (cost=1.29..1.29 rows=2 width=11)
                      ->  Seq Scan on acs_privilege_hierarchy_index h  (cost=0.00..1.29 rows=2 width=11)
          ->  Index Scan using foo_idx on foo f  (cost=0.00..6.01 rows=1 width=4)

Here is the existing relational segment query in acs_permission__permission_p. Note that group perms are about as bad and returning 'f' from the function requires that all checks fail. So this is even worse than it looks ...

explain
select exists (
  select 1
  from acs_object_grantee_priv_map ogpm, rel_seg_approved_member_map rsmm
  where object_id = 13164
    and privilege = 'read'
    and rsmm.member_id = 2781
    and ogpm.grantee_id = rsmm.segment_id);

QUERY PLAN:

Result  (cost=0.00..0.01 rows=1 width=0)
  InitPlan
    ->  Nested Loop  (cost=157.97..1357.23 rows=2 width=149)
          ->  Hash Join  (cost=157.97..1344.15 rows=3 width=137)
                ->  Nested Loop  (cost=28.12..1211.82 rows=75 width=105)
                      ->  Hash Join  (cost=28.12..983.78 rows=75 width=101)
                            ->  Hash Join  (cost=25.47..962.50 rows=678 width=74)
                                  ->  Hash Join  (cost=2.65..926.92 rows=286 width=50)
                                        ->  Index Scan using group_elem_idx_element_idx on group_element_index  (cost=0.00..918.55 rows=286 width=23)
                                        ->  Hash  (cost=2.52..2.52 rows=52 width=27)
                                              ->  Seq Scan on acs_object_types o1  (cost=0.00..2.52 rows=52 width=27)
                                  ->  Hash  (cost=16.03..16.03 rows=703 width=24)
                                        ->  Seq Scan on rel_segments rs  (cost=0.00..16.03 rows=703 width=24)
                            ->  Hash  (cost=2.52..2.52 rows=52 width=27)
                                  ->  Seq Scan on acs_object_types o2  (cost=0.00..2.52 rows=52 width=27)
                      ->  Index Scan using membership_rel_rel_id_pk on membership_rels mr  (cost=0.00..3.02 rows=1 width=4)
                ->  Hash  (cost=129.78..129.78 rows=28 width=32)
                      ->  Hash Join  (cost=1.20..129.78 rows=28 width=32)
                            ->  Nested Loop  (cost=0.00..128.09 rows=28 width=20)
                                  ->  Index Scan using acs_object_context_index_pk on acs_object_context_index  (cost=0.00..18.93 rows=6 width=4)
                                  ->  Index Scan using acs_permissions_pk on acs_permissions p  (cost=0.00..19.60 rows=5 width=16)
                            ->  Hash  (cost=1.16..1.16 rows=16 width=12)
                                  ->  Seq Scan on acs_privileges p1  (cost=0.00..1.16 rows=16 width=12)
          ->  Seq Scan on acs_privileges p2  (cost=0.00..1.20 rows=1 width=12)
          SubPlan
            ->  Nested Loop  (cost=0.00..3.17 rows=1 width=34)
                  ->  Seq Scan on acs_privilege_hierarchy_index h1  (cost=0.00..1.29 rows=1 width=11)
                  ->  Seq Scan on acs_privilege_hierarchy_index h2  (cost=0.00..1.29 rows=1 width=23)

Oracle results

My file storage test case for Oracle returns 52 rows. Here's the query:

select fc.*
from (select fs_objects.object_id,
        fs_objects.name,
        fs_objects.live_revision,
        fs_objects.type,
        to_char(fs_objects.last_modified, 'YYYY-MM-DD HH24:MI:SS') as last_modified_ansi,
        fs_objects.content_size,
        fs_objects.url,
        fs_objects.key,
        fs_objects.sort_key,
        fs_objects.file_upload_name,
        case when fs_objects.last_modified >= (sysdate - 99999) then 1 else 0 end as new_p,
        acs_permission.permission_p(fs_objects.object_id, 2735, 'admin') as admin_p,
        acs_permission.permission_p(fs_objects.object_id, 2735, 'delete') as delete_p,
        acs_permission.permission_p(fs_objects.object_id, 2735, 'write') as write_p
      from fs_objects
      where fs_objects.parent_id = 45732) fc
where 't' = (select acs_permission.permission_p(fc.object_id, 2735, 'read') from dual)
order by fc.sort_key, fc.name;

In the table below, note that the OACS 4.6 Oracle version of permission_p seems to be much slower for direct rather than indirect permissions. This is the opposite of what was seen for PostgreSQL. I have no explanation for this but tested several times. Each query returns the same number of rows (52).

The data in the table's been adjusted for the raw query overhead measured by removing the permissions checks altogether.

Good news

I expanded the party_member_map view into a table as was done for PostgreSQL earlier. As can be seen below the results are stunning. The query with four permission checks per row takes less than twice as long as the query with no permission checks at all, and permission checking takes a very respectable 2.4 milliseconds per row on our test dataset.

acs_permission__permission_p version User gets privilege Execution time (in seconds) Time per permission check (in milliseconds)

N/A (raw query time) N/A 0.55 N/A

OpenACS 4.6 Directly 31.7 152

Rewrite #1 Directly 0.5 2.4

OpenACS 4.6 Indirectly 4.75 22.8

Rewrite #1 Indirectly 0.5 2.4

acs_permission__permission_p version	User gets privilege	Execution time (in seconds)	Time per permission check (in milliseconds)
N/A (raw query time)	N/A	0.55	N/A
OpenACS 4.6	Directly	31.7	152
Rewrite #1	Directly	0.5	2.4
OpenACS 4.6	Indirectly	4.75	22.8
Rewrite #1	Indirectly	0.5	2.4