Query Processing and Optimization for a Custom Retrieval Language (2022)

Abstract: Data annotation has been a pressing issue ever since the rise of machine learning and associated areas. It is well-known that obtaining high-quality annotated data incurs high costs, be they financial or time-related. In our previous work, we have proposed a custom, SQL-like retrieval language used to query collections of short documents, such as chat transcripts or tweets. Its main purpose is enabling a human annotator to select “situations” from such collections, i.e. subsets of documents that are related both thematically and temporally. This language, named Matcher, was prototyped in our custom annotation tool. Entering the next stage of development of the tool, we have tested the prototype implementation. Given the language’s rich semantics, many possible execution options with various costs arise. We have found out we could provide tangible improvement in terms of speed and memory consumption by carefully selecting the execution strategy in each particular case. In this work, we present the improved algorithms and proposed optimization methods, as well as a benchmark suite whose results show the significance of the presented techniques. While this is an initial work and not a full-fledged optimization framework, it nevertheless yields good results, providing up to tenfold improvement.

## introduction in recent years, rule-based approaches to various tasks pertaining to information extraction (ie) and natural language processing (nlp) have been "benched" by the academic community. even ten years ago, rule-based systems were on their downfall of popularity @xcite , and the situation does not seem to have changed now with the rise of machine learning models that are easily fine-tuned for any tasks and frameworks that provide even non-experienced users with all the necessary tools. even the task of data annotation, which has been traditionally dealt with via manual labour, can now be simplified by annotation tools that leverage machine learning capabilities foot_0 . methods such as few-shot or zero-shot learning can help deal with the problem of limited available data, and produce outstanding results in domain-independent natural language tasks. however, rule-based approaches have held their ground in a specific area: industrial applications, especially those that require domain adaptation @xcite , such as biomedical information extraction @xcite . in settings that require high accuracy, the convenience of using an ml model can be traded off to obtain better results. however, using a declarative approach instead of a classical approach to ie (programs written in general-purpose programming languages intended for extraction of "hard-coded" features) adds the convenience and flexibility back. additionally, using such approaches can help overcome issues with machine learning bias @xcite , unfortunate examples of which have been recorded many times. furthermore, the questions of performance and costs constitute a pressing issue. using machine learning in an enterprise environment usually requires the company to both obtain expensive computational resources such as specialized gpus and develop new etl pipelines, given the need to protect the data that their customers provide. furthermore, using an ml model might just not be fast or scalable enough for a business need. however, a rule-based approach to information extraction is scalable by definition, with the help of optimization and other techniques. our project, chat corpora annotator, implements a rule-based approach. it is intended for the task of data exploration and subsequent annotation. at present, its main use is exploring very long chat transcripts with extracting and annotating subsets of messages with open-domain tagsets defined by the user. a sim-figure 1 : the matcher interface implemented inside chat corpora annotator. the left side of the window contains all of the available operators, as well as the word lists used for matching. the top frame contains a matcher query, and the bottom frame contains its results, which can be navigated using the buttons below. the messages that match the query are highlighted in red. the query can be interpreted as extraction of mentions of job postings. the first version of matcher was more of a prototype than an actual ready-to-use instrument, and, subsequently, the methods that actually retrieved and matched messages were implemented without optimization at all. developing the second version, we ran into many performance-related issues while testing matcher on large datasets, especially complex queries with several sub-queries, such as extremely long processing times. therefore, we have proceeded with the decision to develop and study various query evaluation strategies for our language. query optimization is an essential part of database query processing, so we reuse some of its core ideas in our approach. overall, the contributions of this paper are: the rest of this paper is organized as follows: section 2 contains an overview of related work, section 3 provides a description of our query language, section 4 describes the algorithms that we propose for query optimization, and section 5 and section 6 describe the benchmark and showcase the experimental results. finally, we give some concluding remarks in section 7. ## matcher query language matcher query language consists of a basic set of rule-based matching operators, which can be combined into a matcher with boolean operators, and which, in turn, can be combined into matching groups with commas. furthermore, matcher also contains a restriction operator inwin and the unr modifier, which will be explained below. the formal query syntax of matcher is as follows: here, bold denotes language keywords and regular denotes nonterminal symbols. let us consider the language in a bottom-up fashion. formally, a matcher is a template that is matched against a single message in chat history. it consists of a boolean expression which is evaluated for each message, and if it equals true, then the message is added to the output. therefore, a matching group is a set of matchers, each of which provides a single message for the output. in the formal syntax, a matcher is described by the restriction nonterminal symbol, an individual rule-based matching operator by condition, and a matching group by the restriction_seq. the currently the available set of rule-based matching operators is the following: matcher relies on a simple data schema consisting of three fields: a username-like field, a date-like field, and a text-like field. cca focuses on chat datasets, and we believe that this is a minimal restriction on such data. next, the body nonterminal symbol specifies two admissible types of queries: matcher-only and subquery-only. the first one consists only of matchers separated by commas. the second one requires nested selects (separated by semicolons) inside the parent select. matcher-only queries are intended for simple use-cases, while queries with subqueries provide flexibility by allowing to express complex patterns, constructing them in a bottom-up fashion. such queries concatenate results of individual subqueries while checking additional restrictions such as distance between them and ordering. matcher supports subqueries of arbitrary depth. use-case examples are provided in section 5. the window nonterminal describes an optional inwin clause. it provides a way to explicitly restrict the length of the window in which all matched messages should fit. for example, query select hasdate(), haswordofdict(me eting) inwin 20 means that in each returned set of messages, the two messages that conform to the matchers must not be further away than 20 messages from each other. if not specified, this length is implicitly restricted to 50 on the language implementation level for performance reasons. the current version of matcher has been extended with a special unr clause, which significantly improves the expressiveness of the language. it is a modifier that removes the match order constraint on matching groups. without this clause, the outputs of each matching group are ordered according to their order in the query. ## benchmark to ensure repeatability we have created a benchmark which consists of four queries and a message set. this message set contains the first 1 million messages from the freecodecamp gitter chat dataset, available on kaggle foot_2 . its lucene index takes around 100mb of disk space. listing 1: query 1 (q1) select hasword(job), hasword(code), hasusermentioned(kadams223) unr inwin 40 the q1 query matches a group of three messages that have words related to jobs, words related to code and a mention of a specific username. it can be interpreted as extracting a discussion that the specified user has been actively partaking in, receiving many replies. this is a simple query that illustrates the concept behind the unr clause. the results of the matchers are not ordered in accordance to their order in the query, but the whole group should fit into a window of 40 messages. note in that the following listings haswordofdict was shortened to hasword for better readability. listing 2: query 2 (q2) select hasword(job), hasword(skill), hasword(skill), hasword(area), hasword(money) inwin 40 q2 extracts a group of five messages that discuss coding job listings with the mentions of the area of the job, required skill and the salary. this is a simple query with no subqueries, however, it has many matchers and a window length of 40 messages in which the extracted group should fit. listing 3: query 3 (q3) select (select hasword(job), hasword(skill), hasword(code), byuser(lumiras) inwin 60 ); (select byuser(lumiras) and hasword(issue) ) inwin 200 the q3 query extracts the following information: a discussion of job search and coding languages in which user lumiras took part, and it is followed by an issue alert by the same user. this query contains two subqueries, the first of which has a medium-sized window, and the second one has a boolean and which specifies that the output of this matching group, containing a single message, must be by the specified user and contain a reference to an issue. listing 4: query 4 (q4) select (select hasword(job), hasword(skill), hasword(code), byuser(lumiras) ); (select hasword(job), hasword(skill), hasword(code), byuser(odrisck) inwin 40 ); (select hasword(job), hasword(skill), hasword(code), byuser(odrisck) inwin 40 ) inwin 300 q4 extracts three message groups, each of which discusses job search and coding languages. user lumiras participates in the first group, and user odrisck takes part in the second and the third. this query contains three similar subqueries and a large window for the groups to fit in. ## experiments and discussion experimental evaluation was conducted on a pc with the following characteristics: 8-core in-tel®core™ i7-11800h cpu @ 2.30ghz, 16 gb ram, running windows 10.0.19042.1645 (20h2/october2020update). the current version of cca is implemented in c# (.net 6, wpf) using the following libraries: antlr4, lucene.net 4.8.0, newtonsoft.json, and softcircuits.csvparser. to obtain accurate measurements, we have used benchmark-dotnet v0.13.1 foot_3 . it was run with default parameters, a confidence interval of 99.9% was calculated by the benchmark (as a different number of runs was used in each case), and we manually checked that relative error was less than 2%. our source code is available publicly 5 . in our first experiment we have compared the four initial versions of the algorithm: n+ns, n+s, p+ns and p+s. for this, we used the first four queries of our benchmark. the overall results are presented in to provide better insights into the results, we have also constructed a stacked barchart presented in figure 4 . it shows four approaches each depicted by its own bar. each bar is divided into parts that correspond to the contribution of each method. our experiments have clearly demonstrated that all of the proposed strategies are superior in performance to the basic n+ns. overall, p+s is the most efficient approach, which noticeably beats n+s and n+ns, and to a lesser extent p+ns. it was possible to obtain more that 10x speedup for a subset of queries. the next observation is that sorting of group elements is almost free in terms of time. sorting is conducted inside the visitrestriction function and the second experiment concerned out last strategy, h+s. h+s does not always beat p+s, but it never loses to it, either. we have added the q5 to our benchmark as an example on which h+s beats p+s: it takes 1479 ms compared to 1865 ms, thus providing 25% improvement. ## conclusion and future work in this paper, we have presented and described our custom query language matcher, intended for exploration and annotation of large natural language datasets such as chat transcripts. the main body of our work consisted in optimizing one of matcher's execution stages that deals with merging the results of individual parts of the query, which in essence resembles join optimization. we have created five algorithms and a benchmark of five queries to test them against. we have not presented a proper optimizer, but a collection of simple techniques that nevertheless yield surprisingly good results, providing up to 10x improvement. all this warrants further investigation. concerning our future work, the first evident direction is to implement a proper cost model, design rules for enumerating plan space, employ more sophisticated statistics and estimators of intermediate result sizes. next, looking at graphs for the p+s algorithm, one may notice that for q4, lucene index access has become the most costly part and thus, it is necessary to address this. there are many approaches to optimizing lucene index access which can be investigated. finally, note that matcher itself does not support variables so far, however, it is a necessary feature and it will have impact on optimization.