  We consider the task of lexicographic direct access to query answers. That
is, we want to simulate an array containing the answers of a join query sorted
in a lexicographic order chosen by the user. A recent dichotomy showed for
which queries and orders this task can be done in polylogarithmic access time
after quasilinear preprocessing, but this dichotomy does not tell us how much
time is required in the cases classified as hard. We determine the
preprocessing time needed to achieve polylogarithmic access time for all join
queries and all lexicographical orders. To this end, we propose a
decomposition-based general algorithm for direct access on join queries. We
then explore its optimality by proving lower bounds for the preprocessing time
based on the hardness of a certain online Set-Disjointness problem, which shows
that our algorithm's bounds are tight for all lexicographic orders on join
queries. Then, we prove the hardness of Set-Disjointness based on the
Zero-Clique Conjecture which is an established conjecture from fine-grained
complexity theory. Interestingly, while proving our lower bound, we show that
self-joins do not affect the complexity of direct access (up to logarithmic
factors). Our algorithm can also be used to solve queries with projections and
relaxed order requirements, though in these cases, its running time not
necessarily optimal. We also show that similar techniques to those used in our
lower bounds can be used to prove that, for enumerating answers to
Loomis-Whitney joins, it is not possible to significantly improve upon
trivially computing all answers at preprocessing. This, in turn, gives further
evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of
self-join free cyclic joins with respect to linear preprocessing and constant
delay.
