There has been considerable work on automated physical design tuning for database systems. Existing solutions require offline invocations of the tuning tool and depend on DBAs identifying representative workloads manually. In this work, we propose an alternative approach to the physical design problem. Specifically, we design algorithms that are always-on and continuously modify the current physical design reacting to changes in the query workload. Our techniques have low overhead and take into account storage constraints, update statements, and the cost to create temporary physical structures.