G2: graph types, labels, edge properties, catalog

[tamnd]

Milestone G2 of the GQL program (Spec/2064g/gql/plan/00-overview.md). Spec: plan/03.

This is the milestone that turns the run's 16 errors into judged answers. Today a node carries one name and a relationship carries none, because RelTable is { id, name, from, to, edge_count } with nowhere to put a property. Every real benchmark needs edge properties, LDBC SNB needs them on every edge it loads, and the label set model that patterns and the planner both depend on does not exist. Edge properties are the largest storage change in the program and everything downstream assumes them, which is why this lands before patterns and before writes.

labels (plan/03 §2):

• label sets as bitsets over a per graph dictionary, with a declared 64 label fast path
• label expressions compiled to bitset predicates
• the planner prunes label predicates statically when the graph type makes them constant

edge properties (plan/03 §4):

• property directory on RelTable, positional with the CSR
• edge properties cross the sqlite staging hop in both directions, addressed by the edge ordinal the load order gives every edge
• reorder permutes edge properties with the CSR permutation
• on disk format version bump and a recovery matrix entry

graph types (plan/03 §3):

• closed graph types, written out as the element type patterns ISO writes, and LIKE a graph
• open graph types and a graph created with its type inline or LIKE a graph
• a graph created from a source graph that holds tables, which is the block for block AS COPY OF
• element types with key label sets, inference, optional keys
• the three relaxed consistency features, which key the property directory by element type

catalog (plan/03 §5):

• CREATE and DROP for a graph type, with IF EXISTS, IF NOT EXISTS and OR REPLACE
• CREATE and DROP for schema and graph, with the same modifiers
• DROP GRAPH actually reclaims the space, with a case that asserts it

GH (plan/03 §6):

• GH01 external references, which the grammar leaves at "!! See the Syntax Rules.", so gql-compat records it in corpus/unwritable.yaml as a feature no portable case can reach rather than testing it
• GH02 undirected edge patterns

done when:

• GG 12 of 12 and GH 1 of 1 that a portable case can reach, supported in the gql-compat report
• GC 5 of 5 supported, every case of GC01 to GC05 passing, the fifth having wanted a catalog statement and a data statement in one CALL block and getting it in Let a catalog statement open the body of a call the statement begins with #527
• closed graph type static property resolution is demonstrated to remove the per row string compare property lookup, with the before and after number
• the edge property write path is crash harness green
• a graph-bench workload that needs edge properties loads and runs
• bench/budgets.toml green, no regression anywhere in the comparative matrix that this machine can resolve, with the strict regression check left for a controlled machine

[tamnd]

#158 is merged, so a rel table can hold property columns and a pattern that binds a rel variable can read them.

The columns are the node table container reused whole, a PropsDirectory over the same segments with the same encodings and the same readers, so the interesting question was only what a row is. An edge's row is its ordinal in the load order, sorted by source and then by destination, which is the same thing as its position in the concatenated forward neighbor arrays. The group directory carries one edge_base per node group and the slot inside a list is what the binary search a probe already runs finds, so reading a property off a forward walk costs nothing extra and reading one off a backward walk costs that one search. Nothing stores a permutation, which is what keeps the fold and copy --reorder out of maintaining one. Directory version 8, and the root lives in the group directory because the table index slot for a rel id is that directory already and the database header has no free word.

The cost of deriving the ordinal from the endpoints is that the endpoints have to name one edge, so a rel table that stores properties holds each pair once and a store that would break that is refused before it writes anything. A fold that only widens the row domain leaves the load order alone and carries the columns through untouched; a fold that would merge an overlay edge into a table with columns is refused, since the new edge has no value for a column that holds one per edge, and that is what the write statements in G3 have to answer.

verify walks the new chain and checks the column span against the edge count, so a rel column set that goes missing is caught by the pass that catches a node one. The pipeline executor binds slots for node variables only, so a query reading a property off a rel variable falls back to the row engine, with a differential test pinning that it falls back rather than answering null.

The conformance run is unchanged at 155 of 385, which is what this PR should have done: it is storage and read paths, and the skips behind it need the DDL and the writes that come next.

Next is the label set model: a per graph dictionary, a bitset per node with the declared 64 label fast path, label expressions compiled to bitset predicates, and the static pruning the planner gets when the graph type makes a predicate constant. Two of the remaining edge property boxes stay open on purpose: copy --reorder does not carry rel properties yet, and the crash harness has no edge property write in its workload.

