commit 1ac605ab1a8858d4c16771bf08c21a735a4f666c
author Lalit Maganti <lalitm@google.com> Thu Oct 24 19:14:02 2019 +0100
committer Lalit Maganti <lalitm@google.com> Thu Oct 24 19:14:02 2019 +0100
tree 5090514136ceb4db83a0be1630f183b39ef126b1
parent 363647f6b31582419fd5c7f60f2aee96f6e058a6

trace_processor: add fast path for eq constraints on id columns

This CL adds a short circuiting fast path for ID columns which avoids
a full table scan when we have an eq constraint. This significantly
improves the performance for nested subqueries which occur during
joins on id columns

Old:
----------------------------------------------------------------------
Benchmark                               Time           CPU Iterations
----------------------------------------------------------------------
BM_TableFilterIdColumn/1024         42755 ns      42755 ns      16453
BM_TableFilterIdColumn/4096        173391 ns     173393 ns       4037
BM_TableFilterIdColumn/32768      1450592 ns    1450596 ns        479
BM_TableFilterIdColumn/262144    12129560 ns   12129612 ns         58
BM_TableFilterIdColumn/2097152  101641277 ns  101638806 ns          7

New:
----------------------------------------------------------------------
Benchmark                               Time           CPU Iterations
----------------------------------------------------------------------
BM_TableFilterIdColumn/1024          5037 ns       5037 ns     138821
BM_TableFilterIdColumn/4096         19222 ns      19222 ns      36437
BM_TableFilterIdColumn/32768       152193 ns     152188 ns       4607
BM_TableFilterIdColumn/262144     1217069 ns    1217007 ns        574
BM_TableFilterIdColumn/2097152    9802464 ns    9802174 ns         72

Analysis:
There is basically a 8-10x improvement at every size of Table. However,
we are still not at constant time (the goal) because SelectRows still
performs a full scan. A follow up CL will address this issue.

Context: go/perfetto-tp-refactor
Bug: 135177627
Change-Id: I8245fec5201e29dc3f3f06ed598e1946878571c8