Long and Complex MySQL hierarchical Nested Set model optimization for NIST level 2 RBAC

Implemented NIST Level 2 RBAC for jFramework, The core SQL is listed below :

"SELECT COUNT(*) AS Result
    FROM /* Version 2.05 */ 
        `".reg("jf/users/table/name")."` AS TU
    JOIN `".reg("jf/rbac/tables/RoleUsers/table/name")."` AS TUrel ON (TU.`".reg("jf/users/table/UserID")."`=TUrel.`".reg("jf/rbac/tables/RoleUsers/table/UserID")."`)

    JOIN `".reg("jf/rbac/tables/Roles/table/name")."` AS TRdirect ON (TRdirect.`".reg("jf/rbac/tables/Roles/table/RoleID")."`=TUrel.`".reg("jf/rbac/tables/RoleUsers/table/RoleID")."`) 
    JOIN `".reg("jf/rbac/tables/Roles/table/name")."` AS TR ON ( TR.`".reg("jf/rbac/tables/Roles/table/RoleLeft")."` BETWEEN TRdirect.`".reg("jf/rbac/tables/Roles/table/RoleLeft")."` AND TRdirect.`".reg("jf/rbac/tables/Roles/table/RoleRight").开发者_StackOverflow社区"`)
    /* we join direct roles with indirect roles to have all descendants of direct roles */
    JOIN 
    (   `".reg("jf/rbac/tables/Permissions/table/name")."` AS TPdirect 
        JOIN `".reg("jf/rbac/tables/Permissions/table/name")."` AS TP ON ( TPdirect.`".reg("jf/rbac/tables/Permissions/table/PermissionLeft")."` BETWEEN TP.`".reg("jf/rbac/tables/Permissions/table/PermissionLeft")."` AND TP.`".reg("jf/rbac/tables/Permissions/table/PermissionRight")."`)
    /* direct and indirect permissions */
        JOIN `".reg("jf/rbac/tables/RolePermissions/table/name")."` AS TRel ON (TP.`".reg("jf/rbac/tables/Permissions/table/PermissionID")."`=TRel.`".reg("jf/rbac/tables/RolePermissions/table/PermissionID")."`)
    /* joined with role/permissions on roles that are in relation with these permissions*/
    ) ON ( TR.`".reg("jf/rbac/tables/Roles/table/RoleID")."` = TRel.`".reg("jf/rbac/tables/RolePermissions/table/RoleID")."`)
    WHERE 
        TU.`".reg("jf/users/table/UserID")."`=? 
    AND
        TPdirect.{$PermissionCondition}"

This is intended to check if a certain user has a certain permission, and works. I want to know if it can be optimized since it's used very frequently along the application and is relied upon heavily.

The model is :

users : ID,Username,Password
roles : ID,Title,Description, Left , Right (left and right for the nested set model)
permissions : ID,Title,Description , Left , Right
role_permissions : RoleID,PermissionID,AssignmentDate
user_roles : UserID,RoleID

Keep in mind that both roles and permissions tables are hierarchical. So if someone has a role, he/she also has all the descendant roles.

If someone has a permission, he/she also has all the descendant permissions.

Can anyone help me? I know this is a huge one, And i'm going to put big bounty on it.

If you're sticking with nested sets then the following wont be of any use to you but if you're willing to consider using the adjacency list method the following simple example might be of interest.

Full script can be found here : http://pastie.org/1720133

I've provided 2 stored procedures. The first takes a role_id and outputs a list of permissions granted to that role and it's descendants:

mysql> call list_role_permissions(99); -- root role
+---------+---------+-----------+-----------------+
| role_id | perm_id | role_name | permission_name |
+---------+---------+-----------+-----------------+
|      99 |       5 | root      | create forum    |
|       3 |       4 | admin     | move forum      |
|       2 |       3 | moderator | edit post       |
|       1 |       2 | member    | create post     |
|       0 |       1 | guest     | view post       |
+---------+---------+-----------+-----------------+
5 rows in set (0.00 sec)

mysql> call list_role_permissions(2); -- moderator role
+---------+---------+-----------+-----------------+
| role_id | perm_id | role_name | permission_name |
+---------+---------+-----------+-----------------+
|       2 |       3 | moderator | edit post       |
|       1 |       2 | member    | create post     |
|       0 |       1 | guest     | view post       |
+---------+---------+-----------+-----------------+
3 rows in set (0.00 sec)

The second takes a user_id and outputs a list of permissions granted to that user's roles:

mysql> call list_user_role_permissions(1); -- root user
+---------+---------+-----------+-----------------+
| role_id | perm_id | role_name | permission_name |
+---------+---------+-----------+-----------------+
|      99 |       5 | root      | create forum    |
|       3 |       4 | admin     | move forum      |
|       2 |       3 | moderator | edit post       |
|       1 |       2 | member    | create post     |
|       0 |       1 | guest     | view post       |
+---------+---------+-----------+-----------------+
5 rows in set (0.00 sec)

 mysql> call list_user_role_permissions(3); -- moderator user
+---------+---------+-----------+-----------------+
| role_id | perm_id | role_name | permission_name |
+---------+---------+-----------+-----------------+
|       2 |       3 | moderator | edit post       |
|       1 |       2 | member    | create post     |
|       0 |       1 | guest     | view post       |
+---------+---------+-----------+-----------------+
3 rows in set (0.00 sec)

