sql: prefer order-matching index when there is a limit #5246
Comments
|
to govern that "tradeoff", maybe taking into account the "average" (or otherwise characteristic) size of result sets which need to be handled for both possible options. Something like an "adaptive query planner". That must be a thing already in literature. |
|
"Cost based query optimization". |
|
I was more asking about particular techniques/impls in distributed systems. I know Postgres uses all sorts of stats on the data size to guess how much it's going to get back, but we won't have a lot of those luxuries. Are you aware of anything on that subsubject in particular? |
|
Absolutely, you can be smarter if you have some kind of statistics available. We will definitely need to build some infrastructure around that. Until then we can make a simple change to give a "bonus" that offsets the non-covering index penalty when an index satisfies the desired ordering completely AND there is a limit. |
|
I think we can do a decent job with table and index size statistics by using the range meta keys to determine how many ranges a particular range of keys spans. |
RaduBerinde
added
the
C-enhancement
In cockroachdb#4925, we observed ineffective planning for a query in the photos app. We prefer to use the primary index and sort rather than use a non-covering index which makes sense in general (non-covering indices require and expensive indexJoin) but in this case we also had a limit. In such a case using the index would require looking only at the first rows instead of getting all matching rows and sorting. In this change we tweak the index selection: if we have a reasonable limit, we give a "boost" to all indices that match the ordering exactly. The boost exactly offsets the non-covering index penalty. In addition to the new tests, I also verified the photo app query in cockroachdb#4925 now uses the index. Fixes cockroachdb#5246.
In cockroachdb#4925, we observed ineffective planning for a query in the photos app. We prefer to use the primary index and sort rather than use a non-covering index which makes sense in general (non-covering indices require an expensive indexJoin) but in this case we also had a limit. In such a case using the index would require looking only at the first rows instead of getting all matching rows and sorting. In this change we tweak the index selection: if we have a reasonable limit, we give a "boost" to all indices that match the ordering exactly. The boost exactly offsets the non-covering index penalty. In addition to the new tests, I also verified the photo app query in cockroachdb#4925 now uses the index. Fixes cockroachdb#5246.
In cockroachdb#4925, we observed ineffective planning for a query in the photos app. We prefer to use the primary index and sort rather than use a non-covering index which makes sense in general (non-covering indices require an expensive indexJoin) but in this case we also had a limit. In such a case using the index would require looking only at the first rows instead of getting all matching rows and sorting. In this change we tweak the index selection: if we have a reasonable limit, we give a "boost" to all indices that match the ordering exactly. The boost exactly offsets the non-covering index penalty. In addition to the new tests, I also verified the photo app query in cockroachdb#4925 now uses the index. Fixes cockroachdb#5246.
There is a tradeoff between selecting a non-covering index that has the desired ordering vs using a covering index that doesn't. However, when we have a limit the latter has the potential of reading much more data so we should prefer the order-matching index.
See #4925 (comment) for an example.
The text was updated successfully, but these errors were encountered: