Wikidata Query Service/SPARQL Query Characterization

This document describes a means to categorize SPARQL queries sent to the Wikidata eqiad and codfw servers. It is intended to serve as a multi-dimensional framework for both system testing and performance evaluation.

Following the methodology described by Zhang, et al., queries are categorized by their SPARQL algebra, BGPs (graph-pattern shape and join structure), and other, “hybrid” features (for example, combining specific algebraic and pattern features, or considering store-specific cardinalities). The categorization establishes a baseline to build representative benchmark tests, predict execution cost, support timeout management, train/validate machine-learning models (when used with query-log execution data), and generate developer guidance for high-risk patterns.

Executive Summary

To effectively test SPARQL query patterns, they must be classified in a way that accounts for their algebra, graph patterns and the data’s cardinality features. Examining individual query execution in isolation obscures the big picture. Through categorization, we can aggregate performance data to identify systemic bottlenecks and optimizations, and feed that aggregated data (e.g., query features paired with execution metadata) into both deterministic cost heuristics and learned cost models.

The core objectives of this work are to:

• Systematize and Validate Testing: To effectively test query patterns, they must be classified. Ad-hoc testing or relying on benchmarks is insufficient. Categorization allows us to build a comprehensive, representative test suite that guarantees coverage across all topological shapes and computational features. It ensures that we do not miss any infrequently occurring patterns.
• Predict and Manage "Cost" (Resource Allocation): Public endpoints like the Wikidata servers are highly susceptible to resource exhaustion and timeouts. By categorizing queries by their execution and cardinality profiles (e.g., distinguishing a high-selectivity point lookup from a low-selectivity heavy compute aggregation), you create a framework to anticipate the "cost" of a query before it fully executes. This categorization could be the first step toward intelligent query routing, dynamic throttling, or proactive timeout management.
• Establish Best Practices for Query Authors: A multi-dimensional classification creates a shared vocabulary. When you can definitively point out that a "Snowflake Query" combined with "Subtraction (MINUS)" is a high-risk pattern for timeouts, we can write better documentation and guidance for developers and researchers. This can ultimately reduce the load of poorly optimized queries.
• Optimize Backend Architecture and Indexing: Query performance is unique to a store and its triples. Understanding the distribution of query types helps in optimizing the underlying triple store. If the categorization reveals a volume of patterns whose bound predicate has high cardinality in the store, it provides evidence to (perhaps) justify re-indexing strategies, adjust cache layers, or alter how the graph data is physically stored on the servers.

It is important to note that all the details described below will not be captured in the initial analyses to be performed in summer 2026 (due to time limitations). They are defined for completeness and (possible) future implementation. The specific characterizations that are used as part of system testing of Blazegraph and QLever will be fully described as part of the test analysis effort and details appended to this document.

SPARQL Classification Features

Building on existing work (such as the Linked SPARQL Queries (LSQ) dataset and Zhang’s paper), there are various static/structural and runtime features that aid in query characterization.

The multi-dimensional classification design proposed in this paper is based on:

• Query rewritten: Boolean indicating that the use of Blazegraph-specific features, operators and services have been removed in lieu of standard SPARQL 1.1
  • This feature is more for documentation and query rewrite testing
  • It examines the text of the original query for specific Blazegraph identifiers, services and keywords
• Graph shape: List of enumerated patterns
  • Note: The named shapes below (Linear, Star, Snowflake, Cyclic, Composite and Disconnected) are “derived” categories - derived from the triples and graph constructs of the parsed query. They are used as both feature data and for documentation purposes.
  • Linear / Path Query which traverses a chain of nodes
    • Shape: A → B → C → D where the object of one line becomes the subject of the next
    • For example: Find a Person, the city they were born in, the city’s country, and country’s continent
  • Star-Shaped Query which requests information for a single subject (or object)
    • Shape: A → B, A → C, A → D where there is a single subject or object and all triples reference it
    • For example: Find a Person, and return their name, their birth date, and date of death
  • Snowflake / Tree Query which examines join efficiency
    • Shape: A → B and B → C | A → D and D → E which starts with a central node, traverses to its surrounding properties, and then traverse further to the properties of those values
    • For example: Find a Movie and then find the director (and the director's birth city), and the actors (and the actors' birth years)
  • Cyclic Query where the traversal path loops back on itself
    • Shape: A → B → C → A
    • For example: Find a politician who endorsed a candidate, where that candidate in turn endorsed a third person, and the third person endorsed the original politician
  • Composite Query which is a shape built from two or more of the types (above) joined together
    • Especially important: The “dumbbell” pattern (two star clusters connected by a path) is valuable because it occurs in federated queries
  • Disconnected Query which is a set of triple patterns that share no variables (thereby resulting in a potentially large cross product)
    • Its occurrence is usually an error
