Moodle in English: They said it was impossible

They said it was impossible

by Tim Hunt - Thursday, 19 March 2009, 3:14 PM

Several people have said that the roles system is so complicated that the function get_users_by_capability cannot be implemented purely in SQL. Well, I think I have just worked out they are wrong:


SELECT DISTINCT userid
FROM (

  SELECT ra.userid, rc.capability, 100*actx.depth + octx.depth AS weight, SIGN(SUM(rc.permission)) AS combinedperms, MIN(rc.permission) AS prohibits
  FROM (

    SELECT userid, roleid, contextid
    FROM m_role_assignments
    WHERE contextid IN (1,35,36,37,47)

  UNION
    SELECT id AS userid, 7 AS roleid, 1 AS contextid
    FROM m_user

  UNION
    SELECT id AS userid, 12 AS roleid, 2 AS contextid
    FROM m_user
    WHERE 2 IN (1,35,36,37,47)

  ) ra
  JOIN m_context actx ON actx.id = ra.contextid
  JOIN m_role_capabilities rc ON rc.roleid = ra.roleid
  JOIN m_context octx ON octx.id = rc.contextid

  WHERE rc.capability IN ('mod/forum:replypost', 'moodle/site:doanything')
    AND octx.id IN (1,35,36,37,47)

  GROUP BY userid, capability, weight
) combined_permissions
GROUP BY userid, capability
HAVING MIN(prohibits) > -1000
   AND MAX(weight * combinedperms) > -MIN(weight * combinedperms)

That is get_users_by_capability(get_context_instance_by_id(47), 'mod/forum:replypost') on one of my test servers where the prefix is 'm_'. Some explanation of the magic numbers appearing in there:

100 simply needs to be any number that is greater than SELECT MAX(depth) FROM m_context;
1,35,36,37,47 is derived from get_context_instance_by_id(47)->path which is '1/35/36/37/47'
7 is $CFG->defaultuserroleid
1 is the system context id get_context_instance(CONTEXT_SYSTEM)->id
12 is $CFG->defaultfrontpageroleid
2 is the front page context id get_context_instance(CONTEXT_COURSE, SITEID)->id
-1000 is CAP_PROHIBIT

At the moment this skips a lot of the optional parameters get_users_by_capability, but they can all be accommodated by easily using the same sort of extra joins and where clauses that are already used in get_users_by_capability.

Average of ratings: Useful (2)

Re: They said it was impossible

by Tim Hunt - Thursday, 19 March 2009, 3:47 PM

If you are wondering why that works, here is the explanation. There are three nested sub-queries there, and we need to work from the inside, out.

The inner bit, which is a UNION of three SELECTs is just adding the implicit role assignments to $CFG->defaultuserroleid and $CFG->defaultfrontpageroleid to all the explicit role assignments in the role assignments table, to get a single view of all the role assignments we need to process.

Next we have the middle sub-query which does most of the complicated joining. This is pulling out all the data we need to build a table like How_permissions_are_calculated#Representing_the_data_in_tabular_form for each user and capability we might be interested in.

actx is the assignment context, and so actx.depth is the number of the row in that table.
octx is the override context, so octx.depth is the number of the column in the table.
weight = 100*actx.depth + octx.depth is designed to get the cells of the table in the priority order we want. It is highest in the top left cell, and then decreases as you go all along the first row, then all along the second row, and so on.
prohibits = MIN(rc.permission) keeps track of whether there is any PROHIBIT in that cell of the table.
combinedperms = SIGN(SUM(rc.permission)) is one of the clever tricks that makes this whole thing work. Provided that there are PROHIBITs in the cell, then combinedperms is
- 1 if there are more ALLOWs than PREVENTs in this cell
- 0 if there are equal numbers of ALLOWs and PREVENTs
- -1 if there are more PREVENTs than ALLOWs

Finally, we have the outer query. This analyses the cells of the table and works out the has_capability result

MIN(prohibits) > -1000 is checking to see that there are no PROHIBITs anywhere in the table.
MAX(weight * combinedperms) > -MIN(weight * combinedperms) is the second clever trick that makes this whole thing work. This is basically checking whether, as you scan the table, you get to a cell with more ALLOWs than PREVENTs, before you get to one with more PREVENTs than ALLOWs or get to the end. I give a detailed explanation in a simpler context on Development:Filter_enable/disable_by_context#Why_does_this_work.3F.
This check happens for each userid and capability. In the end we are only intersted in the DISTINCT userids where this is true for at least one capability.

