beads/internal/storage/issueops/create_batch_cache.go
Julian Knutsen 5e951a2ff3
perf(issueops): batch create/import without per-row round trips; on-demand graph checks (#7205)
* perf(storage): cut batch-create round trips (import, bulk create, apply-batch)

A multi-issue create (import, bulk create, CreateIssuesWithFullOptions) ran
~20 SQL statements per issue, and its dependency pass ran a recursive cycle
CTE per edge over the union of both dependency tables, which Dolt cannot
index — every recursion step rescanned the edge tables, so an import whose
edges form chains went superlinear (400 issues: 73 s of 82 s in that CTE).

issueops batch create, same transaction and same stored outcome:
- createBatchCache: one IN-list read of every explicit id's presence in both
  planes (replacing two COUNT probes per issue), one read of the batch's
  stored labels (each issue's new labels then land in one multi-row INSERT),
  created/label_added events buffered and written in one pass under the ids
  InsertDerivedEvent would mint (same digest, same lowest free ordinal), and
  runs of brand-new rows written with multi-row INSERTs (same ODKU clause)
  then finished in order.
- Dependency pass: wisp routing and target presence from batch reads; the
  cycle and hierarchy checks walk an in-memory copy of the edge tables,
  loaded once and kept in step with every edge the pass writes (a pair it
  already holds is re-read, since a clientFoundRows connection reports a
  matched duplicate as written).
- createBlockedRecomputeIDs seeds all created edges and expands once.

Shared paths:
- Blocked-state recompute splits ids once per call by whether they own a
  dependency row; edgeless ids (every freshly created issue) skip the two
  union UPDATEs for one plain unmark, run after the chunk's union statements
  on the first pass so the unions see what they saw before.
- appendChildrenInTx reads children per IN-list chunk, not per parent.
- ExecuteCreate hands its BatchContext to the batch body instead of having
  it re-read the same config (-6 statements per apply-batch create item).

Not changed: one version-history row per created issue (the version
contract, version_history.go), journal order and content, and the per-row
bodies, which stay the path for singular creates.

Equivalence: internal/storage/createbatchequiv runs an import scenario
(upserts, duplicate ids, wisps, generated ids, cycles, hierarchy conflicts,
dangling/external targets, stale is_blocked, comments, journal and
versioned history on) through the fast and per-row bodies on the embedded
and server engines and compares every written table and the skip reports.

Re-pinned TestLargeBatchApplyStatementCounts*: embedded 7009/14014/846 ->
6396/12790/793, server 7008/14014/846 -> 6396/12791/793 (breakdown in
pinnedEmbeddedStatementCounts).

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* perf(storage): batch-create review fixes — lazy edge graph, opt-in recompute probe, insert budget

Review of the batch-create round-trip change (S1-S3 and nits):

- The dependency pass's in-memory graph no longer loads both edge tables.
  It reads a node's outgoing edges through the issue_id index the first
  time a walk reaches it: the batch's own endpoints up front, then one
  IN-list read per BFS level. Memory and reads scale with the subgraph
  the batch's walks touch, not the edge tables, so a two-edge create on a
  large database no longer materialises every edge. A written edge whose
  source was never loaded loads that source (row included).
- The blocked-state no-edge probe runs only when a create asks for it or
  when a chunk holds at least 32 ids. Single-issue recomputes on close,
  reopen, update and dependency edits issue exactly the statements they
  did on main (the reopen sqlmock expectation is back to main's).
- Multi-row issue INSERTs are bounded by an estimated 16 MiB of bound
  text as well as 100 rows. When a multi-row statement fails, its rows are
  replayed one at a time, and the batch continues if every row lands
  instead of returning the original error.
- Nits: document the binary-collation assumption behind Go string
  equality; DisableCreateFastPathsForTest documents that it is
  process-global and non-parallel, and panics on an overlapping caller;
  drop the unreachable skip branch; explain why wisp targets need no
  presence read.

Re-pinned TestLargeBatchApplyStatementCounts* classic 40: 793 -> 786
(the +7 probes on dep-add recomputes are gone; net vs main is -60, all of
it ExecuteCreate's config reuse). 356/712 unchanged.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* perf(storage): search the batch dependency graph from both ends

The lazy per-node load (previous commit) still walked forward from the
check's start, so on a large stored graph a single create's cycle check
read every node reachable from its target — about 800 statements per
create on a 2000-issue fixture. The cycle and hierarchy questions a batch
asks almost always end at a row the batch just created, whose only
incoming edges are the batch's own.

depGraph now answers each reachability question with a bidirectional
search: forward from the start along outgoing edges (issue_id index),
backward from the goal along incoming edges (the three target-column
indexes, read as one UNION ALL per table), always expanding the smaller
frontier and loading a level's nodes in that direction once. The batch's
endpoints are loaded in both directions up front, so a create's checks
usually finish with no further read (a chain import, too: each new
edge's goal has no incoming edge yet). Rows are keyed by (table, source,
target), so a row read from both ends counts once. An incoming read
ignores a row whose matching column is not its first set target column,
as the CTE's COALESCE does. A written pair that neither loaded end can
vouch for is re-read instead of assumed new.

On a 50k-issue / 100k-edge database, a create with two blocks edges
now runs 27 statements, against the full-scan or per-node walks before
(numbers in the review-fix summary).

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* test(storage): hold batch create to golden digests from the pre-change code

The batch-create equivalence test compared the fast paths with the same
code's per-row bodies, so changes the fast-path switch does not gate —
the recompute seed merge, the IN-list children read, ExecuteCreate's
context reuse, the prepare/finish split — were checked only by older
contract tests. Its batch was also too small to cross a chunk boundary
and never set RejectStaleUpserts.

createbatchequiv now runs four scenarios, each through the fast and
per-row bodies, and checks both against a per-table row count and
SHA-256 recorded from ebe3b6bcb (before the fast paths existed;
CREATEBATCHEQUIV_GOLDEN_DIR re-records them):
- small: the original scenario;
- import458 and import458-reject-stale: the review's 458-issue batch
  (every chunk boundary, wisps and cross-plane edges, cycles, hierarchy
  conflicts, duplicate ids across deferred runs, generated and
  hierarchical ids, stale upserts rejected and accepted), plus new edges
  whose blocked-state fallout reaches stored rows outside the batch (a
  spawner's waiter, an upserted parent's existing child);
- apply: an apply-batch through ExecuteCreate, dep adds and an update.

The recorded digests match on the embedded and server engines (the
server test now sets the fixture's prefix, so generated ids agree).
Dropping the spawner-waiter seeding is invisible to the fast-vs-per-row
comparison and caught by the golden check.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* test(storage): large-graph create benchmark

batchbench measures creates against a database already holding a large
dependency graph (batchfixtures.LargeGraphInserts: N issues, ~2N
acyclic edges with wide reachable sets and a deep parent-child forest,
committed as a Dolt version): ExecuteCreate under an existing parent with
an existing blocker, a store create with two blocks edges, and an
apply-batch of creates each with a parent-child and a blocks dep_add.
It logs wall time, statements and Go allocation per shape on the
embedded and server engines. Opt in with BEADS_BENCH_LARGE_GRAPH=<issues>
(and BEADS_BENCH_LARGE_GRAPH_CREATES); it asserts nothing.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* perf(storage): read incoming dependency edges one target column at a time

The bidirectional graph search read a node's incoming edges with one
UNION ALL over the three target columns per table. Dolt plans that as a
scan: 0.7 s per read on a 100k-edge table, where each leg alone is a 1 ms
lookup on its own index (EXPLAIN shows IndexedTableAccess per leg). Issue
the three legs as separate reads into one row set; a row matched through
two columns still counts once.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

* test(storage): run the 458-issue equivalence scenarios outside the race lane

The 458-issue golden scenarios took the embedded tier's shard over its
20-minute limit under -race (the in-process engine's own instrumentation;
about 35 s each without it). They move to
TestCreateBatchFastPathsMatchPerRowLarge_Embedded, skipped under -race and
added to nightly.yml's non-race embedded step, following the precedent of
the 712-item statement-count and 1000-item wall-clock cases. The light
scenarios (small, apply) stay in TestCreateBatchFastPathsMatchPerRow_Embedded
on every lane. The server backend (built without -race in its full
suite) runs both: TestCreateBatchFastPathsMatchPerRow_Dolt and, as its own
top-level test so the shard manifest's hash places it on another shard
(about four minutes there), TestCreateBatchFastPathsMatchPerRowLarge_Dolt.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>

---------

Co-authored-by: Claude Opus 5.5 (1M context) <noreply@anthropic.com>
2026-10-04 13:56:12 -07:00

408 lines
15 KiB
Go

package issueops
import (
"context"
"database/sql"
"fmt"
"strings"
"github.com/steveyegge/beads/internal/storage"
"github.com/steveyegge/beads/internal/types"
)
// createBatchCache amortizes the per-issue lookups a multi-issue create
// (import, bulk create) would otherwise pay one round trip each for. It is
// built once per CreateIssuesInTxWithContext call and changes HOW the batch
// learns facts, never WHICH facts it acts on:
//
// - Row presence. The cross-plane collision probe and the new-vs-upsert
// probe each read one id from one table. The cache reads every explicit
// id of the batch from both planes up front and then tracks the rows the
// batch itself inserts, so each answer equals what the per-row read would
// have returned at that point of the batch. Ids it did not read up front
// (generated ids) fall through to the per-row read.
// - Label presence. PersistLabels inserts one label per statement and
// learns from RowsAffected whether the label was new. The cache reads the
// batch's stored labels up front, so each issue's new labels are known
// before its insert, which then lands as one multi-row statement.
// - Issue rows. A run of issues the presence read shows to be brand new is
// written with multi-row INSERTs and then finished one by one, in order
// (deferredCreates); the per-row write would have been a plain insert for
// each of them.
// - Audit events. created/label_added rows in the events tables are
// content-addressed (InsertDerivedEvent) and nothing in the batch reads
// them back, so the cache buffers them and writes them in one pass at the
// end of the per-issue loop, deriving each id exactly as the per-row
// insert would have (same digest, same lowest free ordinal, counting
// same-content rows already stored and those minted earlier in the batch).
//
// A singular create never builds one: its single lookup of each kind costs
// what the cache's batch read would.
//
// COLLATION ASSUMPTION. The cache (and the dependency pass's in-memory graph,
// create_dep_batch.go) compares ids and labels with Go string equality where
// the per-row SQL compared them under the column collation. Those agree under
// the collation every beads table is created with — Dolt's default
// utf8mb4_0900_bin, which is case-sensitive and NO PAD (the migrations name
// no other). On a case-insensitive or PAD SPACE collation they would not: a
// "Bug"/"bug" label pair would land as one row but buffer two label_added
// events. A schema change to such a collation must revisit these paths.
type createBatchCache struct {
// probed holds the ids whose presence in both planes was read up front.
probed map[string]bool
// present is table -> id -> row present, as of the current point of the
// batch (the up-front read plus every row the batch has inserted since).
present map[string]map[string]bool
// labels is label table -> issue id -> stored label set, for the issues
// whose labels were read up front (see labelsProbed).
labels map[string]map[string]map[string]bool
labelsProbed map[string]map[string]bool
// events are the buffered events-plane rows, in mint order.
events []bufferedAuxEvent
}
type bufferedAuxEvent struct {
table string
event AuxEvent
}
// createBatchCacheMinIssues is the batch size at which the up-front reads pay
// for themselves. A one-issue create reads exactly what it would read per row.
const createBatchCacheMinIssues = 2
// newCreateBatchCache reads the presence of every explicit id in issues in
// both planes, and the stored labels of every explicit id that carries
// labels, in a handful of IN-list queries.
func newCreateBatchCache(ctx context.Context, tx DBTX, issues []*types.Issue) (*createBatchCache, error) {
c := &createBatchCache{
probed: map[string]bool{},
present: map[string]map[string]bool{"issues": {}, "wisps": {}},
labels: map[string]map[string]map[string]bool{"labels": {}, "wisp_labels": {}},
labelsProbed: map[string]map[string]bool{"labels": {}, "wisp_labels": {}},
}
var ids []string
labelIDs := map[string][]string{}
for _, issue := range issues {
if issue == nil || issue.ID == "" || c.probed[issue.ID] {
continue
}
c.probed[issue.ID] = true
ids = append(ids, issue.ID)
}
for _, table := range []string{"issues", "wisps"} {
found, err := idSetInTx(ctx, tx, table, ids)
if err != nil {
return nil, err
}
for id := range found {
c.present[table][id] = true
}
}
seenLabelID := map[string]map[string]bool{"labels": {}, "wisp_labels": {}}
for _, issue := range issues {
if issue == nil || issue.ID == "" || len(issue.Labels) == 0 {
continue
}
table := "labels"
if IsWisp(issue) {
table = "wisp_labels"
}
if !seenLabelID[table][issue.ID] {
seenLabelID[table][issue.ID] = true
labelIDs[table] = append(labelIDs[table], issue.ID)
}
}
for _, table := range []string{"labels", "wisp_labels"} {
if len(labelIDs[table]) == 0 {
continue
}
if err := c.loadLabels(ctx, tx, table, labelIDs[table]); err != nil {
return nil, err
}
}
return c, nil
}
// idSetInTx returns the subset of ids present in table (issues or wisps).
//
//nolint:gosec // G201: table is one of two hardcoded constants; only placeholders are formatted in.
func idSetInTx(ctx context.Context, tx DBTX, table string, ids []string) (map[string]bool, error) {
found := map[string]bool{}
for start := 0; start < len(ids); start += queryBatchSize {
end := min(start+queryBatchSize, len(ids))
placeholders, args := buildSQLInClause(ids[start:end])
rows, err := tx.QueryContext(ctx, fmt.Sprintf("SELECT id FROM %s WHERE id IN (%s)", table, placeholders), args...)
if err != nil {
return nil, fmt.Errorf("read %s presence for batch: %w", table, err)
}
for rows.Next() {
var id string
if err := rows.Scan(&id); err != nil {
_ = rows.Close()
return nil, fmt.Errorf("read %s presence for batch: %w", table, err)
}
found[id] = true
}
_ = rows.Close()
if err := rows.Err(); err != nil {
return nil, fmt.Errorf("read %s presence for batch: %w", table, err)
}
}
return found, nil
}
//nolint:gosec // G201: table is one of two hardcoded constants; only placeholders are formatted in.
func (c *createBatchCache) loadLabels(ctx context.Context, tx DBTX, table string, ids []string) error {
for _, id := range ids {
c.labelsProbed[table][id] = true
}
for start := 0; start < len(ids); start += queryBatchSize {
end := min(start+queryBatchSize, len(ids))
placeholders, args := buildSQLInClause(ids[start:end])
rows, err := tx.QueryContext(ctx, fmt.Sprintf("SELECT issue_id, label FROM %s WHERE issue_id IN (%s)", table, placeholders), args...)
if err != nil {
return fmt.Errorf("read stored labels for batch: %w", err)
}
for rows.Next() {
var issueID, label string
if err := rows.Scan(&issueID, &label); err != nil {
_ = rows.Close()
return fmt.Errorf("read stored labels for batch: %w", err)
}
c.addLabel(table, issueID, label)
}
_ = rows.Close()
if err := rows.Err(); err != nil {
return fmt.Errorf("read stored labels for batch: %w", err)
}
}
return nil
}
func (c *createBatchCache) addLabel(table, issueID, label string) {
set := c.labels[table][issueID]
if set == nil {
set = map[string]bool{}
c.labels[table][issueID] = set
}
set[label] = true
}
// rowPresent answers "is there a row with id in table right now" when the
// cache can; ok is false for an id it did not read up front.
func (c *createBatchCache) rowPresent(table, id string) (present, ok bool) {
if c == nil || !c.probed[id] {
return false, false
}
return c.present[table][id], true
}
// rowCount adapts rowPresent to the COUNT(*) shape the per-row probes scan.
func (c *createBatchCache) rowCount(ctx context.Context, tx DBTX, table, id string) (int, error) {
if present, ok := c.rowPresent(table, id); ok {
if present {
return 1, nil
}
return 0, nil
}
var count int
//nolint:gosec // G201: table is one of two hardcoded constants.
err := tx.QueryRowContext(ctx, fmt.Sprintf(`SELECT COUNT(*) FROM %s WHERE id = ?`, table), id).Scan(&count)
return count, err
}
// markInserted records that the batch wrote (inserted or upserted) a row with
// id into table.
func (c *createBatchCache) markInserted(table, id string) {
if c == nil {
return
}
c.present[table][id] = true
}
// storedLabels returns the labels stored for issueID in table, reading them
// when the up-front read did not cover the issue (a generated id).
//
//nolint:gosec // G201: table is one of two hardcoded constants.
func (c *createBatchCache) storedLabels(ctx context.Context, tx DBTX, table, issueID string) (map[string]bool, error) {
if !c.labelsProbed[table][issueID] {
if err := c.loadLabels(ctx, tx, table, []string{issueID}); err != nil {
return nil, err
}
}
return c.labels[table][issueID], nil
}
// bufferEvent queues one events-plane row for flushEvents.
func (c *createBatchCache) bufferEvent(table string, e AuxEvent) {
c.events = append(c.events, bufferedAuxEvent{table: table, event: normalizeAuxEvent(table, e)})
}
// auxEventKey is the same-content key InsertDerivedEventReturningID matches on.
type auxEventKey struct {
issueID, eventType, actor string
oldValue, newValue, comment sql.NullString
createdAt string
}
func keyOfAuxEvent(e AuxEvent) auxEventKey {
return auxEventKey{
issueID: e.IssueID, eventType: string(e.EventType), actor: e.Actor,
oldValue: e.OldValue, newValue: e.NewValue, comment: e.Comment,
createdAt: e.CreatedAt,
}
}
// flushEvents writes the buffered events, per table, under the ids the
// per-row InsertDerivedEvent would have minted: it reads the stored rows that
// could share content with a buffered one (same issue, same second), then
// assigns each buffered row the lowest free ordinal of its digest, counting
// those stored rows and the rows minted before it in this flush.
func (c *createBatchCache) flushEvents(ctx context.Context, tx DBTX) error {
if c == nil || len(c.events) == 0 {
return nil
}
byTable := map[string][]AuxEvent{}
var tables []string
for _, b := range c.events {
if _, ok := byTable[b.table]; !ok {
tables = append(tables, b.table)
}
byTable[b.table] = append(byTable[b.table], b.event)
}
c.events = nil
for _, table := range tables {
if err := flushAuxEvents(ctx, tx, table, byTable[table]); err != nil {
return err
}
}
return nil
}
//nolint:gosec // G201: table is a hardcoded routing constant; only placeholders are formatted in.
func flushAuxEvents(ctx context.Context, tx DBTX, table string, events []AuxEvent) error {
taken := map[auxEventKey]map[string]bool{}
var issueIDs, createdAts []string
seenIssue, seenAt := map[string]bool{}, map[string]bool{}
for _, e := range events {
if !seenIssue[e.IssueID] {
seenIssue[e.IssueID] = true
issueIDs = append(issueIDs, e.IssueID)
}
if !seenAt[e.CreatedAt] {
seenAt[e.CreatedAt] = true
createdAts = append(createdAts, e.CreatedAt)
}
}
atPlaceholders, atArgs := buildSQLInClause(createdAts)
for start := 0; start < len(issueIDs); start += queryBatchSize {
end := min(start+queryBatchSize, len(issueIDs))
idPlaceholders, idArgs := buildSQLInClause(issueIDs[start:end])
args := append(append([]any{}, idArgs...), atArgs...)
rows, err := tx.QueryContext(ctx, fmt.Sprintf(`
SELECT id, issue_id, event_type, actor, old_value, new_value, comment,
DATE_FORMAT(created_at, '%%Y-%%m-%%d %%H:%%i:%%s')
FROM %s
WHERE issue_id IN (%s) AND created_at IN (%s)`, table, idPlaceholders, atPlaceholders), args...)
if err != nil {
return fmt.Errorf("scan same-content events in %s: %w", table, err)
}
for rows.Next() {
var id string
var k auxEventKey
if err := rows.Scan(&id, &k.issueID, &k.eventType, &k.actor, &k.oldValue, &k.newValue, &k.comment, &k.createdAt); err != nil {
_ = rows.Close()
return fmt.Errorf("scan same-content events in %s: %w", table, err)
}
if taken[k] == nil {
taken[k] = map[string]bool{}
}
taken[k][id] = true
}
_ = rows.Close()
if err := rows.Err(); err != nil {
return fmt.Errorf("scan same-content events in %s: %w", table, err)
}
}
const cols = 8
const rowsPerInsert = queryBatchSize
for start := 0; start < len(events); start += rowsPerInsert {
end := min(start+rowsPerInsert, len(events))
values := make([]string, 0, end-start)
args := make([]any, 0, (end-start)*cols)
for _, e := range events[start:end] {
k := keyOfAuxEvent(e)
if taken[k] == nil {
taken[k] = map[string]bool{}
}
id := firstFreeDerivedID(table, auxEventDigest(e), taken[k])
taken[k][id] = true
values = append(values, "(?, ?, ?, ?, ?, ?, ?, ?)")
args = append(args, id, e.IssueID, string(e.EventType), e.Actor, e.OldValue, e.NewValue, e.Comment, e.CreatedAt)
}
if _, err := tx.ExecContext(ctx, fmt.Sprintf(`
INSERT INTO %s (id, issue_id, event_type, actor, old_value, new_value, comment, created_at)
VALUES %s`, table, strings.Join(values, ", ")), args...); err != nil {
return fmt.Errorf("record events in %s: %w", table, err)
}
}
return nil
}
// deferrable reports whether issue's row can join a multi-row INSERT: the
// batch knows, from its up-front read and its own writes, that no row with
// this id exists in either plane, so the per-row write would be a plain
// insert (InsertIssueIfNew's existence probe answers 0; ConflictSkip and
// RejectStaleUpserts only act on an existing row). CreateOnly batches keep the
// per-row path for its shard coordination write.
func (c *createBatchCache) deferrable(issue *types.Issue, opts storage.BatchCreateOptions) bool {
if c == nil || issue == nil || issue.ID == "" || opts.CreateOnly || !c.probed[issue.ID] {
return false
}
return !c.present["issues"][issue.ID] && !c.present["wisps"][issue.ID]
}
// deferredCreate is one prepared issue whose row write is pending.
type deferredCreate struct {
issue *types.Issue
issueTable, eventTable string
}
// deferredCreates is a run of prepared, brand-new issues. Writing their rows
// together and then finishing each in order is invisible to the batch: every
// finishing step (lease, events, labels, comments, journal, version seam)
// reads only its own issue's rows, which are all written by then.
type deferredCreates struct {
created []deferredCreate
}
// flush writes the pending rows per table in multi-row INSERTs, then
// finishes each issue in order, returning one result per pending issue.
func (d *deferredCreates) flush(ctx context.Context, tx DBTX, bc *BatchContext, actor string) ([]CreateIssueResult, error) {
if len(d.created) == 0 {
return nil, nil
}
byTable := map[string][]*types.Issue{}
var tables []string
for _, c := range d.created {
if _, ok := byTable[c.issueTable]; !ok {
tables = append(tables, c.issueTable)
}
byTable[c.issueTable] = append(byTable[c.issueTable], c.issue)
}
for _, table := range tables {
if err := insertIssueRowsIntoTable(ctx, tx, table, byTable[table], bc.Opts.RejectStaleUpserts); err != nil {
return nil, err
}
}
results := make([]CreateIssueResult, len(d.created))
for i, c := range d.created {
result, err := finishCreateIssueInTx(ctx, tx, bc, c.issue, actor, c.issueTable, c.eventTable, true)
if err != nil {
return nil, err
}
results[i] = result
}
return results, nil
}