• Result structure: Enumerated value
  • Considering outputs from SELECT, SELECT DISTINCT, SELECT REDUCED, CONSTRUCT, ASK and DESCRIBE queries
• SPARQL operator and syntax: List of enumerated values
  • Basic: Queries containing only a WHERE clause with further drill-down for requests for. :
    • Only a label, description or alias of an explicit entity
    • Identifiers for an explicit entity (either to bind the entity or as reported values)
    • All/any predicates between 2 explicit entities
    • Instance of/subclass of predicates for an explicit entity
    • Subject or object values for a few (1-3) specific predicates and an explicit entity
    • Subject or object values using inverse predicates
    • The value for a specific predicate for an entity linked from another entity (2-hop)
    • Bounded subject/object and unbounded predicate
    • Bounded subject/predicate or object/predicate
    • Different entity types (Q, P or L)
  • Bindings: Queries with BIND or VALUES
  • Optional & Union Branches: Queries utilizing OPTIONAL or UNION (and their nesting depths)
  • Negation/Subtraction: Queries utilizing MINUS and FILTER NOT EXISTS
  • Advanced Filtering & String Matching: Use of FILTER (with keywords such as EXISTS, logical and comparison operators such as && and !=, and functions such as bound, datatype and regex)
    • Queries using the label service would fall in this category
    • Also important to consider “anchored” (defined using the start ‘^’ or end ‘$’ character) vs unanchored regex patterns
  • Property Paths: Queries utilizing open-ended property paths (e.g., wdt:P31/wdt:P279* to recursively traverse "instance of" and "subclass of" hierarchies)
    • Variable-length/transitive paths (using *, +) are the focus here since they require bounded-evaluation semantics, whereas fixed-length paths reduce to ordinary joins
  • Aggregations & Grouping: Queries utilizing GROUP BY, AVG, COUNT, GROUP_CONCAT, HAVING, MAX, MIN, SAMPLE, or SUM
    • Solution Modifiers: Queries with ORDER BY, ASC, DESC, LIMIT, and OFFSET
    • Deeply paginated queries (e.g., LIMIT 10000 OFFSET 40000) are problematic, and likely time out
  • Federation: Queries containing the SERVICE keyword
  • Nested Subqueries: Queries containing a SELECT inside a WHERE clause
    • Also need to track nesting depth of the subqueries
  • Wikidata-specific namespaces: Queries using truthy (wdt:) vs full-statement (p:/ps:/pq:/prov:) namespaces
  • Not currently relevant to the Wikidata Queries, but listed here for completeness of the taxonomy:
    • Graph/Dataset scoping: Queries using FROM, FROM NAMED and GRAPH
    • Update semantics: Queries using INSERT, DELETE, LOAD, CLEAR, CREATE, DROP, COPY, MOVE or ADD
