Optimizing window joins over data streams can include receiving an input topology and calculating costs of computing a join of data streams based on a number of model topologies, and determining an optimal topology based on the calculated costs and the input topology, wherein the input topology, the model topologies, and the optimal topology each include a number of interconnected operators.