I will admit to one slight cheat. I have had to change the behaviour of an obscure edge case of the permission calculation rules in a way that has previously been discussed in MDL-17210.

Now, that only took us two and a half years to work out from the time the Roles system was released on an unsuspecting world

Also, please note, I am not claimin that this is necessarily faster than the current combined SQL+PHP function, but it is probably worth testing, and also looking for ways to optimise the query. Also, this has only been given some limited testing as yet. There were briefly some unit tests for get_users_by_capability in Moodle 2.0, but they got disabled when we realised that the approach we had taken to unit tests involving database tables was dangerous.

Average of ratings: Useful (2)

Re: They said it was impossible

by Tim Hunt - Thursday, 19 March 2009, 6:27 PM

Testing on last night's backup of the moodle.org database, it seems to get the right list of people allowed to moderate the quiz forum. It gets the right number of participant for this course too - assuming that 4831 is the right number. There are 4834 now, but it is quite likely that more people have signed up.

The query is taking 16 seconds to run (this is on my desktop machine). The explain looks like this (but I am not an expert at reading MySQL explains).

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	20	Using temporary; Using filesort
2	DERIVED	octx	range	PRIMARY	PRIMARY	8	NULL	4	Using where; Using temporary; Using filesort
2	DERIVED	rc	ref	roleid-contextid-capability,roleid,contextid,rolecapa_cap_ix	contextid	8	moodleorg.octx.id	3	Using where
2	DERIVED	<derived3>	ALL	NULL	NULL	NULL	NULL	653668	Using where
2	DERIVED	actx	eq_ref	PRIMARY	PRIMARY	8	ra.contextid	1
3	DERIVED	role_assignments	range	contextid-roleid-userid,contextid	contextid-roleid-userid	8	NULL	7418	Using where; Using index
4	UNION	user	index	NULL	user_deleted	1	NULL	657954	Using index
5	UNION	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
NULL	UNION	RESULT	<union3,4,5>	ALL	NULL	NULL	NULL	NULL	NULL

Average of ratings: -

Re: They said it was impossible

by John White - Thursday, 19 March 2009, 7:35 PM

Tim,

Just AWESOME!

John

Average of ratings: -

Re: They said it was impossible

by Martín Langhoff - Tuesday, 24 March 2009, 11:14 AM

The bad news are in

- 'using temporary; using filesort'
- rows that don't list a 'key'
- rows that are expected to return a ton of data

The table is read from the bottom up, which is how the data will be "read" from disk. It will

- read the user table, grabbing 657K rows of data into memory...
- read role_assignments, grabbing 7K rows
- cheap grab of ra.contextid
- filter the 657K rows in memory
- the read of rc is possibly cheap
- the read of octx reads like it'll be cheap, but "using temporary, using filesort" contradicts that. odd.
- the final merge described in the top row is... well, bad news that stem from trying to merge 657K rows with 7K rows, all in memory

sorry to report such sad news, but hth somehow.

Average of ratings: -

Re: They said it was impossible

by sam marshall - Friday, 20 March 2009, 2:40 AM

Tim, this is very cool, but have you compared performance with the existing one? How does that 16 seconds compare?

--sam

Average of ratings: -

Re: They said it was impossible

by Gary Anderson - Friday, 20 March 2009, 3:00 AM

Tim:

This looks really cool, but I have found one thing that has been a problem with these complex searches using SQL in Moodle: database contention.

The problem I have had is that Moodle wants to write to the user table all the time to update the last access time. But at least with some database configurations, if the user table is being accessed, the query must finish before the update can happen. So the whole site hangs during these long searches. In those cases, it may be better to let PHP do the hard work from a larger SQL output if it can finish the SQL query quicker.

Our site has students seeing any problem assignments they have and teachers seeing anything in their courses that need grading so that is when I have come upon this problem. These are big and complex searches. Indexing things and doing the query right eventually solved it for us, but it did teach me that some times queries that work in testing don't work when put onto the site. Since your's uses the user table also, you might find the same thing.

--Gary

Average of ratings: -

Re: They said it was impossible

by Tim Hunt - Friday, 20 March 2009, 9:37 AM

get_users_by_capability already does big complex queries on exactly these tables, and this function is normally only used on report-y pages like quiz results and participants list.

But, of course, this would never go into core unless we had done some performance measurements.

About contention: It seems to makes a really big difference if you use INNODB tables in MySQL, or a real database like Postgres, which do row-level locking, rather than the MySQL default of MyISAM tables in MySQL which only knows how to lock the entire table.

