v0.2.0 · MIT

graph_query

Declare edges on your models from the associations they already have, walk them in a Ruby chain, a pattern or a Cypher query, and get Active Record relations back. One recursive CTE per walk, nothing to install in the database.

gem 'graph_query'

Getting started

graph_query lets Active Record models on PostgreSQL be walked like a graph. You declare edges on your models from the associations they already have, then traverse them in a Ruby chain or match them with a Cypher-style pattern. Every walk compiles to one WITH RECURSIVE statement, and what comes back is an ordinary Active Record relation you can keep chaining.

It needs nothing installed in the database: no Apache AGE, no extension. That is why it runs on Heroku Postgres.

Install

# Gemfile
gem 'graph_query'

It needs Ruby 4.0+, Active Record 7.1+ and the pg adapter. Once loaded, every Active Record model gets graph_edge, traverse, graph and graph_match. There is no generator, migration or initializer.

A first walk

The examples in this guide use a small schema of places, venues, events and people.

Say locales nest (a state contains cities, a city contains neighborhoods) and venues belong to a locale:

class Locale < ApplicationRecord
  belongs_to ,  'Locale',  true
  has_many ,  'Locale',  
  has_many 

  graph_edge ,  
  graph_edge ,  
  graph_edge ,  
end

Now walk them:

washington = Locale.where( 'Washington')

washington.traverse(,  0..)                       # the state and every locale inside it
washington.traverse(,  0..).traverse()  # every venue in the state
          .where( 'bar').order().limit(20)             # ... still a relation

seattle = Locale.find_by( 'Seattle')
seattle.traverse(,  1..)                            # every locale Seattle lies within

The same walk as a pattern, and as a Cypher query:

GraphQuery.match('(s:Locale)-[:contains*0..]->()-[:has_venue]->(v:Venue)',  washington)
          .where( 'bar')

GraphQuery.cypher(<<~CYPHER, state: 'Washington')
  MATCH (s:Locale {name: $state})-[:contains*0..]->()-[:has_venue]->(v:Venue)
  WHERE v.kind = 'bar'
  RETURN v ORDER BY v.name
CYPHER

The model in one paragraph

A node is a row of a model, named by (node_type, node_id), where the type is the model's polymorphic_name. An edge is a named kind of link from nodes of one model to nodes of another, read from a table: each row whose source and target columns are both set is one edge. A walk starts from a set of nodes (a relation, a record, or pairs) and takes steps; each step follows some edges one or more hops. The nodes the last step reaches are the result.

Where to go next

  • Declaring edges: every way to turn a table into edges.
  • Walking: the options a step takes.
  • Results: relations, depths, pairs, paths, roll-ups and dataloaders.
  • Patterns: the same walks as text, with Ruby bindings.
  • Cypher queries: MATCH, WHERE, RETURN, ORDER BY, SKIP, LIMIT.
  • Writing edges: transactions that link and unlink, and graph mutations on models.
  • GraphQL: fields backed by walks, batched, and mutations from graph mutations.
  • How it runs: the SQL, performance and limits.
  • Reference: every method, errors, and RBS / Sorbet types.

Declaring edges

Call graph_edge name, ... on the model the edge leaves. The name is a Symbol you pick (:contains, :has_venue, :rolls_up). Several declarations with one name make one kind of edge that unions them, even across models and target types.

From an association

The usual way. Name an association the model already has, and graph_query reads the edge from the table that holds the foreign key.

Association Rows that are edges Example
has_many / has_one the target's rows, pointing back with the foreign key graph_edge :contains, association: :children
belongs_to the owner's rows with the foreign key set graph_edge :within, association: :parent
has_many :through a join model that belongs_to the target the join model's rows graph_edge :billed_on, association: :events