If you're concerned about performance of the adjacency list you can check the results of this approach using a 5 million row Yahoo GeoPlanet example I did earlier this month:

Generating Depth based tree from Hierarchical Data in MySQL (no CTEs)

Hope this helps (just ignore if you're stuck on the nested sets path)

Rgds...

Tables

drop table if exists roles;
create table roles
(
role_id tinyint unsigned not null primary key,
name varchar(255) unique not null,
parent_role_id tinyint unsigned,
key (parent_role_id)
)engine=innodb;

drop table if exists users;
create table users
(
user_id int unsigned not null auto_increment primary key,
username varchar(32) unique not null
)engine=innodb;

drop table if exists user_roles;
create table user_roles
(
user_id int unsigned not null,
role_id tinyint unsigned not null,
primary key (user_id, role_id)
)engine=innodb;

drop table if exists permissions;
create table permissions
(
perm_id smallint unsigned not null auto_increment primary key,
name varchar(255) unique not null
)engine=innodb;

drop table if exists role_permissions;
create table role_permissions
(
role_id tinyint unsigned not null,
perm_id smallint unsigned not null,
primary key (role_id, perm_id)
)engine=innodb;

Stored procedures

drop procedure if exists list_role_permissions;

delimiter #

create procedure list_role_permissions
(
in p_role_id tinyint unsigned
)
proc_main:begin

declare done tinyint unsigned default 0;
declare dpth smallint unsigned default 0;

create temporary table hier(
 parent_role_id tinyint unsigned, 
 role_id tinyint unsigned, 
 depth smallint unsigned default 0
)engine = memory;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

insert into hier select parent_role_id, role_id, dpth from roles where role_id = p_role_id;
create temporary table tmp engine=memory select * from hier;

while not done do

    if exists( select 1 from roles r inner join tmp on r.parent_role_id = tmp.role_id and tmp.depth = dpth) then

    insert into hier select r.parent_role_id, r.role_id, dpth + 1 from roles r
            inner join tmp on r.parent_role_id = tmp.role_id and tmp.depth = dpth;

    set dpth = dpth+1;          
        truncate table tmp;
        insert into tmp select * from hier where depth = dpth;
    else
        set done = 1;
    end if;
end while;

select
 rp.*,
 r.name as role_name,
 p.name as permission_name
from
 role_permissions rp
inner join hier h on h.role_id = rp.role_id
inner join permissions p on rp.perm_id = p.perm_id
inner join roles r on rp.role_id = r.role_id
order by
 rp.role_id desc;

drop temporary table if exists hier;
drop temporary table if exists tmp;

end proc_main #

delimiter ;

drop procedure if exists list_user_role_permissions;

delimiter #

create procedure list_user_role_permissions
(
in p_user_id int unsigned
)
proc_main:begin

declare done tinyint unsigned default 0;
declare dpth smallint unsigned default 0;

create temporary table hier(
 parent_role_id tinyint unsigned, 
 role_id tinyint unsigned, 
 depth smallint unsigned default 0
)engine = memory;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

insert into hier select r.parent_role_id, r.role_id, dpth from roles r 
    inner join user_roles ur on ur.user_id = p_user_id and ur.role_id = r.role_id;

create temporary table tmp engine=memory select * from hier;

while not done do

    if exists( select 1 from roles r inner join tmp on r.parent_role_id = tmp.role_id and tmp.depth = dpth) then

    insert into hier select r.parent_role_id, r.role_id, dpth + 1 from roles r
            inner join tmp on r.parent_role_id = tmp.role_id and tmp.depth = dpth;

    set dpth = dpth+1;          
        truncate table tmp;
        insert into tmp select * from hier where depth = dpth;
    else
        set done = 1;
    end if;
end while;

select distinct
 rp.*,
 r.name as role_name,
 p.name as permission_name
from
 role_permissions rp
inner join hier h on h.role_id = rp.role_id
inner join permissions p on rp.perm_id = p.perm_id
inner join roles r on rp.role_id = r.role_id
order by
 rp.role_id desc;

drop temporary table if exists hier;
drop temporary table if exists tmp;

end proc_main #

delimiter ;

Test Data and Testing

insert into roles values 
(99,'root',null),
 (3,'admin',99),
  (2,'moderator',3),
   (1,'member',2),
    (0,'guest',1);

insert into users (username) values 
('f00'),('bar'),('alpha'),('beta'),('gamma');

insert into user_roles values
(1,99), -- (1,1),
(2,3), -- (2,2),(2,1),
(3,2), -- (3,1),
(4,1),
(5,0);

insert into permissions (name) values 
('view post'), ('create post'), ('edit post'), ('move forum'), ('create forum');

insert into role_permissions values 
-- guest
(0,1),
-- member
(1,2),
-- moderator
(2,3),
-- admin
(3,4),
-- root
(99,5);

call list_role_permissions(99); -- root role
call list_role_permissions(3); -- admin role
call list_role_permissions(2); -- moderator role
call list_role_permissions(1); -- member role
call list_role_permissions(0); -- guest role

call list_user_role_permissions(1); -- root user
call list_user_role_permissions(2); -- admin user
call list_user_role_permissions(3); -- moderator user
call list_user_role_permissions(4); -- member user
call list_user_role_permissions(5); -- guest user