PaperlayerView exact revision on arXiv

Source-linked AI summary

Starling: A Scalable Query Engine on Cloud Function Services

Matthew Perron, Raul Castro Fernandez, David DeWitt, Samuel Madden

arXiv:1911.11727v1cs.DB

TL;DR

Bursty or low-volume analytics can leave provisioned clusters idle and costly, making fine-grained cloud functions an appealing alternative. Starling is a query engine built on cloud functions that mitigates their execution and data-exchange challenges. It offers latency comparable to provisioned systems at lower cost for moderate query volumes, with the conclusion describing cost- and performance-competitive operation across dataset sizes.

  • Problem

    Bursty or ad-hoc analytics can leave provisioned clusters underused, while users may also face data-loading steps before querying raw cloud-storage data.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    Starling runs query tasks on elastic cloud-function invocations and uses cloud object storage to exchange intermediate data while mitigating worker and straggler challenges.

    Source: §1 · p. 2

  • Results

    Starling achieves query latency comparable to provisioned systems while decreasing cost for workloads with moderate query volume.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Starling’s optimizations make it cost- and performance-competitive with provisioned systems and allow it to scale from small to large datasets without explicit provisioning decisions.

    Source: §9 · p. 14

    At high concurrency, throughput is limited by cloud-function invocation caps and the coordinator’s capacity to issue parallel HTTP requests.

    Source: §6.5 · p. 12

Abstract

from arXiv · show

Much like on-premises systems, the natural choice for running database analytics workloads in the cloud is to provision a cluster of nodes to run a database instance. However, analytics workloads are often bursty or low volume, leaving clusters idle much of the time, meaning customers pay for compute resources even when unused. The ability of cloud function services, such as AWS Lambda or Azure Functions, to run small, fine granularity tasks make them appear to be a natural choice for query processing in such settings. But implementing an analytics system on cloud functions comes with its own set of challenges. These include managing hundreds of tiny stateless resource-constrained workers, handling stragglers, and shuffling data through opaque cloud services. In this paper we present Starling, a query execution engine built on cloud function services that employs number of techniques to mitigate these challenges, providing interactive query latency at a lower total cost than provisioned systems with low-to-moderate utilization. In particular, on a 1TB TPC-H dataset in cloud storage, Starling is less expensive than the best provisioned systems for workloads when queries arrive 1 minute apart or more. Starling also has lower latency than competing systems reading from cloud object stores and can scale to larger datasets.

1 INTRODUCTION

Bursty analytics workloads can leave provisioned clusters underused, while loading raw data or waiting for slow cluster scaling can make ad-hoc queries costly or slow. Starling uses cloud functions and storage to address these challenges, achieving latency comparable to provisioned systems while decreasing cost for moderate query volumes.

1 INTRODUCTION

  • Provisioned clusters can be underused on unpredictable, ad-hoc workloads, while elastic resizing may take minutes and loading data adds latency for one-off or ETL queries.Cloud storage is also described as an order of magnitude cheaper than other storage services.Source: §1 · p. 1
  • Cloud functions offer low-startup, fine-grained parallel tasks billed by execution time, but constrained, stateless workers make query shuffles and straggler management difficult.Opaque storage services can add variable latency to workers handling exchanged state.Source: §1 · pp. 1–2
  • Starling maps tasks to elastic function invocations, shuffles through cloud object storage, mitigates stragglers, and lets users tune invocation counts for cost or latency.It materializes intermediate results in a format optimized for pay-by-request storage.Source: §1 · p. 2
  • Starling achieves query latency comparable to provisioned systems while decreasing cost for workloads with moderate query volume.The paper positions this as a response to the difficulty of provisioning for unpredictable, ad-hoc workloads.Source: §1 · pp. 1–2

2 MOTIVATION AND DESIGN

Starling targets analytics users who want to query raw cloud-storage data without provisioning a cluster for each workload. It uses cloud functions for flexible execution, while relying on AWS Lambda and S3 for its implementation.

