Query for OPAC copies can be extremely slow

[Dan Wells]

Evergreen 2.9 (at least)

Okay, we are in the process of upgrading to a new server, and in running some speed tests, we found an anomaly. In the end, it turned out to be a multi-layered issue:

Problem: certain OPAC copy querys were ~1000x slower than the rest (e.g. 7 seconds vs 7ms)

Cause: Bad query plan
This much was pretty obvious, but why a bad plan, and why wasn't it consistent? Here are two examples of the generated queries, one slow and one fast (slightly simplified from real-life versions):

--SLOW:
SELECT *
FROM asset.copy AS "acp"
LEFT JOIN asset.copy_part_map AS "acpm" ON ( "acpm".target_copy = "acp".id )
LEFT JOIN biblio.monograph_part AS "bmp" ON ( "bmp".id = "acpm".part AND "bmp".deleted = 'f' )
INNER JOIN config.copy_status AS "ccs" ON ( "ccs".id = "acp".status AND "ccs".opac_visible = 't' )
LEFT JOIN action.circulation AS "circ" ON ( "circ".target_copy = "acp".id AND "circ".checkin_time IS NULL )
INNER JOIN asset.copy_location AS "acpl" ON ( "acpl".id = "acp".location AND "acpl".deleted = 'f' AND "acpl".opac_visible = 't' )
INNER JOIN actor.org_unit AS "aou" ON ( "aou".id = "acp".circ_lib AND "aou".id IN (SELECT (actor.org_unit_descendants("aou".id,'1' ))."id" AS "id" FROM actor.org_unit AS "aou" WHERE "aou".id = 1) )
INNER JOIN asset.call_number AS "acn" ON ( "acn".id = "acp".call_number AND ( "acn".deleted = 'f' ) AND ( "acn".record = '801073' ) )
INNER JOIN asset.call_number_prefix AS "acnp" ON ( "acnp".id = "acn".prefix )
INNER JOIN asset.call_number_suffix AS "acns" ON ( "acns".id = "acn".suffix )
WHERE ( "aou".opac_visible = 't' ) AND ( "acp".opac_visible = 't' AND "acp".deleted = 'f' )
ORDER BY evergreen.rank_ou("aou".id,'1','1' ), "aou".name, "acn".label_sortkey, "acp".copy_number, "acp".barcode, evergreen.rank_cp("acp".id )
LIMIT 10 OFFSET 0;

--FAST:
SELECT *
FROM asset.copy AS "acp"
LEFT JOIN asset.copy_part_map AS "acpm" ON ( "acpm".target_copy = "acp".id )
LEFT JOIN biblio.monograph_part AS "bmp" ON ( "bmp".id = "acpm".part AND "bmp".deleted = 'f' )
INNER JOIN asset.call_number AS "acn" ON ( "acn".id = "acp".call_number AND ( "acn".deleted = 'f' ) AND ( "acn".record = '801073' ) )
INNER JOIN asset.call_number_prefix AS "acnp" ON ( "acnp".id = "acn".prefix )
INNER JOIN asset.call_number_suffix AS "acns" ON ( "acns".id = "acn".suffix )
LEFT JOIN action.circulation AS "circ" ON ( "circ".target_copy = "acp".id AND "circ".checkin_time IS NULL )
INNER JOIN actor.org_unit AS "aou" ON ( "aou".id = "acp".circ_lib AND "aou".id IN (SELECT (actor.org_unit_descendants("aou".id,'1' ))."id" AS "id" FROM actor.org_unit AS "aou" WHERE "aou".id = 1) )
INNER JOIN config.copy_status AS "ccs" ON ( "ccs".id = "acp".status AND "ccs".opac_visible = 't' )
INNER JOIN asset.copy_location AS "acpl" ON ( "acpl".id = "acp".location AND "acpl".deleted = 'f' AND "acpl".opac_visible = 't' )
WHERE ( "acp".deleted = 'f' AND "acp".opac_visible = 't' ) AND ( "aou".opac_visible = 't' )
ORDER BY evergreen.rank_ou("aou".id,'1','1' ), "aou".name, "acn".label_sortkey, "acp".copy_number, "acp".barcode, evergreen.rank_cp("acp".id )
LIMIT 10 OFFSET 0;

These queries are identical in everything but the JOIN order, which generally doesn't matter, since the planner will try to optimize the JOINs away, except...

-- Deeper cause: Too many joins can not be "collapsed"

There is a (configurable) limit on the number of JOINs which can be optimized in the query plan. In this case, the most important JOIN for efficiency is the call number, because without that, we JOIN in a *lot* of extra rows (like every copy and circ, I think). If that JOIN is too far down the list, we hit our optimization limit, and the planner never "sees" it to make the right plan.

---- Potential solution #1: Increase join_collapse_limit (or in some similar cases, from_collapse_limit)

