Skip to main content

dau scheduler

Split row-parallel dataframe work across two compute engines and merge the partial results

Build Status codecov License PyPI

Overview

When a machine has two engines that can both run the same query — two processors, a processor and an accelerator, a local worker and a remote one — the usual choice is all-or-nothing: run it here, or send it there. Running it in both places at once is often faster than either, but only for some queries, and only at the right split.

dau-scheduler makes that decision and makes the result correct. It answers three questions:

  • Should this be split, and by how much? A closed form over each engine's measured throughput gives the share of rows that finishes both arms at the same time. When the engines are comparable the predicted gain approaches 2x; when one is far faster than the other it shrinks toward 1x, and the split reports that figure rather than hiding it. A device job's fixed cost can rule a split out entirely, in which case the answer is host-only and says why.
  • Can this query survive being split? Splitting rows means each engine computes a partial answer, and not every result can be reassembled from partials. Sums and counts add. A mean needs its sum and count carried separately rather than averaged. A top-k merges two k-lists. A grouped aggregation needs a key merge with the group straddling the boundary folded back together. An exact distinct count cannot be combined without the elements themselves. This library writes that taxonomy down and refuses any aggregate the caller has not declared mergeable under it.
  • What if it can't? Refusal is by name and default-deny. A result the merge step does not know how to combine is refused, explicitly and with a reason, rather than silently mis-merged into a wrong answer.

Two commitments shape the rest of the design. Rows, not stages — splitting a query by pipeline stage ships every intermediate across the link between the engines, so the split is always over rows. And cost is measured, not assumed — host cost is profiled per (plan, host) pair and re-measured when the profile goes stale, because a speedup ratio is meaningless without naming the machine it was measured on.

The library is engine-agnostic. Both arms are injected as callables, and nothing here knows what is on the other end.

Install

Python 3.12 or newer, and pydantic; nothing else.

pip install dau-scheduler

Usage

An arm is a callable. It is handed the query, the rows it owns, and the broadcast side of a join if there is one, and it returns the partial result an unsplit run would have produced for those rows. Both arms below are the same plain-Python function, because the executor never learns what is on either end of the seam.

from dau_scheduler import ADDITIVE, MergeRule, execute_split, merge_totals, plan_split

query = {"filter": lambda row: row["day"] < 30}
rows = [{"revenue": (seed * 31) % 1000, "day": seed % 60} for seed in range(100_000)]


def arm(query, rows, build):
    kept = [row for row in rows.values() if query["filter"](row)]
    return {"revenue": sum(row["revenue"] for row in kept), "len": len(kept)}


# how much each engine gets, from one whole-query estimate per engine
split = plan_split("collaborative", cpu_seconds=0.0276, device_seconds=0.0186)
split.device_share  # 0.597...
split.predicted_speedup  # 2.48...

# how the two partial answers become one
merge = MergeRule(
    terminal="reductions",
    combine=lambda partials: merge_totals(partials, ("revenue", "len")),
    mergeable=ADDITIVE,
)

execution = execute_split(
    query,
    rows,
    split,
    merge,
    device=arm,
    host=arm,
    aggregates=[("revenue", "sum"), ("len", "count")],
)
execution.result  # the same object an unsplit run returns
execution.overlap_seconds  # how long both arms were in flight together

aggregates is what makes the refusal possible. Ask for something that cannot be reassembled and it is refused before either engine starts:

from dau_scheduler import SplitError

try:
    execute_split(query, rows, split, merge, device=arm, host=arm, aggregates=[("average", "mean")])
except SplitError as refusal:
    print(refusal)
# average: a mean is not row-partitionable; carry the sum and the count as
# separate outputs and divide after the merge

Rows an arm never reads

An engine running against data it already holds needs one number, not a list of rows: a row count if it holds its own copy, an offset if it holds a resident frame. RowRange is exactly that, and it costs two integers however many rows it names, so a share sweep over six million rows allocates nothing proportional to the row count. An arm that does need the values asks for them and gets a typed refusal from a range rather than a table materialized behind the caller's back.

from dau_scheduler import RowRange


def resident_arm(query, rows, build):
    # an engine that holds the table: it reads the offset and the length,
    # never a row
    return {"revenue": 0, "len": len(rows)}


execute_split(query, RowRange(0, 6_000_000), split, merge, device=resident_arm, host=resident_arm)

Measured host cost

plan_split refuses to guess. The host figure can come from a measurement instead: profile the first run — which has nothing to split onto anyway — and price every later run from it.

from dau_scheduler import ProfileCache, plan_split, profile_from_spans

# (start_us, end_us, node name) per plan node, as the engine reported them
engine_timings = [(0, 11_200, "optimization"), (11_200, 12_900, "scan"), (12_900, 14_600, "filter")]
profile = profile_from_spans(
    engine_timings,
    rows=1_000,
    plan_key="revenue-by-day",
    is_fixed=lambda node: node.startswith("optimization"),
    engine_version="1.42.1",
)
ProfileCache("profiles").put(profile)

if profile.is_stale_for(6_000_000, engine_version="1.42.1"):
    pass  # re-measure rather than extrapolate across orders of magnitude
plan_split("collaborative", device_seconds=0.0186, profile=profile, rows=6_000_000)

Plan-time cost is kept separate from per-row cost, because a query engine's optimizer does not get slower with more rows and folding it into a per-row rate over-estimates a large query by orders of magnitude.

Documentation

The full documentation is at dau-dev.github.io/dau-scheduler.

What is here

module what it decides
posture the share of rows each engine gets, and how that share is delivered
merge which results survive a row split, and how the partials combine
rows which rows an arm owns, by offset and optionally by value
split running both arms at once and merging what comes back
profile measured host cost, keyed by plan and machine, with staleness

Metadata

Release files for dau-scheduler 0.2.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for dau-scheduler 0.2.0
File Size Uploaded Provenance Actions
dau_scheduler-0.2.0.tar.gz 45.3 kB Without provenance Details for dau_scheduler-0.2.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for dau-scheduler 0.2.0
File Interpreter ABI Platform Actions
dau_scheduler-0.2.0-py3-none-any.whl Python 3 none any Details for dau_scheduler-0.2.0-py3-none-any.whl

Total release size: 97.8 kB

Release files / dau_scheduler-0.2.0.tar.gz

Download URL dau_scheduler-0.2.0.tar.gz
Size 45.3 kB
Tags Source
SHA-256 checksum
How to use checksums
e9c0b3a24cde5213c7c597d1fd664dcbb74a36cd0933b2d4ee3fa90572a40788
BLAKE2b-256 checksum
How to use checksums
c0026f4ed359803fb3e99d8a635c319d6505b21f98e30b324b88b504ee9faab4
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.15

Release files / dau_scheduler-0.2.0-py3-none-any.whl

Download URL dau_scheduler-0.2.0-py3-none-any.whl
Size 52.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
1e30ea5729f07c720429d87abab865b2add2528e7cf490e4b70fc5b0ba8fc066
BLAKE2b-256 checksum
How to use checksums
05162c14a44fd293c491d16d483a79b61bad6e5219b8dba097cc6ca82540f4f3
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.15

Security for dau-scheduler 0.2.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page