2.1 Landscape of Cloud Analytic Databases

  • Starling targets low-to-moderate-volume analytics on cloud object storage, avoiding data loading and charging per query while letting users trade cost against performance through per-query parallelism.The section frames these as three features missing together from existing cloud analytics systems.Source: §2.1 · p. 2, Figure 1 · p. 3

2.2 Cloud Functions

  • Cloud functions support direct cloud-storage access, low startup times, per-invocation billing, and parallel execution, but their runtime and resource limits and lack of direct worker communication complicate analytics.Analytic queries can run for hours, while function execution is limited to a few minutes and containers are resource-constrained.Source: §2.2 · p. 3

2.3 Starling Architecture

  • A small coordinator compiles planned queries and schedules tasks to workers, which execute query work in function invocations and exchange state through shared storage.Starling has no query optimizer and takes planned queries as input.Source: §2.3 · p. 3
  • Starling is designed to launch many function invocations in parallel and depends on inexpensive, high-throughput exchange storage.Its performance depends on individual parallel workers maintaining high throughput while others execute concurrently.Source: §2.3 · p. 3

2.4 Choosing a Cloud Function Service

  • The implementation uses AWS Lambda because Google Cloud Functions and Azure Functions impose language or invocation-rate restrictions that can affect parallel query performance.Choosing Lambda restricted intermediate-data exchange to AWS services.Source: §2.4 · p. 4

3 MANAGING DATA IN STARLING

Starling reads base tables from cloud storage and uses S3 to exchange intermediate state between stateless workers. Its data-management design addresses shuffle cost and storage latency through partitioned objects, parallel reads, and doublewrite.

3 MANAGING DATA IN STARLING

  • Starling leaves base-table data in S3 and manages intermediate state separately because function workers are stateless.Its design only requires rows of a specified schema to be parseable from source objects.Source: §3 · p. 4, §3.1 · p. 4

3.1 Base Table Storage

  • ORC supports column selection and skipping input portions through indexes and statistics; the evaluation uses raw ORC data.The base-table design is agnostic to format, with CSV, ORC, and Parquet among common choices.Source: §3.1 · p. 4, Figure 2 · p. 4

3.2 Managing Intermediate State

  • Workers exchange intermediate data through S3, where each producer writes one partitioned object and consumers fetch metadata and the needed partition with two reads.The object format places metadata before partitioned data and supports fetching adjacent partitions with the same number of GET requests as one partition.Source: §3.2 · p. 5

3.3 Mitigating High Storage Latency

  • Parallel S3 reads keep workers less idle: effective throughput rises through 16 parallel reads, while doublewrite reduces the risk that object-visibility delays slow all consumers.Doublewrite stores the same object under two keys, allowing consumers to try the second if the first is unavailable.Source: §3.3 · p. 5, §3.3.1 · p. 5

4 QUERY EXECUTION

Starling executes query stages on cloud functions and uses S3 to exchange intermediate data. Its execution strategies balance latency, cost, and worker limits through shuffle design, task counts, and pipelining.

4 QUERY EXECUTION

  • Starling’s coordinator compiles a physical plan, schedules dependent stages, and invokes tasks that execute as much work as possible without communicating with other workers.The coordinator generates and packages a C++ executable; task inputs and outputs are determined before each stage begins.Source: §4 · p. 5

4.1 Relational Operator Implementation

  • Scans read input portions in parallel, joins use broadcast or partitioned hash strategies, and aggregation combines partial results in a final reduction.Partitioned joins hash-partition on the join key, then build and probe a hash table; aggregation may shuffle on the group-by key first.Source: §4.1 · p. 6

4.2 Shuffling

  • With 5,120 producers and 1,280 consumers, a multistage shuffle reduces S3 read cost to $0.073 from more than $5 for a standard shuffle.Combining tasks read contiguous partitions and produce partitioned outputs; in this example, their additional write cost is $0.00128.Source: §4.2 · pp. 6–7, Figure 4 · p. 6

4.3 Assigning Tasks to Workers

  • More tasks per stage can lower latency but raise exchange costs, while too few can exhaust worker memory; without an optimizer, users tune task counts and shuffle strategy.The coordinator also caps parallel tasks per stage and schedules replacements as tasks finish.Source: §4.3 · p. 7

