Scale-Independent
Query Processing
with PQL

Michael Armbrust, Kristal Curtis, Tim Kraska, Armando Fox,
Michael J. Franklin, David A. Patterson

http://www.cs.berkeley.edu/~marmbrus/

Motivation

Interactive Web Applications

• Built using high-productivity tools

• Frameworks: Ruby on Rails, Django, Play
• Storage: MySQL, Postgres

• Need to respond quickly

• Standard SLO: 99% of requests complete in < 300ms
• Even small delays cause users to abandon your app!

Applications Grow Rapidly

Success Disaster

Databases Often the Culprit

Easy to add stateless application servers. [1]

Harder to scale stateful storage systems. [2]

Traditional Relational Databases

Data Independence

• Pro:
• Declarative queries specify what data, not how to retrieve it.
• Allows optimization and changes to physical/logical schema without changes to application.
• Con: Problems hidden until they cause issues in production.

Dirty Secret: Declarative languages hide complexity.

Traditional Relational Databases

Minimum Average Cost Optimization

Dirty Secret: Fails for the 0.1%! http://www.flickr.com/photos/stephen_downes/6246522381/

NoSQL 'Solution'

• Pro: Provides predictable performance for simple operations.
• Con: Simple operations force developers to reinvent complex abstractions.

PIQL Solution

Guarantee performance for sophisticated relational queries through Scale Independence

• Built on existing scalable key/value stores
• Developers retain productivity benefits of SQL
• Optimizer ensures all queries are scalable even for outliers
• Indexes automatically selected as needed
• Model for reasoning about high-quantile SLO compliance

Architecture Overview

PIQL uses a distributed key/value store [1] for:

• Operations like get(key) and getRange(prefix, limit)
• Scalability with predictable performance [2]
• Consistency

Outline

• Mapping relational queries to bounded key/values store ops

• Language extensions

• SLO compliance prediction

• Future Work

Scale-Independent Optimization

Bound work required to answer all queries [1]

Given the set of all queries in an application $Q$. Let $Exec(q_i)$ denote the number of operations performed in the worst case by a query and $c_{ops}^{q_i}$ be a constant.

Mapping Queries to K/V Ops

Example

SELECT * FROM Posts WHERE topicId = <id> ORDER BY timestamp LIMIT 10

$c_{ops}=1$ GetRange

Mapping Queries to Key/Value Ops

Index Scan

$c_{ops}=1$ GetRange

Mapping Queries to Key/Value Ops

Foreign Key Join

$c_{ops}=|ChildPlan|$ Gets

Mapping Queries to Key/Value Ops

(Sorted) Index Join

$c_{ops}=|Child Plan|$ GetRanges

Handling Harder Queries

Ex: Timeline queries

SELECT p.text FROM Post p, Subscriptions s WHERE s.owner = <currentUser> AND s.topicId = p.topicId AND s.approved = true ORDER BY p.timestamp

Why is this safe to run? Developers have more information than optimizer.

Language Extensions

Bounding Data Returned PAGINATE turns an unbounded query into an unbounded set of bounded queries

Language Extensions

Bounding Data Returned PAGINATE turns an unbounded query into an unbounded set of bounded queries Bounding Intermediate Results Cardinality constraints in the schema allows developers to inform the optimizer of natural relationship limits.

Bound Intermediate and Final Results

SLO Compliance Prediction

Convolve empirical distributions for each operator to predict overall latency.

Measure Single-Op Performance

Predict Query SLO Compliance

Performance Insight Assistant

Helps developers choose acceptable cardinalities

Evaluation

Workloads

• TPC-W - Standard e-commerce database benchmark
• SCADr - Clone of twitter

Qualitative Analysis

• Introduced suggested cardinality constraints.
• PIQL automatically selected indexes.
• Prediction model accurately predicted SLO compliance.

Methodology

• Ran each benchmark on EC2 using SCADS
• Increasing both data and system size (weak scaling).
• Measured throughput and 99th percentile response time.

TPC-W Scale Experiment

Throughput Linear scaling as application grows.

Latency Constant response time as application grows.

Future Work

• Improved Optimization
• Adaptive plan selection
• Scale-Independent Cost-based optimization
• Pre-computation
• Automatically create materialized views
• Ensure scale independence of created views
• Approximate Query Answers

Conclusion

By adding scale independence to the relational model, PIQL makes it easier to build web application that work even as they explode in popularity.

Techniques:

• Scale independent plan selection
• PIQL language extensions
• Automatic index selection
• SLO compliance modeling

Learn More