[tamnd]

#159 landed the label set model, the first of the three label boxes.

A graph now has a label dictionary in the catalog, a name at the position of its id, capped at 64 because a node's label set is one word and a word is what a scan wants to test. A node table declares which of those labels its rows may carry, its own name first, and the set a row does carry is a bitset segment on the props directory, one word per row. It sits beside the columns rather than among them, so no query can name it and no schema change can drop it, and a table that declares only its own name stores no bitset at all.

The binder does most of the work before the plan exists. A pattern's labels compile to a mask, a node table whose declared set is missing one of those bits can hold no matching row and is dropped, and the bits every remaining table gives every row need no test. So MATCH (n:Person) plans as a bare scan with no predicate over it, and MATCH (n:Person:Manager) is a scan of the one table plus one word per row. That is the static pruning box in its simple form; it stays open until label expressions land, because a constant-folded ! or | is where the graph type earns the rest of it.

Both containers are versioned and both read their predecessors: a version 1 catalog reads as one label per node table, interned in table order, which is the graph it always was. verify cross-checks the bitset against the catalog and rejects a row carrying a label its table never declared, a row missing the label its table gives every row, and a bitset that does not cover the rows. A fold that grows the row domain extends the bitset with the table's own label, which is what an appended row carries.

The pipeline executor has nothing to read a label bit with, so it hands back a query that tests one and the row engine answers it. That is the right shape for now: the bit is not a column and a vectorized test over it belongs with the scan rather than with the expression compiler.

The tally is unchanged at 155 of 385, which is what a change with no syntax behind it should do. Nothing in the corpus can declare or set a label yet; the syntax arrives with the catalog statements later in this milestone.

Next is label expressions: &, |, ! and % parsed into an expression rather than the conjunction a repeated colon means today, compiled to bit tests over the same word, and folded per candidate table in three valued logic so a table that satisfies the whole expression keeps its bare scan and a table that cannot satisfy it is dropped.

[tamnd]

PR #160 is merged, which finishes the label half of G2. A node pattern used to take a list of names and mean the conjunction of them; it now takes an expression, with & and | joining, ! negating, % holding of every element, parentheses grouping, and a repeated colon still meaning the conjunction it always meant, so (n:A:B) and (n:A&B) are one pattern. The grammar carries the four rules with | binding loosest and ! tightest.

The interesting part is what the binder does with it. The expression compiles to bit tests over the one word a row carries, and then folds against every node table in three valued logic: a bit the table never declares is false, a bit it gives every row is true, and anything else is unknown. A table the expression cannot hold on is dropped from the candidate list, a table it holds on throughout keeps its bare scan, and only what neither of those settled reaches a row at all. That fold runs a second time after the relationship types have narrowed the endpoints, so MATCH (n:Person|Employee)-[:KNOWS]->(m) ends up testing nothing once KNOWS has said the start is a Person. Bits that every remaining table gives every row also come out of the masks wherever they sit inside the expression, which is why !(Employee&Person) over the Person table reads back in the plan as !Employee, and why a conjunction of plain names stays a single mask and a single AND against the word.

An expression no table can satisfy is still an error rather than an empty answer, and it now names what was asked for, as in no node table can satisfy the labels on 'n:!%'.

The conformance tally is unchanged at 155 of 385. That is expected and stays that way until the catalog statements land, because a label can still only be set through the storage API and no case in the corpus can reach one.

Next in this milestone is the graph type work, GG01 to GG05 and the element types GG20 to GG26, and then the catalog statements GC01 to GC05 with IF [NOT] EXISTS and a DROP GRAPH that gives the blocks back. Those are what let a test declare a label and a SET n:Employee assign one, which is when these two boxes start showing up in the tally.

[tamnd]

PR #161 is in, which is the catalog side of the graph types: element types with their key label sets, graph types with the open and closed distinction, and the inference that gives a file with no declared type one derived from its tables.

The key label set is three cases rather than an optional list, because declared, inferred and absent select differently. A declared key is what was written, so a type keyed on Person still selects an element carrying Person and Employee. An inferred key is the whole label set, which is what a type with no key clause gets. A type with no key at all is one only an open graph type may hold, and since an empty key is contained in every label set, an edge type inferred from a rel table gets selected by its endpoints rather than by its labels.

