Bug 24185

Summary: 'If all unavailable' state for 'on shelf holds' makes holds page very slow if there's a lot of items
Product: Koha Reporter: Andrii Nugged <nugged>
Component: CatalogingAssignee: Andrii Nugged <nugged>
Status: CLOSED FIXED QA Contact: Jonathan Druart <jonathan.druart>
Severity: normal    
Priority: P5 - low CC: 1joynelson, aleisha, fridolin.somers, jonathan.druart, joonas.kylmala, m.de.rooy, martin.renvoize
Version: Main   
Hardware: All   
OS: All   
See Also: https://bugs.koha-community.org/bugzilla3/show_bug.cgi?id=24683
Change sponsored?: --- Patch complexity: Small patch
Documentation contact: Documentation submission:
Text to go in the release notes:
Version(s) released in:
20.05.00
Bug Depends on:    
Bug Blocks: 26523    
Attachments: Bug 24185: 'If all unavailable' for 'on shelf holds' makes holds page slow
Bug 24185: 'If all unavailable' for 'on shelf holds' makes holds page slow
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page faster: preparatory refactoring
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page faster: preparatory refactoring
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page faster: preparatory refactoring
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'
Bug 24185: Make holds page faster - improved "if"
Bug 24185: Make holds page faster - call to subroutine moved below "if"
Bug 24185: Make holds page faster: preparatory refactoring
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'

Description Andrii Nugged 2019-12-06 10:01:25 UTC Comment hidden (obsolete)
Comment 1 Andrii Nugged 2019-12-07 12:43:37 UTC Comment hidden (obsolete)
Comment 2 Andrii Nugged 2019-12-07 13:04:18 UTC Comment hidden (obsolete)
Comment 3 Joonas Kylmälä 2019-12-10 10:10:57 UTC
Thanks. Unfortunately, the patch doesn't apply, please rebase. Also the title "'If all unavailable' for 'on shelf holds' makes holds page slow" describes the problem instead what the commit does. So the commit title should be something like "Make holds page fast when/if/with setting ..." (https://wiki.koha-community.org/wiki/Commit_messages#Examples)
Comment 4 Andrii Nugged 2019-12-10 12:36:55 UTC Comment hidden (obsolete)
Comment 5 Andrii Nugged 2019-12-16 21:28:11 UTC Comment hidden (obsolete)
Comment 6 Joonas Kylmälä 2019-12-17 08:39:57 UTC
Thanks! Couple issues: 

1) you copy & paste the code inside the loop instead of abstracting it to a subroutine. Please fix this so the code is in a subroutine and performance problems like this can be prevented by seeing the problems immediately. This is important also for testability.

2) There should be one logical change per commit, leave "$can_item_be_reserved eq 'OK'" change in the && statement to another commit, and also leave "my $on_shelf_holds = Koha:: [...]" to another commit, plus any other changes I missed not related to fixing the O(n^2) issue here
Comment 7 Andrii Nugged 2019-12-18 20:03:57 UTC Comment hidden (obsolete)
Comment 8 Andrii Nugged 2019-12-18 20:04:13 UTC Comment hidden (obsolete)
Comment 9 Andrii Nugged 2019-12-18 20:47:33 UTC Comment hidden (obsolete)
Comment 10 Andrii Nugged 2019-12-19 16:18:54 UTC Comment hidden (obsolete)
Comment 11 Andrii Nugged 2019-12-19 16:23:47 UTC Comment hidden (obsolete)
Comment 12 Andrii Nugged 2019-12-19 17:06:23 UTC Comment hidden (obsolete)
Comment 13 Andrii Nugged 2019-12-19 20:15:29 UTC Comment hidden (obsolete)
Comment 14 Andrii Nugged 2020-01-15 07:22:41 UTC Comment hidden (obsolete)
Comment 15 Andrii Nugged 2020-01-15 07:23:18 UTC Comment hidden (obsolete)
Comment 16 Andrii Nugged 2020-01-15 07:24:27 UTC Comment hidden (obsolete)
Comment 17 Andrii Nugged 2020-01-15 07:26:25 UTC Comment hidden (obsolete)
Comment 18 Jonathan Druart 2020-03-20 10:22:08 UTC
Andrew, that makes sense to me, thanks for the excellent writing of these patches (split, comments and commit messages are perfect!).
Comment 19 Andrii Nugged 2020-03-22 11:39:22 UTC
Created attachment 101355 [details] [review]
Bug 24185: Make holds page faster - improved "if"