4.4 Pipelining

  • Pipelining starts consuming stages when many producer inputs are available, typically lowering latency at additional cost; disabling it favors the least expensive execution.A straggling producer can leave all standard-shuffle readers idle, increasing stage cost.Source: §4.4 · p. 7, Figure 5 · p. 7

5 STRAGGLERS

S3 request tail latency can delay Starling’s stages, so it uses duplicate requests to mitigate read and write stragglers. Microbenchmarks show shorter latency tails, with compute-time savings exceeding the added request costs in the reported experiments.

5 STRAGGLERS

  • S3’s poor tail latency affects reads and writes, and its opaque operation limits Starling’s insight into straggler causes.A single query may issue hundreds of thousands of S3 GET requests.Source: §5 · p. 7, §5.1 · p. 7

5.1 Read Straggler Mitigation

  • Workers detect reads that exceed expected response time, open a new S3 connection, and retry; the model estimates response time from request size and concurrent readers.The read-response model uses latency and throughput parameters measured as 15 ms and 150 MBps.Source: §5.1 · pp. 7–8
  • At the 99.99th percentile, read latency is more than a second without RSM and .25 seconds with RSM; 99th-percentile writes take almost 9 seconds without WSM and 3.8 seconds with full WSM.For writes, a single timeout yields 5 seconds at the 99th percentile.Source: §5.1 · p. 8, §5.2 · p. 8
  • Read mitigation saves nearly 95 seconds of compute time at an additional read cost equivalent to 1.3 seconds; write mitigation saves 2,100 seconds while costing 314 seconds of compute.The read strategy is triggered in 0.3% of cases; full write mitigation is invoked in 31% of writes in its experiment.Source: §5.1 · p. 8, §5.2 · p. 8

5.2 Write Straggler Mitigation

  • Write stragglers require a second response-time model because S3 may delay its reply after data is sent; Starling starts another write request when either model detects a straggler.The write model uses different parameters from the read model.Source: §5.2 · p. 8

6 EVALUATION

The evaluation compares Starling’s cost, latency, scalability, concurrency, pay-by-query competition, tuning, and optimizations, using mostly 1TB TPC-H experiments.

6 EVALUATION

  • The evaluation tests cost, latency, scalability, concurrency, pay-by-query competition, cost-performance tuning, and the importance of Starling’s optimizations.These questions correspond to Sections 6.2–6.8.Source: §6 · p. 8

6.1 Experimental Setup

  • Most experiments use scale-factor 1,000 (1TB) TPC-H; the evaluation excludes queries 11, 21, and 22 and reports median latency from three sequential executions.The dataset is unskewed and converts from about 1TB uncompressed to 317GB in ORC.Source: §6.1 · p. 8, Figure 6 · p. 9
  • Redshift comparisons include local dense-compute and dense-storage clusters with and without distribution and sort keys, plus Spectrum reading base tables from S3.Redshift costs include on-demand node pricing, with S3 scan costs added for Spectrum.Source: §6.1 · p. 9
  • The evaluation also compares Athena and two Presto cluster sizes; Athena charges by bytes scanned, while Presto runs on 5-node and 17-node clusters.Starling runs with performance optimizations enabled, and its task counts are manually selected.Source: §6.1 · p. 9
  • Starling task counts are tuned manually, and its query plans use join orders from Redshift’s optimizer.Multi-stage shuffling is disabled for scale factor 1,000 and enabled for large joins at scale factor 10,000.Source: §6.1 · p. 9, Figure 7 · p. 10

6.2 Cost of Operation

Starling’s cost advantage depends on workload volume and throughput: it is least expensive at moderate query volumes, while provisioned systems can become cheaper at higher utilization.

