Sorgu Yürütme Operatörleri
Sorgu yürütme operatörleri, bir veritabanı motorunun bir sorgunun sonucunu üretmek için bir plana dönüştürdüğü ve çalıştırdığı taramalar, seçimler, projeksiyonlar, sıralamalar, birleştirmeler ve birleşimler gibi fiziksel algoritmalardır.
Tanım
Bir sorgu yürütme operatörü, demet akışları üzerinde bir algoritma olarak ilişkisel-cebir işleminin bir uygulamasıdır; operatörler, yürütüldüğünde bir sorgunun sonucunu hesaplayan bir ağaç veya boru hattı (pipeline) halinde birleştirilir.
Kapsam
Bu konu, bir sorgu motorunun fiziksel operatörlerini ve bunların yürütme için nasıl organize edildiğini kapsamaktadır: yineleyici (aç-sonraki-kapat) modeli, boru hattı (pipelining) ve materyalizasyon (materialization), tablo ve indeks taramaları, seçim ve projeksiyon, harici birleştirme sıralaması (external merge sort), gruplama ve birleştirme (aggregation) ve mükerrer kayıt eleme (duplicate elimination). Operatörlerin demet akışlarını (tuple streams) nasıl tükettiğini ve ürettiğini, bellek ve G/Ç'nin maliyetlerini nasıl etkilediğini ele almaktadır. Birleşim algoritmalarının (join algorithms) ve operatörler arasından seçim yapan optimize edicinin (optimizer) ayrıntıları bu konunun kapsamı dışındadır, bunlar bitişik konulardır.
Temel sorular
- Yineleyici (aç-sonraki-kapat) modeli, operatörlerin bir boru hattı (pipeline) halinde nasıl birleştirilmesini sağlamaktadır?
- Bir sonuç ne zaman boru hattı (pipelined) olarak işlenir, ne zaman diske materyalize edilir?
- Seçim, projeksiyon ve mükerrer kayıt eleme fiziksel olarak nasıl uygulanmaktadır?
- Harici birleştirme sıralaması (external merge sort), bellekten daha büyük verileri nasıl işlemektedir?
- Bellek bütçesi ve G/Ç maliyeti operatör performansını nasıl şekillendirmektedir?
Anahtar kavramlar
- yineleyici / aç-sonraki-kapat modeli
- tablo ve indeks taramaları
- seçim ve projeksiyon operatörleri
- harici birleştirme sıralaması (external merge sort)
- karma tabanlı gruplama (hash-based grouping)
- birleştirme operatörleri (aggregation operators)
- mükerrer kayıt eleme
- boru hattı (pipelining) ve materyalizasyon (materialization)
Temel kuramlar
- Yineleyici (Volcano) modeli
- Her operatör aç (open), sonraki (next) ve kapat (close) yöntemlerini sunar ve isteğe bağlı olarak alt öğelerinden demetleri çeker; bu tek tip arayüz, rastgele operatörlerin boru hatları (pipelines) halinde birleştirilmesine olanak tanır ve çoğu sorgu motorunun temelini oluşturur.
- Boru hattı (Pipelining) ve materyalizasyon (Materialization)
- Boru hattı (pipelined) operatörleri, ara sonuçları yazmadan demetleri doğrudan üst öğelerine ileterek G/Ç'den tasarruf ederken, sıralama gibi engelleyici (blocking) operatörler çıktı üretmeden önce girdilerini materyalize etmek zorundadır; optimize edici bu ikisi arasında denge kurar.
- Harici sıralama ve birleştirme (aggregation)
- Veri belleği aştığında, harici birleştirme sıralaması (external merge sort) ve karma tabanlı gruplama (hash-based grouping) veriyi disk üzerinde geçişler halinde işler; bu algoritmalar ORDER BY, GROUP BY, mükerrer kayıt eleme ve sıralama-birleştirme (sort-merge) birleşimlerinin temelini oluşturur.
Klinik önem
Yürütme operatörleri, bir sorgu planının tahmini maliyetinin gerçek çalışma zamanına dönüştüğü noktadır: operatörlerin seçimi ve uygulanması, belleği ne kadar iyi kullandıkları ve gereksiz disk G/Ç'sinden ne kadar kaçındıkları, bir veritabanının hizmet verdiği her sorgunun verimini (throughput) ve gecikme süresini (latency) belirlemektedir.
Tarihçe
Yineleyici modeli, Graefe'nin Volcano sorgu değerlendirme çerçevesinde ve ilişkisel motorlar tarafından kullanılan fiziksel operatörleri kataloglayan 1993 tarihli sorgu değerlendirme teknikleri araştırmasında kristalize olmuştur. Modelin tek tip arayüzü, genişletilebilir, birleştirilebilir sorgu motorlarını pratik hale getirmiş ve standart olarak kalmıştır; daha sonraki çalışmalar daha fazla verimlilik için vektörleştirilmiş ve derlenmiş yürütme eklemiştir.
Öne çıkan isimler
- Goetz Graefe
- Jeffrey D. Ullman
İlgili konular
Temel eserler
- graefe1993
- garciamolina2008
Sıkça sorulan sorular
- Yineleyici modeli nedir?
- Her fiziksel operatörün aynı arayüzü — genellikle aç (open), sonraki (next) ve kapat (close) — uyguladığı ve üst öğesi sonraki (next) yöntemini çağırdığında demetleri birer birer ürettiği bir tasarımdır. Tüm operatörler bu arayüzü paylaştığı için, rastgele plan ağaçlarına takılabilirler ve demetler isteğe bağlı olarak ağaç boyunca yukarı doğru akar.
- Bazı operatörlere neden engelleyici (blocking) denmektedir?
- Engelleyici (blocking) bir operatör, tüm girdisini tüketene kadar herhangi bir çıktı üretemez — sıralama ve belirli birleştirmeler (aggregations) buna örnektir, çünkü nihai sonuç her girdi demetine bağlıdır. Engelleyici operatörler girdilerini materyalize etmek zorundadır, oysa seçim gibi boru hattı (pipelined) operatörleri ilerledikçe sonuçları yayabilir.