The three relaxed consistency features came out free, which is why both boxes are ticked at once. Property declarations hang off the element type rather than off a name the graph shares, so two element types may key on the same labels and disagree about which properties they hold, about the type a property of the same name has, and about where they end. The strict case is the same lists with one type per key, so it pays nothing for the relaxed one.

Catalog version is 3. A version 2 file reads as one that declares no graph types, which is the open graph it has always been, and Catalog::store gives the old chain back to the free list before it writes, so a file checkpointed over and over settles at a size and holds there. There is a test that does exactly that and watches the block count.

Next is the statement side: CREATE GRAPH TYPE and CREATE GRAPH with an inline definition, LIKE a graph and from a source graph, then the catalog statements GC01 to GC05 with IF EXISTS and IF NOT EXISTS and a DROP GRAPH that hands the blocks back with a case that asserts the file shrinks. After that the closed type static property resolution with the before and after number, and GH01 and GH02.

[tamnd]

#163 is in: graph type statements, written the way ISO writes them rather than the way I first guessed.

The first pass at this had a phrase grammar, NODE TYPE PersonType LABELS Person KEY Person PROPERTIES { ... }, and it parsed and ran and moved nothing in the report. What the corpus sends is the pattern spelling: an element type is the pattern an element of it matches, so CREATE PROPERTY GRAPH TYPE t { (:Person => :Employee {name :: STRING}) } is a node type keyed on Person that also carries Employee, and (:Person)-[:KNOWS => :Close]->(:Company) is an edge type between two node types it declares along the way. Running the harness before believing the design is the lesson, and it cost a rewrite.

Two decisions came out of that. ISO's element types are anonymous and the catalog needs a name per element type, because a name is what an endpoint points at, so a pattern with no name gets one made of its labels with a number after it when that name is taken. GG24 is two node types over one label in one graph type and the number is what keeps the second from being the first written twice. The other is that an endpoint written out is folded into a node type the graph type already has when it declares nothing of its own, so the three (:Person) patterns of GG25's two edge types name one node type between them rather than three.

One number in it is zu's rather than the standard's, impdef IL003: a written key label set names between 1 and 63 labels. Empty is a type nothing selects and 64 leaves no room in the 64 bit mask a label set is for the label the arrow adds. That is where 42012 to 42015 are raised and it takes the four key label limit cases with it.

Twelve more cases pass, 155 to 167 of 385, features with a passing case 78 to 88, distinct GQLSTATUS values 17 to 21. GG20 through GG26 are done, GC03 is done, and the DROP GRAPH TYPE IF EXISTS that warns rather than fails is done. The tally and the scoreboard page carry the run.

Next is the other half of the catalog: CREATE SCHEMA, CREATE GRAPH with ANY and with a type written inline, LIKE a graph and AS COPY OF one, and a DROP GRAPH that hands the blocks back with a case that asserts the file shrinks. That is GC01, GC02, GC04, GC05 and GG01 through GG05, and it is the last piece before GH01 and GH02.

[tamnd]

#165 is merged, and it is the other half of the catalog: schemas, named graphs, and a drop that hands the blocks back.

A schema is a directory the file holds and a graph lives in one, so CREATE SCHEMA /app adds a path and CREATE GRAPH /app/social ANY adds a graph in it. Every file has the root schema / and starts with one graph in it called home, which is the graph a zu1 file has always been, and a version 3 catalog reads as exactly that: the root schema, the home graph, and every table in it. Which graph a table belongs to is a field on the table rather than a list on the graph, so a table cannot be in two graphs and the contents of a graph are a filter over the tables the catalog already holds. That field is what makes catalog version 4.

A graph is created open (GG01), with the name of a graph type the file holds (GG02), with a type written where the graph is created (GG03) or LIKE another graph (GG04), and a type written inline is kept on the graph rather than added to the file's graph types since nobody wrote a name for it. AS COPY OF is read after the type because it says what the graph starts with rather than what it is: a copy of an empty graph is exact and a copy of a graph that holds tables is refused rather than approximated, because a props directory holds pointers inside block payloads and a copy that walked them wrong would read as data. That one is the box left open above and it is its own change.