6.2 Cost of Operation

  • Around 60 queries per hour on the 1TB dataset, running Redshift becomes less expensive than Starling, although Starling is least expensive across configurations at moderate query volumes.Redshift’s local-data configurations have fixed daily costs, whereas Starling incurs little cost when queries are idle.Source: §6.2 · p. 10
  • At about 120 queries per hour, Starling’s cost exceeds presto-16, but above 153 queries per hour Starling is the only system able to keep up.Presto-4 is cost-competitive with Starling at about 33 queries per hour, its maximum back-to-back throughput.Source: §6.2 · p. 10
  • Starling’s cost per query stays fixed as query inter-arrival time grows, while provisioned systems’ cost per query rises rapidly.Starling’s operational costs include its small coordinator and S3 storage.Source: §6.2 · p. 10

6.3 Query Latency

Starling offers the lowest latency for ad-hoc analytics on cloud object storage, while tuned provisioned systems remain preferable when very low latency is paramount. On 10TB, Starling retains a latency advantage over the tested provisioned systems, with cost advantages depending on query arrival intervals and comparison scope.

6.3 Query Latency

  • Athena did not complete queries 2, 8, 9, and 15 because of resource-exhaustion errors or missing SQL functionality.The comparison also plots the geometric mean for the subset of queries Athena completed.Source: §6.3 · p. 10, Figure 8 · p. 11
  • Starling is just over four times slower than redshift-dc-dk, but less than 50% slower than redshift-dc-dd after Redshift loads data into its native format.On pre-partitioned data, Starling achieves nearly 2x speedup on Q12 over unpartitioned base tables.Source: Figure 9 · p. 11
  • For ad-hoc analytics on data in cloud object storage, Starling has the lowest query latency, while tuned provisioned systems remain best for users requiring very low latency.Against systems with preloaded, sorted local data, Starling is less expensive for query inter-arrival times over 60 seconds; against systems reading S3, it is less expensive over 30 seconds.Source: §6.3 · p. 11

6.4 Scalability

  • On 10TB, every tested provisioned system has latency at least 2.7 times larger than Starling’s.The experiment uses 12 selected queries spanning input sizes and numbers of joins.Source: Figure 11 · p. 11, §6.4 · p. 11
  • On 10TB, Starling has the lowest cost per query among systems reading S3 at achievable query rates, and costs less than Redshift when queries are at least 721 seconds apart.The Redshift comparison uses the existing cluster configuration; the authors note that scaling it up could improve latency.Source: Figure 12 · p. 12, §6.4 · p. 12
  • Under a linear-scaling assumption, a 16-node Redshift cluster would have latency similar to Starling but four times its dollar cost per query.This is an estimate for the predicted 16-node configuration, not a measured comparison.Source: §6.4 · p. 12

6.5 Concurrency

Starling’s concurrency is bounded by function-invocation limits and coordinator load, while comparisons with Athena show trade-offs in completion, latency, and cost.

6.5 Concurrency

  • Throughput can level off at function-invocation limits, while invoking more functions in parallel strains the low-cost coordinator’s HTTP-request capacity.The authors leave coordinator optimization for future work because high concurrency is not the focus.Source: §6.5 · p. 12

6.6 Pay-per-query Services

  • Athena could not complete 2 of 12 queries on the 1TB dataset, and its completed queries took more than 50% longer than Starling’s.On a larger dataset, Athena completed only 5 of 12 queries; those completed took 5 times longer than Starling’s, and Athena cost more than twice as much per query.Source: §6.6 · p. 12
  • Athena’s cost per query was $0.287 versus Starling’s $0.0256 at the highest query rates, but Athena was cheaper below one query every 350 seconds.These comparisons exclude queries Athena could not execute.Source: §6.6 · p. 12
  • For users needing interactive performance, Athena’s inability to tune performance makes it a nonstarter.Figure 14 presents the cost and latency flexibility comparison for TPC-H Q12.Source: Figure 14 · p. 13

6.7 Tunable Performance

Starling lets users trade cost for performance by changing join parallelism, and its optimizations reduce Q12 latency while keeping cost approximately constant.

