Measuring the potential of client-side adaptive query optimisation for link traversal over decentralised Linked Data documents

SUMMARY:

The authors explore the impact of different techniques on the performance of link traversal query execution, in particular relating to how cardinalities are computed, and adaptively resetting query plans upon gaining new information during execution. The authors further explore how real-world network latencies and rate limits might affect the performance gains of such techniques. Experiments are conducted using the LDBC social benchmark loaded into Solid pods.

STRENGTHS:

S1: The paper is well-written, with clear research questions and well-stated hypotheses.

S2: The paper addresses an interesting and relevant problem. Solid provides an interesting use-case for this approach to executing queries on the Web.

S3: This paper is an extended version of a conference paper, which is cited, and the additional contributions described, in the introduction. The extension involves additional experiments in the context of more realistic network settings.

S4: I really appreciate the sober discussion of limitations, the rejection of hypotheses, and the balanced appraisal of the results. Instead of trying to "sell" some approach, the paper gives the sense of trying to gain a better understanding (which I commend).

S5: A variety of configurations are compared, and a wide range of measures are considered to understand performance from various perspectives.

S6: Code is provided for reproducibility. Datasets used are also linked from the paper.

WEAKNESSES:

W1: The paper is not clear on what query language or fragment is supported. SPARQL 1.0? SPARQL 1.1? BGPs? This is important to clarify before reaching Section 4, which seems to focus on joins. What about (e.g.) filters, which would be typically pushed down into the join tree?

W2: The high-level wrapper operator is a bit difficult to follow. In the typical "volcano" model, such an operator would only have “vision” of the production of its direct child or children, not of its ancestors. It is not clear how the wrapper can understand the cardinality of the lower-level triple patterns in this case. I am not sure that presenting the wrapper as an operator is the best abstraction (unless each iterator also passes some sort of accumulated meta-data extended at each step).

W3: It is not immediately clear to me the interaction between traversal and join execution. Wouldn't changing a particular join ordering change the reachable datasets (assuming cMatch)? Or is traversal decoupled from the query processing? For example, under cMatch, if we traverse a triple to satisfy a triple pattern higher up the tree, leading to a dataset with a triple matching a pattern lower down the tree, is that triple "seen" by the lower triple pattern?

W4: Some details of the experimental results are not clear:

- Why do some configurations in Table 3 require more requests? For example, under restart-100ms-predicate, why does client rate limiting affect the overall number of requests (88 vs. 62)? Is this related to the (later) observation "that the engine continues processing its internal link queue even after query execution is over"?

- On the opposite side of the previous point, why is the number of HTTP requests so uniform when the number of completed queries varies?

- Results are shown in bold when better than the baseline, but this can be misleading when looking at times since in some cases (like restart-update-predicate-0m), the number of queries completed is much lower. Granted the data are provided to observe this, but I wonder if it might be good to include average time considering failed queries with the timeout time? (Or are timeouts included in the average?)

- I don't think Figure 4 is an effective way to illustrate the data as an arbitrary number of points might overlap, losing information about the true distribution. A better way would be a box plot or violin plot, for example.

- Rather than presenting Table 3 at the start of Section 6, or before Section 6, it would be good to present the measures used. This would help readers who jump straight to Table 3 from where it is first mentioned.

- Similar to Figure 4, I worry that Figure 5 is also not effective due to the overlap of information. If you draw the black series after the blue series (on top of it), the results could (not necessarily would) look quite different.

- Regarding the observation that rate limits "are indeed produced more smoothly over time", this seems a bit unusual to me, particularly the "wait and burst" pattern. Could this switching between traversal and query processing be analysed or explained in more detail? In particular, why does the rate-limit pause force the engine to switch to query processing if this is in one single thread?