DROP GRAPH is the first statement in zu that hands blocks back. It frees the props directory of every node table in the graph, the group directory of every edge table, the tombstone chain of every node table that has one, and the table index and stats chains it rewrites, and nothing is published along the way, so the checkpoint that stores the catalog makes all three visible together and a drop that fails halfway leaves the file as it was. Freed blocks become allocatable at the checkpoint after the one that published the free and the block count is a high water mark, so the case measures what came back in the free list and not in the size of the file. CREATE OR REPLACE GRAPH frees the same way and asks everything the add could refuse before it frees anything, so a replacement that cannot be kept leaves the graph that was there. DROP SCHEMA is RESTRICT and the error says which graph is in the way.

Eleven more cases of the corpus pass, 167 to 178 of 385, and features with a passing case go 88 to 95. GC is 5 of 5 and GG is 12 of 12 with a passing case, GH is the pair still open. The ladybug column was taken again on the corpus as it stands so the two columns share it: ladybug 72 of 385, neo4j 186 of 377 from the run of the 14th, zu 178 of 385.

Next is GH01 external references and GH02 undirected edge patterns, then the block for block copy, then the two edge property boxes and the done when lines.

[tamnd]

GH02 undirected edge patterns is done, #181, with the harness side in tamnd/gql-compat#22.

ISO 18.9 writes seven edge patterns and zu read three, because every rel table was directed and three spellings are all a directed table can answer. A rel table now says whether its edges have a direction. An undirected edge is stored once, from whichever end wrote it, and both stored lists answer for it, so an undirected table costs what a directed one costs and a directed table costs nothing extra.

The pattern half is one rule and everything defers to it: a pattern plus a table's flag resolves to the direction the step actually reads, or to nothing when the two cannot meet. The binder drops a table a pattern cannot walk, the optimizer asks the same question before it colors a step, both executors call it once per step. That kept the change to the executor at one line per step loop. A pattern that can match no table is refused where it is bound, the same as every other impossible step. The bracket less abbreviations parse to the same seven patterns, and the parser refuses a relationship that is a tilde at one end and a dash at the other, or a tilde with arrowheads both ways, as 42001.

Storage carries the flag in the catalog at version 5 and in zu_catalog at user_version 3, both with a migration that reads an older file as a file of directed edges, which is what it is. Conversion moves it in both directions.

The run reads 182 of 385 now, up from 178, and 98 ISO features hold a passing case, up from 95. The four that moved are the undirected edge pattern itself and the three abbreviated spellings under G044 and G045. Those three left the consensus dispositions file at the same time, because a case one engine passes is no longer a case every engine failed.

One thing came out of the CI run and got its own change, #183. The absolute backstop on the refusal gate is a number of microseconds, and the runner reads that refusal at 3.37 to 4.04 us against a ceiling of 4, so it was a coin flip and had already gone red on main once with nothing wrong with the engine. The bench now measures the host with a loop that touches nothing in zu and reads the backstop at what that says, so the runner is held to 5.85 us instead of 4. The ratio gate is untouched.

Next is GH01 external references, then the block for block copy, then the two edge property boxes and the done when lines.

[tamnd]

#185 is merged, with tamnd/gql-compat#23 merged just before it.

Edge properties already survived a query and a round trip through storage, but not the sqlite staging hop the harness loads every fixture through, so a property written on an edge was dropped on the way in and there was no way to measure the feature end to end. Both directions now carry it. One scan of a rel table ordered by source and then destination is at once the edge list the bulk loader wants and the order an edge ordinal counts in, so the property column and the CSR neighbor array cannot drift apart, and the walk back out counts the same ordinal off the forward neighbor list.

Two smaller things came out of that. An edge whose endpoint sits outside its node table's row domain used to be dropped in silence by the old walk and is now a named error. And a rel table holding one ordered pair twice is refused at load, because an ordinal lookup searches the forward list for a destination and both edges answer it identically, so one value would be read for both.

That refusal is a real limit rather than a bug, so it is declared as one. The harness grew a parallel-edge-properties capability, separate from parallel-edges, for engines that can hold both edges and still put a distinct property on each. Neo4j and Ladybug declare it true, zu declares it false, and mandatory/pattern/parallel-edges now skips with that reason instead of failing to load.

The tally is unchanged at 182 pass, 77 fail, 116 skip, 10 error. Only two corpus fixtures carry edge properties and each is blocked behind something else, so this buys no case today and unblocks the ones that arrive when multiple-node-labels lands. That is the next piece here: rel tables with distinct from and to node tables end to end, which is the single largest block in the run at 91 skipped cases.