Average of ratings: -

Re: They said it was impossible

by Eloy Lafuente (stronk7) - Friday, 20 March 2009, 7:52 AM

Hi Tim,

great query! Just two comments:

1) From a SQL perspective... those two selects from m_user can be real killers... couldn't them be taken out from the inner query and be added later conditionally (in an outer UNION or so only if the cap being checked is "meaningful" in those $CFG roles and contexts (system and site). That could speed up the query in a lot of cases.

2) From a logic perspective... I think it exposes the same problem being commented/discussed in the Role overrides revisited page, where permissions are compensated between roles, one thing I continue seeing as a mistake.

Anyway, nice query, I love them!

(ninja) Ciao

Average of ratings: -

Re: They said it was impossible

by Tim Hunt - Friday, 20 March 2009, 10:06 AM

1) On the performance side, several responses

For now, I was more interested in getting the right answer than in optimising the query. The performance can probably be improved.
There is, of course scope for doing some tests in PHP when building the SQL, to leave out unnecessary parts when they are not needed. If you were doing groups, you would put the group join right in the middle, to cut down the list of users as quickly as possible.

2) Well, this was partly an intellectual exercise. I suddenly realised that this could actually be done, and so worked out the details.

There are two justifications given on Role overrides revisited:

One is that the roles system has to be simplified becuase you cannot JOIN on the result of gete_users_by_capability, and that is bad for performance.
The other is that the roles system has to be simplified becuase no one understands it, and so the fact it is very flexible is wasted.

I have just shown that the first of these points in invalid. On the second, I still think, and keep saying, that before we try to design a new system, we should try to decide how much flexibility we need, rather that just proposing new code. I tried to start a thread in the Roles forum and a wiki page.

I still don't get the way people are phrasing this: "permissions are compensated between roles" (and similar in other places). If a user has two roles, one which says 'allow' and another which says 'prevent', then we need some rule for resolving that. And the answer is either going to be 'allow' or 'prevent', which mean that the permission from one role have overruled the permission from another role. Is that what you mean by the permissions from one role affecting the permissions from another role? If so, it is inevitable.

Anyway, the rule we have is that the most specific permission wins, and the details of that are essentially unchanged since the original specification. I think that there is a huge burden of proof to overcome for anyone proposing a change to the rule. I am not saying that we should never change. Just that we should be very, very careful. (I also think that we have enough other things to change for Moodle 2.0 that are more important, so we should leave this for now.)

Average of ratings: Useful (1)

Re: They said it was impossible

by Eloy Lafuente (stronk7) - Friday, 20 March 2009, 9:52 PM

>"I still don't get the way people are phrasing this: "permissions are compensated between roles" (and similar in other places). If a user has two roles, one which says 'allow' and another which says 'prevent', then we need some rule for resolving that."

Obviously, we need some rule for resolving that. The important bit is that I think it's incorrect to do so in "the middle" of the process (at some intermediate context level), because it causes the process to continue/stop processing lower contexts incorrectly.

I other words, current permissions are calculated horizontally (summarising them for all the roles in each context) and then vertically (inner wins).

And, IMO, they should be calculated vertically (inner wins, for each role), and then horizontally (over those final results per role).

I know it's a difference only affecting "border cases" (with contradictory permissions in different roles at the same context), so I wouldn't call it "we try to design a new system". Just to make it easier to understand, avoiding the creation of those "extra" capabilities in other contexs to solve that horrible (IMO, of course) behaviour of compensating permissions in the middle of the process.

That's the reason of Role overrides revisited if I'm not wrong.

Ciao

Average of ratings: -

Re: They said it was impossible

by Tim Hunt - Friday, 20 March 2009, 11:11 PM

I'm not sure I follow the vertical and horizontal wording. Can you give some specific examples with a small number of roles.

Average of ratings: -

Re: They said it was impossible

by Eloy Lafuente (stronk7) - Saturday, 21 March 2009, 1:13 AM

Hi Tim,

I didn't invented the vertical/horizontal nomenclature. Just compare the process described in:

1) Current approach: where you call it "right to left" (uhm?), "top to bottom" (i.e. horizontally, then vertically):

2) Role overrides revisited: Where perms are calculated per role (vertically) and then computed (horizontally).

Note I'm not saying that's a good example. Just trying to show the differences between both types of calculations and the horizontal/vertical concept.

Ciao

Average of ratings: -

Re: They said it was impossible

