Estimating the selectivity of LIKE queries using pattern-based histograms

Mehmet Ayti̇Mur, Ali Çakmak*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Accurate cost and time estimation of a query is one of the major success indicators for database management systems. SQL allows the expression of flexible queries on text-formatted data. The LIKE operator is used to search for a specified pattern (e.g., LIKE “luck%”) in a string database. It is vital to estimate the selectivity of such flexible predicates for the query optimizer to choose an efficient execution plan. In this paper, we study the problem of estimating the selectivity of a LIKE query predicate over a bag of strings. We propose a new type of pattern-based histogram structure to summarize the data distribution in a particular column. More specifically, we first mine sequential patterns over a given 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 a real 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 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.

Original languageEnglish
Pages (from-to)3319-3334
Number of pages16
JournalTurkish Journal of Electrical Engineering and Computer Sciences
Volume26
Issue number6
DOIs
Publication statusPublished - 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
© TÜBİTAK.

Keywords

  • Data management
  • Histograms
  • Selectivity estimation
  • Sequence mining

Fingerprint

Dive into the research topics of 'Estimating the selectivity of LIKE queries using pattern-based histograms'. Together they form a unique fingerprint.

Cite this