[CX] Investigate overhead of small queries

We found that small (even empty) queries have overheads that are proportional to the number of partitions. We need to

• characterize the problem
• add instrumentation
• determine time-sinks
• create a plan to address the time-sinks