• Execution and cardinality profiles: List of enumerated values
  • Single triple pattern combinations - Based on the Subject (S), Predicate (P), and Object (O) pattern, and whether each is a bound or unbounded variable. They are:
    • S P O: Fully bound (a test for existence)
    • S P ?: Bound subject & predicate
    • S ? ?: Bound subject only
    • ? P O: Bound predicate and object
    • ? ? O: Bound object only
    • ? P ?: Bound predicate only
    • S ? O: Bound subject and object
    • ? ? ?: Fully unbound
  • Multi-pattern triple combinations – Computed from the parsed query. Statistics include:
    • Raw length of the query in characters (a “rough size” proxy)
    • Number of triples overall
    • Number of distinct variables, projection-variable count (variables appearing in the SELECT list), join-variable count (variables appearing in ≥ 2 triples), and ratio of the number of variables to bound IRIs
    • For each variable, count of the number of triples that reference it (i.e., the variable's "degree")
      • Tracking the max, mean, and median across variables
      • Why? Max alone can identify a star but cannot distinguish a 30-pattern star (high mean) from a 30-pattern dumbbell (where most variables have degree 1)
    • Number of triple patterns that contain at least one bound IRI as subject or object (e.g., an “anchor” count) or that contain no bound IRIs
      • Why? Queries with no anchors are problematic since the evaluation has no place to start
    • Number of triples that are fully bound
    • Count of the join types of triples that share a variable (indicating whether the join is subject-subject, subject-object or object-object)
    • Presence of disconnected triples (joins with no common variables)
    • Counts of the various SPARQL syntax elements (e.g., BIND, OPTIONAL, FILTER, etc.)
    • Nesting depths of subqueries and UNION/OPTIONAL subgraphs
    • Count of each graph shape (Cyclic, Star, …)
    • Cycle count of the join graph (variables forming a closed loop — distinguishes the Cyclic shape from the acyclic shapes)
      • Why? Cyclic counts are relatively rare and could be a structural “hazard” flag)
    • Pattern-distribution dictionary reporting the counts of the 8 single-triple patterns (above)
    • “Hazard” counts identifying unbounded triples, or ? P ? triples where the predicate cardinality exceeds a certain threshold
      • Other triple patterns may be added over time
• Size of the result set and breadth of the search space:
  • Result set size
    • Including bounded (LIMIT-capped) and unbounded sets
    • Also including zero result sets which are relevant for ASK queries and for validation/consistency-check patterns (they still incur search costs and could highlight constantly-false join predicates)
  • Execution time
• Other SPARQL aspects not included in the current analysis, listed for completeness (and possibly to be included in future work)
  • Incorporation of semantic context (such as the degree/number of connections of bound IRIs or a predicate’s frequency)
  • Details related to the execution environment (e.g., number of concurrent queries or update tasks)

Lastly, three “hybrid” features are included. These are defined by combining SPARQL constructs and BPG details. (Note that this list could be extended by adding dataset details - such as the degree of a bounded IRI or a predicate’s frequency - but that is left for a future exercise.)

The “hybrid” features are:

• SPARQL-BGP composition (defined by Zhang) analyzing the size and depth of BGPs within various scoping parentheses (i.e., scopes delimited by parentheses such as OPTIONAL { … })
  • max_bgp_size_at_any_node: Largest number of triples in any subtree
    • Why? A single 5-pattern OPTIONAL branch is heavier than five separate 1-pattern OPTIONALs
  • Branch balance/skew: Difference between min and max triple size across sub-trees
    • Why? Skewed branches are harder to plan since selectivity estimation is noisier when one branch dominates
    • For example, a 5-triple UNION branch joined to a 1-triple branch is differently shaped from a balanced 3-and-3 split (the gap between min and max is the branch skew)
    • Also capture if there is any intersection/overlap of the variables in the branches (if they share bound variables, early pruning can occur versus needing a potentially massive join)
  • Depth × width: For each leaf BGP, multiplication of its depth from the root by its size
    • Deep-and-wide BGPs (e.g., a 3-pattern BGP inside a SELECT subquery inside an OPTIONAL) cost more than shallow-and-wide
• Tractability flag (defined by Pérez, et al.) for SELECT queries with OPTIONAL clauses:
  • Boolean indicating that the query is “well-defined” - i.e., iff every variable appearing inside an OPTIONAL block also appears in a non-optional pattern at or above the OPTIONAL in the algebra tree
• Pagination flag accounting for LIMIT/OFFSET:
  • A boolean indicating that the query combines ORDER BY + LIMIT + OFFSET, along with the OFFSET magnitude
  • E.g., OFFSET 1000 is fine, but 400000 is not

