Where(predicate).Reverse() is optimizable (assuming the predicate itself is selecting only a subset of the keys).
Technical details: PersistentDictionary.Where returns a PersistentDictionaryLinqKeyValueEnumerable object, which will walk only a subset of the keys. The Reverse() method is called on the PersistentDictionaryLinqKeyValueEnumerable and tells it to walk the
keys in the opposite order.
So, using the latest release I expect these cases to be optimized:
var dict = new PersistentDictionary<int, string>();
var q = dict.Where(x.Key > 100).Reverse();
var q2 = dict.Where(x.Key < 1000).Reverse();
Note that the type of the dictionary is important! If you change the type of dict in the example from PersistentDictionary to IDictionary then the query will be run using the LINQ extension operators, which will always do a full enumeration.