tree 55e450b8c5ae5cb0b8ab69ebd8289cf0b457fbbd
parent e7d642a71ef935b454e52016e8535865e1eef944
author Lalit Maganti <lalitm@google.com> 1716483863 +0100
committer Lalit Maganti <lalitm@google.com> 1716483863 +0100

tp: rewrite OrderedIndexSearch to be truly O(logn)

This CL changes the implementation of OrderedIndexSearch to
do a binary search direclty at the top level instead of
passing the indices down. This is because translating
all the indices is O(n) wheras we only need O(logn) indices
to be translated.

This *significantly* improves the performance of queries
which happen to end up sorting on a nullable/selector column.

We also remove a bunch of quite complex code which is no longer
necessary.

Before:
```
BM_QEFilterNullOrderedArrangement     112494 ns       112488 ns         6115 s/out=57.6271ns s/row=3.06658ns
```

After:
```
BM_QEFilterNullOrderedArrangement        172 ns          172 ns      4114198 s/out=87.8902ps s/row=4.677ps
```

Change-Id: I34499034b720dfeb3250006e308c3e851078f5e2