  The performance of worst-case optimal join algorithms depends on the order in
which the join attributes are processed. Selecting good orders before query
execution is hard, due to the large space of possible orders and unreliable
execution cost estimates in case of data skew or data correlation. We propose
ADOPT, a query engine that combines adaptive query processing with a worst-case
optimal join algorithm, which uses an order on the join attributes instead of a
join order on relations. ADOPT divides query execution into episodes in which
different attribute orders are tried. Based on run time feedback on attribute
order performance, ADOPT converges quickly to near-optimal orders. It avoids
redundant work across different orders via a novel data structure, keeping
track of parts of the join input that have been successfully processed. It
selects attribute orders to try via reinforcement learning, balancing the need
for exploring new orders with the desire to exploit promising orders. In
experiments with various data sets and queries, it outperforms baselines,
including commercial and open-source systems using worst-case optimal join
algorithms, whenever queries become complex and therefore difficult to
optimize.
