Veritabanlarında "Top K" sorguları, belirli bir sütuna göre sıralanmış en iyi K adet satırı getirme anlamına gelir. Örneğin, en yeni kayıtlar veya en yüksek puanlar gibi. Bu, basit bir problem gibi görünse de, özellikle filtreler eklendiğinde PostgreSQL gibi genel amaçlı veritabanlarında karmaşık hale gelebilir.
PostgreSQL, bu tür sorgular için B-tree indekslerini kullanır. B-tree'ler, sıralı yapıları sayesinde basit ORDER BY ... LIMIT K sorgularında oldukça etkilidir ve performansı O(K) seviyesine düşürür. İndeks, kökten en büyük değere sahip yaprağa atlar ve ardından K adet satırı toplayana kadar bağlı yapraklar arasında geriye doğru ilerler. Bu yöntem, indeksin sorgu şekliyle tam olarak eşleştiği durumlarda 5ms gibi etkileyici yanıt süreleri sağlayabilir.
Ancak, sorguya WHERE koşulları eklendiğinde durum değişir. Örneğin, WHERE severity < 3 gibi bir filtreyle birlikte Top K sorgusu çalıştırıldığında, PostgreSQL bir ikilemle karşılaşır. Ya doğru sıralamayı sağlamak için B-tree indeksini kullanır ancak her satır için filtreyi kontrol etmek zorunda kalır ve çoğu satırı atar (bu da tüm indeksi taramak anlamına gelebilir), ya da önce filtreye uyan satırları tarar ve ardından sonuçları sıralar (bu da sıralama maliyeti getirir). Her iki durumda da, PostgreSQL K'den çok daha fazla satırı taramak zorunda kalır ve sorgu performansı 15 saniyeye kadar düşebilir. Bu durum, özel Top K optimizasyonlarına sahip Lucene/Tantivy gibi arama kütüphanelerinin veya ParadeDB gibi veritabanlarının neden farklı bir yaklaşım benimsediğini göstermektedir.
PostgreSQL'deki Top K sorgularının, basit indekslemeyle çözülemeyen karmaşık performans sorunları barındırdığını ve özellikle filtrelerle birlikte kullanıldığında özel optimizasyonlar gerektirdiğini ortaya koyuyor.