Sorgu İşleme ve Optimizasyonu
Sorgu işleme, bir sorguyu değerlendirmek için tersine çevrilmiş bir dizini (inverted index) tarayan algoritmalar kümesidir ve optimizasyon teknikleri, gereksiz işlerden kaçınarak bu süreci hızlandırmaktadır.
Tanım
Sorgu işleme ve optimizasyonu, tersine çevrilmiş gönderileri (inverted postings) tarayarak bir sorgu için eşleşen veya en üst sıradaki belgeleri hesaplayan algoritmaların tasarımıdır; ayrıca, sonucu değiştirmeden (veya değişimi sınırlayarak) puanlanan belge sayısını ve okunan gönderi sayısını en aza indiren budama ve sıralama tekniklerini de içermektedir.
Kapsam
Bu konu, sorguların tersine çevrilmiş bir dizine (inverted index) karşı nasıl verimli bir şekilde değerlendirildiğini ele almaktadır: Boolean sorgular için gönderi listesi (postings-list) kesişimi ve birleştirilmesi, sıralı erişim (ranked retrieval) için belge bazında (document-at-a-time) ve terim bazında (term-at-a-time) stratejiler ve en iyi sonuçlara giremeyecek belgeleri atlayan MaxScore ve WAND gibi dinamik budama (dynamic pruning) algoritmaları aracılığıyla en iyi k (top-k) optimizasyonu incelenmektedir. Atlatma işaretçileri (skip pointers), sorgu yeniden sıralaması ve katmanlı veya iki seviyeli erişim (tiered or two-level retrieval) konularını ele almakta olup, sıralama modeli veya dizin kodlamasından ziyade sonuçların döndürülmesindeki algoritmik verimliliğe odaklanmaktadır.
Temel sorular
- Boolean ve sıralı sorguları değerlendirmek için gönderi listeleri nasıl kesiştirilir veya birleştirilir?
- Belge bazında (document-at-a-time) ve terim bazında (term-at-a-time) değerlendirme arasındaki fark nedir?
- Her aday belgeyi tam olarak puanlamadan en iyi k (top-k) sonuçları nasıl bulunabilir?
- MaxScore ve WAND gibi dinamik budama (dynamic pruning) yöntemleri belgeleri güvenli bir şekilde nasıl atlar?
- Atlatma işaretçileri (skip pointers) ve sorgu yeniden sıralaması iş yükünü nasıl azaltır?
Anahtar kavramlar
- gönderi kesişimi ve birleştirilmesi
- belge bazında (document-at-a-time) değerlendirme
- terim bazında (term-at-a-time) değerlendirme
- en iyi k (top-k) erişimi
- dinamik budama (dynamic pruning) (MaxScore, WAND)
- atlatma işaretçileri (skip pointers)
- sorgu terimi yeniden sıralaması
- iki seviyeli / katmanlı erişim
Temel kuramlar
- Belge bazında (document-at-a-time) ve terim bazında (term-at-a-time) değerlendirme
- Sıralı erişim (ranked retrieval), tüm sorgu terimlerinin gönderilerini belge sırasına göre ilerleterek her belgenin puanını aynı anda biriktirebilir veya bir terimin gönderilerini bir sonrakine geçmeden önce tamamen işleyebilir; bu seçim bellek kullanımını, budama fırsatlarını ve önbellek davranışını etkilemektedir.
- En iyi k (top-k) erişimi için dinamik budama (dynamic pruning)
- Mevcut k'inci en iyi belgenin puanını koruyarak ve terim başına maksimum puan sınırlarını kullanarak, MaxScore ve WAND gibi algoritmalar, en iyi k'ye giremeyeceği kanıtlanmış belgeleri atlamakta ve aynı sıralı sonuçları çok daha hızlı döndürmektedir.
Klinik önem
Verimli sorgu işleme, milyarlarca belge üzerinde etkileşimli, düşük gecikmeli aramayı mümkün kılan unsurdur. WAND gibi dinamik budama teknikleri, yaygın olarak kullanılan arama motorlarında ve açık kaynaklı arama kütüphanelerinde uygulanmakta olup, büyük ölçekte yanıt süresini ve hizmet maliyetini doğrudan kontrol etmektedir.
Tarihçe
Temel sorgu değerlendirme stratejileri ve optimizasyonları 1995 yılında Turtle ve Flood tarafından sistemleştirilmiştir. Web araması ölçeklendikçe, en iyi k (top-k) optimizasyonu kritik hale gelmiş ve Broder ve meslektaşlarının 2003 yılındaki WAND algoritması güvenli dinamik budamayı (dynamic pruning) yaygınlaştırmıştır. Sonraki blok tabanlı varyantlar değerlendirmeyi daha da hızlandırmış olup, bu yöntemler günümüzde üretim erişim motorlarında standart olarak kullanılmaktadır.
Öne çıkan isimler
- Howard Turtle
- Andrei Z. Broder
- David Carmel
- W. Bruce Croft
İlgili konular
Temel eserler
- turtle1995
- broder2003
- manning2008
Sıkça sorulan sorular
- En iyi k (top-k) erişimi nedir?
- En iyi k (top-k) erişimi, tüm koleksiyonu puanlamak ve sıralamak yerine, bir sorgu için yalnızca en yüksek puan alan k belgeyi döndürmek anlamına gelmektedir. Kullanıcılar yalnızca ilk sonuçları gördüğü için, sistemler bunu en iyi k'ye giremeyecek belgeleri atlamak için kullanmakta ve önemli ölçüde iş yükünden tasarruf sağlamaktadır.
- WAND gibi budama yöntemleri kayıpsız mıdır?
- Temel güvenli formlarında evet: MaxScore ve WAND, en iyi k'ye giremeyeceği kanıtlanmış belgeleri atlamakta, bu nedenle kapsamlı puanlamayla tamamen aynı sıralı sonuçları, sadece daha hızlı bir şekilde döndürmektedirler. Yaklaşık varyantlar, ek hız karşılığında küçük bir doğruluk kaybını kabul etmektedir.