What carries over from the association:

  • Its scope. has_many :published_posts, -> { where(published: true) } makes edges only to published posts. The scope must not take the owner record (a scope with an argument can't be walked, since there is no one owner).
  • as: on a polymorphic has_many adds a condition on the type column, so only rows pointing at this model count.
  • The join model's scope on a :through association.

What can't be an edge (each raises ArgumentError when the edge is first built):

  • A polymorphic belongs_to: it has no one target model. Declare one edge per target with through: or sql:.
  • A :through association with its own scope: that scope filters the target, not the join rows. Use through: with where: instead.
  • A :through chain through another :through, or one whose source isn't a belongs_to.

From a join model, named outright

When there's no association, or you need a different shape, name the table's model and its two columns:

class Locale < ApplicationRecord
  graph_edge ,  Locale,  LocaleGrouping,
                         ,  
end
  • to: the model the edge arrives at.
  • through: the model whose table holds the rows. It can be the target itself: graph_edge :rolls_up, to: EventSeries, through: EventSeries, source: :locale_id, target: :id.
  • source: the column holding the id of the node the edge leaves (defaults to the model's foreign_key).
  • target: the column holding the id of the node it arrives at.

to: and through: take a class, which keeps them checked by Ruby and by type checkers, or a model name as a String. A class loads that model when this one loads; a name is looked up only when a query first needs the edge, so use one to break a load-order cycle or to name a model that may not exist in every app.

From SQL

For anything else, give SQL selecting source_id and target_id:

class Venue < ApplicationRecord
  graph_edge ,  Venue,  <<~SQL
    SELECT a.id AS source_id, b.id AS target_id
    FROM venues a JOIN venues b ON a.id <> b.id AND ST_DWithin(a.location, b.location, 500)
  SQL
end

SQL edges can't take edge_where: filters (there's no model to check columns against), and the planner can only use indexes if it can push the source_id = ... condition into your SQL.

Computed edges

When the SQL depends on something known only when the query runs (the current time, a setting, a scope built in Ruby), give a callable instead. It runs each time a query is built, and returns a relation or a String that selects source_id and target_id:

class Venue < ApplicationRecord
  # Pass it as computed:
  graph_edge ,  Venue,  lambda {
    VenuePair.where('opens_at <= ? AND closes_at > ?', Time.current, Time.current)
             .select('venue_a_id AS source_id, venue_b_id AS target_id')
  }

  # or as a block
  graph_edge(,  Venue) do
    Venue.joins('JOIN venues other ON other.locale_id = venues.locale_id AND other.id <> venues.id')
         .select('venues.id AS source_id, other.id AS target_id')
  end
end

The result is compiled into the walk's one statement like any other edge. The callable only builds the SQL: it isn't called once per node, so it can't run Ruby on each row. Computed edges, like SQL edges, take no edge_where: and can't be written by a transaction.

Filtering an edge's rows: where:

Every form takes where:, a Hash or a scope Proc run on the edge's table:

graph_edge ,  ,  {  'headliner' }
graph_edge ,  Person,  Membership,  ,  ,
                              -> { where( nil) }

Unions

Declarations with the same name are one edge kind. A walk over :contains follows both of these:

graph_edge ,                         # a locale's sub-locales
graph_edge ,  Locale,  LocaleGrouping,          # and, for a super locale, its members
                       ,  

Edges with one name can also arrive at different models: a :rolls_up edge can go from a venue to its events and its event series.

When edges are built

Declarations are lazy. They're stored as builders and turned into edges the first time a query needs them, so a declaration may name a model that isn't loaded yet, and model classes can be declared in any order. When Rails reloads a model, its declarations replace the old ones instead of adding to them.

To see what's declared:

GraphQuery.registry.all
# => [#<GraphQuery::Edge Locale -[:contains]-> Locale>, #<GraphQuery::Edge Locale -[:within]-> Locale>, ...]

Ids

Node ids in one walk must share a SQL type, because each step's rows are unioned into one node_id column. Use uuid everywhere, or bigint everywhere.

Walking

Start a walk from a scope, a record, or a whole model, and add steps with traverse:

Locale.where( 'Washington').traverse(,  0..)   # from a scope
locale.traverse(,  1..)                               # from one record
Venue.traverse()                                             # from every row of a model

Each traverse returns a new GraphQuery::Query (queries are immutable), so steps chain:

Locale.where( 'Washington')
      .traverse(,  0..)    # step 1: the state and everything in it
      .traverse()               # step 2: their venues
      .traverse(,  Event)        # step 3: the events those venues host

traverse(names = nil, **options)

names is a Symbol, an Array of Symbols (follow any of them), or nil / :* for every edge leaving the current nodes.

Option Default Meaning
depth: 1 Hops, as an Integer or a Range. See below.
direction: :out :out (source to target), :in (target to source: ancestors, "who points at this"), or :both.
to: any Only arrive at these models: a model, a name, or an Array.
where: none Only arrive at nodes in this relation. An Array gives one relation per model (any may match). A Hash filters the one model the step reaches.
through: none Every node the step passes through, the last included, must be in this relation (or Array, one per model). Nodes of other models pass freely.
edge_where: none A Hash (or scope Proc) each edge's row must match.

depth

Value Reaches
1 nodes one hop away (the default)
3 nodes exactly three hops away
1..3 one to three hops away
0.. the start nodes and everything reachable
1.. everything reachable, not the start nodes
2.. everything at least two hops away
0..1 the start nodes and their neighbours

A node counts if some route reaches it within the range. Walks that can go on forever (1.., 0..) stop when no new node turns up, so cycles end them. Unbounded walks that have to count hops (2.., with_depth, paths) stop at GraphQuery.max_depth, 32 by default:

GraphQuery.max_depth = 64

direction

:in walks an edge backwards. With only :contains declared, you still get ancestors:

seattle.traverse(,  ,  1..)   # everything that contains Seattle

out, inbound and both are shorthands:

query.out()       # traverse(:contains, direction: :out)
query.inbound()   # traverse(:contains, direction: :in)
query.both(,  1..2)

to:, where:, through:

to: and where: filter where the step arrives; the walk still passes through other nodes on the way:

# Every bar anywhere under Washington, but walk through every locale to find them.
washington.traverse(,  0..).traverse(,  Venue.where( 'bar'))

# The same with a Hash, because the step reaches one model.
washington.traverse(,  0..).traverse(,  {  'bar' })

# A step whose edges reach several models: arrive only at events.
venue.traverse(,  1..,  Event)

through: filters every node on the way (Cypher's all(n IN nodes(p) WHERE ...)). A node outside the relation stops the walk there:

# Only descend through active locales; a retired county hides everything under it.
washington.traverse(,  1..,  Locale.where( nil))

edge_where:

Filters the edge rows themselves:

event.traverse(,  {  'headliner' })
person.traverse(,  -> { where( nil) })

Like a missing property in Cypher, an edge kept in a table without the filter's columns doesn't match it, so a union edge is narrowed to the parts that have the column. SQL edges match no filter.

Starting elsewhere

GraphQuery.from(Venue.where( 'bar'))                 # any relation, record or model
GraphQuery.from_pairs([[Venue, venue_id], ['Person', person_id]])   # nodes of several models at once
GraphQuery.from_query(other_query)                        # the nodes another walk reached
Locale.where(...).graph                                   # a Query that hasn't moved yet; chain .out/.inbound

Errors

  • GraphQuery::NoEdges: the step names edges that don't leave the nodes it starts on (no has_venue (out) from Person), or its to: can't be reached. A step with depth: 0.. from nodes with no such edges isn't an error: it keeps the nodes it started on.
  • GraphQuery::AmbiguousResult: you asked for a relation, but the walk reaches several models. Name one, add to:, or use pairs / records / polymorphic.
  • ArgumentError: a bad depth: or direction:.

Results

A walk doesn't run until you ask for something. What you can ask for:

Method Gives
relation methods (where, order, pluck, count, each, find_each, exists?, ...) the reached nodes, as a relation (the walk must reach one model)
to_relation(Model) / nodes(Model) the reached nodes of one model, as a relation
with_depth(Model) that relation plus graph_depth, the fewest hops in the last step
pairs [[type, id], ...] for every node reached, whatever its model
records every node reached, loaded, whatever its model
polymorphic(scope, :name) rows of scope whose polymorphic association points at a reached node
by_origin(Model) {start id => [reached records]}
origin_pairs(Model) [[start id, reached id], ...], unloaded
paths every simple path, [[type, id], ...] from start to end
to_sql(origin:, depth:, path:) the statement
types the model names the walk can end on

Relations

When the last step reaches one model, a Query acts as a relation of it:

venues = washington.traverse(,  0..).traverse()
venues.where( 'bar').order().limit(10).to_a
venues.count
venues.pluck()
venues.includes().find_each { ... }

Under the hood that's Venue.where(id: <the walk>), so it composes with scopes, joins, merge and pagination. If the walk can reach several models, pick one: query.to_relation(Event).

Depth

with_depth joins the walk and selects each node's hop count in the last step as graph_depth:

seattle.traverse(,  1..).with_depth
       .reorder(Arel.sql('graph_query_nodes.depth DESC'))    # outermost first
       .pluck()

Order by graph_query_nodes.depth rather than graph_depth: the alias doesn't survive pluck.

Several models

walk = venue.traverse(,  1..)   # events and event series
walk.types     # => ["Event", "EventSeries"]
walk.pairs     # => [["Event", "4c1..."], ["EventSeries", "9ae..."], ...]
walk.records   # => [#<Event ...>, #<EventSeries ...>, ...] (one query per model)

Roll-ups: polymorphic

Given a scope of rows with a polymorphic association, keep those pointing at any node the walk reaches. This is how "everything linked to anything under this venue" works:

venue.traverse(,  0..)
     .polymorphic(EntityLink.where(), )   # target_type / target_id
     .order( )

The association's foreign_type / foreign_key are used if it's declared; otherwise name_type / name_id.

Batching many starts: by_origin

Walk from many nodes in one statement and group what each reached, for a GraphQL dataloader:

class LocalPeopleSource < GraphQL::Dataloader::Source
  def fetch(locale_ids)
    found = Locale.where( locale_ids).traverse(,  0..).traverse().by_origin(Person)
    locale_ids.map { found.fetch(it, []) }
  end
end

origin_pairs gives the same as [[locale_id, person_id], ...] without loading anything.

Paths

GraphQuery.from(person).traverse(,  1..3).paths
# => [[["Person", "a"], ["Person", "b"]], [["Person", "a"], ["Person", "b"], ["Person", "c"]], ...]

Paths never revisit a node. Rows are routes, not nodes, so their number can grow fast: use paths to show a route, not on big graphs.

SQL

query.to_sql                 # node_type, node_id
query.to_sql( true)   # + origin_type, origin_id (the start node each row came from)
query.to_sql( true)    # + depth (fewest hops in the last step)
query.to_sql( true)     # + path ('Type:id' text[])

Use it for EXPLAIN ANALYZE, or to join a walk by hand:

Event.joins("JOIN (#{walk.to_sql}) g ON g.node_type = 'Event' AND g.node_id = events.id")

Patterns

GraphQuery.match(pattern, **bindings) runs a linear Cypher-style pattern with Ruby bindings. For a whole Cypher query as text (MATCH ... WHERE ... RETURN), see Cypher queries. It builds the same steps as traverse, so everything about walks applies.

GraphQuery.match(
  '(s:Locale)-[:contains*0..]->()-[:has_venue]->(v:Venue)-[:hosts]->(e:Event)<-[:billed_on]-(p:Person)',
   Locale.where( 'Washington'),
   Event.upcoming
).nodes()   # venues in Washington where someone is billed on an upcoming event

From a scope, the scope binds the first node:

Locale.where( 'Seattle').graph_match('(l)-[:contains*0..]->()-[:has_venue]->(v:Venue)')

Syntax

Part Means
(v), (v:Venue), `(:Venue Event), ()`
(v:Venue {kind: 'bar', city: $city}) a node whose columns match a property map
-[:billed_on {role: 'headliner'}]-> edges whose rows match a property map
-[:has_venue]-> one hop out along has_venue
<-[:hosts]- one hop in (walk hosts backwards)
-[:knows]- one hop either way
`-[r:billed_on hosts]->`
-->, <--, -- any edge, one hop
* one or more hops
*2 exactly two
*1..3, *..3 one to three
*0.. zero or more (the node itself too)

Names may be written as in Cypher: CONTAINS and hasVenue match :contains and :has_venue. Labels are model names (event_series and EventSeries both work).

Bindings

There's no WHERE or RETURN text. Bind variables instead:

  • A node variable to a relation (or record, or model): the node must be in it. v: Venue.where(kind: 'bar').
  • A relationship variable to a Hash or scope Proc: an edge_where: on that step. GraphQuery.match('(e:Event)<-[b:billed_on]-(p:Person)', e: event, b: { role: 'headliner' }).

Property maps do the same job inline. Their values are literals ('text', 42, 1.5, true, null, [...]) or $params, read from params::

GraphQuery.match("(s:Locale {name: $state})-[:contains*0..]->()-[:has_venue]->(v:Venue {kind: 'bar'})",
                  {  'Washington' })

A node with a property map needs one label or a binding, so graph_query knows which table the columns are in.

The first node must be bound or have exactly one label ((s:Locale) alone starts from every locale).

Results

A Match acts as a relation of the last node's matches, like a Query. For another node, use nodes(:var):

match = GraphQuery.match('(s:Locale)-[:contains*0..]->(l)-[:has_venue]->(v:Venue)',  washington,
                          Venue.where( 'bar'))
match.count          # bars
match.nodes()      # only the locales that have a bar under them
match.paths          # each full route
match.query          # the underlying GraphQuery::Query

A variable in the middle counts only nodes that lie on a full match: graph_query walks forward to that node, walks back from the end of every full match to it, and keeps the overlap.

Beyond one path

More than one path, WHERE, RETURN, ORDER BY, SKIP and LIMIT: Cypher queries take those. For anything else, chain traverse steps or use from_query to start a second walk from the first one's result.

Cypher queries

GraphQuery.cypher(query, **params) runs a read-only Cypher query on the same walker as traverse: no Apache AGE, no extension, one WITH RECURSIVE per path.

GraphQuery.cypher(<<~CYPHER, state: 'Washington', limit: 10)
  MATCH (s:Locale {name: $state})-[:contains*0..]->(c:Locale)-[:has_venue]->(v:Venue)
  WHERE c.kind = 'city' AND v.name STARTS WITH 'The' AND NOT v.closed
  RETURN v
  ORDER BY v.name
  LIMIT $limit
CYPHER
# => a Venue relation, still chainable

Clauses

Clause Takes
MATCH one or more patterns, comma-separated or in several MATCH clauses
WHERE conditions on node properties (after any MATCH; several are ANDed)
RETURN v, v.name, v.kind (with optional AS), count(*), count(v), count(DISTINCT v); DISTINCT
ORDER BY v.name, toLower(v.name) DESC, several
SKIP, LIMIT a whole number or a $param

Labels are model names; relationship types are edge names (HAS_VENUE and hasVenue both match :has_venue). Properties are the model's columns. Keywords are case-insensitive, // starts a comment, and a trailing ; is fine.

WHERE

Condition SQL
v.x = 1, <>, !=, <, <=, >, >= comparisons (= null is IS NULL)
v.x IS NULL, v.x IS NOT NULL null tests
v.x IN ['a', 'b'], v.x NOT IN $list IN
v.x STARTS WITH 'a', ENDS WITH, CONTAINS LIKE, with % and _ escaped
v.x =~ 'Sea.*' a PostgreSQL regular expression on the whole value
toLower(v.x) = 'bar', toUpper(...) LOWER() / UPPER()
v.open v.open = true
v.x = v.y two columns of the same node
AND, OR, XOR, NOT, ( ... ) as written

Each condition is about one variable. graph_query turns each variable's conditions into a relation and walks through it, so conditions on nodes in the middle of a path narrow the walk as it goes:

MATCH (s:Locale)-[:contains*0..]->(c:Locale)-[:has_venue]->(v:Venue)
WHERE s.name = 'USA' AND c.kind = 'city' AND (v.name STARTS WITH 'E' OR v.name ENDS WITH 'sh')
RETURN v

A condition comparing two variables (a.name = b.name) raises GraphQuery::UnsupportedCypher.

RETURN

RETURN Gives
v a relation of v's nodes (lazy, chainable)
v.name pluck(:name): ['Eagle', 'Globe']
v.name, v.kind pluck(:name, :kind): [['Eagle', 'bar'], ...]
DISTINCT v.kind distinct values
count(*), count(v), count(DISTINCT v) an Integer: how many distinct nodes

Return one variable. A walk finds the nodes that can be reached, not every combination of nodes along the way, so RETURN a, b raises UnsupportedCypher; return one and walk again from it if you need the other.

Several patterns

Patterns that share a variable are joined on it:

MATCH (p:Person)-[:billed_on]->(e:Event), (v:Venue)-[:hosts]->(e)
MATCH (:Locale {name: 'Oregon'})-[:contains*0..]->()-[:has_venue]->(v)
RETURN e

Each pattern narrows the shared variables to the nodes it can match, and the narrowing repeats once per pattern so it carries through chains of patterns. This is exact when the patterns form a tree (joined one variable at a time). When two patterns share two variables, each variable is narrowed on its own, so a pair that matches separately but not together still passes.

Parameters

$name reads the keyword arguments: in property maps, WHERE, IN, SKIP and LIMIT. Values are always passed to SQL as quoted values, never as SQL text. A missing parameter raises GraphQuery::PatternError.

Not supported

Writing clauses (CREATE, MERGE, SET, DELETE), OPTIONAL MATCH, WITH, UNWIND, UNION, aggregation other than count, path variables (p = (a)-->(b)), and returning several variables. Each raises a PatternError or UnsupportedCypher that names what it met.

If a database has Apache AGE, GraphQuery::Age.cypher passes full Cypher through to it (see How it runs).

Writing edges

The edges you declare to read the graph can also write it. GraphQuery.transaction opens one database transaction and gives you a GraphQuery::Transaction that links and unlinks by edge name:

GraphQuery.transaction do |graph|
  hill = graph.create(Locale,  'Capitol Hill')
  graph.link(seattle, , hill)                                   # sets locales.parent_id
  graph.link(northwest, , hill,  LocaleGrouping,            # creates a join row
                                          {  'core' })
  graph.relink(hill, , eagle,  downtown)                  # moves the venue
  graph.unlink(seattle, , closed_bar)
end

Where a write lands

An edge is written where it's kept:

The edge is kept link unlink
on the target's row (has_many, has_one) sets the target's foreign key clears it
on the source's row (belongs_to) sets the source's foreign key clears it
in a join model (has_many :through, through:) creates a join row with the edge's Hash where: conditions and attributes: destroys the matching rows

Linking an edge that's already there, or unlinking one that isn't, changes nothing. SQL and computed edges can't be written.

When several edges share a name between the same two models (a has_many and a join model, say), pass via: with the model that holds the one you mean. Without it the transaction raises GraphQuery::AmbiguousResult.

Methods

Method
link(from, name, to, via: nil, attributes: {}) add the edge
unlink(from, name, to, via: nil) remove it
relink(new_from, name, to, from:, via: nil, attributes: {}) unlink from from:, link from new_from
linked?(from, name, to, via: nil) whether the edge is there
create(model, **attributes), update(record, **attributes), destroy(record) write nodes in the same transaction
changes what was written, in order: Change(action, edge, from, to, record)

Rows are saved with save! and destroy!, so validations and callbacks run. Any exception rolls every write back. GraphQuery.transaction nests inside an outer transaction as a savepoint.

Graph mutations

A graph mutation is a model method that writes the graph, marked so that it runs in a transaction and can be exposed to GraphQL. Put graph_mutation on the line before the def:

class Locale < ApplicationRecord
  graph_mutation  {  Locale,  String },  'Make child a member of this locale.'
  def adopt(child:,  nil, )
    graph.link(self, , child,  LocaleGrouping,  {  })
    self
  end

  graph_mutation def close = update!( Time.current) && self   # or in front of it, with no options

  graph_mutation  {  [Venue] },  Venue
  def take_venues(venues:, )
    venues.each { graph.relink(self, , it,  it.locale) }
    venues.first
  end
end

northwest.adopt( seattle)       # runs in GraphQuery.transaction; graph: is filled in
Locale.graph_mutations                # => { adopt: #<GraphQuery::Mutation Locale#adopt>, take_venues: ... }
  • The method runs inside GraphQuery.transaction. If it takes a graph: keyword, it's given the transaction.
  • arguments: types each keyword for GraphQL. A model takes an ID, [Model] takes a list of IDs, and String, Integer, Float, :boolean, :id, :json, Date, Time or a GraphQL type pass straight through. Required keywords become required arguments.
  • returns: types the result. The default is the model.
  • Models may be given as classes or as names ('Venue'); a name avoids loading a model the class body can't see yet.
  • Calling the method from Ruby works the same way, so the same write path backs a console, a job and the API.

See GraphQL for turning these into mutation fields.

GraphQL

require 'graph_query/graphql' adds graphql-ruby support (graphql 2.3 or later; the gem doesn't depend on it otherwise). Declared edges back fields, and graph mutations back mutation fields.

Fields backed by walks

Extend an object type with GraphQuery::GraphQL::Fields, then declare fields by edge, pattern or block:

class Types::LocaleType < Types::BaseObject
  extend GraphQuery::GraphQL::Fields

  graph_field , [Types::LocaleType],                         # one hop
  graph_field , [Types::VenueType],  %i[contains has_venue],  0.. # contains*0.. then has_venue
  graph_field , Types::VenueType.connection_type,                              # paginated
               '()-[:contains*0..]->()-[:has_venue]->(v:Venue)',
               ->(venues, context) { venues.where( 'bar').order() }
  graph_field(, [Types::EventType]) do |start|                               # anything a Query can do
    start.traverse(,  0..).traverse().traverse(,  {  false })
  end
end
Option
edge: an edge name, or several walked in turn (depth: and the other walk options apply to all but the last)
pattern: a pattern whose first node is the object; the field returns the last node
a block given GraphQuery.from(object), returns a Query
depth:, direction:, to:, through:, edge_where: as in walking
scope: ->(relation, context) to filter, order or authorize the result
model: the result's model, when the walk can reach several

A list field is batched. graph_query loads it through GraphQL::Dataloader, so 50 locales asking for their venues run one walk from all 50 (with origin_pairs) and one load, not 50 of each. Add use GraphQL::Dataloader to the schema. A connection field returns a relation per object, so graphql-ruby paginates it in SQL.

A field per declared edge

graph_edges adds a list field for every edge a model declares, one hop out:

class Types::LocaleType < Types::BaseObject
  extend GraphQuery::GraphQL::Fields
  graph_edges Locale,  %i[within rolls_up]   # within: [LocaleType], rolls_up_venues, rolls_up_events ...
end

A field is named after its edge, or edge_targets when one edge name reaches several models. except: leaves edges out, and scope: applies to every field.

Types are found by model name through GraphQuery::GraphQL.type_for. The default returns "Types::<Model>Type", which graphql-ruby resolves lazily, so a type can list edges back to itself. Set your own when the types are named differently:

GraphQuery::GraphQL.type_for = ->(model_name) { "Types::#{model_name}Object" }

Mutations from graph mutations

Extend the mutation type with GraphQuery::GraphQL::MutationFields and name the models:

class Types::MutationType < Types::BaseObject
  extend GraphQuery::GraphQL::MutationFields
  graph_mutations Locale, Venue                  # localeAdopt, localeTakeVenues, ...
end

Each graph mutation becomes a Relay-style mutation named <model>_<method>:

mutation {
  localeAdopt(input: { id: "...", childId: "...", role: "core" }) { result { name } errors }
}
  • id finds the record to call the method on. Model arguments become childId / venueIds and are loaded through GraphQuery::GraphQL.record_for. By default that's the schema's object_from_id, falling back to Model.find.
  • result is what the method returns, typed by returns:. errors lists messages.
  • The whole mutation runs in one transaction. A validation failure, a GraphQuery::Error or a returned errors rolls it back and comes back in errors.
  • only: and except: pick methods, and base: sets the mutation base class.

Other mutations

For a mutation written by hand, include GraphQuery::GraphQL::TransactionalMutation. resolve then runs in one transaction with graph open:

class Mutations::MoveVenue < Types::BaseMutation
  include GraphQuery::GraphQL::TransactionalMutation
  argument , ID
  argument , ID
  field , Types::VenueType
  field , [String],  false

  def resolve(venue_id:, )
    venue = Venue.find(venue_id)
    graph.relink(Locale.find(locale_id), , venue,  venue.locale)
    {  venue.reload,  [] }
  end
end

Without an errors field, failures are raised as GraphQL::ExecutionError.

To link or unlink one edge by ID, edge_mutation builds the whole class:

field ,  GraphQuery::GraphQL.edge_mutation(Locale, , Venue)
field ,  GraphQuery::GraphQL.edge_mutation(Locale, , Venue,  )
# addVenue(input: { fromId: "...", toId: "..." }) { changed from { name } to { name } errors }

Authorize these the way you authorize any graphql-ruby mutation (ready?, authorized?, or the base class you pass as base:).

How it runs

One statement per walk

Each walk compiles to one WITH RECURSIVE statement. Node sets are CTEs: g0 is the start, gN the nodes after step N, each with columns (node_type, node_id) plus whatever the result needs (origin_type/origin_id, depth, path).

This walk:

Locale.where( 'Seattle').traverse(,  0..).traverse()

compiles to (reformatted):

WITH RECURSIVE
g0 AS (
  SELECT DISTINCT node_type, node_id FROM (
    SELECT 'Locale'::text AS node_type, start_rows."id" AS node_id
    FROM (SELECT "locales"."id" FROM "locales" WHERE "locales"."name" = 'Seattle') start_rows
  ) graph_query_start),
g1_walk(node_type, node_id) AS (
  SELECT p.node_type, p.node_id FROM g0 p
  UNION
  SELECT e.to_type, e.to_id FROM g1_walk w
  CROSS JOIN LATERAL (
    (SELECT 'Locale'::text AS from_type, edge_rows.source_id AS from_id,
            'Locale'::text AS to_type,   edge_rows.target_id AS to_id
     FROM (SELECT parent_id AS source_id, id AS target_id FROM locales
           WHERE parent_id IS NOT NULL AND id IS NOT NULL) edge_rows
     WHERE edge_rows.source_id = w.node_id AND w.node_type = 'Locale')
    UNION ALL
    (SELECT 'Locale', edge_rows.source_id, 'Locale', edge_rows.target_id
     FROM (SELECT super_locale_id AS source_id, member_locale_id AS target_id FROM locale_groupings
           WHERE super_locale_id IS NOT NULL AND member_locale_id IS NOT NULL) edge_rows
     WHERE edge_rows.source_id = w.node_id AND w.node_type = 'Locale')
  ) e),
g1(node_type, node_id) AS (SELECT DISTINCT * FROM g1_walk x),
g2(node_type, node_id) AS (
  SELECT DISTINCT * FROM (
    SELECT e.to_type, e.to_id FROM g1 p
    CROSS JOIN LATERAL (
      (SELECT 'Locale', edge_rows.source_id, 'Person', edge_rows.target_id
       FROM (SELECT locale_id AS source_id, person_id AS target_id FROM person_locales
             WHERE locale_id IS NOT NULL AND person_id IS NOT NULL) edge_rows
       WHERE edge_rows.source_id = p.node_id AND p.node_type = 'Locale')
    ) e) x)
SELECT * FROM g2

Step shapes

The compiler picks the cheapest shape a step allows:

Step Shape
no edge to follow, depth: 0.. keep the nodes it started on
depth: 1 or 0..1 one join
depth: 1.. or 0.. a recursive set with UNION: it ends when nothing new turns up, so cycles end it
depth: 1..3, 2.., or anything needing with_depth a hop count on each row, stopping at the bound (or max_depth), then grouped to the fewest hops
paths UNION ALL of routes, each carrying a text[] of 'Type:id' and refusing to revisit a node

Why LATERAL

Each hop joins the edges through CROSS JOIN LATERAL, with the source_id = node_id condition inside each branch of the edge union. That lets PostgreSQL read each edge table through its index on the column that points back, one row of the frontier at a time, instead of scanning and hashing whole tables on every iteration. On a 200,000-locale tree, a subtree walk went from 62 ms to 8 ms with this change. Index the foreign key columns your edges read (Rails does for references).

Which edges a step uses

Before compiling, a step works out which edges it may follow: those leaving the models it starts on and, for a multi-hop step, those leaving every model it can reach, until no new model turns up. A step over :rolls_up from a Locale therefore also follows Venue's and EventSeries' :rolls_up edges. Only those edges' tables appear in the SQL.

Limits

  • Node ids share a type within a walk (all uuid, or all bigint).
  • max_depth (32) caps unbounded steps that count hops. Plain closures (0.., 1..) have no cap; cycles end them.
  • paths grows with the number of routes, not nodes.
  • No branching patterns. Chain steps or start a second walk with from_query.
  • SQL edges don't take edge_where:, and only use indexes if the planner can push the condition into them.

Apache AGE

Where a database has Apache AGE, GraphQuery::Age passes real Cypher through:

GraphQuery::Age.available?   # => false on Heroku Postgres
GraphQuery::Age.cypher('my_graph', 'MATCH (a)-[:KNOWS]->(b) RETURN a, b',  %w[a b])

It's a pass-through for databases that have it, not a second engine: everything else in graph_query runs on the CTE walker, which is also why GraphQuery.cypher works on Heroku Postgres, RDS and anywhere else without AGE.

Tests

The behaviour is written as shared examples (spec/support/graph_query_examples.rb) over a small graph in gq_ tables, so an app can run the same examples against its own database. On their own:

createdb graph_query_test
GRAPH_QUERY_DATABASE_URL=postgres:///graph_query_test bundle exec rake

rake runs the specs, RuboCop and rbs validate.

Reference

On every model

Method
graph_edge(name, association:) an edge from an association
graph_edge(name, to:, through:, source:, target:) an edge from a join model's columns
graph_edge(name, to:, sql:) an edge from SQL selecting source_id, target_id
graph_edge(name, to:, computed: -> { ... }), graph_edge(name, to:) { ... } an edge from a relation or SQL built per query
... where: a Hash or scope Proc the edge's rows must match
Model.traverse(names = nil, **options) a Query from the current scope
Model.graph a Query from the current scope, no steps yet
Model.graph_match(pattern, params: {}, **bindings) a Match whose first node is the current scope
record.traverse(...), record.graph the same from one record
graph_mutation(name = nil, arguments: {}, returns: nil, description: nil) mark a method as a graph mutation
Model.graph_mutations the model's graph mutations, by name

to:, through: and via: take a model class or its name.

GraphQuery

Method
GraphQuery.from(scope) a Query from a relation, record or model
GraphQuery.from_pairs(pairs) a Query from [[type, id], ...] of any models
GraphQuery.from_query(query) a Query from the nodes another one reaches
GraphQuery.match(pattern, params: {}, **bindings) a Match
GraphQuery.cypher(query, **params) a relation, pluck rows or a count (see Cypher queries)
GraphQuery.transaction { |graph| ... } a Transaction in one database transaction
GraphQuery.max_depth, max_depth= the hop cap for counted unbounded steps (32)
GraphQuery.registry.all every declared edge

GraphQuery::Query

Method
traverse(names = nil, depth: 1, direction: :out, to: nil, where: nil, through: nil, edge_where: nil) add a step
out(names, **), inbound(names, **), both(names, **) a step with the direction fixed
types model names the walk can end on
to_relation(model = nil), nodes reached nodes as a relation
with_depth(model = nil) that relation with graph_depth
pairs, records every reached node, any model
by_origin(model = nil), origin_pairs(model = nil) reached nodes grouped by start node
polymorphic(scope, name) rows of scope whose polymorphic name points at a reached node
paths every simple path
to_sql(origin: false, depth: false, path: false) the statement
relation methods delegated to to_relation when the walk reaches one model

GraphQuery::Match

Method
nodes(var = nil, model: nil) a node variable's matches (default: the last node)
paths every full match's path
query(upto = all) the Query for the pattern (up to a node index)
relation methods delegated to nodes

GraphQuery::Cypher

Method
Cypher.new(query, params = {}) parse a query (raises on bad syntax)
result what GraphQuery.cypher returns
nodes(:var) any node variable's matches, as a relation
patterns, items, orders, skip, limit, distinct the parsed query

GraphQuery::Transaction

Method
link(from, name, to, via: nil, attributes: {}) add an edge (the written record, or nil if it was already there)
unlink(from, name, to, via: nil) remove an edge
relink(new_from, name, to, from:, via: nil, attributes: {}) move an edge to a new source
linked?(from, name, to, via: nil) whether an edge is there
create, update, destroy write nodes
changes every write, in order

GraphQuery::GraphQL

Loaded with require 'graph_query/graphql'.

Method
Fields#graph_field(name, type, edge: | pattern: | &block, scope:, model:, depth:, ...) a field backed by a walk, batched
Fields#graph_edges(model, only:, except:, scope:, type_for:) a field per declared edge
MutationFields#graph_mutations(*models, only:, except:, base:) a mutation field per graph mutation
TransactionalMutation include in a mutation: resolve runs in a transaction with graph
GraphQuery::GraphQL.edge_mutation(from_model, name, to_model, action: :link, via:, graphql_name:, base:) a mutation that links or unlinks one edge by ID
GraphQuery::GraphQL.type_for, type_for= model name to GraphQL type (default "Types::<Model>Type")
GraphQuery::GraphQL.record_for, record_for= (model, id, context) to a record

Errors

All inherit from GraphQuery::Error.

Error When
GraphQuery::NoEdges a step names edges that don't leave its nodes, or can never reach its to:
GraphQuery::AmbiguousResult a relation was asked of a walk that reaches several models
GraphQuery::PatternError a pattern or query can't be read, binds an unknown variable, misses a $param, or has an unbound, unlabelled first node
GraphQuery::UnsupportedCypher Cypher that reads fine but asks for what graph_query doesn't do (two variables in one condition, RETURN a, b, OPTIONAL MATCH)

Types

The gem ships signatures for both type checkers:

  • RBS in sig/graph_query.rbs. Steep and other RBS tools find it in the installed gem; Active Record's own types come from gem_rbs_collection (rbs collection install).
  • Sorbet in rbi/graph_query.rbi. bin/tapioca gem graph_query copies it into sorbet/rbi/gems.

Both describe graph_edge, graph_mutation, traverse, graph and graph_match on every model, and Query, Match, Cypher, Pattern, Edge, Transaction, Mutation and the errors. The GraphQL module isn't typed: graphql-ruby's class DSL has no signatures to build on.