`$can_item_be_reserved eq 'OK'` moved in `&&` before `IsAvailableForItemLevelRequest`
to cut away with static known values before calling to more resource consuming subroutine.
Comment 20 Andrii Nugged 2020-03-22 11:40:04 UTC
Created attachment 101356 [details] [review]
Bug 24185: Make holds page faster - call to subroutine moved below "if"

`$on_shelf_holds` was assigned before "return .. if" but not used in that code piece,
so sometimes it was useless. Moved assignment after "return .. if".
Comment 21 Andrii Nugged 2020-03-22 11:40:32 UTC
Created attachment 101357 [details] [review]
Bug 24185: Make holds page faster: preparatory refactoring

This is just refactoring. extracting logically independent code
to separate sub + tests update. No logic change yet.

Searching for "any_available" item among all biblionumber items was done
inside of "elsif on_shelf_holds == 2", and it is logically very independent
piece of code (this "@items" loop), it needs just biblionumber and patron
as parameters so it can be extracted into separate subroutine, and
later also called/reused from somewhere else.

This ability to call from another place also made for future patch
to remove O(n^2) problem with nested loops.
Comment 22 Andrii Nugged 2020-03-22 11:41:30 UTC
Created attachment 101358 [details] [review]
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'

When "reserve/request.pl -> C4/Reserves.pm::IsAvailableForItemLevelRequest" called many times with hundred of items and "on shelf holds" parameter set to "If all unavailable" for these items + patron, it goes slow.

It happens because in subloop it is checking if all items available so it is O(n^2) and it re-checks each time the same info for each item with repeating DB/data requests.

Fix:
The inner loop 1:1 picked out into separate subroutine and called outside of the loop, saving data in 'items_any_available' variable once, this variable passed to IsAvailableForItemLevelRequest to be used inside as the precalculated result.

This made algorithm O(n) instead of O(n^2) so there is noticeable speed increase.

How to reproduce:

1) on freshly installed kohadevbox create/import one book,
remember that biblionumber for later use it in down below,

2) add 100 items for that book for some library,

3) find some patron, that patron's card number we will
use as a borrower down below to open holds page,

4) check for the rule or set up a single circulation rule
in admin "/cgi-bin/koha/admin/smart-rules.pl",
that rule should match above book items/library/patron,
check that rule to have a non-zero number of holds (total, daily, count) allowed,
and, IMPORTANT: set up "On shelf holds allowed" to "If all unavailable",
("item level holds" doesn't matter).

5) open "Home > Catalog > THAT_BOOK > Place a hold on THAT_BOOK" page
("holds" tab), and enter patron code in the search field,
or you can create a direct link by yourself, for example, in my case it was:
/cgi-bin/koha/reserve/request.pl?biblionumber=4&findborrower=23529000686353

6) it should be pretty long page generation time on old code, densely increasing for every hundred items added. In the case of this solution, it's fast, and time increases a little only, linear.

I tested on my computer in VirtualBox for page generation times,
did 3-5 runs for same case to check if results are stable, and got such values:

(old code):
  100 items:    50 seconds
  200 items:   3.2 minutes
  300 items:   7.3 minutes

(version with fix):
  100 items:   4.4 seconds
  200 items:   7.5 seconds
  300 items:  10.4 seconds
Comment 23 Fridolin Somers 2020-03-24 15:09:30 UTC
Created attachment 101607 [details] [review]
Bug 24185: Make holds page faster - improved "if"

`$can_item_be_reserved eq 'OK'` moved in `&&` before `IsAvailableForItemLevelRequest`
to cut away with static known values before calling to more resource consuming subroutine.

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>
Comment 24 Fridolin Somers 2020-03-24 15:10:26 UTC
Created attachment 101608 [details] [review]
Bug 24185: Make holds page faster - call to subroutine moved below "if"

