Pred Choice

The choice of predicate matters a lot. In the worst case, consider queries inserted in order A < 10; A < 9; ... ; A < 1. Looking at just the current predicate is bad here as no future predicate insertion improves the total workload cost (as inserting A < X does not benefit the queries A < Y where Y > X).

To combat this, in addition to A < X, we may need to examine a few other predicates seen before on that attribute.