  We study the question of when we can provide direct access to the k-th answer
to a Conjunctive Query (CQ) according to a specified order over the answers in
time logarithmic in the size of the database, following a preprocessing step
that constructs a data structure in time quasilinear in database size.
Specifically, we embark on the challenge of identifying the tractable answer
orderings, that is, those orders that allow for such complexity guarantees. To
better understand the computational challenge at hand, we also investigate the
more modest task of providing access to only a single answer (i.e., finding the
answer at a given position), a task that we refer to as the selection problem,
and ask when it can be performed in quasilinear time. We also explore the
question of when selection is indeed easier than ranked direct access.
  We begin with lexicographic orders. For each of the two problems, we give a
decidable characterization (under conventional complexity assumptions) of the
class of tractable lexicographic orders for every CQ without self-joins. We
then continue to the more general orders by the sum of attribute weights and
establish the corresponding decidable characterizations, for each of the two
problems, of the tractable CQs without self-joins. Finally, we explore the
question of when the satisfaction of Functional Dependencies (FDs) can be
utilized for tractability, and establish the corresponding generalizations of
our characterizations for every set of unary FDs.