- As an overall comment, the failed queries often create a confounding factor for the presentation of metrics (e.g., "and thus the CPU-seconds and GBseconds were mostly identical to baseline, ignoring the experiment without added network latency, that failed to execute most of the queries and this exhibited abnormally low values for these metrics"). A better way to address this (as a suggestion) might be to present an analysis of in how many cases a certain approach is better, worse or tied with the baseline for a given measure. If a query fails in A and not in B, it can be considered worse. Granted this might be intricate given the number of configurations and measures, but something along these lines might help clarify. As it stands, it can be difficult to interpret the time, memory and network measures as they are always qualified by separate query success rates.

W5: The hypotheses are rejected or accepted more informally, without statistical analysis. Could p-values be computed for these hypotheses? (This seems feasible.) Also, by testing on only one dataset, it might be too early to reject or accept such general hypotheses.

W6 (Subjective): Overall the work is quite incremental compared with related work, and the extension over the conference paper (arguably) not particularly ambitious. Some of the results are artefacts of the system used and engineering details rather than some more general phenomenon.

TECHNICAL COMMENTS:

* "With the dataset bounded by the chosen reachability criteria [...] while not complete within an unbounded Web-wide context" But if the reachability criteria are to follow all links, isn't this effectively unbounded in the same sense at least as the Web-wide context?

* "provided the query contains no blocking operations" This refers to "non-monotonic" operators like MINUS, COUNT, OPTIONAL, etc.?

* I know this is not the authors' proposal, but the formula for subjA ?p objA seems a bit strange in that it can give estimates less than one triple. For example, in a dataset with 100 triples, 50 unique subjects, and 10 unique objects, it is strange that the estimation is 0.2 triples. I guess it assumes random subjects and objects, with independent probabilities, which is a strong assumption, even for an estimate. A similar comment applies for all triple patterns with fixed subject and object. I understand they are estimates, but they “feel” a bit strange.

* Though the hypotheses are well-written in general, H2 is a bit difficult to follow the first time around. What does "Using a uniform interval for plan evaluation and restart" mean?

* I don't follow equation (1). Could you explain more clearly the notation and provide a concrete example?

* Perhaps it would be out of scope, but to emulate more realistic network behaviour, it would be interesting to model non-uniform rate limits and latency across sources / datasets. This would require the query plan cost to move away from cardinality, and towards something that (also) captures network costs.

* Latency is one factor, but what about bandwidth / transfer rate? Could this have a reasonable overhead in practice?

* Even at 125% zoom, some figures are unreadable. Given that there is not (I believe) a page limit, why not use more vertical space (e.g., to put three graphics of Figure 2 on one row, and two graphics centered on a second row)?

OVERALL:

I found the results of the paper quite interesting, and appreciate the sober presentation and analysis. That said, picking through the experimental results to gain understanding requires perhaps too much effort as currently presented (W4). Looking at W1-W5, I believe these could be addressed as part of a revision (along with some of the technical comments). W6 is a subjective appraisal, and not necessarily a reason to reject, just a general wish that the authors were a bit more ambitious to dig deeper into the issues seen (e.g., modifying the engine). Overall however, this article provides solid advances and new insights relating to optimising LTQE in different contexts. Taking this into consideration, I recommend a Major Revision.

MINOR COMMENTS:

* "Alongside the emergence of decentralisation" This sentence (the first of the abstract) is a bit complicated and difficult to read.

* "The ideal, zero-knowl[e]dge"

* "experiment[al] setup"

* Tables 1, 2, 3: Typically I think the table captions go above the table.

* "such as by [30]". I would suggest "such as by Chaudhuri et al. [30]", which is much more informative and readable.

* "varied between unlimited restarts[,] a one-time restart"

* "we are incli[n]ed to accept Hypothesis 1"

This manuscript is an extended version of a conference paper which introduces an approach to improve the performance of link traversal-based execution of SPARQL queries over Linked Data. The idea of the approach is to continuously update cardinality estimates while executing a query using an initially-determined join order, and if these updated estimates suggest an alternative join order, then restart the execution using that join order.