The default limit for JOIN collapsing is '8'. In this case, if we bump it (join_collapse_limit) up to '9', the problem is solved, and both queries run fast.

------ Problem with solution #1: O(n!) complexity

With this bump, we don't generate 12.5% more plans, we generate 900% more plans, as every possible JOIN order is considered (factorial complexity). If we go to '10', then we're at 9,000% more plans (or something like that). Point is, we can't just bump this value without thinking long and hard about it.

---- Even deeper cause: JSON queries cannot be ordered in Perl (object order is preserved in direct JSON)

The reason the order is inconsistent in the first place is because this begins as a JSON query represented in Perl. In our case, the "acn" join comes first in the Perl, but that doesn't matter since the Perl JOIN hash doesn't give us any real ordering.

------ Potential solution #2: Find a way to specify JOIN order in Perl

If order can be maintained, then more selective JOINs can reliably come first in the resulting query, and we will hit this issue less often, or at least the performance will be consistent. For example, if we run the same queries (more or less) in srfsh as direct JSON, we don't have this problem [*] .

-------- Problems with solution #2: Ugh, where to start with this one... (or maybe there's a way?)

The 'Tie::IxHash' is one example of an ordered hash-like Perl structure, but retrofitting our infrastructure would be a huge undertaking. Perhaps slightly more feasible would be to allow an array-of-objects optional JOIN syntax, then only retrofit known cases (like this one) where order matters. All this said, the parser syntax is pretty rich already, so maybe some other option exists already to help cases like this?

------ Potential solution #3: Restructure this query to use "acn" as the core table

This is untested, but I imagine it would work. Still, it won't *always* work if the best plans rely on selectivity of two or more tables.

------ Potential workarounds

Give up and run this query as raw SQL in 'storage', make a DB function out of it, etc.

Anyway, just throwing this out for discussion. For our needs, we plan to bump up the 'join_collapse_limit' to 9 or 10 for now, but time will tell if we're hurting ourselves more broadly. Even if there is some other simple solution, I hope this research helps build our collective knowledge about how some of this stuff actually works.

Sincerely,
Dan

* Here's a (fast) query for srfsh (moving the "acn" join to the end of the list will make it slow):
request open-ils.cstore open-ils.cstore.json_query.atomic { "select" : { "acp" : ["id", "barcode", "circ_lib", "create_date", "active_date", "age_protect", "holdable", "copy_number"], "acpl" : [ {"column" : "name", "alias" : "copy_location"}, {"column" : "holdable", "alias" : "location_holdable"} ], "ccs" : [ {"column" : "id", "alias" : "status_code"}, {"column" : "name", "alias" : "copy_status"}, {"column" : "holdable", "alias" : "status_holdable"} ], "acn" : [ {"column" : "label", "alias" : "call_number_label"}, {"column" : "id", "alias" : "call_number"}, {"column" : "owning_lib", "alias" : "call_number_owning_lib"} ], "circ" : ["due_date"], "acnp" : [ {"column" : "label", "alias" : "call_number_prefix_label"}, {"column" : "id", "alias" : "call_number_prefix"} ], "acns" : [ {"column" : "label", "alias" : "call_number_suffix_label"}, {"column" : "id", "alias" : "call_number_suffix"} ], "bmp" : [ {"column" : "label", "alias" : "part_label"} ] }, "from" : { "acp" : { "acn" : { "join" : { "acnp" : { "fkey" : "prefix" }, "acns" : { "fkey" : "suffix" } }, "filter" : [ {"deleted" : "f"}, {"record" : "801073"} ] }, "circ" : { "type" : "left", "filter" : {"checkin_time" : null} }, "acpl" : { "filter" : { "deleted" : "f", "opac_visible" : "t" } }, "ccs" : { "filter" : { "opac_visible" : "t" } }, "aou" :{ "fkey" : "circ_lib", "field" : "id", "filter" : { "id" : { "in" : { "select" : {"aou" : [{ "column" : "id", "transform" : "actor.org_unit_descendants", "result_field" : "id", "params" : [1] }]}, "from" : "aou", "where" : {"id" : 1} } } } }, "acpm" : { "type" : "left", "join" : { "bmp" : { "type" : "left", "filter" : { "deleted" : "f" } } } } } }, "where" : { "+acp" : { "deleted" : "f" } }, "order_by" : [ {"class" : "aou", "field" : "name"}, {"class" : "acn", "field" : "label_sortkey"}, {"class" : "bmp", "field" : "label_sortkey"}, {"class" : "acp", "field" : "copy_number"}, {"class" : "acp", "field" : "barcode"} ], "limit" : 10, "offset" : 0 }

[Mike Rylander (mrylander)]

Dan, where in the code is this query generated? I wonder if we can't remove some of the joins if they provide unnecessary information in some contexts...

[Dan Wells (dbw2)]

