[SERVER-63778] Try getNext before seek for time-series IXSCAN Created: 17/Feb/22 Updated: 01/Apr/22 Resolved: 23/Mar/22 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | Sam Mercier | Assignee: | Dan Larkin-York |
| Resolution: | Won't Do | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||
| Sprint: | QO 2022-03-21, QO 2022-04-04 | ||||
| Participants: | |||||
| Description |
|
A query with multiple range predicates that scans a compound index can end up doing many small seeks--in the worst case it can do one seek per index entry, which is slower than scanning those same entries would be. Let's try calling SortedDataInterface::next(), optimistically. If we are doing few big seeks, then this shouldn't add much overhead, and if we are doing many tiny seeks it could avoid the overhead of SortedDataInterface::seek(). |
| Comments |
| Comment by Dan Larkin-York [ 23/Mar/22 ] | ||||||||||
|
Closing this out as Won't Do. After some further discussion with members of the Query Execution team, we've decided that this approach is somewhat risky. First, it will be difficult to port cleanly to work when we enable SBE support for time-series collections. Second, it runs the risk of hurting performance for some workloads (even when restricted to time-series collections), since the effectiveness of the optimization is highly dependent on the data distribution. Instead I've filed a few tickets that account for some more modest and (hopefully) less controversial optimizations to our indexing code: | ||||||||||
| Comment by Dan Larkin-York [ 02/Mar/22 ] | ||||||||||
|
The WT team has confirmed that they already have an optimization like this. Roughly speaking, when seeking, they will search the current leaf page for the key; if it's not found, then they will proceed to do a full search from the root. That said, there are other costs to a seek at intermediate layers, and if we can replace a seek on the index cursor with a next() call, then we may still benefit. I think the potential improvement here would be at the query layer, rather than lower down the stack. We might need to keep track of additional data in IndexScan, or if not, we certainly would need to add additional checks. Suppose we are scanning a compound index on (x, y), for bounds ((x_1, x_2), (y_1, y_2)). Our current position might be at (a, b) for x_1 < a < x_2 and b < y_1. In this case we will currently seek to (a, y_1). Since this is strictly greater than (a, b), we will advance the cursor. However, it is quite possible that we will land on some new value (c, d) such that a < c < x_2 and d < y_1, meaning we will again seek to (c, y_1), and potentially on and on as such. In the general case, that seek may have skipped over many values (a, b_1), (a, b_2), ... (a, b_n) where all values b* < y_1. But it may also be the case that it did not skip over any values. That is, that the index entry (c, d) immediately followed (a, b) in order, so the seek((a, y_1)) call had the same effect as if we had called next(). The idea here is that we would optimistically call next() when we detect the need for a seek. But if the new key has the same prefix as the key that necessitated the seek, then we would need to actually seek. That is, if we are at (a, b), and want to "seek" to (a, y_1), then we would call next(), and check. If our new key is (a, b') for some b' < y_1, we would then go ahead and seek((a, y_1)). But if we in fact found some new key (c, d), then we could avoid the seek. We do keep track of this prefix information in some form: IndexScan::_seekPoint.keyPrefix. So when we perform our seek, we could first do a next, and check against the prefix. It's a bit unclear to me at the moment how long it would take to try this out and see if it helps. I'm confident it's not trivial, but it could take from a few hours to a few days work to get something that works. Someone with a bit more familiarity with this bounds checking code might be able to give a better estimate. | ||||||||||
| Comment by David Percy [ 28/Feb/22 ] | ||||||||||
|
Some pseudocode:
I think a worst case for this approach would be if every call to seek() needs to advance by 2 records. Then the early return never happens; we still call actuallySeek() on every seek(), but we also add the overhead of advance(). | ||||||||||
| Comment by Timour Katchaounov [ 18/Feb/22 ] | ||||||||||
|
This description begs for some pseudocode to specify the proposed algorithm. What is important to understand is whether the proposed change will make relevant index plans always better (via some kind of dynamic adaptation) or not. If not, then the only way to pick the right strategy is via some cost estimation. |