kv: Scans with limit acquire excessively large latches

[bdarnell]

A query like SELECT * FROM t WHERE indexed_column > $1 LIMIT 1 has a very large key Span (from key $1 to the end of the table or the end of the range, whichever comes first), but really only depends on a small amount of data (from $1 to the first key greater than that value). The command queue only sees the former, so this query must wait behind any updates to any other rows in the table, not just the rows that it will eventually return.

We could minimize this contention at the expense of throughput as follows. For read-only commands with (small) limits, execute the command first, before putting it in the command queue. If it reaches its limit, narrow the span based on the keys that were actually touched. Put it in the command queue under the narrowed span. After waiting on the command queue, execute it again. If it doesn't hit the limit while staying inside the narrowed span, something has changed out from under us and we have to re-queue with a broader span.

There is probably a way to be clever and avoid the double execution in the common case, e.g. if the command queue allows the narrowed span to execute immediately we can use the results of the first execution.

This is a major cause of slowness for photos (#9247). For example, this trace spends 100ms in the command queue on its first scan. There is probably a related problem with the timestamp cache, but I haven't confirmed its existence or impact yet.

[petermattis]

That query seems to be an artifact of photos, not of the load photos is intended to model. photos uses that query to find a random user-id to to list the photos of but in a real app the user-id would be known.

[tamird]

Since we already have a pagination mechanism via resume_span, could we
instead insert into the command queue the maximum span that doesn't overlap
with other, already-running commands? Then we'd paginate as usual if
another read is required to meet the limit.

On Sat, Sep 24, 2016 at 7:31 AM, Peter Mattis [email protected]
wrote:

That query seems to be an artifact of photos, not of the load photos is
intended to model. photos uses that query to find a random user-id to to
list the photos of but in a real app the user-id would be known.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#9521 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABdsPJSTFpOfsEDKMesoT-ab1Z4tPf0vks5qtQoXgaJpZM4KFjKu
.

[bdarnell]

@petermattis Yes, this query is not a part of the load photos is intended to model. However, it is a useful enough pattern that it's worth optimizing (and we should probably come up with another load generator (or transaction for photos) that exercises this.

@tamird Ah, that's a nice idea. I think there's some concern on the SQL side about what happens if we serve partial results when the client didn't ask for it, but in general returning partial results instead of blocking in the command queue seems like a good idea.

[andreimatei]

@tamird this pagination trick would help with this scan command not waiting for others before it, but wouldn't help with the scan blocking other commands that come after it (at least in the case the command queue is empty to begin with), right?

I like the idea of attempting an inconsistent read first to get a clue about the required span. @bdarnell, seems to me that double execution can be avoided easily in the uncontended case if the command queue (or the replica otherwise) would maintain sequence numbers for incoming commands (or the spans of recent commands) and so it could assert that no overlapping command went through while we were doing the inconsistent read. Or, actually, can't the timestamp cache (which seems to contain writes too) serve this purpose?

[tamird]

@andreimatei I think that's an orthogonal problem. In the case we're discussing here, the ... LIMIT 1 query results in a very large span, and the corresponding wait on entering the command queue is very long. However, once the command executes, it is likely to finish very quickly (because it is limited to one row).

That said, I agree that we have a general granularity problem in the command queue (scans shouldn't hold up commands in their "wake"), but it doesn't seem immediately relevant here.

[tbg]

We have this granularity problem on various levels. @vivekmenezes touches on something similar in #9419, but in the realm of intent resolution, where the problem is pretty dramatic given that the current code churns through a lot of data for nothing.

With the above query, we'll "always" end up waiting on at least a few Raft commands, which is also pretty drastic. I like @bdarnell's suggestion: we execute the read, check for getOverlaps in the command queue for the resulting span, and if there aren't any we get to use our previous result. If there is something outstanding, we bite the bullet and grab the whole span plus re-execute when it's our turn. Optimizing that second case further could be useful at some point too, but it's more complicated and less frequently useful.

[andreimatei]

Umm can we just call getOverlaps and return the result? What if there was a quick write in there that finished by the time we call getOverlaps? Don't we need to either use the timestamp cache, or redo the read, this time going through the CommandQueue (with the small span), and then possibly re-doing it again if the consistent read failed to satisfy our limit this time?

[tbg]

You're right, the read would need to be done while holding the lock. That is probably too expensive so maybe we're going to have to be real smart™ right from the get-go, unfortunately.

[petermattis]

#13349 truncates the span added for scans when possible.