Please review this post for how to interpret O(n) of CDT operations. The referenced O(n) discussion is about data structure performance, which is typically a fraction of overall request execution. If the data size is large, you can employ techniques to break the data across multiple records, keep the relevant data (say, top 5000 instead on 1M titles) in a record, and so on.