CODEWITHSUNDEEP
mysqlsql
Billy ONeal
Billy ONeal

Reputation: 106549

Help improve this SQL UNION query

Alright, I've got an access control list system which mimics NT DACLs. Basically, I've got users, groups, a membership mapping between them, and ACLs with any number of ACEs referencing users or groups.

(For example, this lets the "Marketing Department" group access to something, but Joe who works in marketing is a problem child, so you could deny him access to that something, and he would be denied, but everyone else in the group would be allowed)

I need to enumerate a list of objects which are controlled by a given ACL -- in this case, the "controlled objects" are the user objects themselves. For example, let's say user Bob (with uid=1) wants to delete another user from the system, and I want a list of users to show Bob on which he may perform that action. If a user (denoted here by the WHERE usr.id = 1 (the "1" would be cached by the PHP app this is being embedded into)) has access to the given object, I want to show it, and if (s)he does not, then it shouldn't exist in the result set.

Here's the best I've come up with so far:

SELECT `acelist`.id, `acelist`.first_name, `acelist`.last_name, `acelist`.acl
FROM
(
  (
    SELECT `usResult`.id, `usResult`.first_name, `usResult`.last_name, `usResult`.acl, `ace`.`allowed`
    FROM `user` usResult
    INNER JOIN access_control_list acl ON usResult.acl = acl.id
    INNER JOIN group_access_control_entry ace ON acl.id = ace.acl
    INNER JOIN `group` gp ON ace.gid = gp.id
    INNER JOIN group_membership ON gp.id = group_membership.gid
    INNER JOIN `user` usr ON group_membership.uid = usr.id
    WHERE usr.id = 1
  )
  UNION ALL
  (
    SELECT `usResult`.id, `usResult`.first_name, `usResult`.last_name, `usResult`.acl, `ace`.`allowed`
    FROM `user` usResult
    INNER JOIN access_control_list acl ON usResult.acl = acl.id
    INNER JOIN user_access_control_entry ace ON acl.id = ace.acl
    INNER JOIN `user` usr ON ace.uid = usr.id
    WHERE usr.id = 1
  )
) AS acelist
GROUP BY `acelist`.id
HAVING COUNT(acelist.allowed) = SUM(acelist.allowed)

And here's the schema I'm working with:

# Generated by Propel ORM
# This is a fix for InnoDB in MySQL >= 4.1.x
# It "suspends judgement" for fkey relationships until are tables are set.
SET FOREIGN_KEY_CHECKS = 0;

-- ---------------------------------------------------------------------
-- user
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `user`;