The main extension of the given manuscript over the conference version is a more comprehensive set of experiments that considers network latencies and rate limitations on the number of requests per server per second. Additionally, there is an expanded discussion of related work and a (slightly) more detailed description of the approach. I consider these extensions sufficient to justify a journal article.

I am generally in favor of accepting this work for publication in the journal. However, there are four main points that the authors need to work on a bit more, plus several other more minor points.

Main points to work on:

M1. The description of the approach needs to be expanded with further details and clarifications; especially, the parts about the discovery and the estimation of cardinalities is not fully clear in the details. Relevant questions that the current text does not answer:

M1a (discovery):

The caption of Figure 1 suggests that there is a point during the query execution process at which "the cardinalities are discovered" and I wonder: How exactly does this discovery happen? Every triple pattern of the query may, in principle, have matching triples in each of the reachable documents, and these documents may be discovered and retrieved at arbitrary points during the process.

Related to the previous point, lines 32-33 on page 7 say that "the cardinality estimate of a triple pattern is updated [...] when the query engine discovers a VoID dataset description applicable to the currently executing query." Given that the approach focuses on queries over Linked Data documents (not over SPARQL endpoints), I wonder:
- Where do such VoID descriptions come from?
- How exactly would such a VoID description be discovered during traversal-based query execution (especially under cMatch semantics, as considered for the experiments in the paper)?
- What set of data exactly is such a VoID description assumed to cover?
- If it is assumed to cover more than a single Linked Data document, how are the statistics of it assumed to be broken down to the individual document level? ...or to the subset of the documents that are cMatch-reachable by the query?

M1b (estimation):

The two approaches for triple pattern cardinality estimation (as described at the beginning of page 8) consider formulas that are defined based on the statistics given in a VoID description for a single dataset and, in fact, the two bullet points about these two approaches even talk about "the dataset." In wonder:
- What exactly is "the dataset" in the case of traversal-based execution of queries over Linked Data?
- How are the formulas applied if there are multiple VoID descriptions for different (sets of?) Linked Data documents?
- How do the approaches take into account that there may be (cMatch-reachable) Linked Data documents that have not been reached yet during the traversal-based query execution process, and for which no VoID description has been discovered yet?

Figure 1 seems to suggest that the approach takes only the triple pattern cardinalities into account. Is that really the case? Why not also the join cardinalities? For instance, for the example in Figure 1, what happens if the result of the join over TP1 and TP2 has a cardinality of 10 whereas the result of the join over TP3 and TP2 has a cardinality of 100?

According to line 39 on page 7, "the wrapper performs cardinality estimation for the entire query plan." How exactly is that done? In particular, what approach is used to estimate the cardinality of joins?

Probably related to the previous question, lines 18-19 on page 8 say that "the cardinality estimator [...] reconstructs the higher-level cardinality as a worst-case estimate of the lower-level components." What exactly is meant by "worst-case estimate"? For instance, for a join, does it mean that the result of the join is estimated to be the cross-product of the two inputs?

M2. The description of the implementation needs to be expanded as well. Important questions that the current text does not answer:
- What types of join plans does the implementation consider? (left-deep plans only, or bushy plans as well)
- What algorithm does the implementation use to enumerate the join plans? Is it the dynamic programming approach that many system use or just some greedy approach (i.e., select the triple patterns for the first join first, and then add one more join in each step, without backtracking) or something else?
- Which physical operator(s) does the implementation use for performing the joins (i.e., which join algorithm(s) does it use)?
- What exactly is the execution model in which the plans are executed? (iterator/pull-based or push-based)
- How exactly do the data retrieval part (URI lookups) and the pattern matching part of the query execution process interact with one another? For instance, what exactly is the way in which the triples retrieved by URI lookups are fed into the operators of the plan?

Regarding the latter question, notice that the original iterator based approach [4,7] does not guarantee result completeness under cMatch semantics; see Sections 7.2 and 7.3 in https://olafhartig.de/files/DissertationOlafHartig.pdf -- The implementation approach described in the "walking without a map" paper [9] does not have this problem.