by Robert Brenstein - Saturday, 21 March 2009, 12:14 AM

Could that be partly that the system works technically only with capabilities but we think and talk about roles, although there is no clean match among these?

Average of ratings: -

Re: They said it was impossible

by Martín Langhoff - Tuesday, 24 March 2009, 11:06 AM

Getting to this conversation late... fantastic SQL, but I don't think it solves the problem

- You are cheating a bit by having pre-fetched the ids for the context hierarchy

-- which I made easy on purpose with the context 'path' field.

- The cost of that UNION over the user table can be huge

- The rolecap resolution cannot be solved by a mere SUM/MULTIPLY unfortunately. The tricky nexted logic I wrote... well, I did try to resolve with simple adds and multiplications, but it's just not like that. Consider scenarios with various conflicting roles assigned at different context depths.

Petr's proposed simplification may help there, but still, the scenarios with various conflicting roles... I don't think they can be done in pure SQL.

And if they can, the SQL is perhaps so costly as to be frankly undesirable.

Here is something I would like to stress: the most important thing is to have

- SQL queries that are as efficient as possible across the many different use cases (many courses, many role assignments, many role overrides, many users) and various DBs. This is incredibly hard to test -- we took the leap with 1.9, found plenty of "bad" cases to fix, and have been polishing things quite a bit. (well, you guys have, I went olpc-way...)

- A _bound_ number of SQL queries regadless of the size of those variables above.

That the number is _bound_ and hopefully low does NOT mean that "1 query" is a good answer (or even the best!) to the problem.

So my question are:

- Is the 1-query solution correct?
- Is the 1-query solution faster / more efficient for all the scenarios?

Average of ratings: Useful (1)

Re: They said it was impossible

by Tim Hunt - Tuesday, 24 March 2009, 11:45 AM

I agree with almost everything Martín says apart from:

In think the SQL does almost everything the PHP does, and the one minor change to the rules that it makes is irrelevant in any real situation.

The big win of a single query is when you want to JOIN onto another table, like quiz results or gradebook data, with paging. It sucks to have to pull a list of userids into PHP, and then do a second big IN query (even though, as you say, it may be the best practical solution.)

Average of ratings: -

Re: They said it was impossible

by Martín Langhoff - Tuesday, 24 March 2009, 12:56 PM

OK. If close enough is good enough, and you want something JOIN-able then I think an approach that will work better is to:

1 - Run a query first that explores which roles are going to give you what you want.

2 - with the "interesting roles" identified, run a simpler query that mainly reads from role_assignment and is JOIN-able with anything. Now, the roles may be interesting but 'negative', creative use of CASE can do the dirty job here.

3 - Instead of actually "running" the query described in #2, just return the SQL, ready to be embedded as a subselect to be JOINed in a bigger chunk of SQL by the caller.

I suspect #3 has been the heart of your cunning your plan all along with this, but I thought it was worth a mention

Hope I didn't ruin the suspense...

However... the caller has to be able to parse the results to go from "good enough" to "completely correct". There I say...

- What efficient assistance can we give that caller?

- Damn! that means that paging is out because the "correct" filtering may remove items. S^%t

That's where I am at a bit of a loss. The plan otherwise is great, and something I thought of doing when I was making a mess of accesslib.

Average of ratings: -

Re: They said it was impossible

by Martín Langhoff - Tuesday, 24 March 2009, 1:08 PM

Thinking a bit more about the need for correctness and pagination, maybe we're making this way harder than it needs to be.

What I mean to say is: we need temp tables for this. If you do the magic, and select into a temptable, then you can tell your caller - hey, just JOIN against table $foo and we are sorted.

Back in the big rewrite mess, I hit this wall hard too. I am sure there's a thread on this forum about patches to make our DB layer support temptables, for this exact reason.

The short of it: it is a veritable a mess to try to support temptables across the DBs we have with consistent semantics. Some have automatic 'garbage collection', some have private namespaces, some have special names for them that need to be escaped or specialcased everywhere.

It's not impossible, but at the time, it was hard enough to fall in the 'for later' basket.

If we can get temptables working... woohoo! Second option: if we can get an established "results cache" table then what you are tring to do becomes possible. The 'results cache' table is going to become a bottleneck on large sites though so it's better to avoid it.

Average of ratings: -

General developer forum

They said it was impossible

They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Re: They said it was impossible

Empowering educators to improve our world

Moodle

Support

Get Involved

Contributions

Downloads

Tracker

Development

Empowering educators to improve our world