Abstract
Worst-case analysis is not always satisfactory in the database setting because input size is typically not a lower bound on query evaluation runtime. In particular, database relations are usually sorted and indexed, thus allowing many queries to be answered in sublinear time. One approach to look beyond worst-case analysis is instance optimality, where the target is to meet the best runtime possible for any algorithm on a specific input instance. At the center of this analysis is the notion of a “certificate”. A certificate is a proof of output correctness that any algorithm has to implicitly produce. Thus, the minimum certificate size for a given instance serves as a lower bound on the runtime of any algorithm.
In this talk, we summarize some of the recent lines of work on database query evaluation in instance-optimal runtime. We present two natural notions of certificates for database join queries: comparison certificates and geometric certificates. We show that geometric certificates are smaller. Aided with this notion of certificates, we describe a couple of instance-optimal algorithms for join queries. Along the way, we develop a geometric proof system for the problem that allows us to derive proof-complexity upper and lower bounds. We list some of the open problems in this direction.