Diagnostic GitHub API
A nested GraphQL query requests more than 500,000 nodes
The query worked all week against the test org, which has four repositories. Pointed at the real one it comes back rejected with MAX_NODE_LIMIT_EXCEEDED before a single row is read. The instinct is that the org is too big, so somebody reduces the date range and it fails identically, because the limit was never about how much data exists. It is about the numbers written in the query, and those did not change.
GitHub caps a single GraphQL query at 500,000 nodes, and the count is computed from the first and last values you requested, multiplied down through the nesting. One hundred repositories, each with one hundred pull requests, each with one hundred comments is 100 + 10,000 + 1,000,000, which is 1,010,100 nodes and over the cap. The query is rejected before execution, so a small organisation fails exactly as fast as a large one.
The repair is arithmetic rather than filtering. Lower the first values at the deepest levels, where the multiplier is largest, and page those connections separately with pageInfo { hasNextPage endCursor }. Because the whole calculation depends only on the query text, you can do it without sending anything: this is the one check in the section that needs no token and spends no points.
The problem in plain words
The query gets built by a reasonable process. Someone needs repositories, their pull requests and the comments on those pull requests, and writing that as one GraphQL document instead of ten thousand REST calls is exactly the right instinct. Then first: 100 goes on every connection, because 100 is the maximum and asking for the maximum means fewer round trips, which is the lesson everybody learned from the REST pagination bugs. Both decisions are individually correct and together they are a million nodes.
It passes review for the same reason. Nothing in the document looks large; it is about fifteen lines and every number in it is 100. The multiplication that makes it enormous happens nowhere on the screen, and there is no linter watching for it, so the query goes to production with the same confidence as any other.
The failure then misleads on arrival. Everything about the error says "too much data" and the org is the biggest thing in sight, so the fix people reach for is a narrower filter: a date range, a label, an archived-repository exclusion. None of it helps, because the cost is derived from what the query asks for rather than from what exists, and the numbers being asked for are still 100. Watching four consecutive narrower filters fail identically is the part that eats the afternoon.
Why it happens
The count multiplies, it does not add. Each connection contributes the product of its own first and every first above it. Three levels of 100 is 100 + (100 × 100) + (100 × 100 × 100), so the deepest level supplies 99 per cent of the total on its own. That is also why the repair is aimed at the bottom of the query: halving the outermost number halves everything, but lowering the innermost one is where the cheap wins are.
It is computed from the request, not the response. A limit derived from what exists could be discovered by trying. This one is derived from the document, which is why the same query fails against an organisation with four repositories and against one with four thousand. It also means the whole thing can be decided statically, before anything is sent, which is what this script does.
Rejection happens before execution, so it costs nothing and teaches nothing. There is no partial result and no indication of which connection was responsible. The error names the limit and stops. If you want the actual number, ask for rateLimit { nodeCount cost } in a query small enough to run, and the server will report the computed node total for that call.
It is not the point budget. Points measure what a query costs against an hourly allowance and running out of them is a different failure with a different error type: it clears on its own, and the same query will succeed later. A node-limit rejection never clears. Nothing about waiting, retrying or having more quota changes it, because the query itself is the thing that is too large, and a retry loop that does not know the difference will spin against it until the point budget is gone as well.
The static count has two honest blind spots. A first supplied as a variable cannot be evaluated without the variables, so the script asks for them rather than guessing. And a named fragment spread hides part of the selection set from a text-level analyser, so the computed total is a lower bound when one is present. Both are reported as caveats rather than quietly rolled into the number.
A connection with no first at all is a separate error. GitHub requires a slicing argument on connections, so leaving one off is rejected too, with a different message. That is a schema problem rather than a size problem and this script does not attempt to diagnose it; the node count it reports simply does not include a connection it could not see a number for.
The fix, as a flow
No token, no request, no points. The node count is a function of the query text, so the document is stripped of comments and strings, walked once with a stack of multipliers, and every connection carrying a first or a last contributes the product of its own value and every value above it. That total is the number the server computes, which is why the check can be run in CI over a directory of query files. The script then solves for the largest slice the deepest connection could take and still fit, so the repair is a specific number in a specific place rather than an instruction to make the query smaller.
How to fix it
Compute the node count before you send anything
Feed the query text to the checker. It walks the document, multiplies each connection's first by the product of everything above it, and prints the total against the 500,000 cap. No token, no request, no points. This runs in CI on a file of queries as easily as it runs on one.
Look at where the nodes actually are
The per-connection breakdown almost always shows one line carrying the overwhelming majority. In the three-level example the comments connection is 1,000,000 of the 1,010,100. Knowing that turns a vague "make the query smaller" into a specific number to change in a specific place.
Take the suggested value at the deepest level
The script solves for the largest first at the deepest connection that brings the total under the cap and prints it. For the example that is 48. It is a starting point rather than a target: a smaller number leaves headroom for the day somebody adds another level.
Page the connection you shrank
Reducing a first only helps if the rest of the data is still reachable, so add pageInfo { hasNextPage endCursor } to the connection you shrank and follow the cursor. One hundred repositories with ten pull requests each, paging the pull requests, reads the same data as one hundred by one hundred and stays comfortably inside the limit.
Confirm against the server only if you want to
--confirm sends the document and reports whether GitHub agrees, either by rejecting it or by returning rateLimit { nodeCount } if the document asks for it. That costs one point and the script says so first. It is not required: the arithmetic is the same arithmetic the server does.
How to check it worked
The check runs on a file in CI, with no token, and the repair is a number rather than an instruction.
python3 github_graphql_nodes.py --file queries/org_activity.graphql
# point cost: 0 point(s). The node count is computed from the query text and
# nothing is sent.
# node count: 1,010,100 against a limit of 500,000
# repositories first=100 depth 3 ancestors x1 100 nodes
# pullRequests first=100 depth 5 ancestors x100 10,000 nodes
# comments first=100 depth 7 ancestors x10,000 1,000,000 nodes
# over-node-limit: 1,010,100 nodes is 202% of the 500,000 cap, so this query is
# rejected before it runs whatever the organisation contains
# repair: lower first on comments from 100 to 48 and paginate it separately
# with pageInfo { hasNextPage endCursor }
# after the change
# node count: 490,100 against a limit of 500,000
# near-node-limit: 98% of the cap, which leaves no room for another levelThe full code
A parser and some multiplication. The document is stripped of comments and string literals, walked once while a stack of multipliers is maintained, and every connection carrying a first or last contributes the product of that value and everything above it. The total, the per-connection breakdown and the largest value the deepest connection could take are all pure functions of the text, so the default run opens no socket and needs no credential. Confirming against the server is one opt-in point, announced before it is spent.
"""Compute a GraphQL query's node count from its text, before sending it.
Read only, and by default not even that: the node count is derived from the
query document, so the standard run makes no request, needs no token and spends
no points. The optional --confirm sends the document once and costs one point.
Queries only. GitHub's GraphQL endpoint takes a document in the request body, so
a read is carried by POST there just as a write would be; that is transport, not
intent. Any document containing a mutation or a subscription is refused before a
socket opens. Nothing is written and the repair is printed rather than performed.
GitHub caps one query at 500,000 nodes and computes the count from the first and
last values you requested, multiplied down through the nesting. Three levels of
first: 100 is 100 + 10,000 + 1,000,000 nodes. Because the cost comes from the
request rather than from what exists, a four-repository organisation fails
exactly as a four-thousand-repository one does.
What this can and cannot see: a first supplied as a variable cannot be evaluated
without the variables, and a named fragment spread hides part of the selection
set from a text-level analyser. Both are reported as caveats rather than folded
silently into the number.
"""
import argparse
import json
import logging
import os
import re
import sys
logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
log = logging.getLogger("github_graphql_nodes")
API = "https://api.github.com"
UA = "github-graphql-nodes/1.0"
# The documented ceiling on one query. Named because it is printed and a reader
# checking this against the documentation should find it in one place.
NODE_LIMIT = 500_000
# Above this fraction of the cap, say so: a query at 98 per cent is one schema
# change away from being rejected.
NEAR = 0.8
# The canonical shape of the problem, used when no document is supplied.
DEMO_QUERY = """query {
organization(login: "acme") {
repositories(first: 100) {
nodes {
pullRequests(first: 100) {
nodes {
comments(first: 100) { nodes { id } }
}
}
}
}
}
}"""
PAGING = re.compile(r"\b(first|last)\s*:\s*(\$?[A-Za-z0-9_]+)")
SPREAD = re.compile(r"\.\.\.\s*([A-Za-z_][A-Za-z0-9_]*)")
def strip_noise(document):
"""Remove GraphQL comments and string literals from a document. Pure."""
src = str(document or "")
out = []
i, n = 0, len(src)
while i < n:
ch = src[i]
if ch == "#":
while i < n and src[i] != "\n":
i += 1
continue
if src.startswith('"""', i):
j = src.find('"""', i + 3)
i = n if j < 0 else j + 3
out.append(" ")
continue
if ch == '"':
i += 1
while i < n and src[i] != '"':
i += 2 if src[i] == "\\" else 1
i += 1
out.append(" ")
continue
out.append(ch)
i += 1
return "".join(out)
def operations(document):
"""The top-level operations in a document, in order. Pure."""
src = strip_noise(document)
ops, depth, word, declared = [], 0, "", None
for ch in src + " ":
if ch.isalnum() or ch == "_":
word += ch
continue
if word:
if depth == 0 and word in ("query", "mutation", "subscription", "fragment"):
declared = word
word = ""
if ch == "{":
if depth == 0:
ops.append(declared or "query")
declared = None
depth += 1
elif ch == "}":
depth = max(0, depth - 1)
return ops
def refusal(document):
"""Why this document will not be sent, or None if it is a read. Pure."""
ops = operations(document)
if not ops:
return "the document contains no operation to send."
for kind in ("mutation", "subscription"):
if kind in ops:
return ("the document contains a %s. This script sends queries only: "
"a query is a read, and the section it belongs to promises "
"its scripts never write." % kind)
return None
def commas(n):
"""Group a count in thousands so it can be read at a glance. Pure."""
try:
return "{:,}".format(int(n))
except (TypeError, ValueError):
return str(n)
def _paging(field, args, variables):
"""The slicing argument on one field, if there is one. Pure."""
m = PAGING.search(args or "")
if not m:
return None
arg, raw = m.group(1), m.group(2)
variable = raw[1:] if raw.startswith("$") else None
value = (variables or {}).get(variable) if variable else raw
try:
requested = int(value)
except (TypeError, ValueError):
requested = None
return {"field": field or "?", "arg": arg, "variable": variable,
"requested": requested}
def connections(document, variables=None):
"""Every sliced connection in a document, with its node contribution. Pure.
Walks the text once with a stack of multipliers. A connection contributes
the product of its own first/last and every one enclosing it, which is the
rule the server applies and the reason a three-level query is a million
nodes rather than three hundred.
"""
src = strip_noise(document)
out, stack, pending, field = [], [], None, None
i, n = 0, len(src)
while i < n:
ch = src[i]
if ch == "(":
j = src.find(")", i)
args = src[i + 1:j] if j >= 0 else src[i + 1:]
found = _paging(field, args, variables)
# Only overwrite a pending slice when this argument group carries one,
# so a directive such as @include(if: $x) cannot erase the first:
# value that came immediately before it.
if found is not None:
pending = found
i = n if j < 0 else j + 1
continue
if ch == "{":
if pending is not None:
ancestors = 1
for m in stack:
ancestors *= m
rec = dict(pending)
rec["depth"] = len(stack) + 1
rec["ancestors"] = ancestors
rec["nodes"] = (None if rec["requested"] is None
else ancestors * rec["requested"])
out.append(rec)
stack.append(rec["requested"] if rec["requested"] else 1)
else:
stack.append(1)
pending, field = None, None
i += 1
continue
if ch == "}":
if stack:
stack.pop()
pending, field = None, None
i += 1
continue
if ch.isalpha() or ch == "_":
j = i
while j < n and (src[j].isalnum() or src[j] == "_"):
j += 1
field = src[i:j]
i = j
continue
i += 1
return out
def node_count(document, variables=None):
"""The node total the server will compute for this document. Pure."""
return sum(c["nodes"] for c in connections(document, variables)
if c["nodes"] is not None)
def unresolved(document, variables=None):
"""Connections whose slice is a variable nobody supplied. Pure."""
return [c["field"] for c in connections(document, variables)
if c["requested"] is None]
def fragment_spreads(document):
"""Named fragment spreads, which hide part of the selection set. Pure."""
src = strip_noise(document)
return sorted({m.group(1) for m in SPREAD.finditer(src) if m.group(1) != "on"})
def caveats(document, variables=None):
"""Everything that makes the computed total less than certain. Pure."""
out = []
missing = unresolved(document, variables)
if missing:
out.append("the slice on %s is a variable this run has no value for, so "
"those connections are not in the total. Pass --variables."
% ", ".join(sorted(set(missing))))
spreads = fragment_spreads(document)
if spreads:
out.append("the document spreads the fragment(s) %s, whose selection set "
"this text-level check does not expand, so the total is a "
"lower bound." % ", ".join(spreads))
return out
def deepest(document, variables=None):
"""The connection carrying the largest multiplier. Pure. None if there is none."""
resolved = [c for c in connections(document, variables) if c["nodes"] is not None]
if not resolved:
return None
return max(resolved, key=lambda c: (c["depth"], c["nodes"]))
def reshape(document, variables=None, limit=NODE_LIMIT):
"""The largest slice the deepest connection could take. Pure.
Returns (field, current, suggested). suggested is None when even a slice of
one leaves the query over the cap, which means the shape itself has to
change rather than a number in it.
"""
d = deepest(document, variables)
if d is None:
return (None, None, None)
total = node_count(document, variables)
without = total - d["nodes"]
room = limit - without
if d["ancestors"] <= 0:
return (d["field"], d["requested"], None)
k = room // d["ancestors"]
if k < 1:
return (d["field"], d["requested"], None)
return (d["field"], d["requested"], int(min(k, 100)))
def exceeds(count, limit=NODE_LIMIT):
"""Whether this node total is over the cap. Pure."""
try:
return int(count) > int(limit)
except (TypeError, ValueError):
return False
def verdict(document, variables=None, limit=NODE_LIMIT):
"""Classify one document. Pure. Returns (state, detail)."""
conns = connections(document, variables)
if not conns:
return ("no-connections",
"this document slices no connections, so it has no node count "
"worth speaking of.")
if any(c["nodes"] is None for c in conns):
return ("unresolved-variables",
"at least one slice is a variable with no value supplied, so the "
"node count cannot be computed from the text alone.")
total = node_count(document, variables)
pct = round(100.0 * total / float(limit))
if exceeds(total, limit):
return ("over-node-limit",
"%s nodes is %d%% of the %s cap, so this query is rejected before "
"it runs whatever the organisation contains."
% (commas(total), pct, commas(limit)))
if total > limit * NEAR:
return ("near-node-limit",
"%s nodes is %d%% of the cap, which leaves no room for another "
"level." % (commas(total), pct))
return ("within-node-limit",
"%s nodes is %d%% of the cap." % (commas(total), pct))
def repair(state, field=None, current=None, suggested=None):
"""The sentence a reader has to act on. Pure."""
if state in ("over-node-limit", "near-node-limit"):
if suggested is not None:
return ("lower first on %s from %s to %d and paginate it separately "
"with pageInfo { hasNextPage endCursor }."
% (field, current, suggested))
return ("even a slice of one on %s leaves this query over the cap, so "
"split it into separate queries rather than tuning a number."
% field)
if state == "unresolved-variables":
return ("pass the variables with --variables so the slices can be "
"resolved. A slice you cannot evaluate is a slice you cannot "
"budget for.")
if state == "no-connections":
return "nothing. There is nothing here to multiply."
return "nothing on the node count."
def reported_node_count(body):
"""The node count the server computed, if the document asked for it. Pure."""
if not isinstance(body, dict):
return None
data = body.get("data")
if not isinstance(data, dict):
return None
rl = data.get("rateLimit")
if not isinstance(rl, dict):
return None
try:
return int(rl.get("nodeCount"))
except (TypeError, ValueError):
return None
def rejected_for_nodes(body):
"""Whether the server refused this document for its size. Pure."""
if not isinstance(body, dict):
return False
for err in body.get("errors") or []:
if isinstance(err, dict) and err.get("type") == "MAX_NODE_LIMIT_EXCEEDED":
return True
return False
def point_cost(confirm):
"""Points this run will spend. Pure. Zero unless --confirm is passed."""
return 1 if confirm else 0
def main():
ap = argparse.ArgumentParser(description=__doc__)
ap.add_argument("--file", help="read the query document from this file")
ap.add_argument("--query", help="the query document itself")
ap.add_argument("--variables", help="JSON object supplying the query's variables")
ap.add_argument("--confirm", action="store_true",
help="spend one point sending the document so the server can "
"agree or disagree")
args = ap.parse_args()
if args.file:
with open(args.file, "r", encoding="utf-8") as fh:
document = fh.read()
else:
document = args.query or DEMO_QUERY
try:
variables = json.loads(args.variables) if args.variables else {}
except ValueError:
log.error("--variables must be a JSON object")
return 2
why_not = refusal(document)
if why_not:
log.error("refusing to analyse and send: %s", why_not)
return 2
if args.confirm:
log.info("point cost: %d point(s) against the 5,000/hour GraphQL budget",
point_cost(True))
else:
log.info("point cost: %d point(s). The node count is computed from the "
"query text and nothing is sent.", point_cost(False))
conns = connections(document, variables)
total = node_count(document, variables)
log.info("node count: %s against a limit of %s", commas(total), commas(NODE_LIMIT))
for c in conns:
log.info(" %-16s %s=%-6s depth %-3d ancestors x%-8s %s nodes",
c["field"], c["arg"],
c["requested"] if c["requested"] is not None else "?",
c["depth"], commas(c["ancestors"]),
commas(c["nodes"]) if c["nodes"] is not None else "?")
state, detail = verdict(document, variables)
log.info("%s: %s", state, detail)
for c in caveats(document, variables):
log.info("caveat: %s", c)
field, current, suggested = reshape(document, variables)
log.info("repair: %s", repair(state, field, current, suggested))
server = {}
if args.confirm:
token = os.environ.get("GITHUB_TOKEN")
if not token:
log.error("--confirm needs GITHUB_TOKEN (a read-only token is enough)")
return 2
import requests
session = requests.Session()
session.headers.update({
"Authorization": "Bearer " + token,
"Accept": "application/vnd.github+json",
"User-Agent": UA,
})
# A GraphQL query is a read; POST is only how the document reaches the
# endpoint, which is why the verb sits here beside the URL rather than
# in a constant where it could be mistaken for a write path.
resp = session.post(API + "/graphql",
json={"query": document, "variables": variables},
timeout=30)
try:
body = resp.json()
except ValueError:
body = None
server = {"rejected": rejected_for_nodes(body),
"reported_node_count": reported_node_count(body)}
if server["rejected"]:
log.info("the server rejected the document for its node count, which "
"confirms the arithmetic above")
elif server["reported_node_count"] is not None:
log.info("the server computed %s node(s); this check computed %s",
commas(server["reported_node_count"]), commas(total))
else:
log.info("the server accepted the document and reported no node "
"count. Add rateLimit { nodeCount } to compare directly.")
print(json.dumps({
"points_spent": point_cost(args.confirm),
"node_count": total,
"node_limit": NODE_LIMIT,
"over_limit": exceeds(total),
"connections": conns,
"caveats": caveats(document, variables),
"deepest": deepest(document, variables),
"suggested": {"field": field, "current": current, "first": suggested},
"server": server,
"state": state,
"detail": detail,
}, indent=2, default=str))
return 1 if state in ("over-node-limit", "near-node-limit") else 0
if __name__ == "__main__":
sys.exit(main())
/**
* Compute a GraphQL query's node count from its text, before sending it.
*
* Read only, and by default not even that: the node count is derived from the
* query document, so the standard run makes no request, needs no token and
* spends no points. The optional confirm step sends the document once and
* costs one point.
*
* Queries only. GitHub's GraphQL endpoint takes a document in the request body,
* so a read is carried by POST there just as a write would be; that is
* transport, not intent. Any document containing a mutation or a subscription
* is refused before a socket opens.
*
* Environment:
* GITHUB_QUERY the query document itself
* GITHUB_VARIABLES JSON object supplying the query's variables
* GITHUB_CONFIRM set to spend one point asking the server to agree
* GITHUB_TOKEN only needed when confirming
*/
const API = 'https://api.github.com';
const UA = 'github-graphql-nodes/1.0';
/** The documented ceiling on one query. */
export const NODE_LIMIT = 500000;
/** Above this fraction of the cap, say so. */
export const NEAR = 0.8;
const DEMO_QUERY = `query {
organization(login: "acme") {
repositories(first: 100) {
nodes {
pullRequests(first: 100) {
nodes {
comments(first: 100) { nodes { id } }
}
}
}
}
}
}`;
const PAGING = /\b(first|last)\s*:\s*(\$?[A-Za-z0-9_]+)/;
const SPREAD = /\.\.\.\s*([A-Za-z_][A-Za-z0-9_]*)/g;
/** Remove GraphQL comments and string literals from a document. Pure. */
export function stripNoise(document) {
const src = String(document ?? '');
const out = [];
let i = 0;
while (i < src.length) {
const ch = src[i];
if (ch === '#') {
while (i < src.length && src[i] !== '\n') i += 1;
continue;
}
if (src.startsWith('"""', i)) {
const j = src.indexOf('"""', i + 3);
i = j < 0 ? src.length : j + 3;
out.push(' ');
continue;
}
if (ch === '"') {
i += 1;
while (i < src.length && src[i] !== '"') i += src[i] === '\\' ? 2 : 1;
i += 1;
out.push(' ');
continue;
}
out.push(ch);
i += 1;
}
return out.join('');
}
/** The top-level operations in a document, in order. Pure. */
export function operations(document) {
const src = `${stripNoise(document)} `;
const ops = [];
let depth = 0;
let word = '';
let declared = null;
for (const ch of src) {
if (/[A-Za-z0-9_]/.test(ch)) { word += ch; continue; }
if (word) {
if (depth === 0 && ['query', 'mutation', 'subscription', 'fragment'].includes(word)) {
declared = word;
}
word = '';
}
if (ch === '{') {
if (depth === 0) { ops.push(declared || 'query'); declared = null; }
depth += 1;
} else if (ch === '}') {
depth = Math.max(0, depth - 1);
}
}
return ops;
}
/** Why this document will not be sent, or null if it is a read. Pure. */
export function refusal(document) {
const ops = operations(document);
if (ops.length === 0) return 'the document contains no operation to send.';
for (const kind of ['mutation', 'subscription']) {
if (ops.includes(kind)) {
return `the document contains a ${kind}. This script sends queries only: `
+ 'a query is a read, and the section it belongs to promises its '
+ 'scripts never write.';
}
}
return null;
}
/** Group a count in thousands so it can be read at a glance. Pure. */
export function commas(n) {
if (n === null || n === undefined || n === '') return String(n);
const v = Number(n);
if (!Number.isFinite(v)) return String(n);
return Math.trunc(v).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ',');
}
function paging(field, args, variables) {
const m = PAGING.exec(args || '');
if (!m) return null;
const [, arg, raw] = m;
const variable = raw.startsWith('$') ? raw.slice(1) : null;
const value = variable ? (variables || {})[variable] : raw;
const n = Number(value);
return {
field: field || '?',
arg,
variable,
requested: Number.isInteger(n) ? n : null,
};
}
/** Every sliced connection in a document, with its node contribution. Pure. */
export function connections(document, variables = null) {
const src = stripNoise(document);
const out = [];
const stack = [];
let pending = null;
let field = null;
let i = 0;
while (i < src.length) {
const ch = src[i];
if (ch === '(') {
const j = src.indexOf(')', i);
const args = j < 0 ? src.slice(i + 1) : src.slice(i + 1, j);
const found = paging(field, args, variables);
// Only overwrite a pending slice when this argument group carries one, so
// a directive such as @include(if: $x) cannot erase the first: value that
// came immediately before it.
if (found !== null) pending = found;
i = j < 0 ? src.length : j + 1;
continue;
}
if (ch === '{') {
if (pending !== null) {
const ancestors = stack.reduce((a, b) => a * b, 1);
const rec = { ...pending, depth: stack.length + 1, ancestors };
rec.nodes = rec.requested === null ? null : ancestors * rec.requested;
out.push(rec);
stack.push(rec.requested || 1);
} else {
stack.push(1);
}
pending = null;
field = null;
i += 1;
continue;
}
if (ch === '}') {
stack.pop();
pending = null;
field = null;
i += 1;
continue;
}
if (/[A-Za-z_]/.test(ch)) {
let j = i;
while (j < src.length && /[A-Za-z0-9_]/.test(src[j])) j += 1;
field = src.slice(i, j);
i = j;
continue;
}
i += 1;
}
return out;
}
/** The node total the server will compute for this document. Pure. */
export function nodeCount(document, variables = null) {
return connections(document, variables)
.filter((c) => c.nodes !== null)
.reduce((sum, c) => sum + c.nodes, 0);
}
/** Connections whose slice is a variable nobody supplied. Pure. */
export function unresolved(document, variables = null) {
return connections(document, variables)
.filter((c) => c.requested === null)
.map((c) => c.field);
}
/** Named fragment spreads, which hide part of the selection set. Pure. */
export function fragmentSpreads(document) {
const src = stripNoise(document);
const found = new Set();
for (const m of src.matchAll(SPREAD)) {
if (m[1] !== 'on') found.add(m[1]);
}
return [...found].sort();
}
/** Everything that makes the computed total less than certain. Pure. */
export function caveats(document, variables = null) {
const out = [];
const missing = [...new Set(unresolved(document, variables))].sort();
if (missing.length > 0) {
out.push(`the slice on ${missing.join(', ')} is a variable this run has no `
+ 'value for, so those connections are not in the total. Pass GITHUB_VARIABLES.');
}
const spreads = fragmentSpreads(document);
if (spreads.length > 0) {
out.push(`the document spreads the fragment(s) ${spreads.join(', ')}, whose `
+ 'selection set this text-level check does not expand, so the total is a '
+ 'lower bound.');
}
return out;
}
/** The connection carrying the largest multiplier. Pure. null if there is none. */
export function deepest(document, variables = null) {
const resolved = connections(document, variables).filter((c) => c.nodes !== null);
if (resolved.length === 0) return null;
return resolved.reduce((best, c) => {
if (c.depth > best.depth) return c;
if (c.depth === best.depth && c.nodes > best.nodes) return c;
return best;
}, resolved[0]);
}
/** The largest slice the deepest connection could take. Pure. */
export function reshape(document, variables = null, limit = NODE_LIMIT) {
const d = deepest(document, variables);
if (d === null) return [null, null, null];
const total = nodeCount(document, variables);
const room = limit - (total - d.nodes);
if (d.ancestors <= 0) return [d.field, d.requested, null];
const k = Math.floor(room / d.ancestors);
if (k < 1) return [d.field, d.requested, null];
return [d.field, d.requested, Math.min(k, 100)];
}
/** Whether this node total is over the cap. Pure. */
export function exceeds(count, limit = NODE_LIMIT) {
const n = Number(count);
return Number.isFinite(n) && n > Number(limit);
}
/** Classify one document. Pure. Returns [state, detail]. */
export function verdict(document, variables = null, limit = NODE_LIMIT) {
const conns = connections(document, variables);
if (conns.length === 0) {
return ['no-connections', 'this document slices no connections, so it has '
+ 'no node count worth speaking of.'];
}
if (conns.some((c) => c.nodes === null)) {
return ['unresolved-variables', 'at least one slice is a variable with no '
+ 'value supplied, so the node count cannot be computed from the text alone.'];
}
const total = nodeCount(document, variables);
const pct = Math.round((100 * total) / limit);
if (exceeds(total, limit)) {
return ['over-node-limit', `${commas(total)} nodes is ${pct}% of the `
+ `${commas(limit)} cap, so this query is rejected before it runs whatever `
+ 'the organisation contains.'];
}
if (total > limit * NEAR) {
return ['near-node-limit', `${commas(total)} nodes is ${pct}% of the cap, `
+ 'which leaves no room for another level.'];
}
return ['within-node-limit', `${commas(total)} nodes is ${pct}% of the cap.`];
}
/** The sentence a reader has to act on. Pure. */
export function repair(state, field = null, current = null, suggested = null) {
if (state === 'over-node-limit' || state === 'near-node-limit') {
if (suggested !== null && suggested !== undefined) {
return `lower first on ${field} from ${current} to ${suggested} and `
+ 'paginate it separately with pageInfo { hasNextPage endCursor }.';
}
return `even a slice of one on ${field} leaves this query over the cap, so `
+ 'split it into separate queries rather than tuning a number.';
}
if (state === 'unresolved-variables') {
return 'pass the variables with GITHUB_VARIABLES so the slices can be '
+ 'resolved. A slice you cannot evaluate is a slice you cannot budget for.';
}
if (state === 'no-connections') return 'nothing. There is nothing here to multiply.';
return 'nothing on the node count.';
}
/** The node count the server computed, if the document asked for it. Pure. */
export function reportedNodeCount(body) {
if (!body || typeof body !== 'object') return null;
const data = body.data;
if (!data || typeof data !== 'object') return null;
const rl = data.rateLimit;
if (!rl || typeof rl !== 'object') return null;
const n = Number(rl.nodeCount);
return Number.isFinite(n) ? Math.trunc(n) : null;
}
/** Whether the server refused this document for its size. Pure. */
export function rejectedForNodes(body) {
if (!body || typeof body !== 'object' || !Array.isArray(body.errors)) return false;
return body.errors.some(
(e) => e && typeof e === 'object' && e.type === 'MAX_NODE_LIMIT_EXCEEDED',
);
}
/** Points this run will spend. Pure. Zero unless the confirm step is asked for. */
export function pointCost(confirm) {
return confirm ? 1 : 0;
}
async function main() {
const document = process.env.GITHUB_QUERY || DEMO_QUERY;
let variables = {};
if (process.env.GITHUB_VARIABLES) {
try { variables = JSON.parse(process.env.GITHUB_VARIABLES); } catch {
console.error('GITHUB_VARIABLES must be a JSON object');
process.exitCode = 2;
return;
}
}
const confirm = Boolean(process.env.GITHUB_CONFIRM);
const whyNot = refusal(document);
if (whyNot) {
console.error(`refusing to analyse and send: ${whyNot}`);
process.exitCode = 2;
return;
}
if (confirm) {
console.log(`point cost: ${pointCost(true)} point(s) against the 5,000/hour GraphQL budget`);
} else {
console.log(`point cost: ${pointCost(false)} point(s). The node count is `
+ 'computed from the query text and nothing is sent.');
}
const conns = connections(document, variables);
const total = nodeCount(document, variables);
console.log(`node count: ${commas(total)} against a limit of ${commas(NODE_LIMIT)}`);
for (const c of conns) {
console.log(` ${c.field.padEnd(16)} ${c.arg}=${String(c.requested ?? '?').padEnd(6)} `
+ `depth ${String(c.depth).padEnd(3)} ancestors x${commas(c.ancestors).padEnd(8)} `
+ `${c.nodes === null ? '?' : commas(c.nodes)} nodes`);
}
const [state, detail] = verdict(document, variables);
console.log(`${state}: ${detail}`);
for (const c of caveats(document, variables)) console.log(`caveat: ${c}`);
const [field, current, suggested] = reshape(document, variables);
console.log(`repair: ${repair(state, field, current, suggested)}`);
let server = {};
if (confirm) {
const token = process.env.GITHUB_TOKEN;
if (!token) {
console.error('confirming needs GITHUB_TOKEN (read-only is enough)');
process.exitCode = 2;
return;
}
const res = await fetch(`${API}/graphql`, {
// A GraphQL query is a read. POST is only how the document reaches the
// endpoint, and refusal() has already rejected anything that is not.
method: 'POST',
headers: {
Authorization: `Bearer ${token}`,
Accept: 'application/vnd.github+json',
'Content-Type': 'application/json',
'User-Agent': UA,
},
body: JSON.stringify({ query: document, variables }),
});
let body = null;
try { body = await res.json(); } catch { body = null; }
server = { rejected: rejectedForNodes(body), reported_node_count: reportedNodeCount(body) };
if (server.rejected) {
console.log('the server rejected the document for its node count, which '
+ 'confirms the arithmetic above');
} else if (server.reported_node_count !== null) {
console.log(`the server computed ${commas(server.reported_node_count)} node(s); `
+ `this check computed ${commas(total)}`);
} else {
console.log('the server accepted the document and reported no node count. '
+ 'Add rateLimit { nodeCount } to compare directly.');
}
}
console.log(JSON.stringify({
points_spent: pointCost(confirm),
node_count: total,
node_limit: NODE_LIMIT,
over_limit: exceeds(total),
connections: conns,
caveats: caveats(document, variables),
deepest: deepest(document, variables),
suggested: { field, current, first: suggested },
server,
state,
detail,
}, null, 2));
process.exitCode = ['over-node-limit', 'near-node-limit'].includes(state) ? 1 : 0;
}
// Guarded so importing this file from the test runner does not start a run and
// fail the suite even as every test passes.
if (import.meta.url === `file://${process.argv[1]}`) {
main().catch((err) => { console.error(err.message); process.exitCode = 2; });
}
Add a test
The arithmetic is the note, so the canonical three-level query is asserted at exactly 1,010,100 nodes and the suggested repair at exactly 48, which is the largest slice the deepest connection can take and still fit. Around that: the multiplier chain checked at each level, a slice supplied as a variable both with and without its value, a directive that must not erase the first: that precedes it, a fragment spread that makes the total a lower bound rather than an answer, the word first appearing inside a string literal, and the boundary cases at and just over the cap. Nothing in this suite needs a network, which is the same reason the script does not.
from github_graphql_nodes import (
NODE_LIMIT, caveats, commas, connections, deepest, exceeds,
fragment_spreads, node_count, operations, point_cost, refusal, repair,
reported_node_count, rejected_for_nodes, reshape, unresolved, verdict,
)
THREE_LEVELS = """query {
organization(login: "acme") {
repositories(first: 100) {
nodes {
pullRequests(first: 100) {
nodes {
comments(first: 100) { nodes { id } }
}
}
}
}
}
}"""
SMALL = """query {
organization(login: "acme") {
repositories(first: 100) {
nodes { pullRequests(first: 10) { nodes { number } } }
}
}
}"""
def test_the_canonical_query_is_the_documented_million():
assert node_count(THREE_LEVELS) == 1_010_100
assert exceeds(node_count(THREE_LEVELS))
assert NODE_LIMIT == 500_000
def test_the_multiplier_chain_is_what_makes_it_large():
conns = connections(THREE_LEVELS)
by_field = {c["field"]: c for c in conns}
assert by_field["repositories"]["ancestors"] == 1
assert by_field["repositories"]["nodes"] == 100
assert by_field["pullRequests"]["ancestors"] == 100
assert by_field["pullRequests"]["nodes"] == 10_000
assert by_field["comments"]["ancestors"] == 10_000
assert by_field["comments"]["nodes"] == 1_000_000
def test_the_deepest_connection_carries_almost_all_of_it():
d = deepest(THREE_LEVELS)
assert d["field"] == "comments"
assert d["nodes"] == 1_000_000
def test_the_repair_is_a_number_and_the_number_fits():
field, current, suggested = reshape(THREE_LEVELS)
assert field == "comments"
assert current == 100
assert suggested == 48
# The point of the suggestion is that taking it works.
fixed = THREE_LEVELS.replace("comments(first: 100)", "comments(first: 48)")
assert node_count(fixed) == 490_100
assert not exceeds(node_count(fixed))
def test_a_query_that_cannot_be_rescued_by_one_number_says_so():
huge = ("query { a(first: 100) { nodes { b(first: 100) { nodes { "
"c(first: 100) { nodes { d(first: 100) { nodes { id } } } } } } } } }")
assert exceeds(node_count(huge))
field, _current, suggested = reshape(huge)
assert suggested is None
assert "split it into separate queries" in repair("over-node-limit", field, 100, None)
def test_a_small_query_is_not_flagged():
assert node_count(SMALL) == 1_100
state, detail = verdict(SMALL)
assert state == "within-node-limit"
assert "0%" in detail or "%" in detail
def test_the_verdict_names_the_three_bands():
assert verdict(THREE_LEVELS)[0] == "over-node-limit"
near = "query { a(first: 100) { nodes { b(first: 4500) { nodes { id } } } } }"
assert node_count(near) == 450_100
assert verdict(near)[0] == "near-node-limit"
assert verdict(SMALL)[0] == "within-node-limit"
assert verdict("query { viewer { login } }")[0] == "no-connections"
def test_a_slice_supplied_as_a_variable_is_resolved_or_reported():
doc = "query($n: Int!) { a(first: $n) { nodes { id } } }"
assert node_count(doc, {"n": 50}) == 50
assert verdict(doc, {"n": 50})[0] == "within-node-limit"
assert unresolved(doc) == ["a"]
assert verdict(doc)[0] == "unresolved-variables"
assert "Pass --variables" in caveats(doc)[0]
def test_a_directive_does_not_erase_the_slice_before_it():
doc = ("query($show: Boolean!) { repositories(first: 100) @include(if: $show) "
"{ nodes { id } } }")
assert node_count(doc) == 100
def test_a_fragment_spread_makes_the_total_a_lower_bound():
doc = ("query { repositories(first: 100) { nodes { ...RepoBits } } } "
"fragment RepoBits on Repository { pullRequests(first: 100) { nodes { id } } }")
assert fragment_spreads(doc) == ["RepoBits"]
assert any("lower bound" in c for c in caveats(doc))
def test_an_inline_fragment_is_not_mistaken_for_a_spread():
doc = "query { search(query: \"x\", type: ISSUE, first: 10) { nodes { ... on Issue { id } } } }"
assert fragment_spreads(doc) == []
assert node_count(doc) == 10
def test_the_word_first_inside_a_string_is_not_a_slice():
doc = 'query { search(query: "first: 100", type: ISSUE, first: 5) { nodes { id } } }'
assert node_count(doc) == 5
def test_a_comment_is_not_read_as_part_of_the_query():
doc = "# repositories(first: 100)\nquery { a(first: 7) { nodes { id } } }"
assert node_count(doc) == 7
def test_the_server_can_be_asked_to_agree_but_does_not_have_to_be():
assert rejected_for_nodes({"errors": [{"type": "MAX_NODE_LIMIT_EXCEEDED"}]})
assert not rejected_for_nodes({"errors": [{"type": "RATE_LIMITED"}]})
assert reported_node_count({"data": {"rateLimit": {"nodeCount": 1100}}}) == 1100
assert reported_node_count({"data": {"viewer": {"login": "ada"}}}) is None
def test_counts_are_printed_in_something_readable():
assert commas(1_010_100) == "1,010,100"
assert commas(100) == "100"
assert commas(None) == "None"
def test_the_default_run_spends_nothing():
assert point_cost(False) == 0
assert point_cost(True) == 1
def test_the_script_refuses_to_analyse_and_send_a_mutation():
assert operations(THREE_LEVELS) == ["query"]
assert refusal("mutation M { addStar(input: {}) { clientMutationId } }")
assert refusal(THREE_LEVELS) is None
import { test } from 'node:test';
import assert from 'node:assert/strict';
import {
NODE_LIMIT, caveats, commas, connections, deepest, exceeds, fragmentSpreads,
nodeCount, operations, pointCost, refusal, rejectedForNodes, repair,
reportedNodeCount, reshape, unresolved, verdict,
} from './github-graphql-nodes.mjs';
const THREE_LEVELS = `query {
organization(login: "acme") {
repositories(first: 100) {
nodes {
pullRequests(first: 100) {
nodes {
comments(first: 100) { nodes { id } }
}
}
}
}
}
}`;
const SMALL = `query {
organization(login: "acme") {
repositories(first: 100) {
nodes { pullRequests(first: 10) { nodes { number } } }
}
}
}`;
test('the canonical query is the documented million', () => {
assert.equal(nodeCount(THREE_LEVELS), 1010100);
assert.ok(exceeds(nodeCount(THREE_LEVELS)));
assert.equal(NODE_LIMIT, 500000);
});
test('the multiplier chain is what makes it large', () => {
const byField = Object.fromEntries(connections(THREE_LEVELS).map((c) => [c.field, c]));
assert.equal(byField.repositories.ancestors, 1);
assert.equal(byField.repositories.nodes, 100);
assert.equal(byField.pullRequests.ancestors, 100);
assert.equal(byField.pullRequests.nodes, 10000);
assert.equal(byField.comments.ancestors, 10000);
assert.equal(byField.comments.nodes, 1000000);
});
test('the deepest connection carries almost all of it', () => {
const d = deepest(THREE_LEVELS);
assert.equal(d.field, 'comments');
assert.equal(d.nodes, 1000000);
});
test('the repair is a number and the number fits', () => {
const [field, current, suggested] = reshape(THREE_LEVELS);
assert.equal(field, 'comments');
assert.equal(current, 100);
assert.equal(suggested, 48);
const fixed = THREE_LEVELS.replace('comments(first: 100)', 'comments(first: 48)');
assert.equal(nodeCount(fixed), 490100);
assert.ok(!exceeds(nodeCount(fixed)));
});
test('a query that cannot be rescued by one number says so', () => {
const huge = 'query { a(first: 100) { nodes { b(first: 100) { nodes { '
+ 'c(first: 100) { nodes { d(first: 100) { nodes { id } } } } } } } } }';
assert.ok(exceeds(nodeCount(huge)));
const [field, , suggested] = reshape(huge);
assert.equal(suggested, null);
assert.match(repair('over-node-limit', field, 100, null), /split it into separate queries/);
});
test('a small query is not flagged', () => {
assert.equal(nodeCount(SMALL), 1100);
assert.equal(verdict(SMALL)[0], 'within-node-limit');
});
test('the verdict names the three bands', () => {
assert.equal(verdict(THREE_LEVELS)[0], 'over-node-limit');
const near = 'query { a(first: 100) { nodes { b(first: 4500) { nodes { id } } } } }';
assert.equal(nodeCount(near), 450100);
assert.equal(verdict(near)[0], 'near-node-limit');
assert.equal(verdict(SMALL)[0], 'within-node-limit');
assert.equal(verdict('query { viewer { login } }')[0], 'no-connections');
});
test('a slice supplied as a variable is resolved or reported', () => {
const doc = 'query($n: Int!) { a(first: $n) { nodes { id } } }';
assert.equal(nodeCount(doc, { n: 50 }), 50);
assert.equal(verdict(doc, { n: 50 })[0], 'within-node-limit');
assert.deepEqual(unresolved(doc), ['a']);
assert.equal(verdict(doc)[0], 'unresolved-variables');
assert.match(caveats(doc)[0], /GITHUB_VARIABLES/);
});
test('a directive does not erase the slice before it', () => {
const doc = 'query($show: Boolean!) { repositories(first: 100) @include(if: $show) '
+ '{ nodes { id } } }';
assert.equal(nodeCount(doc), 100);
});
test('a fragment spread makes the total a lower bound', () => {
const doc = 'query { repositories(first: 100) { nodes { ...RepoBits } } } '
+ 'fragment RepoBits on Repository { pullRequests(first: 100) { nodes { id } } }';
assert.deepEqual(fragmentSpreads(doc), ['RepoBits']);
assert.ok(caveats(doc).some((c) => c.includes('lower bound')));
});
test('an inline fragment is not mistaken for a spread', () => {
const doc = 'query { search(query: "x", type: ISSUE, first: 10) { nodes { ... on Issue { id } } } }';
assert.deepEqual(fragmentSpreads(doc), []);
assert.equal(nodeCount(doc), 10);
});
test('the word first inside a string is not a slice', () => {
const doc = 'query { search(query: "first: 100", type: ISSUE, first: 5) { nodes { id } } }';
assert.equal(nodeCount(doc), 5);
});
test('a comment is not read as part of the query', () => {
const doc = '# repositories(first: 100)\nquery { a(first: 7) { nodes { id } } }';
assert.equal(nodeCount(doc), 7);
});
test('the server can be asked to agree but does not have to be', () => {
assert.ok(rejectedForNodes({ errors: [{ type: 'MAX_NODE_LIMIT_EXCEEDED' }] }));
assert.ok(!rejectedForNodes({ errors: [{ type: 'RATE_LIMITED' }] }));
assert.equal(reportedNodeCount({ data: { rateLimit: { nodeCount: 1100 } } }), 1100);
assert.equal(reportedNodeCount({ data: { viewer: { login: 'ada' } } }), null);
});
test('counts are printed in something readable', () => {
assert.equal(commas(1010100), '1,010,100');
assert.equal(commas(100), '100');
assert.equal(commas(null), 'null');
});
test('the default run spends nothing', () => {
assert.equal(pointCost(false), 0);
assert.equal(pointCost(true), 1);
});
test('the script refuses to analyse and send a mutation', () => {
assert.deepEqual(operations(THREE_LEVELS), ['query']);
assert.ok(refusal('mutation M { addStar(input: {}) { clientMutationId } }'));
assert.equal(refusal(THREE_LEVELS), null);
});
FAQ
Why does the query fail against a tiny organisation?
Because the node count is computed from the numbers in the query, not from the rows behind them. A request for 100 repositories with 100 pull requests each with 100 comments each is 1,010,100 nodes whether the organisation has four repositories or four thousand, and the check happens before anything is fetched. This is also why narrowing a date range or excluding archived repositories does not help: those change what exists, and the limit does not care what exists.
Is this the same thing as running out of points?
No, and confusing them wastes real time. Points are an hourly allowance and running out is temporary: the same query succeeds an hour later. A node-limit rejection is permanent for that query text, because the query is what is too large. The error types are different too, MAX_NODE_LIMIT_EXCEEDED against RATE_LIMITED, which is exactly why a client should branch on the type rather than on the message: one of these deserves a wait and a retry and the other will burn the point budget in a loop that can never succeed.
Which first should I lower?
The deepest one, because it is multiplied by everything above it and therefore contributes almost the whole total. In the three-level example the comments connection is 1,000,000 of the 1,010,100 nodes; lowering it from 100 to 48 brings the query in, while halving the outermost value only gets you to about 505,000. The script prints the per-connection breakdown so this is a reading rather than a guess, and it solves for the largest value the deepest connection can take.
Do I need a token to run this?
No, and that is deliberate. The node count is a function of the query text, so the check parses, multiplies and prints without a credential, without a request and without spending a point. That makes it something you can run in CI over a directory of query files, which is where it belongs: the failure it prevents is a query going to production with an arithmetic problem nobody could see by reading it. The --confirm flag will ask the server to agree, costs one point and says so first.
What can a text-level check not see?
Two things, and it reports both rather than hiding them. A first supplied as a variable cannot be evaluated without the variables, so the script asks for them instead of assuming a value. And a named fragment spread hides part of the selection set, so when one is present the computed total is a lower bound rather than the answer; inline fragments are fine, since their selection set is right there in the document. Beyond that the arithmetic is the same arithmetic the server does.
Related field notes
- GraphQL points run out in their own bucket
- A GraphQL 200 that carries an errors array
- per_page above 100 is clamped, not rejected
Sources
Every figure in this note is traced to one of these. Prices are list rates and change — check them for your own region before acting.
- Resource limitations — GitHub GraphQL API
- Rate limits and node limits for the GraphQL API — GitHub Docs
- Using pagination in the GraphQL API — GitHub Docs
- Migrating from REST to GraphQL — GitHub Docs
If your setup is misbehaving in a way this note does not cover, message me on LinkedIn with what you are seeing.