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
diff --git a/Android.bp b/Android.bp
index 3ccd745..e3312bb 100644
--- a/Android.bp
+++ b/Android.bp
@@ -2391,6 +2391,7 @@
":perfetto_src_shared_lib_test_utils",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
@@ -16048,6 +16049,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
@@ -16284,6 +16286,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_importers_common_common",
":perfetto_src_trace_processor_importers_common_parser_types",
@@ -16443,6 +16446,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
