  SkinnerDB is designed from the ground up for reliable join ordering. It
maintains no data statistics and uses no cost or cardinality models. Instead,
it uses reinforcement learning to learn optimal join orders on the fly, during
the execution of the current query. To that purpose, we divide the execution of
a query into many small time slices. Different join orders are tried in
different time slices. We merge result tuples generated according to different
join orders until a complete result is obtained. By measuring execution
progress per time slice, we identify promising join orders as execution
proceeds.
  Along with SkinnerDB, we introduce a new quality criterion for query
execution strategies. We compare expected execution cost against execution cost
for an optimal join order. SkinnerDB features multiple execution strategies
that are optimized for that criterion. Some of them can be executed on top of
existing database systems. For maximal performance, we introduce a customized
execution engine, facilitating fast join order switching via specialized
multi-way join algorithms and tuple representations.
  We experimentally compare SkinnerDB's performance against various baselines,
including MonetDB, Postgres, and adaptive processing methods. We consider
various benchmarks, including the join order benchmark and TPC-H variants with
user-defined functions. Overall, the overheads of reliable join ordering are
negligible compared to the performance impact of the occasional, catastrophic
join order choice.
