Re:SQLite Release 3.25.0 adds support for window functions
by irishsultan on Thursday August 16, 2018 @11:28AM
(#17775472)
This is what I expected the optimization to be, except I'm still not sure that I understand the wording of "that match the columns to the right", I'd expect that to be "that match the columns to the left", after all, you're checking the existence of (1,* ), not of (* ,2) or (* ,3).
Re:SQLite Release 3.25.0 adds support for window functions
by molyss on Wednesday August 15, 2018 @12:46PM
(#17767476)
That makes sense. I completely misunderstood the release note.
Thanks for the clarification.
The insight is very interesting. I always thought there would be 2 separate binary searches...
The insight here is that a multi-column key value can be resolved using a single binary search. It is not a sequence thing where we first look for the key1=1 and then do a separate lookup in a subtree for key2. Both key1 and key2 are resolved in the same binary search.