Thread: Improving Performance of Query ~ Filter by A, Sort by B

Something about the estimated row counts (this problem persisted after I tried ANALYZEing)

forces usage of the tmstmp index and Merge Append (which seems wise) but also a filter condition on parent_id over an index condition, which is apparently prohibitively slow.

I tried creating a multicolumn index like:

CREATE INDEX "a_partition1_parent_and_tmstmp_idx" on "a_partition2" USING btree ("parent_id", "tmstmp" DESC);

But this didn't help (it wasn't used).

This query plan (which is the same as when LIMIT is removed) has been a good short term solution when the number of "parent_id"s I'm using is still relatively small, but unfortunately queries grow untenably slow as the number of "parent_id"s involved increases:

I'd be very grateful for help with one or both of these questions:

1) Why is adding an unnecessary (from the perspective of result correctness) ORDER BY valuable for forcing the parent_id index usage, and does that indicate that there is something wrong with my table/indexes/statistics/etc.?

2) Is there any way I can improve my query time when there are many "parent_id"s involved? I seem to only be able to get the query plan to use at most one of the parent_id index and the tmstmp index at a time. Perhaps the correct multicolumn index would help?

On Tue, Jul 10, 2018 at 11:07 AM, Lincoln Swaine-Moore <lswainemoore@gmail.com> wrote:

Something about the estimated row counts (this problem persisted after I tried ANALYZEing)

What is your default_statistics_target?  What can you tell us about the distribution of parent_id?  (exponential, power law, etc?).  Can you show the results for select * from pg_stats where tablename='a' and attname='parent_id' \x\g\x  ?

 

forces usage of the tmstmp index and Merge Append (which seems wise) but also a filter condition on parent_id over an index condition, which is apparently prohibitively slow.

I tried creating a multicolumn index like:

CREATE INDEX "a_partition1_parent_and_tmstmp_idx" on "a_partition2" USING btree ("parent_id", "tmstmp" DESC);

But this didn't help (it wasn't used).

You could try reversing the order and adding a column to be (tmstmp, parent_id, id) and keeping the table well vacuumed.  This would allow the slow plan to still walk the indexes in tmstmp order but do it as an index-only scan, so it could omit the extra trip to the table. That trip to the table must be awfully slow to explain the numbers you show later in the thread.

...

 

This query plan (which is the same as when LIMIT is removed) has been a good short term solution when the number of "parent_id"s I'm using is still relatively small, but unfortunately queries grow untenably slow as the number of "parent_id"s involved increases:

What happens when you remove that extra order by phrase that you added?  The original slow plan should become much faster when the number of parent_ids is large (it has to dig through fewer index entries before accumulating 20 good ones), so you should try going back to that.

...

I'd be very grateful for help with one or both of these questions:

1) Why is adding an unnecessary (from the perspective of result correctness) ORDER BY valuable for forcing the parent_id index usage, and does that indicate that there is something wrong with my table/indexes/statistics/etc.?

It finds the indexes on tmstmp to be falsely attractive, as it can walk in tmstmp order and so avoid the sort. (Really not the sort itself, but the fact that sort has to first read every row to be sorted, while walking an index can abort once the LIMIT is satisfied).  Adding an extra phrase to the ORDER BY means the index is no longer capable of delivering rows in the needed order, so it no longer looks falsely attractive.  The same thing could be obtained by doing a dummy operation, such as ORDER BY tmstmp + '0 seconds' DESC.  I prefer that method, as it is more obviously a tuning trick.  Adding in "id" looks more like a legitimate desire to break any ties that might occasionally occur in tmstmp.

As Tom pointed out, there clearly is something wrong with your statistics, although we don't know what is causing it to go wrong.  Fixing the statistics isn't guaranteed to fix the problem, but it would be a good start.

 

 

2) Is there any way I can improve my query time when there are many "parent_id"s involved? I seem to only be able to get the query plan to use at most one of the parent_id index and the tmstmp index at a time. Perhaps the correct multicolumn index would help?

A few things mentioned above might help.  

But if they don't, is there any chance you could redesign your partitioning so that all parent_id queries together will always be in the same partition?  And if not, could you just get rid of the partitioning altogether?  1e7 row is not all that many and doesn't generally need partitioning.  Unless it is serving a specific purpose, it is probably costing you more than you are getting.  

Finally, could you rewrite it as a join to a VALUES list, rather than as an in-list?

 

Cheers,

Jeff

Tom and Jeff,

Thanks very much for the suggestions!

Here's what I've found so far after playing around for a few more days:

What is your default_statistics_target?  What can you tell us about the distribution of parent_id?  (exponential, power law, etc?).  Can you show the results for select * from pg_stats where tablename='a' and attname='parent_id' \x\g\x  ?

The default_statistics_target is 500, which I agree seems quite insufficient for these purposes. I bumped this up to 2000, and saw some improvement in the row count estimation, but pretty much the same query plans. Unfortunately the distribution of counts is not intended to be correlated to parent_id, which is one reason I imagine the histograms might not be particularly effective unless theres one bucket for every value. Here is the output you requested:

select * from pg_stats where tablename='a' and attname='parent_id';

schemaname             | public

tablename              | a

attname                | parent_id

inherited              | t

null_frac              | 0

avg_width              | 4

n_distinct             | 18871

most_common_vals       | {15503,49787,49786,24595,49784,17549, ...} (2000 values)

most_common_freqs      | {0.0252983,0.02435,0.0241317,0.02329,0.019095,0.0103967,0.00758833,0.004245, ...} (2000 values)

A few questions re: statistics:

 1) would it be helpful to bump column statistics to, say, 20k (the number of distinct values of parent_id)?

 2) is the discrepancy between the statistics on the parent and child table be expected? certainly I would think that the statistics would be different, but I would've imagined they would have histograms of the same size given the settings being the same.

 3) is there a way to manually specify the the distribution of rows to be even? that is, set the frequency of each value to be ~ n_rows/n_distinct. This isn't quite accurate, but is a reasonable assumption about the distribution, and might generate better query plans.

You could try reversing the order and adding a column to be (tmstmp, parent_id, id) and keeping the table well vacuumed.  This would allow the slow plan to still walk the indexes in tmstmp order but do it as an index-only scan, so it could omit the extra trip to the table. That trip to the table must be awfully slow to explain the numbers you show later in the thread.

 

Just to clarify, do you mean building indexes like:

CREATE INDEX "a_tmstmp_parent_id_id_idx_[PART_KEY]" on "a_partition[PART_KEY]" USING btree("tmstmp", "parent_id", "id")

That seems promising! Is the intuition here that we want the first key of the index to be the one we are ultimately ordering by? Sounds like I make have had that flipped initially. My understanding of this whole situation (and please do correct me if this doesn't make sense) is the big bottleneck here is reading pages from disk (when looking at stopped up queries, the wait_event is DataFileRead), and so anything that can be done to minimize the pages read will be valuable. Which is why I would love to get the query plan to use the tmstmp index without having to filter thereafter by parent_id.

What happens when you remove that extra order by phrase that you added?  The original slow plan should become much faster when the number of parent_ids is large (it has to dig through fewer index entries before accumulating 20 good ones), so you should try going back to that.

Unfortunately, I've found that even when the number of parent_ids is large (2000), it's still prohibitively slow (haven't got it to finish), and maintains a query plan that involves an Index Scan Backward across the a_tmstmp_idxs (with a filter for parent_id).