Stardog Query Optimiser: Architecture and Cardinality Estimations for Graph Queries
summary
Stardog runs a cost‑based SPARQL optimizer on top of RocksDB, maps each triple pattern to index scans and focuses on join order and cardinality. It precomputes subject star-shaped graphs and augments them with count‑min sketches to estimate selectivity, finds only 50–150 distinct star-shaped patterns even on billions of edges, uses average in‑degree and frequent‑chain counts for joins, and falls back to spilling to disk and runtime feedback when estimates go wildly wrong.
AI-written summary · about
chapters (31)
- 0:00Intro
- 1:20Overview
- 2:28Company
- 7:39What is RDF
- 9:09RDF is relational
- 10:05RDF Schema
- 10:48No RDF Schema
- 12:11Sparkle
- 13:19Sparkle Algebra
- 14:13Graph Patterns
- 16:26traversals
- 19:40join order
- 20:06costbased optimization
- 20:35search space
- 25:55the basic problem
- 26:11the constraints
- 27:11the cardinality estimate
- 29:04starshaped subgraphs
- 34:22starshaped articles
- 35:13count means sketches
- 38:26precompute sketch
- 38:41bound objects
- 39:26join objects
- 39:46starshaped patterns
- 40:22frequent chain estimations
- 41:17name chains
- 41:59frequent chains
- 43:26Algorithm
- 45:59Problems
- 47:42Safety nets
- 54:19Wrapping up
related talks
40mAdaptive query optimization in PostgreSQL
29mAll about graphs in Database
41mConstant-Time Aggregations with Star-Tree in OpenSearch
30mAnalyze connections and find patterns in data with graphs
01h 07mAn Overview of the Starburst Trino Query Optimizer
14mDeductive Optimization of Relational Data Storage
31mAnswering Multi-dimensional Queries on Massive Datasets
15mOptimizing Query Performance in Big Data Systems