CREATE TABLE `user`
(
    `id` INTEGER NOT NULL,
    `first_name` VARCHAR(255) NOT NULL,
    `last_name` VARCHAR(255) NOT NULL,
    `direct_login` INTEGER,
    `acl` INTEGER NOT NULL,
    PRIMARY KEY (`id`),
    INDEX `user_FI_1` (`acl`),
    CONSTRAINT `user_FK_1`
        FOREIGN KEY (`acl`)
        REFERENCES `access_control_list` (`id`)
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- case_id_user
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `case_id_user`;

CREATE TABLE `case_id_user`
(
    `uid` INTEGER NOT NULL,
    `case_id` VARCHAR(8),
    PRIMARY KEY (`uid`),
    UNIQUE INDEX `case_id_user_U_1` (`case_id`),
    CONSTRAINT `case_id_user_FK_1`
        FOREIGN KEY (`uid`)
        REFERENCES `user` (`id`)
        ON UPDATE CASCADE
        ON DELETE CASCADE
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- direct_login_user
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `direct_login_user`;

CREATE TABLE `direct_login_user`
(
    `uid` INTEGER NOT NULL,
    `passhash` CHAR(60) NOT NULL,
    `email` VARCHAR(255) NOT NULL,
    `user_name` VARCHAR(45) NOT NULL,
    PRIMARY KEY (`uid`),
    UNIQUE INDEX `direct_login_user_U_1` (`user_name`),
    CONSTRAINT `direct_login_user_FK_1`
        FOREIGN KEY (`uid`)
        REFERENCES `user` (`id`)
        ON UPDATE CASCADE
        ON DELETE CASCADE
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- group
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `group`;

CREATE TABLE `group`
(
    `id` INTEGER NOT NULL,
    `name` VARCHAR(45) NOT NULL,
    `description` TEXT NOT NULL,
    `acl` INTEGER NOT NULL,
    PRIMARY KEY (`id`),
    UNIQUE INDEX `group_U_1` (`name`),
    INDEX `group_FI_1` (`acl`),
    CONSTRAINT `group_FK_1`
        FOREIGN KEY (`acl`)
        REFERENCES `access_control_list` (`id`)
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- privilege
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `privilege`;

CREATE TABLE `privilege`
(
    `id` INTEGER NOT NULL AUTO_INCREMENT,
    `name` VARCHAR(45) NOT NULL,
    PRIMARY KEY (`id`),
    UNIQUE INDEX `privilege_U_1` (`name`)
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- access_control_list
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `access_control_list`;

CREATE TABLE `access_control_list`
(
    `id` INTEGER NOT NULL AUTO_INCREMENT,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- user_access_control_entry
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `user_access_control_entry`;

CREATE TABLE `user_access_control_entry`
(
    `acl` INTEGER NOT NULL,
    `uid` INTEGER NOT NULL,
    `privilege_id` INTEGER NOT NULL,
    `allowed` TINYINT NOT NULL,
    PRIMARY KEY (`acl`,`uid`,`privilege_id`,`allowed`),
    INDEX `user_access_control_entry_FI_1` (`privilege_id`),
    INDEX `user_access_control_entry_FI_2` (`uid`),
    CONSTRAINT `user_access_control_entry_FK_1`
        FOREIGN KEY (`privilege_id`)
        REFERENCES `privilege` (`id`)
        ON UPDATE CASCADE
        ON DELETE CASCADE,
    CONSTRAINT `user_access_control_entry_FK_2`
        FOREIGN KEY (`uid`)
        REFERENCES `user` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE,
    CONSTRAINT `user_access_control_entry_FK_3`
        FOREIGN KEY (`acl`)
        REFERENCES `access_control_list` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- group_access_control_entry
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `group_access_control_entry`;

CREATE TABLE `group_access_control_entry`
(
    `acl` INTEGER NOT NULL,
    `gid` INTEGER NOT NULL,
    `privilege_id` INTEGER NOT NULL,
    `allowed` TINYINT NOT NULL,
    PRIMARY KEY (`acl`,`gid`,`privilege_id`,`allowed`),
    INDEX `group_access_control_entry_FI_1` (`privilege_id`),
    INDEX `group_access_control_entry_FI_2` (`gid`),
    CONSTRAINT `group_access_control_entry_FK_1`
        FOREIGN KEY (`privilege_id`)
        REFERENCES `privilege` (`id`)
        ON UPDATE CASCADE
        ON DELETE CASCADE,
    CONSTRAINT `group_access_control_entry_FK_2`
        FOREIGN KEY (`gid`)
        REFERENCES `group` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE,
    CONSTRAINT `group_access_control_entry_FK_3`
        FOREIGN KEY (`acl`)
        REFERENCES `access_control_list` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE
) ENGINE=InnoDB;

-- ---------------------------------------------------------------------
-- group_membership
-- ---------------------------------------------------------------------

DROP TABLE IF EXISTS `group_membership`;

CREATE TABLE `group_membership`
(
    `uid` INTEGER NOT NULL,
    `gid` INTEGER NOT NULL,
    PRIMARY KEY (`uid`,`gid`),
    INDEX `group_membership_FI_2` (`gid`),
    CONSTRAINT `group_membership_FK_1`
        FOREIGN KEY (`uid`)
        REFERENCES `user` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE,
    CONSTRAINT `group_membership_FK_2`
        FOREIGN KEY (`gid`)
        REFERENCES `group` (`id`)
        ON UPDATE RESTRICT
        ON DELETE CASCADE
) ENGINE=InnoDB;

# This restores the fkey checks, after having unset them earlier
SET FOREIGN_KEY_CHECKS = 1;

Do any of the SQL gurus here see anything I might do to either simplify the query, or to make it execute more quickly?

EDIT: Ideally, I'd somehow be able to make the complicated bits of this work for any ACL'd object so that I could avoid having to write a query like this for every ACL'd object in the database....

Upvotes: 1

Views: 243

Answers (2)

Unreason
Unreason

Reputation: 12704

Depending on the number of your users and the frequency of authorised actions you might want to consider caching the whole permission subtree for a specific user.

You can insist on ACID cache by keeping track of last time when the permissions tables had been updated and this gives you a quick query that can detect if the slower one needs to run.

Otherwise you queries look ok; I don't like the COUNT(allowed) = SUM(allowed) to establish that there are no zeros. The NOT EXIST variant should be able to optimize compared to this approach which must calculate COUNT() and SUM() over all records. However assuming sane data distribution I would expect much larger win factor for caching the permissions.

Upvotes: 0

Lieven Keersmaekers
Lieven Keersmaekers

Reputation: 58441

Certainly not prettier but it might be faster because there's less data to juggle with.

SELECT  `acelist`.id, `acelist`.first_name, `acelist`.last_name, `acelist`.acl 
FROM    `usResult` acl
        INNER JOIN (
          SELECT  `usResult`.id
          FROM    (      
                    SELECT  `usResult`.id
                             , SUM(`ace`.`allowed`) AS SumAllowed
                             , COUNT(`ace`.`allowed`) AS CountAllowed
                    FROM    `user` usResult
                            INNER JOIN access_control_list acl ON usResult.acl = acl.id
                            INNER JOIN group_access_control_entry ace ON acl.id = ace.acl
                            INNER JOIN `group` gp ON ace.gid = gp.id
                            INNER JOIN group_membership ON gp.id = group_membership.gid
                            INNER JOIN `user` usr ON group_membership.uid = usr.id
                    WHERE   usr.id = 1
                    GROUP BY
                            `usResult`.id
                    UNION ALL 
                    SELECT  `usResult`.id
                             , SUM(`ace`.`allowed`) AS SumAllowed
                             , COUNT(`ace`.`allowed`) AS CountAllowed
                    FROM    `user` usResult
                            INNER JOIN access_control_list acl ON usResult.acl = acl.id
                            INNER JOIN user_access_control_entry ace ON acl.id = ace.acl
                            INNER JOIN `user` usr ON ace.uid = usr.id
                    WHERE usr.id = 1
                    GROUP BY
                            `usResult`.id
                  ) results
          GROUP BY
                  results.id
          HAVING  SUM(results.SumAllowed) = SUM(results.CountAllowed)
      ) r ON r.id = acl.id

Upvotes: 1

Related Questions