Right, sorry. This query is generated by mk_copy_query() in EGCatLoader/Record.pm, though most of the guts come from basic_opac_copy_query() in AppUtils.pm.

[Jeff Davis (jdavis-sitka)]

Same issue as bug 1499086? I have some code there that modified basic_opac_copy_query() to fix a very similar sounding problem.

[Dan Wells (dbw2)]

Jeff, thanks for tying these issues together. Yes, this is the same root code, and yes, your fix is solution #3 above (as you guessed in IRC).

It's good to know that solution works, and maybe in the end that sort of case-by-case tweaking is the best route.

[Dan Wells (dbw2)]

Quick update:

Though I didn't lay blame, I had assumed this change in behavior was related to our Postgres upgrade (to 9.4). I now believe this is fundamentally an issue caused by newer Perl (5.18+), particularly the new hash randomization. In theory (untested), if our query hashes were predictable (or at least the *same*) for each run, then we wouldn't have previously seen the indeterminacy aspects of this bug.

We talked this over at the conference, and it seems possible that some judicious use of the PERL_PERTURB_KEYS env variable set to 0 could be a crutch to get back to where we were (i.e. a form of "solution #2" above).

For reference:
http://search.cpan.org/dist/perl-5.18.0/pod/perldelta.pod#Hash_overhaul

[Mike Rylander (mrylander)]

Here's a proposed branch to address this at the OpenSRF level:

http://git.evergreen-ils.org/?p=working/OpenSRF.git;a=shortlog;h=refs/heads/user/miker/lp-1527731-stable_hash_keys

I'll add OpenSRF as an affected project, also.

[Mike Rylander (mrylander)]

I've updated the OpenSRF branch with documentation about how to enable repeatable hash key order in mod_perl.

Also, there's an Evergreen branch now that updates autogen.sh so that it generates stable cache keys across runs and across machines. That is probably the biggest benefit of all this -- having an actual cache key, rather than having all apache servers fighting with the browser cache.

http://git.evergreen-ils.org/?p=working/Evergreen.git;a=shortlog;h=refs/heads/user/miker/lp-1527731-stable_hash_keys

[Mike Rylander (mrylander)]

I have a new branch available that allows us to specify join order for cstore and friends.

http://git.evergreen-ils.org/?p=working/Evergreen.git;a=shortlog;h=refs/heads/user/miker/lp-1527731-ordered-joins

From the commit message:

With this commit we now support user-defined join order in cstore and friends.
Previously, because the join structure of oils_sql beyond the specification of
a single table was only allowed to be represented as a JSON object, it was
subject to potential hash key reordering -- thanks, Perl. By supporting an
intervening array layer, one can now specify the exact join order of the
tables in a join tree.

For example, given the following JSON object passing through a modern Perl 5
interpreter as a nested hash:

{select : {acp:['id'],
             acn:['record'],
             acpl:['label']
            },
  from : {acp:
                {acn:{filter:{record:12345}},
                 acpl:null
                }
            }
}

the FROM clause of the query may end up as:

  FROM acp
        JOIN acn ON (acp.call_number = acn.id AND acn.record = 12345)
        JOIN acpl ON (acp.location = acpl.id)

Or as:

  FROM acp
        JOIN acpl ON (acp.location = acpl.id)
        JOIN acn ON (acp.call_number = acn.id AND acn.record = 12345)

In some situations, the join order will matter either to the semantics of the
query plan, or to its performance. The following example of the newly
supported syntax illustrates how to specify join order:

{select : {acp:['id'],
             acn:['record'],
             acpl:['label']
            },
  from : {acp:[
                {acn:{filter:{record:12345}}},
                 'acpl'
            ]}
}

And the only FROM clause the can be generated is:

  FROM acp
        JOIN acn ON (acp.call_number = acn.id AND acn.record = 12345)
        JOIN acpl ON (acp.location = acpl.id)

Why is this important
---------------------
While Postgre' planner is very smart, a join tree with many tables may create
a plan search space that is simply too large to be tested effeciently. In such
cases, Postgres will do it's best to find a good plan for the query using its
GEQO algorithm. Often, a DBA or developer has enough understanding of the
expected relative data sizes involved to give Postgres a leg up by specifying
a join order that improves the planner's chances of generating an optimal plan.

[Jason Stephenson (jstephenson)]

I have tested the branch and it works for me.

I have pushed a sign off branch to working/user/dyrcona/lp-1527731-ordered-joins

http://git.evergreen-ils.org/?p=working/Evergreen.git;a=shortlog;h=refs/heads/user/dyrcona/lp-1527731-ordered-joins

I think we need another sign off since this touches the guts of oils_sql.c and a couple of Perl modules.

[Galen Charlton (gmc)]

Pushed to master and rel_3_0. Thanks, Mike and Jason!

[Galen Charlton (gmc)]

See also bug 1731048