- Another aspect that seems to be an issue of the implementation and that needs to be explained is that "the engine continues processing its internal link queue even after query execution is over" (line 36 on page 14) and "end[s] up doing more link traversal than is necessary to answer the queries." How can the query execution be over when there are still links to be followed? Which link traversal does the engine do that is not necessary (under cMatch semantics)?

M3. The description of the experiments needs to be expanded. Important information that is missing:

- How is the LDP container structure of the Solid pods considered within the benchmark queries? Given that the queries are evaluated under cMatch semantics, I would expect the queries to contain triple patterns that match the container structure links, but the queries in the SolidBench GitHub repository do not seem to contain such triple patterns.

- Which seed URIs have been used for the benchmark queries?

- Related to the previous two questions, and also to the more general questions under point M1a above, I wonder how the benchmark queries resulted in the discovery of the VoID descriptions that "were placed at the pod roots as metadata, and thus served by the Community Solid Server when a client requests the pod root URI"? Given the use of cMatch semantics, why/how would it happen for every query that the "client requests the pod root URI"?

- How different are the VoID statistics from one another for the different Solid pods within the benchmark dataset? I would assume that these statistics are quite similar across all the pods. The reason why this question is relevant is because highly similar VoID descriptions may actually be very beneficial for the approach and may even explain some of the observations (if the VoID descriptions are similar, it doesn't matter so much how many of them have been discovered already; the relative differences between the cardinality estimates for the triple patterns will not change much when more VoID descriptions are discovered).

- How many cores/threads of the virtual machine used for the experiments have been allocated to the query engine, respectively to the server?

- How was the RAM of the machine distributed between query engine and server?

M4. The analysis of the measurements in Sec.6 is a bit chaotic and not easy to follow. In particular, in Sec.6.1, I felt lost a couple of times, not knowing what exactly is currently being discussed and compared to one another. I suggest to restructure Sec.6.1, either split it into multiple smaller sections or introduce sub-sub-sections with section titles that make it easier to navigate the discussion. Also, several of the details remain unclear:

- What has been aggregated to arrive at the minimums, averages, and maximums in Table 3?

- Why are some of the percentages in the text given as ranges (e.g., "17...29%")?

- Several of the sentences make comparison statements (something being slower, or the time for something increased by some percentage), without explicitly saying what the thing being discussed is compared to. In some of the cases, it is possible to figure it out from the context, but there are also several cases where I felt lost. I strongly suggest to almost always mention the points of comparison explicitly, instead of relying on the reader to figure it out from the context. For instance, instead of just writing that something was X% slower, mention explicitly: "slower than ..."

Additional things that need to be clarified and fixed (in the order in which these things appear in the manuscript):

A1. It is not clear what these "optimising zero-knowledge client-side techniques" are whose potential is evaluated (according to line 15 on page).

A2. Likewise, what "client-side techniques" does line 17 on page 2 refer to?

A3. Related to the previous two points, but on a more general level, I would like the introduction section to be more explicit about the approaches/techniques considered in this work.

A4. The sentence in lines 1-2 on page 3 should include a reference to the paper that introduces these reachability criteria:

Olaf Hartig: SPARQL for a Web of Linked Data: Semantics and Computability. In Proceedings of the 9th Extended Semantic Web Conference (ESWC), 2012.

A5. Reference [7] is not the right reference for the sentence in lines 3-4 of page 3. Instead, the reference for that sentence should also be the ESWC'12 paper mentioned in the previous point.

A6. In contrast to the statement in line 47 of page 4, the join plan is not only about "the order of join" but, generally, also about the join algorithms selected for each of the joins.

A7. There are many places where the text talks about "bindings" (mostly in Sec.4, but I think I have seen it elsewhere as well). This is not a well-defined concept in the context of SPARQL. I suggest to replace all of these mentions by the term "solution mappings".

A8. Likewise, in several places, the text uses the term "results" as a synonym for "solution mappings", which can also be confusing because the term "result" may also refer to the (multi)set of solution mappings that is the result of evaluating a query (or of executing a (sub)plan).

A9. The terms "virtual passthrough join operator" and "tree join of join" (line 46 on page 6) are not clear.

A10. In the description of the request rate limiter (second paragraph of Sec.4.4), it needs to be clarified what exactly a "server" is assumed to be in the given context of traversal-based query execution.

A11. Something seems to be wrong with the formula in equation (1) on page 8. First of all, i_0 is undefined (because the first case of the formula, for n=0, defines i_{0+1} = i_1). Moreover, assuming i_0 is meant to be 0, then the third case of the formula begins with an i_{n-1}=0 and an i_n=0, resulting i_{n+1}=0. Consequently, for any n, the result of the formula is 0.

A12. The sentence that mentions "observations of real-life latencies" and the reasons for choosing 50ms and 100ms as latencies for the experiments should be backed up by a reference.

A13. Throughout all of Section 6, the word "results" is used to refer to the authors' measurements (e.g., twice on line 43 of page 10, line 47 on page 10, line 14 on page 11). These are not results but, indeed, only measurements. Results of an experiment or of an evaluation are the things that the measurements show; the insights that we can extract from analyzing the measurements.

A14. Lines 48-49 on page 11: "the predicate-based estimator failed the most queries," -- "failed" in what sense?

A15. Also, what exactly are "most queries"? 15 of the 16 queries? Or 10 of the 16?

A16. Lines 48-49 on page 11: "resulting from unnecessarily conservative query plan selection in fear of its .." -- I don't think there was "fear" in the process. Also, I don't understand in what sense the query plan selection was "conservative." Wasn't it just a result of the cardinality estimates?

A17. Lines 50-51 on page 11: "The queries that worked [...] did so much better thanks to this." -- It is absolutely unclear what "this" is. Additionally, a "10...15%" reduction of execution times is a (good but) modest improvement; not something that I would call "so much better" (also, I suggest to avoid such a colloquial way of writing).

A18. Line 12 on page 12 mentions "overly optimistic estimates." -- It is not clear to me what "optimistic" means in this context. How can a cardinality estimate be optimistic?

A19. A reference needs to be added to the last part of the sentence at line 17 on page 12 ("as was the case also in our prior work.").

A20. I do not understand what the whole "but.." part of the sentence at lines 29-32 on page 12 is meant to say, and why it begins with "but." Maybe the sentence can be rephrased to make it clearer.

A21. Line 41 on page 12: "intergal" -> "integral"

A22. Line 42 on page 12: "dief@k" -> "dieff@k"

A23. Regarding the motivation for using dieff@k with k = the query result cardinality (lines 43-44 on page 12), I wonder how this way of using dieff@k is conceptually different from the "Last Result(s)" metric as used before. Of course, dieff@k is calculated using the integral, but other than that?

A24. I have no idea what "save for the outliers" means (line 48 on page 12).

A25. Lines 48-49 on page 12: " for the estimate update-based restart experiment, [..] the diefficiency values remain lower than without rate limits" -- But in comparison to what?

A26. The fact that the x-axis in the left-hand side of Fig.4 is reversed is confusing and not immediately noticeable.

A27. Lines 18-19 on page 14: It is not 100% clear from this sentence whether it was the "overhead experiments" or the baseline that achieved "an average 10% lower CPU-seconds."

A28. Lines 46-48 on page 14: It is not clear what "these metrics" are. The first sentence of the paragraph does not really introduce any metrics (not explicitly, at least).

A29. Moreover, how can "these metrics [...] help understand how much or little data is needed to actually answer a given query"? I wonder because the sentence before says that "the data download and upload [is] impossible to associate with individual queries."

A30. The second sentence of Sec.7 is way too long and short be broken up into smaller sentences. In addition to this sentence, there are several other very long sentences that stretch over almost three complete lines and, thus, may better be broken up as well (examples: the first sentence on page 15, the sentence at lines 29-32 on page 12; lines 40-43 on page 11).

A31. I believe that the observation discussed around lines 33-37 on page 15 is not a general finding but a Comunica-specific one, caused by the single-threaded implementation of the Comunica engine. In this sense, Hypothesis 5 may be rejected for Comunica, but not in general. The text should make this difference clear.

A32. Line 35 on page 15: "expensive" -> "expense"

This paper investigates client-side adaptive query planning for Link Traversal Query Processing (LTQP) over decentralized Linked Data, using the Solid ecosystem as the target environment. The authors implement a restart-based query planning approach within the Comunica framework: a wrapper operator monitors triple pattern cardinality estimates as they become available during traversal, evaluates whether the current plan is still optimal, and transparently restarts execution with a better plan when it is not. Two cardinality estimation techniques (formula-based and predicate-based, both leveraging VoID descriptions) and two plan evaluation strategies (interval-based and update-based) are tested. The paper extends prior conference work [3] by adding client-side rate limiting and network latency simulation, broadening the experimental scenarios to more realistic conditions.

Originality

The paper is an extension of [3] (ICWE 2025). The extension is substantial: the new experiments with rate limiting and latency simulation are well-motivated and produce genuinely interesting findings (e.g., rate-limiting forces better resource allocation, improving efficiency despite longer wall-clock times). I would not say the extension is methodologically original, but it is a legitimate work for an SWJ extension. The paper also found something that was counterintuitive to the authors.

Significance

This paper is topically relevant and timely for the Semantic Web community. Decentralized querying, LTQP, and Solid are of high interest, in my opinion. The impact beyond the community is arguable. However, I think it produces actionable practical insight on cost, guidance on when to optimize, and shows a useful negative result. I think it is a bit engine-specific, so I wonder how generalizable the paper findings are.

Quality of the writing

The paper's prose is easy to follow, and the structure and the hypothesis framing help the reading. I enjoyed the paper. However, there are many typing issues. In particular, I think the figures were not so well described. Better captions could help. Some of the writing issues are:

1. Page 2, line 11: "The ideal, zero-knowldge approach to data discovery"
-> "zero-knowledge"

2. Page 4, line 16: "from the LDBC social network benchmark datset [21]"
-> "dataset"

3. Page 6, line 27 (Hypothesis 5): "real-world rate limiting scenarions"
-> "scenarios"

4. Page 8, line 3: "that uses the the formulae from Hagedorn et al. [28]"
-> remove the duplicated word: "uses the formulae"

5. Page 9, line 32: "without any of our implementation overheard"
-> "overhead"

6. Page 11, line 43: "Thus, the predicate-bases estimator, upon plan evaluation"
-> "predicate-based"

7. Page 12, line 14: "the worst-case performance of the forumlaic estimator"
-> "formulaic"

8. Page 12, line 41: "calculated as an intergal of the result distribution function"
-> "integral"

9. Page 13, line 34: "could make for a better experimence"
-> "experience"

10. Page 15, line 4: "The problem is further excacerbated by the engine"
-> "exacerbated"

11. Page 15, line 25: "we are inclided to accept Hypothesis 1"
-> "inclined"

12. Page 19, Table 2 caption (line 49): "The formulaic cardinlaity estimator"
-> "cardinality"

I think you should use an automatic tool to check grammar because I passed this through a grammar checker, and it found 39 issues.

Resources

The artifacts look fine. However, GitHub ≠ long-term preservation; Zenodo, Figshare, or long-term preservation servers hosted by universities would help.

I suggest this paper be approved after a minor revision to fix the writing issues, improve some minor issues regarding the clarity (e.g., the captions that would help the understanding of figures), and provide a long-term preservation URL for the resources.