Use case: pull-based triple pattern access over gRPC

[GregHanson]

Context

We're building a distributed SPARQL engine in Rust. Query evaluation is federated
across peer nodes, each of which serves a set of RDF files; the evaluator on the
asking node pushes individual triple patterns out to peers and joins the results
locally. Peer-to-peer transport is gRPC.

We currently use a homegrown proto for this and are evaluating replacing its
payload with Jelly's rdf.proto. Everything on the response side maps over
cleanly. The request side has no equivalent in Jelly, which is what this issue
is about.

The gap

grpc.proto is push-oriented: SubscribeRdf(topic) and PublishRdf(stream).
Both model a producer that already knows what it wants to send. There is no way
for a client to say "return the triples matching (s, p, o)".

sparql.proto defines how to serialize a solution sequence, but no request
message. It specifies the answer, not the question.

So any Jelly implementation that wants to expose pull-based, pattern-scoped
access has to invent its own request message. We've invented one; presumably
others will too, and they will all be different, while the response side is
already standardized. That asymmetry seems worth at least a decision, even if
the decision is "out of scope."

Sketch

Not a proposal so much as the shape of the thing, to make the discussion concrete:

// A triple pattern. An unset oneof denotes a variable.
// NOTE: this cannot reuse RdfTriple, see below.
message RdfTriplePattern {
  oneof subject {
    RdfIri     s_iri = 1;
    string     s_bnode = 2;
    RdfLiteral s_literal = 3;
  }
  oneof predicate { /* p_iri = 5, ...  field numbering as in RdfTriple */ }
  oneof object    { /* o_iri = 9, ... */ }
  oneof graph     { /* optional, for quad patterns */ }
}

message RdfPatternRequest {
  // Which graphs/datasets to match against. Scope TBD, see open questions.
  repeated string graphs = 1;
  RdfTriplePattern pattern = 2;
  RdfStreamOptions requested_options = 3;
}

service RdfPatternService {
  rpc GetTriples (stream RdfPatternRequest) returns (stream RdfStreamFrame);
}

The bidirectional stream is the substantive part, not incidental: it is what
lets the lookup tables persist across many patterns (see below).

RdfTriple cannot be reused as a pattern

Worth flagging because it is the first thing an implementer will try. In
RdfTriple, an unset term oneof already means "repeat the term in this position
from the previous statement." A pattern needs unset to mean "variable." The two
readings collide, so a pattern message has to be a distinct type, or carry an
explicit variable marker.

Why this may belong in Jelly rather than outside it

The reason we're asking rather than just defining our own is that the win here
is a property of Jelly's design specifically, not of gRPC.

A SPARQL evaluator issues one request per triple pattern per join probe, so a
single BGP against one peer is many messages. With a per-message encoding, every
one of those re-sends the same IRIs. Jelly's lookup tables are stream state, so
over a session they amortize - and that is something generic transport
compression structurally cannot do, because its window resets per message.

Measured on one of our datasets, a 12-pattern BGP against a single peer,
19,527 result rows total, comparing total bytes for the whole exchange:

encoding	raw	gzipped
our current proto (plain strings), 12 messages, gzip each	3549K	139.3K
Jelly, lookup tables rebuilt per message	398K	104.2K
Jelly, one lookup table across the session	286K	66.7K

The last row is 2.09x better than our current wire, of which 1.56x comes purely
from holding the dictionary open across requests. The dictionary that does this
is small: 1,431 names and 17 prefixes for the whole exchange.

Two honesty notes on those numbers. This dataset is IRI-dense (~80% of payload
bytes are IRIs). On a blank-node-heavy dataset of ours (~28% of payload bytes
are bnode labels, ~20% literals), the same comparison is much weaker - the
gzip-to-gzip ratio falls to 1.02–1.09x on the high-volume patterns (1.45x on one
narrow rdf:type pattern), because Jelly carries bnode labels and lexical forms
verbatim and gzip was already handling them well. That is
arguably a datapoint for #16 more than for this issue, and I'm happy to write it
up there separately if useful.

Relationship to existing issues

• Proposal draft: pre-shared dictionaries #36: a pair of federation peers that talk
  repeatedly is close to an ideal case for a negotiated, non-preshared-but-
  persistent dictionary. If a pattern-request protocol existed, the session
  dictionary and the pre-shared dictionary would want to share a design.
• Investigation: statement pattern compression #38: different mechanism, but our
  measurements on patterns with bound predicate and object may be relevant
  input; happy to share.
• Proposal draft: implement RDF Delta in gRPC #21: precedent that grpc.proto can grow services
  that aren't pub/sub.
• Make a space to report protocol extensions #15 / Versioning of new specs based on the Jelly serialization format #23: if the answer here is "extension, not core," these are
  presumably where it would land.

Open questions

1. Correlating responses to requests. With both sides streaming, the client
   needs to know which frames answer which pattern. RdfStreamFrame.metadata
   could carry a correlation id, or the server could answer strictly in order
   with explicit boundaries. Unclear which is preferable.
2. Do the pattern's terms use the lookup tables? If so, the request stream
   needs to carry lookup entries too, and dictionary state becomes bidirectional.
   Our inclination is that it shouldn't: patterns are few and tiny next to
   results, so plain strings in the request are simpler and cost almost nothing.

What we're asking

Mainly: is pull-based pattern access something Jelly wants to cover, or is it
out of scope by design?

Either answer is useful to us. If it's in scope, we'd rather implement whatever
you'd standardize than ship something divergent and have to break it later. If
it's out of scope, we'll define it in the ≥10000 extension version space and
register it per #15 and we'd still rather do that having asked, so that the
divergence is deliberate.

[Ostrzyciel]

Hello @GregHanson! Thank you for opening the issue and the detailed motivation :)

In short, I would be happy to add this as an "experimental" proto to this repository and the website. I think this is a very useful thing, and I think some other people (e.g., in UGent) may also be interested in this. If there is enough community interest (either from you or from someone else), we can mark it as stable. But, I think starting from an "experimental" proto will be easier – you will be free to evolve the proto as you see fit.

I encourage you to submit a PR with this! :)

A couple of notes that came to my mind:

• "RdfTriple cannot be reused as a pattern" – I disagree, I think it could very well be used for patterns, because this is a different context in which you apply the message. The thing that applies the rule "missing term = repeat previous" is the decoder, not the proto parser itself. I don't feel strongly about this, though :)
• The RdfTriplePattern message is in fact a quad pattern, so I think it should be called accordingly.
• "RdfStreamFrame.metadata could carry a correlation id, or the server could answer strictly in order with explicit boundaries." – gRPC has the advantage of having very good delivery and ordering guarantees, so I see no reason to not use the in-order method. Correlation IDs require buffers, which adds complexity, raises latency, and creates new places for things to break.
• "Do the pattern's terms use the lookup tables?" – I agree that they should not.
• If you are not using zstd for binary compression already, do give it a go. It works with Jelly much much better than gzip.
• I would be happy to hear your findings regarding how Jelly does in different scenarios! If you see an issue that discusses something relevant to you, please don't hesitate to add your 2 cents there :) it would help a lot.