Evergreen

Bug #1438136
Comment #12

Comment 12 for bug 1438136

Revision history for this message

Mike Rylander (mrylander) wrote on 2015-04-03:

#12

SO! I'm confident that I've pinned down the issue, and that I have a likely solution.

The problem: Array query selectivity is Hard(tm). Very simple operators can use the data in pg_stats to estimate selectivity, but complicated ones (like generalized overlap/contains/contained, and especially query_int) require things like data distribution and correlation information that is 1) hard to gather 2) large to store 3) expensive to use. So, instead, the default selectivity estimate for arrays is used, and that estimate is 0.5%. That is bad for very common values in complicated queries (such as our core search query).

The solution: We need to be able to tell the planner that a particular WHERE clause is expensive. But, ^- that! AH! But all WHERE clauses boil down to a boolean expression in the end, and the selectivity of a user defined function that returns a BOOL in Postgres is 0.333, or 33%, which is well past the "it's super cheap, use whatever index you can find!" threshold. By wrapping the @@ operator use in a function like this:

CREATE FUNCTION evergreen.query_int_wrapper (INT[],TEXT)
RETURNS BOOL $$ BEGIN RETURN $1 @@ $2::query_int; END; $$ LANGUAGE PLPGSQL STABLE;

we can convince the planner to move the condition to the end of the list of tests, or at least convince it to avoid a nested loop over the result of that filter. Common attribute value inference achievement unlocked!

"But wait," you say, "what about rare attr values! Those are SUPER fast with an index! We want to keep that speedup!"

The optimization: In my previous comment I showed how to find the most common values (as seen by the analyzer in PG) for array elements like this. So, we'll pull those at QueryParser startup (appropriately fenced by a PG version check) just like we do for query rewriting information, and sorters and whatnot, decide whether we use the @@ operator directly, or the function, based on whether any of the values in the query_int we construct are one of theose super-common values and is not negated. (The reason for "and not negated" is that those are always a recheck issue, and is a sunk cost regarless, so we ignore negated common values.)

Thoughts?

SO! I'm confident that I've pinned down the issue, and that I have a likely solution.

The problem: Array query selectivity is Hard(tm).  Very simple operators can use the data in pg_stats to estimate selectivity, but complicated ones (like generalized overlap/contains/contained, and especially query_int) require things like data distribution and correlation information that is 1) hard to gather 2) large to store 3) expensive to use.  So, instead, the default selectivity estimate for arrays is used, and that estimate is 0.5%.  That is bad for very common values in complicated queries (such as our core search query).

The solution: We need to be able to tell the planner that a particular WHERE clause is expensive.  But, ^- that!  AH! But all WHERE clauses boil down to a boolean expression in the end, and the selectivity of a user defined function that returns a BOOL in Postgres is 0.333, or 33%, which is well past the "it's super cheap, use whatever index you can find!" threshold.  By wrapping the @@ operator use in a function like this:

CREATE FUNCTION evergreen.query_int_wrapper (INT[],TEXT)
 RETURNS BOOL $$ BEGIN RETURN $1 @@ $2::query_int; END; $$ LANGUAGE PLPGSQL STABLE;

we can convince the planner to move the condition to the end of the list of tests, or at least convince it to avoid a nested loop over the result of that filter.  Common attribute value inference achievement unlocked!

"But wait," you say, "what about rare attr values!  Those are SUPER fast with an index!  We want to keep that speedup!"

The optimization:  In my previous comment I showed how to find the most common values (as seen by the analyzer in PG) for array elements like this.  So, we'll pull those at QueryParser startup (appropriately fenced by a PG version check) just like we do for query rewriting information, and sorters and whatnot, decide whether we use the @@ operator directly, or the function, based on whether any of the values in the query_int we construct are one of theose super-common values and is not negated.  (The reason for "and not negated" is that those are always a recheck issue, and is a sunk cost regarless, so we ignore negated common values.)

Thoughts?