In research, searching for patterns within large datasets is a common task but often results in long-running queries. Various approaches exist to speed up individual searches, for example, indexing, denormalization, or caching. These approaches come with their advantages, but also limitations. For caching, the data is usually either cached on a low level, for example, to bufer data structures in memory to increase the read access performance, or the complete results are stored for specific queries so that if the same query is observed again, the system can serve the cached result instead of recomputing the results in the database management system. In this work, we propose an architecture that can increase read performance by utilizing a caching approach that acts as an index by storing references to distinct partitions based on partial queries. This allows memory-eficient caching while gaining the ability to improve not only already-seen queries but also queries that have not been computed before. This approach is designed for workloads often observed in scientific domains, targeting analytical queries that search for patterns in datasets, for example, in bioinformatics, spatial data, or time series.
are individual days in temporal data, regions in geospatial data, or experiments in scientific data. To obtain all In the scientific domain, one of the often occurring tasks matches where the given properties are fulfilled, usually is to search for defined patterns, for example, searching all partitions need to be searched. Putting diferent data for patterns in protein structures in bioinformatics [1] or points in relation to each other requires joining them. patterns in spatial datasets [2]. While simple properties Optimizing the join order or using search trees speeds are fast to find in datasets using index structures, other up processing. If the attribute conditions are not specific, properties are more complex or require computational ef- a high number of join candidates need to be considered, fort if several data points are put in relation to each other. and indexes may be of limited use. Optimizations do If the pattern contains, for example, several spatial points not remove the necessity of performing time-consuming with distance constraints, the distances between many computations in many cases. This is especially troublepossible points need to be calculated for each search. some if these queries have an increased runtime due to This can be even more challenging if distances are not complex conditions and a large dataset spanning across Euclidean but, for example, require a shortest-path rout- many partitions. ing. Complete denormalization is often impractical since Even if analytical queries often have conditions specthe selected points can vary depending on the query and ified that are used frequently among several searches, use case. Although relations between points can be de- their results are often recomputed for each new search. normalized in a small dataset, for example, in a property To reduce the number of required condition checks, graph, there would be too many possible combinations we aim to store already computed conditions of partial in large datasets. If a changing set of rows, depending on queries. specified attributes, is put into relation to each other, the We propose utilizing an architecture that enriches a data is often stored in a relational database management cache with already-seen queries and their derivatives. To system (RDBMS). gain the derivatives, we utilize query decomposition to
As usually only points within the same area need to ifnd partial queries. This cache acts as an index structure be compared, many problems can be divided into individ- to map queries to partitions to reduce the search space ual search problems if the dataset has multiple disjunct for a given query. The cache stores references to all parpartitions. Examples of natural partitions in datasets titions with at least one result for the specific cached query, reducing the number of partitions that must be 35th GI-Workshop on Foundations of Databases (Grundlagen von Daten- searched if the system encounters a query found in the banken), May 22-24, 2024, Herdecke, Germany. cache. This allows for more flexible utilization, as im$ martin.poppinga@uni-hamburg.de (M. Poppinga) provements are not restricted to a specific kind of query, 0000-0001-8529-8376 (M. Poppinga) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License as in many denormalization approaches. It also allows Attribution 4.0 International (CC BY 4.0). for combining multiple cache hits for one query, unlike a number may become too large to be represented as a common result cache, allowing it to work for new queries. graph or otherwise denormalized. Utilizing already-seen query parts can be combined with Relational database management systems (RDBMS) are a warmed-up cache approach, where we pre-populate generally utilized to store normalized data. Here, each the cache with expected conditions, like an often-used data point is stored in a row in a table and joined with timespan, a specific set of regions or experiments, or other data points depending on the query, computing predefined fingerprints. relations, and checking conditions if needed. RDBMS can handle large amounts of data and, in many cases, achieve very good performance metrics. Depending on 2. Background the data and queries, diferent index structures are used to increase read performance, common structures are 2.1. Definitions B-trees [8], r-trees [9] for spatial data, or bitmap indexes A partition consists of a set of data points where the data [10] for range conditions. Index structures allow individcan be put in relation to each other. These can be, for ual rows or sets of rows to be found eficiently, but can example, spatial areas, time frames, or individual experi- lose efectiveness in cases where rows are put in relation ments. This work focuses on disjunct natural partitions to each other and single conditions are not very selective defined by some partition key per data point. If overlap- (see Section 3.1). ping partitions are required, data points can be duplicated to all relevant partitions to ensure that matches are found Searching Patterns This work aims mainly to imwithin one partition. prove query runtime to find geometric patterns in protein
A query is a defined search in a dataset. For this work, data [1]. However, it is also targeted to resemble a useful we focus on analytical SQL queries that search for groups approach for searching for spatial properties in geospatial of data points related to each other. They specify con- datasets [2] and other domains that face similar workditions that describe a pattern searched in the data to loads. In previous work [11], we showed that for our mine for matching occurrences. They match within a scientific workload in GeoMine [ 1], the database mansingle partition and often place data points in relation to agement system achieved better performance if given each other by some property, such as a distance. See also lfexibility to reorder and optimize query execution plans, Section 3.1. in contrast to customized algorithmic approaches. Al
A partial query is a query that uses only a subset of though systems can optimize query execution plans, the predicates of another query by removing one or multiple query and index design must also be suficient to allow conditions or dimensions involved. One query can have such optimizations. However, with increasing dataset multiple partial queries as derivates. Such partial queries size, these classical approaches came to their limits if the are created by decomposing queries[3]. whole dataset needed to be searched. 2.2. Related Work Caching Diferent techniques are utilized to improve query response times in databases. One way to reduce Database Systems Depending on the workload, dif- the computational load is by reusing already computed ferent storage models in database systems have advan- results by caching parts of the data. RDBMS often bufer tages over others. Designated solutions target scien- pages in memory to prevent slow access to secondary tific data, such as SciDB[ 4] or DuckDB[5]. As column- storage, for example, often accessed indexes or tables. As based databases generally perform well for aggregations relational databases focus on data consistency, serving [6], they are often used for analytical queries. Systems outdated results would be a big issue. Cache invalidation, like DuckDB target OLAP (Online Analytical Processing) deciding if a cache no longer holds a valid result set, is a queries, while most relational systems focus on OLTP big problem and can cause computational overhead. (Online Transaction Processing). While column-based It is also possible to cache the complete results resystems are beneficial for most analytical queries, as ag- lated to a query, allowing for a fast return of previously gregations on individual rows are of interest, queries that seen queries. This reduces the load on databases that freneed to be executed on various subsets of the data and quently serve the same queries, for example, on a website. use changing attributes for selections often rely on row- This can be directly integrated into the database or added based systems. Many approaches to improve query speed as a separate caching layer in the application logic or include data denormalization [7]. If relationships are of by using some middleware. Often, such approaches utiinterest, graph databases are often utilized. However, lize designated in-memory key-value stores for caching on large datasets, if each point has a potential (spatial) [12].However, these approaches only serve the results to relationship to all other points in the same partition, the exactly these queries that have been computed before, and if large result sets are returned, memory consump- The described environment is related to the workload tion is also of concern. Other approaches, for example, described in GeoMine [1], but it is also expected to be simfor SBQL (Stack-based Query Language), use the object- ilar in other scientific domains. It is designed for a useroriented model to decompose a query and cache specific defined search through a research application where the subqueries based on the object tree [13]. user defines properties that must be matched in the data. Such flexible data mining tasks are often exploratory, runMaterialized Views On many systems, materialized ning similar queries until the desired pattern is found. views [14] do exist, which serve similar purposes as result The conditions bring various data points in relation caching. They allow precomputation of SQL expressions to each other, for example, by defining the distances beand transformations, reducing the need to compute these tween various points selected by their attributes. This parts for each query execution. These views can be uti- creates queries that join several large tables in a single lized directly in queries by specifying the view in contrast query [11], as, for example, an SQL query processed by to the base table. Furthermore, there are approaches to an RDBMS. Such a query looks for all occurrences of the redirect queries from the base table directly to the mate- specified properties within several areas. The diferent rialized view by rewriting the queries [14]. areas can be viewed as natural partitions specified by
Keeping the views valid is usually transparent to the partition keys. In our example (see Listing 1), these are user as the RDBMS handles the updates if entries are cities, reducing required table joins to those within a city. added or updated. However, as with other denormaliza- In other workloads, such partitions could be individual tion techniques, they come with increased storage con- experiments or data sources with no relevant connecsumption and reduced write performance. In addition, tions between two partitions. Data points are selected precomputations are usually only beneficial for specific by their attributes, such as the type or name of a point queries; if varying queries are expected, multiple mate- of interest (POI), and placed in relation to each other, for rialized views are required, often with individual index example, by a maximum distance. One query consists of structures, which further increase storage consumption. multiple references to one or more tables that are related to each other, if no special conditions between individual data points are specified, the result consists of all combinations of all matching points within a partition. Further, partitions can be part of other conditions like a subquery restricting the number of partitions.
indexes to fingerprinted structures are specified. Such descriptors describe the areas in which these predefined structures are present. For example, in [15], spatial triangle structures are defined in a fingerprinting approach.
The triangle descriptor, a bit vector, represents whether the given triangle is in a partition. This allows the extraction of all specified triangles (or, more generally, defined SELECT p1 . name patterns or fingerprints) from a query and compares all FROM p o i a s p1 , p o i a s p2 , p o i a s p3 bit filters to reduce the number of partitions to search in WHERE p1 . t y p e = ’ s c h o o l ’ the following steps. AND p2 . name I L I K E ’ %museum% ’
There are two ways to specify which structures are AND p3 . t y p e = ’ s o c c e r _ f i e l d ’ present in which partitions. An inverted index describes AND d i s t ( p1 . geom , p2 . geom ) < 2 0 0 which partitions each descriptor is present in, for exam- AND d i s t ( p1 . geom , p3 . geom ) < 5 0 0 ple, by providing a list of partition keys or using a bit AND p1 . c i t y = p2 . c i t y vector in which the partitions are encoded. Alternatively, AND p1 . c i t y = p3 . c i t y a forward index can be used where it is for each parti- AND p1 . c i t y i n ( SELECT c i t y FROM tion specified which descriptors are present. This can be c i t i e s WHERE p o p u l a t i o n < 1 0 0 0 0 ) stored as a list again, or if only estimated containment is needed by structures like bloom filters, which reduces the memory footprint. Both approaches have advantages and drawbacks depending on the individual workload.
tions between several points
As only spatial relations within a partition need to be computed, this reduces the number of required comparisons; still, many combinations of data points must be checked. As the number of relevant points can often be reduced by filtering for the point’s attributes, the usage 3. Basic Concept of spatial indexes in the presence of a partition key is of limited use if the partitions are small. In our example, 3.1. Problem Description we could use a spatial index to select all points that are within the defined distance. However, since attributes Our work aims at scientific workloads with no frequent need to be checked for each point, in many cases, it is updates, where we want to improve query response times. faster to instead filter for the attributes and compute the distances to all matching points within the partition. As each query may filter for diferent attributes, multiple indexes would be required, creating even more overhead maintaining combined spatial indexes. Furthermore, because of the high number of theoretical combinations, the distances can usually not be easily precomputed, which limits the usage of range-based indexes.
In cases where we have a highly selective point, we can directly limit the search to these partitions. However, individual data points, even if filtered by multiple attributes, are often not very specific, as similar points are present in many, if not most, partitions. For example, most cities will have a school, many a school with a nearby soccer field, but only a few also have a nearby museum, while each type of POI may be present in most cities. If the search contains, for example, conditions with text searches with a prefixed wildcard, a high number of points may need to be evaluated, even if a point has only a few matches, due to limited indexing possibilities. Although each point itself is not very selective, the combination of several points, together with distance constraints, reduces the number of results.
Depending on the environment, a dataset can consist of thousands to millions of partitions and data points can have low cardinality, so that single conditions are very unspecific. As matches can theoretically occur in all partitions, the entire dataset with many points must be considered for each query. One way to reduce the search space is to utilize caching.
Our approach does not aim to replace the RDBMS; it tries to help the system search more eficiently by reducing the search space. If only a limited number of partitions need to be considered, less data must be read from the secondary storage, and the computational efort of distance checks needs to be performed in fewer partitions. In contrast to other caching approaches, we focus on the partition keys instead of the actual results; this has several benefits, as will be discussed later. We must know which partitions the query may find valid results, to reduce the search space. As we search for conjunctive conditions, we can determine that partitions in which at least one query condition is not fulfilled cannot contain a valid result. The same is true for any subset of conditions or tables involved.
Using this property, we can check for each (sub)set of conditions if we have information stored; if we have information, we can restrict the search to the stored partitions, as shown in Figure 1. , and are sets of partition keys based on conditions , and . These conditions can be selections on attributes of a single point, as well as multiple points that are put in relation to each other via a distance or similar. If we have stored the set of A
A∩B
A∩B A
B A∩B∩C A∩C
A C
A∩C
C partition keys in which conditions ∧ are fulfilled and the set of partition keys in which ∧ is fulfilled from previous queries, we can restrict the search space for a new query ∧ ∧ to a smaller number of partitions in ∩ ∩ .
This way, we can restrict the search to the intersection of all known conditions if we have information on multiple subsets of conditions. In the best case, combining several conditions can restrict the search space to only those partitions where we have valid results. This can be, for example, the case if seeing a very similar query or having encountered multiple queries that contain each one part of the new query. This approach works best if a restrictive part of the query has been cached, so new queries which added or changed other constraints benefit, but also combining several less restrictive sets of partition keys can lead to a overall reduced number of partitions to search.
The cache will be populated by analyzing queries observed on the database system. The system will monitor the database logs and obtain all queries that are run against the database. It will rerun the queries seen in the database and store the resulting partition keys. Furthermore, the system will identify partial queries, which are queries that are based on the original search but omit one or more of the joined tables. These partial queries consist of all possible combinations that are conjunc- Hashes Partition keys tively connected. For this, the conjunctive normal form hash1 {0,3,4} is created. With this approach, it is more resilient to hash2 {0,1} ∩ {0,4} changes in queries, as we have valid results in the cache Query hash3 {0,1,4,5} if a part of the original query is changed and searched hash4 {3,4,5} again. The system can be restricted to limit the number of hash5 not in cache derivations of the query to prevent too many unspecific partial queries from being created from a decomposed Figure 2: A query is decomposed in partial queries, each query. To ensure better cache utilization, we can addi- represented by a hash; In this example hash1, hash3 and tionally generate more generalized queries, for example, hash5, of whom hash1 and hash3 are already present in the by rounding numeral conditions like distances to integers cache. Hash5 was not found in the cache, as this partial query to prevent cache misses if a distance is slightly changed. wthaesmnaottchseeednhbaeshfoerseaarendinitserisgencotreedda.nTdhceanpatrhteitniobne kuesyeds toof However, defining which generalization steps are helpful restrict the search space to partitions 0 and 4. may depend on the dataset. In a final step, the query is rearranged and normalized so that a unique hash is generated for each query, regardless of diferent named aliases or a diferent ordering of conditions. We utilize with table combinations that have a specific relation to a concurrently running system to avoid a negative im- each other, like a distance metric, as otherwise too many pact on the user experience, which would occur if we results could be found, increasing computation time and materialize intermediate results, as they usually existed the number of partitions. Furthermore, to reduce memonly in memory or were never computed due to optimiza- ory consumption, it could be possible to group partitions tion techniques of the database. The cache now contains and reference these clusters; this can be beneficial if the hashes of (partial)queries with all partition keys where data has many similarities between diferent partitions. results for this query can be found. In a similar approach, queries with similar result sets can be grouped. Here, the hashing function must be adapted and the results for all combined hashes must be united. 3.4. Utilizing the Cache If there are a high number of unspecific conditions, it is If a query is run, it is checked against all known entries also possible to maintain a negative cache, containing in the cache. For this, the query is, like while cache pop- per query all partitions where no matches are found; all ulation, normalized and decomposed into all possible such matches can then be united and used in the SQL partial queries. In addition, more variants can be created query or cut with the result for the positive cache. How than were created while populating the cache. Additional efective it is to store the partition keys instead of the query variants, for example, with a wider range condi- actual results in terms of storage consumption depends tion, can be utilized as long as we can guarantee query on the size of the partitions and the number of results containment so that no results are lost. From all partial per partition. Here, further analyses are necessary for queries found in the caches, the sets of stored partition specific workloads. keys can be intersected, resulting in a set of partition As we focus on read-only and append-only datasets, keys that can then be appended to the SQL query, which cache invalidation is currently not in our focus. For sciis executed on the RDBMS (see Figure 2). The partition entific datasets, many projects work with dataset dumps keys may contain false positives, but the result remains with no updates or only periodic ones. To prevent invalid as the RDBMS still verifies all conditions. definite growth of the cache, eviction strategies, such as least recently used or removing the largest (least specific) cache entries, can be used.
sults, it needs more storage to store partition keys, and, at the same time, it has less benefit in the overall approach.
It is possible to store only queries that yield fewer than a specified number of partitions to reduce the required storage space. To prevent the entry from being calculated repeatedly, a separate table can hold the number of partitions resulting from each query, indicating that the query has already been computed. To focus on more specific queries, it can be beneficial to only cache query variants Dataset Updates Datasets can be updated as long as partitions are immutable. Deleting partitions would increase the false positive rate, but not create false negatives. Append-only datasets can be handled by maintaining a list of the newest partition available when adding a query to the cache. If we hit a cache entry created in an old database state, we can identify the oldest state and add all partitions to our result set that were added later.
To prevent a growing number of false positives, cached queries can be rerun to update the set of partitions.
If data within an existing partition is changed, this partition either needs to be considered for each subsequent Data Structure Storing the cache in an inverted index search regardless of its presence in a cache entry, or all or some related data structure helps fast retrieval of the cache entries must be revalidated for this partition. set of partition keys for a given query. Adding a new cache entry is also simple, as just a new key value pair Prepopulation It is also possible to prepopulate the needs to be added, even if this may cause some balancing cache with expected queries, for example, by altering of the data structure. Also, it would be possible to store the seen queries by changing individual attributes. Also, not a set of partition keys but utilizing a bit vector, deoften searched fingerprint-like patterns can be precom- scribing in which partitions the query is matching. Fast puted, and structures specific enough to reduce the intersections are possible here, but storage consumption number of partitions can be integrated, integrating ap- is higher in contrast to sets with only a few members. proaches described in Related Work. Alternatively, a forward index can be used to store the queries that match for each partition. This can reduce Efectiveness This approach relies on recurring pat- storage consumption, but increases search time as all terns in queries and disjunct partitions. This approach indexes need to be checked. However, using probabilistic creates some overhead, so the efectiveness must be high data structures, such as a bloom filter or a hierarchical enough to reduce the overall runtime. For this, the fre- bloom filter, can reduce storage consumption and search quency of the cache hit and the number of false positive time. quotes are most relevant. In addition, it may not be helpful for a search that requires less than a few seconds. 6. Conclusion
In addition to complex partial queries, it may also be beneficial to store simple queries. While these queries can usulay be quickly resolved by a relational system, it can also be beneficial to reduce the number of possible partitions early within a cache as it reduces computational efort in intersecting and rewriting the query. Data Storage Diferent solutions are possible to store the cache. Each cache entry could be realized as a separate materialized view, while query rewriting would allow each existing matching view to be joined to restrict the search space. Similarly, large tables can be utilized to reference partition keys or key-value approaches within the RDBMS. These approaches allow all data to be stored within a single location, and the RDBMS to have maximum freedom for optimization steps. Alternatively, an external key-value store can be used. To integrate this, either a query engine like PrestoDB2 can be utilized, or the RDBMS can provide such integration. Furthermore, query rewriting could happen at the application level, where the cache is based on an embedded store or a separate system.
Although it does not eliminate the need for database computations, our approach aims to reduce the search space within the database and, therefore, the runtime. As we decided to store only the set of partitions and not the actual results, it consumes less memory and creates less overhead to intersect and serialize the query. In addition, 5. Technical Realization cache hits of diferent partial queries can be combined. It allows the utilization of multicolumn indexes based on Usage Although this approach is designed to work partition keys, reducing access time when verifying conwith standard SQL, it should also directly work with ditions. Since sets of partition keys of partial queries can common extensions, such as the spatial PostGIS1 exten- be intersected, it is more resistant to changes in queries sion for PostgreSQL. The approach itself is also not lim- than other approaches. This allows it to provide cached ited to a defined language and can be utilized in various results even if new queries are run that combine elements environments. Furthermore, this approach can still be of already existing queries. In contrast to approaches that combined with alternative techniques, such as a fan-out rely solely on precalculated structures, this approach is in distributed setups or specilized index structures. more flexible in terms of relevant structures expressed by the queries, which allows for a better reduction of the search space.
Open questions remain for future work as the choice of technology is still open for discussion. Although the general approach works with diferent technologies, depending on the specific workloads, the utilization of inverted and forward indexes, as well as the usage of sets and descriptors, must be evaluated. Diferent approaches may be combined to utilize positive and negative sets or probabilistic structures, such as a bloom filter. The options where to store the cache, range from an embedded system within the application, a separate key-value store, to storing it within the same database as the original data.
Additionally, a middleware or separate processing layer could be used to integrate our approach with existing systems and approaches. ference on Computer Science and Information Systems (FedCSIS), 2011, pp. 841–848. [1] J. Graef, C. Ehrt, K. Diedrich, M. Poppinga, N. Ritter, [14] R. Chirkova, J. Yang, Materialized views, FoundaM. Rarey, Searching geometric patterns in protein tions and Trends® in Databases 4 (2012) 295–405. binding sites and their application to data mining doi:10.1561/1900000020. in protein kinase structures, Journal of Medicinal [15] T. Inhester, S. Bietz, M. Hilbig, R. Schmidt, M. Rarey, Chemistry 65 (2022) 1384–1395. doi:10.1021/acs. Index-based searching of interaction patterns in jmedchem.1c01046. large collections of protein–ligand interfaces, Jour[2] Y. Fang, R. Cheng, G. Cong, N. Mamoulis, Y. Li, nal of Chemical Information and Modeling 57 (2017) On spatial pattern matching, in: 2018 IEEE 148–158. doi:10.1021/acs.jcim.6b00561. 34th International Conference on Data Engineering (ICDE), 2018, pp. 293–304. doi:10.1109/ICDE.
2018.00035. [3] E. Wong, K. Youssefi, Decomposition—a strategy for query processing, ACM Trans. Database Syst. 1 (1976) 223–241. doi:10.1145/320473.320479. [4] M. Stonebraker, P. Brown, D. Zhang, J. Becla, Scidb:
A database management system for applications with complex analytics, Computing in Science &
Engineering 15 (2013). [5] M. Raasveldt, H. Mühleisen, Duckdb: an embeddable analytical database, in: Proceedings of the 2019 International Conference on Management of
Data, 2019. [6] G. P. Copeland, S. N. Khoshafian, A decomposition storage model, SIGMOD Rec. 14 (1985) 268–279.
doi:10.1145/971699.318923. [7] G. Sanders, S. Shin, Denormalization efects on performance of rdbms, in: Proceedings of the 34th Annual Hawaii International Conference on System Sciences, 2001, pp. 9 pp.–. doi:10.1109/HICSS.
2001.926306. [8] D. Comer, Ubiquitous b-tree, ACM Computing
Surveys (CSUR) 11 (1979) 121–137. [9] A. Guttman, R-trees: A dynamic index structure for spatial searching, in: Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 47–57. [10] C.-Y. Chan, Y. E. Ioannidis, Bitmap index design and evaluation, in: Proceedings of the 1998 ACM SIGMOD international conference on Management of data, 1998, pp. 355–366. [11] M. Poppinga, J. Graef, K. Diedrich, M. Rarey, N. Ritter, Database and workflow optimizations for spatial-geometric queries in geomine, in: Lernen, Wissen, Daten, Analysen (LWDA) Conference Proceedings, 2023, pp. 86–97. [12] B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang,
M. Paleczny, Workload analysis of a large-scale key-value store, in: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, 2012, pp. 53–64. [13] P. Cybula, K. Subieta, Decomposition of sbql queries for optimal result caching, in: 2011 Federated Con