`$on_shelf_holds` was assigned before "return .. if" but not used in that code piece,
so sometimes it was useless. Moved assignment after "return .. if".

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>
Comment 25 Fridolin Somers 2020-03-24 15:10:57 UTC
Created attachment 101609 [details] [review]
Bug 24185: Make holds page faster: preparatory refactoring

This is just refactoring. extracting logically independent code
to separate sub + tests update. No logic change yet.

Searching for "any_available" item among all biblionumber items was done
inside of "elsif on_shelf_holds == 2", and it is logically very independent
piece of code (this "@items" loop), it needs just biblionumber and patron
as parameters so it can be extracted into separate subroutine, and
later also called/reused from somewhere else.

This ability to call from another place also made for future patch
to remove O(n^2) problem with nested loops.

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>
Comment 26 Fridolin Somers 2020-03-24 15:16:09 UTC
Rebased on current master with an obvious conflict because of Bug 24468.

Performance is really better, tested on my laptop :
100 items => 54 seconds without patch, 8 seconds with patch
Comment 27 Andrii Nugged 2020-03-24 15:17:47 UTC
oh, thanks for REBASE! In a case, if another assistance needed – I am monitoring this actively.
Comment 28 Fridolin Somers 2020-03-24 15:26:45 UTC
Created attachment 101611 [details] [review]
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'

When "reserve/request.pl -> C4/Reserves.pm::IsAvailableForItemLevelRequest" called many times with hundred of items and "on shelf holds" parameter set to "If all unavailable" for these items + patron, it goes slow.

It happens because in subloop it is checking if all items available so it is O(n^2) and it re-checks each time the same info for each item with repeating DB/data requests.

Fix:
The inner loop 1:1 picked out into separate subroutine and called outside of the loop, saving data in 'items_any_available' variable once, this variable passed to IsAvailableForItemLevelRequest to be used inside as the precalculated result.

This made algorithm O(n) instead of O(n^2) so there is noticeable speed increase.

How to reproduce:

1) on freshly installed kohadevbox create/import one book,
remember that biblionumber for later use it in down below,

2) add 100 items for that book for some library,

3) find some patron, that patron's card number we will
use as a borrower down below to open holds page,

4) check for the rule or set up a single circulation rule
in admin "/cgi-bin/koha/admin/smart-rules.pl",
that rule should match above book items/library/patron,
check that rule to have a non-zero number of holds (total, daily, count) allowed,
and, IMPORTANT: set up "On shelf holds allowed" to "If all unavailable",
("item level holds" doesn't matter).

5) open "Home > Catalog > THAT_BOOK > Place a hold on THAT_BOOK" page
("holds" tab), and enter patron code in the search field,
or you can create a direct link by yourself, for example, in my case it was:
/cgi-bin/koha/reserve/request.pl?biblionumber=4&findborrower=23529000686353

6) it should be pretty long page generation time on old code, densely increasing for every hundred items added. In the case of this solution, it's fast, and time increases a little only, linear.

I tested on my computer in VirtualBox for page generation times,
did 3-5 runs for same case to check if results are stable, and got such values:

(old code):
  100 items:    50 seconds
  200 items:   3.2 minutes
  300 items:   7.3 minutes

