305506 - Reduce number of SQL calls in Bugzilla::User->groups

Status: RESOLVED FIXED

(Bugzilla :: Administration, task, P3)

Description

[u197037]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b) Gecko/20050217
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b) Gecko/20050217

If user is a member of big set of groups and if DB connectivity is quite poor,
group() function in User.pm take quite long to finish.

As of Joel's comment on IRC, it still need recursion loop.

Reproducible: Always

Comment 1

[u197037]

Attachment: Proposed patch (w/o recursion loop)

Comment 2

[Joel Peshkin]

This is a good idea

Comment 3

[u197037]

Attachment: v2 patch. Including recursion

Groups membership recursion processing added.
Assuming, that for 3 level hierarhy it's better to call
"$dbh->prepare(SQLStatement)" 3 times than 5-10 times call previously prepared
$sth->execute($bindvalue).
Arguable.

Comment 4

[Max Kanat-Alexander]

You could also grab every GROUP_MEMBERSHIP group in one SQL call and do all the
logic in perl. Would that be faster? (You'd have to profile it to know for sure.)

Comment 5

[Joel Peshkin]

Actually, there is a slight tweak on this that would make this even better. 
When things stabilize a bit in general, I'll add that tweak to Denis' patch and
I think we'll have a winner.  In the query, we can ask for the groups that are
IN  groupidstocheck AND NOT IN groupidschecked

Comment 6

[u197037]

(In reply to comment #5)
...
> I think we'll have a winner.  In the query, we can ask for the groups that are
> IN  groupidstocheck AND NOT IN groupidschecked

I do not see the reason for this: values are added to @groupidstocheck only if
NOT seen in %groupidschecked, so they are already "NOT IN".

Comment 7

[u197037]

Attachment: v3 patch with mkanat suggestions.

While Joel have one more variant pending, here is a patch implementing mkanat's
idea of fetching all stuff to server and building groups list in Perl.
In my particular case, both of them take almost equal time (floating in range
from 0.7 to 1.2s). But while v2 patch will add time for each level of groups
hierarhy, v3 will have almost constant time.
I'm not removing v2 patch, since v3 is also a proposal to be discussed. Next
turn is Joel's.

Comment 8

[Joel Peshkin]

Actually, I think I am going to change my position on this....

mkanat's approach shifts more burden to the webserver running the perl script
which is pretty scalable if you assume that really large sites will run
multi-cpu systems.

The alternative follows the philosophy of shifting the burden to the SQL server,
but it involves several additional queries.

Comment 9

[Max Kanat-Alexander]

Comment on attachment 193918 [details] [diff] [review]
v3 patch with mkanat suggestions.

Profiling data using perl's DProf shows this to actually be slightly slower
than our current method of doing things, because it calls fetchrow_array so
many times. Try just doing a selectall_arrayref once; that will probably speed
things up.

Comment 10

[u197037]

Attachment: The same as v3, but with selectall_arrayref()

Yep. It is significantly faster.

Comment 11

[u197037]

Also, the article at
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html gives good
idea how groups hierarchies could be managed. "Nested sets" model is slow on
insert/delete operations but really fast on lookups. I my particular case,
"Retrieving a Single Path" sample could be easily modified with:
-AND node.name = 'FLASH'
+AND node.name IN (join(',', @leaf_nodes_list))

Any ideas of incorporate this? Not in this bug, sure.

Comment 12

[Max Kanat-Alexander]

(In reply to comment #11)
> Any ideas of incorporate this? Not in this bug, sure.

  If we could get it to work, that sounds like it might be a good idea. The
added complexity might be bad, though. We should evaluate the real-world
performance problems we run into with the current method, before adding
complexity to improve performance.

  Also, does that Nested Set model actually work with our group inheritance
model? A single group can be a "member" of more than one group. (That is, a
single child can be in multiple places, or have "multiple parents.")

Comment 13

[u197037]

(In reply to comment #12)
...
>   Also, does that Nested Set model actually work with our group inheritance
> model? A single group can be a "member" of more than one group. (That is, a
> single child can be in multiple places, or have "multiple parents.")

Nope, I missed this point... It definitely not allow multiple inheritance.
The other way (not ideal though) is to have cached full groups membership table,
rebuilt each time membership changed. Somesing like:

group|level|member_of
    1|    0| NULL #or absent row at all
    1|    1|        2
    1|    2|        3
    1|    1|        7
    1|    2|        9
    2|    0| NULL #or absent row at all
    2|    1|        3
    2|    1|        9
    3|    0| NULL #or absent row at all
    7|    0| NULL #or absent row at all
    7|    1|9
    9|    0| NULL #or absent row at all

Comment 14

[u197037]

Attachment: v5 - avoid $_ usage

As you asked me on IRC - changed $_ to $newgroupid

Comment 15

[Max Kanat-Alexander]

Comment on attachment 197180 [details] [diff] [review]
v5 - avoid $_ usage

Profiling shows this code to be slightly *slower* (average 2.3 seconds for 2000
users vs 2.1 seconds for 2000 users) than the previous code, in a normal
situation. However, when the SQL server is remote, this should be a good win.

I tested this and determined that for all landfill users, the group settings
were exactly the same with and without the patch. (No differences at all
between Dumper($user->groups) for all users.)

If speed is still a concern even after this, we can cache the entire
group_membership list inside Bugzilla::User somehow.

Comment 16

[Max Kanat-Alexander]

Ideally, however, this code needs more comments before I check it in. It's hard
to understand. You can carry forward r+ if all you do is add comments.

Comment 17

[u197037]

Attachment: Commented out version of v5

Commented out version of v5 patch. No changes in logic. Carrying forward review
flag according to Max's comment #16

Comment 18

[Max Kanat-Alexander]

Checking in Bugzilla/User.pm;
/cvsroot/mozilla/webtools/bugzilla/Bugzilla/User.pm,v  <--  User.pm
new revision: 1.83; previous revision: 1.82
done

Comment 19

[Frédéric Buclin]

Patch backed out. Group inheritance now seems broken:

Checking in Bugzilla/User.pm;
/cvsroot/mozilla/webtools/bugzilla/Bugzilla/User.pm,v  <--  User.pm
new revision: 1.85; previous revision: 1.84
done

Comment 20

[Teemu Mannermaa (:wicked)]

Could the added "if (!$groupidschecked{$member_id})" as the last line changed in
the patch after mkanat's review trigger the regression?

Comment 21

[u197037]

(In reply to comment #20)
> Could the added "if (!$groupidschecked{$member_id})" as the last line changed in
> the patch after mkanat's review trigger the regression?

No, it shouldn't. All it does is just skip unwanted iterations. 

Anyway, I'll investigate this shortly. Also, will appreciate any comments on how
it breaks the inheritance: Frederic, any samples?

Comment 22

[Olav Vitters]

Dennis: admins only have editbugs+canconfirm. Not the others.

Comment 23

[u197037]

(In reply to comment #21)
> (In reply to comment #20)
> > Could the added "if (!$groupidschecked{$member_id})" as the last line changed in
> > the patch after mkanat's review trigger the regression?
> 
> No, it shouldn't. All it does is just skip unwanted iterations. 
But did. :(
There sure must be 'if (!$groupidschecked{$newgroupid});' instead of 'if
(!$groupidschecked{$member_id});'

Resume: Never work while ill and never change even obvious part of code if reviewed.

Thanks, Teemu.

Comment 24

[u197037]

Attachment: Fixed regression, introduced in v6

Fixed regression. Max, please take a look at patch again.

Comment 25

[Frédéric Buclin]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

I want a second review from joel

Comment 26

[Max Kanat-Alexander]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

Can you explain why that "if" is there at all? It wasn't there in the previous, working patch.

Comment 27

[u197037]

(In reply to comment #26)
> (From update of attachment 197697 [details] [diff] [review] [edit])
> Can you explain why that "if" is there at all? It wasn't there in the previous,
> working patch.
It is there to avoid unnecessary loops for already processed group IDs.
Previous patch had them. Otherwise, the @groupsidtocheck array could grow significantly each time.

Comment 28

[Max Kanat-Alexander]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

OK. Wicked, could you test this bug? I did extensive tests on the old patch, but I haven't tested this version at all.

Comment 29

[Frédéric Buclin]

Too risky for 2.22, see comment 19. And the trunk is frozen anyway to prepare bugzilla 2.22.

Comment 30

[Teemu Mannermaa (:wicked)]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

>Index: Bugzilla/User.pm
>===================================================================
>+#                 Dennis Melentyev <[e-mail]>

Nit: This first hunk no longer apply.

>@@ -265,21 +266,49 @@
>     my $sth;

This is now unused, please remove it before commit.

Otherwise, this doesn't seem to break group inheritance anymore so it's probably good to go in.

Comment 31

[Max Kanat-Alexander]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

I think wicked's review is enough.

Comment 32

[Frédéric Buclin]

joel, does this patch look good to you?

Comment 33

[Vlad Dascalu]

Comment on attachment 197697 [details] [diff] [review]
Fixed regression, introduced in v6

s/curcular/circular/ in this attachment.

Comment 34

[Vlad Dascalu]

Attachment: v8: Fixed hunk from v7, removed unused $sth, s/curcular/circular/

Carrying over review flag from v7.

This patch has the following differences to the previous v7:
  -> fixed first hunk that no longer applied cleanly (due to new contributors).
  -> line numbers in the diff are updated to the trunk (applies cleanly).
  -> $sth that is no longer used was removed per comment #30
  -> s/Curcular/Circular/ per comment #33

Comment 35

[Vlad Dascalu]

Comment on attachment 224676 [details] [diff] [review]
v8: Fixed hunk from v7, removed unused $sth, s/curcular/circular/

+            # Add all it's members to check list FIFO

s/it's/its/ in this attachment.

Comment 36

[Vlad Dascalu]

Comment on attachment 224676 [details] [diff] [review]
v8: Fixed hunk from v7, removed unused $sth, s/curcular/circular/

+    # Let's walk the groups hierarhy tree (using FIFO)

s/hierarhy/hierarchy/ in this attachment.

Comment 37

[Vlad Dascalu]

Comment on attachment 224676 [details] [diff] [review]
v8: Fixed hunk from v7, removed unused $sth, s/curcular/circular/

+    # membership. Later on, each group can add it's own members into the

s/it's/its/ for this attachment.

Comment 38

[Vlad Dascalu]

Attachment: v9: spelling and wording fixes on v8

Carrying over r=wicked.

Differences compared to v8:

-+    # Let's walk the groups hierarhy tree (using FIFO)
++    # Let's walk the groups hierarchy tree (using FIFO)

(comment 36)

-+    # membership. Later on, each group can add it's own members into the
++    # membership. Later on, each group can add its own members into the

(comment 37)

-+            # Add all it's members to check list FIFO
++            # Add all its members to the FIFO check list

(comment 35 and a re-wording that seemed natural)

and one more rewording:

-+        # Skip the group if we have it checked already
++        # Skip the group if we have already checked it

Comment 39

[Vlad Dascalu]

Commiting v9 on trunk.

All tests successful.
Files=11, Tests=2526, 91 wallclock secs (51.15 cusr +  9.22 csys = 60.37 CPU)

Checking in Bugzilla/User.pm;
/cvsroot/mozilla/webtools/bugzilla/Bugzilla/User.pm,v  <--  User.pm
new revision: 1.110; previous revision: 1.109
done