Scale-Independent
Query Processing
with PQL
Michael Armbrust, Kristal Curtis, Tim Kraska,
Michael Franklin, Armando Fox, David Patterson

Motivation

Target: Applications with SLOs for query execution time. (e.g. facebook, twitter, gmail, salesforce.com, digg)

[1] E. Schurman and J. Brutlag. Performance Related Changes and their User Impact. Presented at Velocity Web Performance and Operations Conference, June 2009

The NoSQL 'Solution'

SQL databases are fundamentally non-scalable, and there is no magical pixie dust that we, or anyone, can sprinkle on them to suddenly make them scale.

Adam Wiggins - Heroku

Separate NoSQL Systems

[1] “Large-scale Incremental Processing Using Distributed Transactions and Notifications”, Daniel Peng, Frank Dabek, Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, 2010.

Overview: Scale Independence

A scale independent system guarantees consistent performance for any sized database.

Our techniques:

[1] Michael Armbrust, Kristal Curtis, Tim Kraska, Armando Fox, Michael J. Franklin, David A. Patterson: PIQL: Success-Tolerant Query Processing in the Cloud. PVLDB 5(3): 181-192 (2011)

Scale Independent Relational Architecture

The PIQL library relies on a distributed key/value store to provide:

[1] Beth Trushkowsky, Peter Bodík, Armando Fox, Michael J. Franklin, Michael I. Jordan, and David A. Patterson. 2011. The SCADS director: scaling a distributed storage system under stringent performance requirements. In Proceedings of FAST'11

Scale Independent Optimization

PIQL Language Extensions

Optimization

Select physical operators that limit total k/v store operations, creating indexes as needed.

SLO Compliance Prediction

Use empirical response-time distributions to predict query SLO compliance.

Evaluation

TPC-W Scale Experiment

Throughput scales linearly with the number of machines.

TPC-W Scale Experiment

The 99th percentile latency remains constant, independent of the size of the data and the number of machines.

Comparison with Cost-Based Optimization

SELECT * FROM SUBSCRIPTIONS 
WHERE target = <target user> AND
owner IN <friends of current user>

What About Other Queries?

Solution: Incrementally Maintained Materialized Views and Stream Processing

Scale Independent View Maintenance

Consistency and Failure Handling

View Selection Rules

Create a view such that:

View Selection Example

How many followers does a given user have:

SELECT count(*)
FROM Subscriptions
WHERE target = <user>

The resulting view counts the followers for every user:

SELECT target, count(*)
FROM subscriptions
GROUP BY target

Reasoning about View Size

Incremental View Maintenance 101

For each update run a delta query that computes any tuples that will be added or removed from a given view

The delta query can be derived by substituting the updated tuple in the view definition and simplifying the resulting relational algebra [1].

[1] Ceri, S. and Widom, J. (1991) Deriving Production Rules for Incremental View Maintenance. In: VLDB.

Query Delta Calculation

Given a query that shows all tweets in order for a given user's subscriptions:

SELECT t.*
FROM tweets t, subscriptions s
WHERE s.owner = <user>
      t.owner = s.target
      s.approved = true
ORDER BY t.timestamp
PAGINATE 10

Query Delta Calculation

The selected view computes the timeline for all possible users:

SELECT s.owner, t.timestamp, t.owner
FROM tweets t, subscriptions s
WHERE s.owner = <user>
      t.owner = s.target
      s.approved = true
ORDER BY t.timestamp
PAGINATE 10

Query Delta Calculation

When a new tweet (@t) is inserted the delta query distributes it to all followers:

SELECT s.owner, t.timestamp, t.owner
FROM @t, subscriptions s
WHERE @t.owner = s.target
      s.approved = true
ORDER BY t.timestamp
PAGINATE 10

Query Delta Calculation

When a new subscription (@s) is inserted the delta query distributes updates the users timeline with any existing tweets:

SELECT s.owner, t.timestamp, t.owner
FROM tweets t, @s
WHERE t.owner = @s.target
      @s.approved = true
ORDER BY t.timestamp
PAGINATE 10

Techniques for Bounding Update Visibility Delay

Techniques for Limiting Contention

Aggregations

Conclusion

By using scale independence as the objective function for optimization, PIQL guarantees consistent performance even for applications with exploding data volumes.

Techniques:

Questions?

Bounding Data Returned

Pagination and Limit DDL

[1] M. J. Carey and D. Kossmann. On saying “Enough already!” in SQL. SIGMOD Rec., 26(2):219–230, 1997.

Bounding Intermediate Results

Relationship Cardinality Constraints

Allows developers to express natural limits on cardinality in an application's schema.

CREATE TABLE Subscriptions (
  ownerUserId INT,
  targetUserId INT,
  ...
  CARDINALITY LIMIT 100 (ownerUserId)
)

View Selection Example #1

Show the first 10 objects that are tagged with two given words:

SELECT t1.id 
FROM tags t1, tags t2
WHERE t1.tag = <tag1> AND
      t2.tag = <tag2> AND
      t1.id = t2.id
PAGINATE 10

The resulting view pre materializes all pairs of tags for a given object:

SELECT t1.tag, t2.tag, t1.id
FROM tags t1, tags t2
WHERE t1.tag = <tag1> AND
      t2.tag = <tag2> AND
      t1.id = t2.id
PAGINATE 10

View Size Example

SELECT t1.tag, t2.tag, t1.id
FROM tags t1, tags t2
WHERE t1.id = t2.id AND
PAGINATE 10

Size without cardinality constraint: $|tags| * |tags|$

Size with constraint on tags per object $|tags| * c$

/

#