(version with fix):
  100 items:   4.4 seconds
  200 items:   7.5 seconds
  300 items:  10.4 seconds

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>
Comment 29 Fridolin Somers 2020-03-24 15:28:33 UTC
(In reply to Andrew Nugged from comment #27)
> oh, thanks for REBASE! In a case, if another assistance needed – I am
> monitoring this actively.

Your welcome, please check its OK
Comment 30 Jonathan Druart 2020-03-24 15:47:47 UTC
Created attachment 101613 [details] [review]
Bug 24185: Make holds page faster - improved "if"

`$can_item_be_reserved eq 'OK'` moved in `&&` before `IsAvailableForItemLevelRequest`
to cut away with static known values before calling to more resource consuming subroutine.

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Comment 31 Jonathan Druart 2020-03-24 15:47:52 UTC
Created attachment 101614 [details] [review]
Bug 24185: Make holds page faster - call to subroutine moved below "if"

`$on_shelf_holds` was assigned before "return .. if" but not used in that code piece,
so sometimes it was useless. Moved assignment after "return .. if".

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Comment 32 Jonathan Druart 2020-03-24 15:47:57 UTC
Created attachment 101615 [details] [review]
Bug 24185: Make holds page faster: preparatory refactoring

This is just refactoring. extracting logically independent code
to separate sub + tests update. No logic change yet.

Searching for "any_available" item among all biblionumber items was done
inside of "elsif on_shelf_holds == 2", and it is logically very independent
piece of code (this "@items" loop), it needs just biblionumber and patron
as parameters so it can be extracted into separate subroutine, and
later also called/reused from somewhere else.

This ability to call from another place also made for future patch
to remove O(n^2) problem with nested loops.

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Amended patch, I moved up the last line of the test, sounds more logical
to me.
Comment 33 Jonathan Druart 2020-03-24 15:48:01 UTC
Created attachment 101616 [details] [review]
Bug 24185: Make holds page fast when 'on shelf holds' set to 'If all unavailable'

When "reserve/request.pl -> C4/Reserves.pm::IsAvailableForItemLevelRequest" called many times with hundred of items and "on shelf holds" parameter set to "If all unavailable" for these items + patron, it goes slow.

It happens because in subloop it is checking if all items available so it is O(n^2) and it re-checks each time the same info for each item with repeating DB/data requests.

Fix:
The inner loop 1:1 picked out into separate subroutine and called outside of the loop, saving data in 'items_any_available' variable once, this variable passed to IsAvailableForItemLevelRequest to be used inside as the precalculated result.

This made algorithm O(n) instead of O(n^2) so there is noticeable speed increase.

How to reproduce:

1) on freshly installed kohadevbox create/import one book,
remember that biblionumber for later use it in down below,

2) add 100 items for that book for some library,

3) find some patron, that patron's card number we will
use as a borrower down below to open holds page,

4) check for the rule or set up a single circulation rule
in admin "/cgi-bin/koha/admin/smart-rules.pl",
that rule should match above book items/library/patron,
check that rule to have a non-zero number of holds (total, daily, count) allowed,
and, IMPORTANT: set up "On shelf holds allowed" to "If all unavailable",
("item level holds" doesn't matter).

5) open "Home > Catalog > THAT_BOOK > Place a hold on THAT_BOOK" page
("holds" tab), and enter patron code in the search field,
or you can create a direct link by yourself, for example, in my case it was:
/cgi-bin/koha/reserve/request.pl?biblionumber=4&findborrower=23529000686353

6) it should be pretty long page generation time on old code, densely increasing for every hundred items added. In the case of this solution, it's fast, and time increases a little only, linear.

I tested on my computer in VirtualBox for page generation times,
did 3-5 runs for same case to check if results are stable, and got such values:

(old code):
  100 items:    50 seconds
  200 items:   3.2 minutes
  300 items:   7.3 minutes

(version with fix):
  100 items:   4.4 seconds
  200 items:   7.5 seconds
  300 items:  10.4 seconds

Signed-off-by: Fridolin Somers <fridolin.somers@biblibre.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Comment 34 Martin Renvoize 2020-03-24 19:09:34 UTC
Excellent work, thanks everyone!
Comment 35 Martin Renvoize 2020-03-25 09:43:33 UTC
Nice work everyone!

Pushed to master for 20.05
Comment 36 Joy Nelson 2020-04-03 22:15:39 UTC
does not apply to 19.11.x 
please rebase if needed.
Comment 37 Martin Renvoize 2020-05-12 10:22:05 UTC
Nice work everyone!

Pushed to master for 20.05
Comment 38 Andrii Nugged 2020-06-11 23:47:58 UTC
I've backported this to v19.11.x because people requested: where I should push patches for 19.11.06? Should I create a separate ticket?
Comment 39 Katrin Fischer 2020-06-12 06:29:59 UTC
(In reply to Andrew Nugged from comment #38)
> I've backported this to v19.11.x because people requested: where I should
> push patches for 19.11.06? Should I create a separate ticket?

Usually the same bug is used and you can state the version in your commit message for example by adding [19.11] at the beginning of the subject line so it shows in the list of patches here.