DuckDB plans views that share reads in time exponential in their depth — draft for upstream

Đang mở
  • Có gì không ổn?
#292 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 3 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
1-3 giờ
Mức phù hợp với người mới
18/100
Loại issue
Lỗi
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
python, sql
Lĩnh vực
databases

Hướng nghiên cứu

The reproduction is the Python script in the issue body, view_plan_repro.py, which builds the node, edge and w tables and then a chain of mesh_N views in DuckDB. Run it with python view_plan_repro.py 6 to confirm the planning times in the table. Done means the script is searched against existing DuckDB issues, and either a match is linked or the script is filed upstream with its table definitions. The issue does not ask for a change in this repository.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

ml

🌀 Claude: DuckDB's planning time grows exponentially when views read the previous view several times, although the plan it finds stays small. The GraphCast demo (#270) writes each processor round as a view of the round before. On it, DuckDB plans one round in 45 s, and doesn't finish planning two within 10 minutes. This is a draft for an upstream DuckDB issue.

Reproduction

Each view reads the one before three times: as each edge's sender, as its receiver, and as a residual. This is one round of message passing in a graph neural network, with a layer norm's windows. The script needs only duckdb, and runs in seconds up to round 5:

import sys
import time
import duckdb

nodes, edges, f = 100, 400, 4
con = duckdb.connect()
con.execute(f"CREATE TABLE node AS SELECT i // {f} AS id, i % {f} AS f, random() AS val FROM range({nodes * f}) t(i)")
con.execute(f"CREATE TABLE edge AS SELECT i AS edge, (i * 7) % {nodes} AS sender, (i * 13) % {nodes} AS receiver FROM range({edges}) t(i)")
con.execute(f"CREATE TABLE w AS SELECT i // {2*f} AS f, i % {2*f} AS g, random() AS w FROM range({2 * f * 2 * f}) t(i)")
con.execute("CREATE VIEW mesh_0 AS SELECT * FROM node")
print("duckdb", duckdb.__version__)
for r in range(int(sys.argv[1])):
    con.execute(f"""CREATE VIEW mesh_{r + 1} AS
WITH edge_in AS (
  SELECT e.edge AS id, s.f, s.val FROM edge e JOIN mesh_{r} s ON e.sender = s.id
  UNION ALL
  SELECT e.edge AS id, x.f + {f} AS f, x.val FROM edge e JOIN mesh_{r} x ON e.receiver = x.id),
message AS (
  SELECT i.id, w.g AS f, SUM(i.val * w.w) AS val
  FROM edge_in i JOIN w ON i.f = w.f GROUP BY i.id, w.g),
normed AS (
  SELECT id, f, (val - AVG(val) OVER (PARTITION BY id))
               / sqrt(VAR_POP(val) OVER (PARTITION BY id) + 1e-5) AS val
  FROM message),
summed AS (
  SELECT e.receiver AS id, m.f, SUM(m.val) AS val
  FROM normed m JOIN edge e ON m.id = e.edge WHERE m.f < {f} GROUP BY e.receiver, m.f)
SELECT x.id, x.f, x.val + coalesce(s.val, 0) AS val
FROM mesh_{r} x LEFT JOIN summed s ON x.id = s.id AND x.f = s.f""")
    start = time.perf_counter()
    plan = con.sql(f"EXPLAIN SELECT * FROM mesh_{r + 1}").fetchall()[0][1]
    print(f"mesh_{r + 1}: planned in {time.perf_counter() - start:6.2f} s, {plan.count('┌')} boxes", flush=True)

python view_plan_repro.py 6, with DuckDB 1.5.6 on an Intel i7-8700:

View Planning (EXPLAIN) Boxes in the plan
mesh_1 0.00 s 28
mesh_2 0.01 s 57
mesh_3 0.05 s 79
mesh_4 0.45 s 81
mesh_5 6.71 s 83
mesh_6 111 s 85

Planning time grows about 15× per view, while the plan grows by two boxes. So DuckDB finds that each view's reads are shared, and computes them once, but only after doing work exponential in the depth. It looks as if the views are expanded inline before the shared reads are found.

In the GraphCast demo

The same shape, with GraphCast_small's real tables: 308 operators for the encoder (mesh_0), planned in 0.21 s; 504 for one processor round (mesh_1), planned in 45 s; mesh_2 didn't finish planning in 10 minutes. A forecast has 16 rounds. DataFusion doesn't plan it either, for a different reason: it inlines every read, so its plan grows 4.7× per round (#267).

For upstream

  • Search DuckDB's issues for planning time with nested views or CTEs, before filing.
  • If there's no existing issue, file this script and its table.
  • The demo keeps its SQL as written; it will run on DuckDB once planning is linear in depth.
Ngôn ngữ chính
Python
Star
142
Fork
19
Merge trung bình
3 ngày 47 phút
Pull request đã merge (30 ngày)
8

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của xqlsystems/xarray-sql

Tất cả issue của xqlsystems/xarray-sql

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.