Test Architecture for QLever

This document outlines the testing strategy to validate the Wikidata infrastructure as part of the migration from Blazegraph to QLever. The work is defined in Phabricator ticket T422097.

The goal is to define the technical components required to validate queries' data equivalence and performance, and categorize output comparisons across the two environments.

Executive Summary & Overall Architecture

Migration testing is critical since Blazegraph acts as a specialized query engine (via custom extensions) for Wikidata. In fact, one of the overall strategies of the migration project is to decouple the query engine from these extensions. When this is done, the backing query engine will be compliant with standard SPARQL 1.1 and aspects of GeoSPARQL (which Blazegraph does not support), while other components (executing both before/after the query engine) handle authentication, rate limiting, etc.

This architecture is defined as a two-way differential test. Its goal is to determine whether QLever, running rewritten and original queries (where the queries are compliant with SPARQL 1.1), produces results equivalent to Blazegraph running the original queries. And, where the results from the two systems diverge, divergences will be surfaced for human review.

Scope and Limitations of Two-Way Differential Testing

Because only two systems are compared, a divergence can only establish that Blazegraph and QLever disagree, not which one is correct. This architecture therefore does not determine absolute "correctness or completeness" against the SPARQL 1.1 / GeoSPARQL 1.1 specifications. Both engines have known divergences from the specifications. However, the architecture does establish "correctness and completeness" vis-a-vis the current Blazegraph implementation.

"Equivalent" results between the two environments are defined as:

