Estimating the selectivity of LIKE queries using pattern-based histograms

Abstract

Accurate cost and time estimation of a query is one of the major success indicators for database managementsystems. SQL allows the expression of flexible queries on text-formatted data. The LIKE operator is used to search for aspecified pattern (e.g., LIKE “luck%”) in a string database. It is vital to estimate the selectivity of such flexible predicatesfor the query optimizer to choose an efficient execution plan. In this paper, we study the problem of estimating theselectivity of a LIKE query predicate over a bag of strings. We propose a new type of pattern-based histogram structureto summarize the data distribution in a particular column. More specifically, we first mine sequential patterns over agiven string database and then construct a special histogram out of the mined patterns. During query optimization time,pattern-based histograms are exploited to estimate the selectivity of a LIKE predicate. The experimental results on areal dataset from DBLP show that the proposed technique outperforms 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 requiresmore than two orders of magnitude smaller memory space, and the estimation time is almost an order of magnitude lessin comparison to the state of the art.