Estimating the selectivity of Sql Like queries

Abstract

Metin tabanlı verilerin miktarında internet kaynaklarının da etkisiyle gözlemlenen dramatik artış nedeniyle, bu tür verileri esnek arama kalıpları ile sorgulama giderek yaygınlaşmaktadır. İlişkisel veritabanları, SQL LIKE operatörünü kullanarak esnek filtrelerle metinsel verileri sorgulamaya izin vermektedir (örn., LIKE `Sub%`, `Sub` ile başlayan tüm satırlar ile eşleşir). Metinsel verilerin büyük boyutlu olmasından dolayı, bu tür sorguları en verimli şekilde yürütmek, veritabanı performansı için oldukça kritik önem taşır. Verilen bir LIKE sorgusu için en verimli yürütme planını oluştururken, sorgu eniyileyici, sorguda yer alan esnek sorgu yüklemleri için seçicilik tahminine ihtiyaç duyar. Bu tez çalışmasında, bir metin verisi sütundaki veri dağılımını özetlemek üzere yeni bir desen tabanlı histogram yapısı kullanan, SPH ve P-SPH isimleri altında iki yeni algoritma geliştirilmiştir. Daha spesifik olarak, önce bir metin veritabanındaki dizi motifleri (SPH) veya konumsal dizi motifleri (P-SPH) hesaplanır. Sonra bu motiflerden özel bir histogram oluşturulur. Sorgu eniyileme sürecinde, bir LIKE sorgu yükleminin seçiciliğini tahmin etmek için bu histogramlar kullanılır. DBLP bibliyografya verileri üzerinde yapılan deney sonuçları, önerdiğimiz tekniklerin, genel LIKE ifadeleri için literatürdeki son teknikten daha az tahmin hatasına sahip olduğunu göstermektedir. Dahası , önerdiğimiz histogram bazlı teknikler geçmişte önerilen en gelişmiş teknikten iki kat daha az hafıza ve bir kat daha az zaman gerektirir.

With the dramatic increase in the amount of the text-based data which commonly contains misspellings and other typos, querying such data with flexible search patterns becomes more and more commonplace. Relational databases support SQL LIKE operator to allow searching with a particular wild-card predicate (e.g., LIKE `Sub%`, which matches all strings starting with `Sub`). Due to large size of text data, executing such queries in the most optimal way is quite critical for database performance. While building the most efficient execution plan for a LIKE query, the query optimizer requires the selectivity estimate of the corresponding flexible wild-card query predicate(s). To this end, we propose novel algorithms to estimate the selectivity of LIKE query predicates. We first introduce SPH (Sequential Pattern-based Histogram) algorithm that is based on a new type of pattern-based histogram structure to summarize the data distribution in a particular text column. More specifically, we first mine sequential patterns in a given string database, and then construct a special histogram out of the mined patterns offline, i.e., before query processing starts. Then, during query optimization time, pattern-based histograms are exploited to estimate the selectivity of a LIKE predicate. The experimental results on a real dataset from DBLP show that the proposed techniques outperform the state of the art for generic LIKE queries like %s1%s2%...%sn% where si represents one or more characters. What is more, the proposed histogram structure requires more than two orders of magnitude smaller memory space, and the estimation time is almost an order of magnitude less in comparison to the state of the art. Next, we introduce another LIKE query selectivity estimation algorithm, called P-SPH. P-SPH extends SPH in three distinct ways: (i) it extends regular sequence patterns into more specific positional sequence patterns, and use them in its histograms, (ii) it introduces a slider-based more flexible matching scheme, and (iii) it employs an information-theoretic redundant pattern elimination mechanism. We experimentally demonstrate that P-SPH further improves the accuracy of SPH at the expense of using more memory.