• Identical HTTP status
• The same multiset of solution mappings (duplicates and cardinality preserved), compared independently of order
• Matching terms including datatype IRIs
• Blank nodes matched up to isomorphism (checking that there's a consistent one-to-one relabeling of one side's blank nodes onto the other's, making the two results identical)
• Any query whose result is inherently non-deterministic (see the Canonicalization section below) is normalized before comparison or excluded from the comparison

If a divergence is found, it is flagged for human adjudication against the specifications. The architecture does not attempt to resolve it automatically.

Prerequisites

Work on the items noted below is already underway (references are provided):

• Internal Blazegraph and QLever SPARQL endpoints are available for (non-anonymized) testing, with the same (static) Wikidata image loaded on each
  • For the first iteration of the work, the systems will have a static image (no streaming updates will be applied)
  • As a future exercise, it is recommended that testing include rerunning the toolsets with the systems being updated via the streaming-updater
  • Note that queries addressed to the scholarly graph SPARQL endpoint are not included in this analysis – but queries that include federation to the scholarly graph will be used
    • A static-image of the scholarly graph endpoint must also be available
• Query logs have been collected reflecting several (e.g., mid-week versus weekend, and/or light- versus heavy-load) 24-hour periods (Phabricator ticket T424452)
  • At least two 24-hour logs be collected
• Query characterization/categorization is defined
  • Details are provided in the document, SPARQL Query Categorization
  • Note that it is unlikely that all aspects of this categorization will be captured in the initial analysis (due to time limitations) but are defined for completeness and (possible) future implementation
• Query rewrite patterns (or the documented omission of them) are defined for the following custom features in Blazegraph (Phabricator ticket T424306):
  • Geospatial functions including (geof:) distance, buffer, latitutde/longitude, and topology relations comparing two geometries (geof:sfWithin, sfContains, sfIntersects, sfEquals, and sfTouches) and radius and bounding box searches (wikibase:around and wikibase:box)
  • Full-text search including wikibase:mwapi, bds:search, bds:matchAllTerms, bds:relevance, bds: rank, bds:min/maxRank and bds:min/maxRelevance
  • Analytic and graph algorithms including the Gather-Apply-Scatter (GAS) API supporting breadth-first Search (BFS), single-source shortest path (SSSP), and PageRank and defining traversal direction (Directed, Undirected, or Reverse)
  • Other functions: wikibase:label, named sub-queries, wikibase:decodeURI, bd:slice and bd:sample
  • Note that query hints will not be migrated as they are not part of the SPARQL standard but vendor-specific tuning features
    • All query hints must be removed from the rewritten queries

Software Development Tasks

Development occurs in conjunction with defining the query characterization and rewrite patterns listed above.

The steps are described below and expected to be carried out roughly in order:

1. Data extraction from the 24-hour query logs: Toolset to process the logged data and extract each query’s endpoint and stream (eqiad/codfw, internal/external), time received, user details, backend resource, and query text
2. Query rewriting: Toolset to rewrite the extracted queries per the patterns and best practices documented as part of Phabricator ticket T424306
3. Query rewrite validation: Processing to exercise the rewrite patterns and tool created in #2, to validate that the responses from the 2 backends are equivalent (or to understand differences)
   1. It is important to exercise the complete set of “rewrite” rules, making sure to test all Blazegraph-specific geospatial functions, full-text search, GAS API, label service, etc.
   2. The queries in the logs will be filtered to select 5-10 that exercise each of the functions/services
   3. Where there are many occurrences of a particular “rewrite” rule (for example, Blazegraph’s label service), 5-10 will be randomly sampled
   4. If there are no occurrences of a particular “rewrite” rule, several will be generated for testing
   5. In addition, where there are “bugs” reported in Phabricator against the Blazegraph query engine, specific queries will be added to test those patterns/issues
   6. Validation of cross-rewrite-rule queries (queries that trigger ≥ 2 rules) is also needed to check for rule rewrite interactions
4. Backend worker to pull original and rewritten queries, and send those queries to Blazegraph and QLever
   1. Requires ability to send the queries to Blazegraph and QLever, using the timing of the original query requests, and to store all query/feature details and results for analysis
   2. Includes reporting/storing the individual status codes, binding sets and execution times for each query
   3. Note that the goal is to provide a comprehensive set of data for analysis (Step #6) of the two backends
5. Query characterization: Toolset to characterize the log’s queries per the categories established in the document, SPARQL Query Categorization
   1. For the initial implementation, this work will be defined by what is possible to capture by parsing the query and analyzing its SPARQL Algebra
   2. SPARQL Algebra will be generated using Jena ARQ leveraging similar infrastructure to that defined for the Linked SPARQL Query (LSQ) Framework and DARQL
6. Analytics: Toolset to aggregate/analyze the stored queries and results from both triple stores with the ability to highlight and drill-down into:
   1. Divergences: Analysis of the results beyond simple pass/fail logic. The following differences are important to capture for further examination:
      1. Datatype Divergence: The lexical value is correct but the datatype IRI differs (e.g. one engine returns "5"^^xsd:integer where the other returns "5"^^xsd:decimal, or a typed versus untyped literal is returned)
         1. Admittedly, this is a form of logic/term-level divergence but is known difference in behavior of several SPARQL engines and worth capturing separately
      2. Precision Divergence: The logic executed, but algorithmic or floating-point drift occurred (e.g., a proprietary scoring metric returning 0.876543 vs 0.876500), outside of a configurable "fuzziness" tolerance
      3. Logic Divergence: A mismatch in number of binding sets returned, in the information within a binding set, etc.
      4. Response Divergence: Comparing response codes, proper termination of the response body, whether Content-Length matches response body size), timeout details, and whether responses are truncated
   2. Performance indication: Capture of end-to-end latency contrasting the Blazegraph and QLever execution times
      1. Although not relevant to the goals of this analysis, timing information can be an indicator of issues and/or useful in cost estimation

It should also be noted that the tooling will provide an aggregation layer with the ability for per-query example extraction or specific-query drill-down. For example, “divergent” or “non-performant” queries (clustered by feature similarity, k-NN) can report what percentage are precision-type versus logic versus response divergences. Then, specific examples could be extracted for testing review. This should provide a better review experience than straight per-query reporting.

Canonicalization

Some query canonicalization is required as part of the analytics processing - since results and ordering can vary, and since proprietary data types and custom extensions are involved. Specifically:

• Handling of non-deterministic ordering: Queries without an explicit ORDER BY clause will produce results (binding sets) in an arbitrary order. Comparison must therefore be order-independent and must preserve duplicate cardinality, since results form a multiset (a bag) unless DISTINCT is used. The recommended method is to canonicalize each solution mapping (normalizing terms and datatypes) and compare the multisets of per-mapping hashes, which is roughly linear.
  • The algorithm is coded as:
    • For each row, one canonical string is constructed from its bindings (variable names + canonicalized terms, including datatype IRIs, in a fixed order so {?x=…, ?y=…} and {?y=…, ?x=…} produce the same string), and then hashed
    • A "multiset of hashes" stores the hash and the number of times that it is encountered
    • QLever's and Blazegraph's multisets are compared
      • The bags are equal iff they contain the same hashes with the same counts
  • Full sorting of the binding sets is avoided as result sets can be very large and sorting may not be practical
• Handling of non-deterministic query constructs: Constructs that yield different results on each evaluation must be neutralized before comparison.
  • Examples are: NOW(), RAND(), UUID(), and STRUUID()
  • "Neutralization" is accomplished by replacing those functions with a fixed value so that the results are not labeled as divergent because of those functions
• Handling of LIMIT / OFFSET: A LIMIT or OFFSET without a total ORDER BY returns an arbitrary subset, so two engines can each be correct yet disagree. Such queries must be compared with the LIMIT/OFFSET removed, or compared when a total order can make the results deterministic
• Handling of blank nodes: Since the Wikidata RDF loaded to Blazegraph and QLever are indexed with skolemized graphs, special handling is not required for blank nodes originating in the data. However, blank nodes generated at query time (via BNODE() or CONSTRUCT) are named using arbitrary, engine-assigned labels and will certainly diverge. Comparison of query-generated blank nodes must therefore be performed using a consistent, triple-preserving relabeling of blank nodes.
  • Note that Jena has a graph-isomorphism capability (Model.isIsomorphicWith(Model and Graph.isIsomorphicWith) which can be used to determine if two result graphs are equal assuming a consistent blank-node relabeling