6.7 Tunable Performance

  • Increasing join-stage task count raises both performance and cost; at lower task counts Lambda execution time dominates cost, while at higher counts S3 reads dominate.The experiment uses TPC-H Query 12, a select-project-join-aggregate query over the dataset’s two largest tables.Source: §6.7 · p. 13
  • Starling remains on the Pareto frontier for Q12 under the strictest query-arrival assumption, costing less than Spectrum and Athena at the same performance while reaching higher performance than other S3-reading systems.Compared with provisioned systems, it is also easier to tune for cost and performance goals.Source: §6.7 · p. 13

6.8 Performance Optimizations

  • Without optimizations, Q12 averaged about 80 seconds with high variance; parallel reads substantially improved performance, with cost remaining approximately constant as optimizations were added.The experiment fixed join workers at 128 and enabled optimizations one by one.Source: §6.8 · p. 13
  • 12.8 seconds: doublewrite reduced Q12’s mean latency to this level, six times faster than without optimizations and more than 2.4 times faster than with parallel reads alone.WSM reduces runtime variance and brings latency on par with presto-16 by reducing variance in individual reads and writes.Source: Figure 15 · p. 13

7 DISCUSSION: STARLING’S COST TO CLOUD PROVIDERS

The provider-cost discussion compares Starling’s compute use with a 16-node Presto proxy and argues that lower provider resource use is plausible, but not certain without provider-only utilization data.

7 DISCUSSION: STARLING’S COST TO CLOUD PROVIDERS

  • The comparison uses Athena’s similarity to a 16-node Presto cluster as its proxy, while recognizing that Athena’s internal configuration is unavailable.The geometric mean of Athena query latencies on the 1TB dataset was within 3.5 seconds of presto-16.Source: §7 · p. 13
  • For most queries, Starling consumed less compute than optimized presto-16 for the same query.Figure 16 compares per-query core-seconds; the presto-16 baseline uses 16 r4.8xlarge nodes, assumed to provide full cluster use for each Athena query.Source: §7 · pp. 13–14, Figure 16 · p. 14
  • Provider-side efficiency may favor function-based execution when query stages use only a subset of a provisioned cluster’s cores.The discussion notes that such stages can leave cluster resources underutilized.Source: §7 · p. 14
  • Without cloud-provider details on cluster architecture, load, and utilization, the authors cannot say with certainty that Starling uses fewer provider resources than Athena.They regard lower utilization as likely based on conservative CPU-utilization estimates.Source: §7 · p. 14

8 RELATED WORK

Related work spans serverless job frameworks and cloud analytics systems; Starling is presented as the first analytical database engine built on a serverless platform.

8 RELATED WORK

  • PyWren does not demonstrate competitive query-processing performance or cost, while GG manages tasks and stragglers but is not query-specialized.ExCamera and Sprocket target video workloads with simpler communication patterns than query processing.Source: §8 · p. 14
  • Query processing requires complex communication such as join shuffles; prior function-service shuffle work relies on provisioned virtual machines and does not execute full SQL queries.Spark on Lambda is Spark-restricted, lacks straggler mitigation, and does not demonstrate competitive performance.Source: §8 · p. 14
  • The authors describe Starling as the first analytical database engine on a serverless platform, addressing a landscape where existing systems do not fulfill all three goals: no data preloading, per-query charges, and tunable performance.The text contrasts Starling’s workload-specific optimizations with general-purpose cloud-function tools.Source: §8 · p. 14

9 CONCLUSION

Starling targets interactive, low-cost analytics for ad-hoc workloads, with performance and cost tunable to user objectives. Its optimizations make it competitive with provisioned systems and let it scale across dataset sizes without explicit provisioning decisions.

9 CONCLUSION

  • Starling’s optimizations make it cost- and performance-competitive with provisioned systems while scaling across small and large datasets without explicit provisioning.The conclusion also says it can scale from small to large datasets and back.Source: §9 · p. 14
  • Starling harnesses cloud functions’ rapid scaling and fine granularity to target interactive, low-cost per-query analytics tunable to performance and cost objectives.The stated scope is ad-hoc workloads.Source: §9 · p. 14
  • Starling addresses managing hundreds of stateless workers that must exchange data through opaque cloud storage.Source: §9 · p. 14

Related papers

Loading 1911.11727v1…