Estimating SPARQL “Cost”

This section describes two mechanisms for predicting query timeout and one for predicting query execution time based on the query characterizations above.

For timeout, both a static heuristic and a learned model could be used. For execution time prediction, the learned model is needed. The latter would take a query characterization as input and return p50 and p95 execution times.

The static heuristic. The simplest timeout/cost analysis provides a “go/no go” result based on “hazardous” query shapes. These include the presence of recursive/unbounded property paths, deep OFFSET values, unanchored variables, disconnected components, and fully-unbound triple patterns. Using the results of the query comparisons, other problematic patterns may be identified.

The learned model. Supervised-learning requires inputs/features and defined results. Since the collected query logs will be characterized and will include execution details (runtime, output size, and timeout details), we have the necessary information for supervised-learning. There are three potential learned targets: 1) timeout vs no-timeout, 2) runtime estimation at p50 and p95 percentiles, and 3) output size. At present, prediction of output size is out-of-scope.

Gradient-boosted trees (XGBoost, LightGBM) are standard baselines for feature-engineered tabular data of this scale.

Note 1: It is currently planned to collect query logs across at least two 24-hour windows (1 weekday and 1 weekend day, at a minimum). Data for each day should be carefully split into training and validation sets, making sure to randomize across all hours to ensure that diurnal variations (if present) are taken into account.

Note 2: Two days of data will capture high-frequency, standard queries. However, to accurately predict p95 execution times or to identify rare but catastrophic timeouts, this is likely insufficient. Problematic queries (like heavy federated queries) may run on weekly or monthly batch cycles. It would be valuable to expand the log collection window, or artificially up-sample known "hazardous" queries in the training sets to ensure the XGBoost/LightGBM models have enough minority-class examples.

Learned Targets

1. Timeout vs no-timeout — binary classification / highest-leverage target operationally. It directly feeds rate-limiting and request-routing decisions. The label is a single boolean per query indicating if the execution exceeded the configured timeout. The model output is a probability that a query will time out, which a rate-limiter could compare against a chosen threshold - for example, P(timeout) > 0.85 → throttle. A main consideration is class imbalance since most queries do not time out. A naive accuracy metric is misleading (a model that always predicts "no timeout" likely scores 95–99% accuracy yet is useless). The results need to be evaluated with precision, recall, ROC-AUC, and a precision-recall curve.
2. Runtime estimation at p50 and p95 percentiles — regression analysis. It predicts a value for "how long will this query take" which is useful for capacity planning, queue depth estimation, and pre-execution feedback to query authors. Two separate regressors are trained on the same feature record, one targeting the median runtime and one the 95th-percentile runtime. These answer different operational questions and benefit from being independent since median captures the typical case and p95 captures tail risk. The dominant consideration is label noise since a single execution's runtime is influenced by factors the model cannot see (e.g., concurrent load, cache state, etc.). Therefore, it is valuable to aggregate to per-template percentiles. A query characterization that ran 500 times would yield fairly stable p50 and p95 estimates overall. Characterizations with only a few executions (perhaps less than 60) and would have to fall through to a basic go/no-go heuristic decision. Runtime should be log-transformed before fitting, since they can span several orders of magnitude.
3. Output size — regression analysis. (Out of scope for this iteration.) Output size (the number of rows returned) is in the framework even though not implemented now. Operationally, it could warn clients that they will receive an unexpectedly large response ("this query may return millions of rows; consider adding LIMIT") and could provide input to client-facing tools.

Note that the above targets are correlated but not redundant. A query can return large output without timing out (a simple anchored BGP that retrieves 50,000 rows directly via index lookup); another can time out with tiny output (a COUNT GROUP BY traversing millions of intermediate bindings to produce 20 rows). Operational decisions therefore depend on the combination of the targets, not any one in isolation. So, a query may be treated as high-cost if the timeout classifier says "likely timeout," or the p95 runtime regressor exceeds an SLA threshold, or the heuristic's hazard flags fire independently.