Link Traversal-based Query Processing (LTQP) is an integrated querying approach that allows the query engine to start with zero knowledge of the data to query and discover data sources on the fly. The query engine starts with some seed documents and dynamically discovers new data sources by dereferencing hyperlinks in previously ingested data. Given the dynamic nature of source discovery, query processing tends to be relatively slow. Optimization techniques exist, such as exploiting existing structural information, but they depend on a deep understanding of the link queue during LTQP. To this end, we investigate the evolution of the types of link sources in the link queue and introduce metrics that describe key link queue characteristics. This paper analyses the link queue to guide future work on LTQP query optimization approaches that exploit structural information within a Solid environment. We ifnd that queries exhibit two diferent execution patterns, one where the link queue is primarily empty and the other where the link queue fills faster than the engine can process. Our results show that the link queue is not functioning optimally and that our current approach to link discovery is not suficiently selective.
LGOBE
(R. Verborgh)
https://www.rubensworks.net/ (R. Taelman); https://ruben.verborgh.org/#site (R. Verborgh)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
criteria that limit the number of accessed documents and various link prioritization techniques
[
The Solid protocol describes a linked data publishing paradigm based on access permissions. Depending on the user permissions, some data should be inaccessible. The widely used approach to linked data publishing is to harvest data and provide a single access point. However, this is currently impossible for the personal data stored in a Solid pod due to privacy and permission concerns. LTQP can query this data by skipping any document the client can not access.
Furthermore, we know the general topology of the data in Solid. Personal data vaults act as data hubs and predicates known beforehand indicate the structure within data vaults and relationships between data. These predicates serve as link “sources” that contain information on the possible relevancy or priority of the link. To incorporate link source knowledge into query execution, we must understand how the types of link sources are discovered and present in the link queue. To this end, we investigate the diversity of link source types that enter the queue, how many links of each source are in the link queue, and for how long they stay there. This information can guide future LTQP optimization research eforts and uncover unexplored avenues for optimization. Our contributions are as follows: 1. We analyze the type of links that enter the link queue and the time of arrival of these links.
Thus, providing insight into how LTQP traverses the Solid ecosystem. 2. We measure the diversity of link types in the link queue during query execution. Link type diversity indicates the possible merit of link prioritization based on these link types. While we analyze the Solid decentralized environment, future work can extend our analysis to other decentralized environments.
In LTQP literature, the focus is on querying the entire Web of linked data without any
assumptions on the structural properties of the distributed environment. We will discuss graph-based,
intermediate solution-based [
Graph-based link prioritization [
Intermediate solutions-based link prioritization (ISLP) [
For all approaches, the literature suggests that while link prioritization outperforms a simple FiFo queue for some queries, it performs worse for others. We conclude that, while link prioritization has merit, it needs more in-depth research into what makes a sound link prioritization approach and why some queries show no benefit from link prioritization and others do.
In this section, we first describe the data we use for our analysis. We then introduce the possible
link types we can track in the Solid environment and how we measure the link queue evolution.
Finally, we introduce metrics to represent the diversity of links in the queue.
3.1. Data
We use the recently introduced SolidBench benchmark [
The SolidBench benchmark uses the read-only interactive workload of SNB, which
corresponds to the workload that social network applications encounter. The interactive workload
of SNB has two query template classes: complex and short. Preliminary testing [
In the Solid ecosystem, multiple predicates serve a distinct function and result from the structural
properties of the ecosystem. For example, LDP Basic Containers serve as folders that contain
references to documents or other LDP containers, while type indexes denote a direct link to
a resource in the vault with a type or class, like comments or posts. For a more in-depth
explanation of the Solid environment and its structural properties, we refer to [
In Table 1, we show all considered predicate types and the short versions of their name. Note
the presence of cMatch, the reachability criterion described in [
To investigate the behavior of the link queue during LTQP, we will register the link source for each dereferenced link during query execution. We snapshot the link sources in the link queue whenever a link is popped from or pushed to the link queue and register the timestamp. Thus, we obtain the evolution of the sources in the link queue during query execution.
Using this information, we will first plot the diferent types of sources and their numbers present in the link queue. This plot will give us an understanding of the data discovery pattern of the query engine and allow us to investigate avenues for link prioritization algorithms or other forms of optimization.
To support the visual analysis of the link queue, we introduce metrics that measure link queue characteristics. We are interested in what percentage of all links we obtain from a given source. Furthermore, we will determine the fraction of time the link queue contains or more links ( Ef () ) and calculate the time-weighted average number of link types present in the link queue, given links are present ( ̄ () ). These metrics give us insight into possible bottlenecks during query execution and whether link prioritization based on link sources has merit for LTQP. We calculate these metrics using Ef () = ∑ { 0≤ < | ≥}
+1 − − 0 , ̄ () = ∑ { 0≤ < | ≥} ( +1 − )
− 0 .
(1)
With 0 the first timestamp recorded, the final timestamp, and the number of diferent
link sources in the queue at timestamp . These timestamps are obtained whenever a push or
pop event happens in the link queue. This implies that signals the end of the query and
not a change in the link queue. We execute the queries using Comunica [
In Figure 1, we present a selection of the link queue evolutions that accurately represent what we found in all 27 queries. From these figures, we find two categories of queries: queries where the engine can quickly process the number of discovered links and queries where the number of links followed increases steadily to the point that the query engine cannot handle the number of discovered links. Furthermore, we set the timeout to 1,100 seconds for Figure 1e in order to investigate the spike of cMatch links. The result is given in Figure 1f. We find that the cMatch criterion can quickly generate a large number of links to follow, slowing down the query execution and making the query infeasible to execute.
We investigate the metrics introduced in Section 3 to quantify the two query categories. We split the queries into two groups: one with a non-zero number of links in the queue for more than 50% of the query execution time, and the other for less than 50%. The group with high queue occupancy contains twelve queries, while the other group contains fiteen queries. Interestingly, all discover queries belong to the query group with low queue occupancy. The average metrics of the groups are shown in Table 2.
Query Complex-3 Query Discover-7 800 (c) The link queue quickly fills up with many cMatch links, and the query engine cannot process the volume of links.
By dividing the queries based on queue occupancy, we find a clear diference in link queue characteristics. Queries with high queue occupancy have a higher percentage of cMatch links and, on average, have more than one type of link in the queue for 50% of the query execution time. On the other hand, queries with low queue occupancy have a higher occurrence rate of contains links and seldom have more than two types of links in the queue at a given time.
The queries where the link queue is empty for most of the query execution time support
the conclusion of our previous work that current query plan optimization approaches perform
poorly for LTQP [
For queries with many links in the queue, we find that the link queue often contains diferent
types of links during query execution. This diversity of links indicates that link prioritization
strategies based on link sources can influence query execution strategy during LTQP.
Furthermore, for queries with many links to follow, the query engine discovers most links using the
cMatch criterion. The engine primarily uses cMatch to traverse to other Solid pods since all
data in a single pod can be retrieved using the contains, storage, and type index predicate
links [
In this paper, we investigated the contents of the link queue during LTQP over Solid pods. Based on the content of the link queue during query execution, we divide queries into two types. The ifrst query type has a primarily empty link queue during query execution. In contrast, the second query type has a link queue that fills rapidly, and the query engine cannot empty it quickly enough. For low queue occupancy queries, the bottleneck is their query execution plan. This bottleneck shows that improving existing zero-knowledge query planning is required to optimize LTQP over the Solid environment. For high queue occupancy queries, we find that while the link queue quickly fills up with links retrieved using cMatch, other link sources are often present concurrently.
These observations highlight that link prioritization based on the structural properties of Solid can influence query execution time and that the cMatch criterion is not suficiently selective for eficient LTQP. We conclude that future work on LTQP has three avenues for research: 1. Investigate new query optimization algorithms to improve low queue occupancy query execution. Adaptive query planning seems especially promising due to the lack of prior knowledge of the data during LTQP. 2. For high queue occupancy queries, our analysis shows that link prioritization using the structural properties of the Solid ecosystem can influence query execution. Thus, future research into how to use these structural assumptions to prioritize links is an interesting future direction. 3. Finally, the large number of cMatch sourced links in the link queue of high queue occupancy queries show that using cMatch to discover new Solid pods is insuficiently selective. Future work should investigate alternative approaches that allow for more selective cross-pod link traversal.
This research was supported by SolidLab Vlaanderen (Flemish Government, EWI and RRF project VV023/10). Ruben Taelman is a postdoctoral researcher at the Research Foundation – Flanders (FWO).