How the Entity Mentions System Implements a Bidirectional Graph in Macro

The Macro entity mentions system stores every relationship as a dual-keyed row in comms_entity_mentions, enabling O(log N) traversal in either direction without separate tables.

The macro-inc/macro codebase models relationships between messages, documents, channels, and users as a bidirectional graph using a single, flexible database table. This design avoids the complexity of adjacency lists or separate foreign-key tables while supporting efficient queries for both "what does this entity mention?" and "what mentions this entity?"

Core Data Model: The comms_entity_mentions Table

The graph lives in PostgreSQL as the comms_entity_mentions table, defined in crates/comms_db_client/fixtures/message_mentions.sql. Each row represents a directed edge with enough metadata to query it from either endpoint.

Column	Purpose
source_entity_type	Kind of the node that creates the mention (e.g., "message", "doc")
source_entity_id	UUID of the source node
entity_type	Kind of the node that is mentioned (e.g., "user", "doc")
entity_id	UUID of the target node
user_id	Optional: user who caused the mention (enables reply-to semantics)
id	Primary key, generated via gen_random_uuid()

Because both source and target pairs are stored in every row, the same table answers both directions of the relationship. Composite indexes on (source_entity_type, source_entity_id) and (entity_type, entity_id) guarantee fast lookups from either side.

Creating Edges: create_message_mentions.rs

Mentions are inserted in bulk when a message is saved. The create_message_mentions function in crates/comms_db_client/src/messages/create_message_mentions.rs builds an INSERT … SELECT that writes one row per detected mention, deduplicating via ON CONFLICT DO NOTHING.

// crates/comms_db_client/src/messages/create_message_mentions.rs
sqlx::query!(
    r#"
    INSERT INTO comms_entity_mentions
        (id, source_entity_type, source_entity_id, entity_type, entity_id, user_id)
    SELECT
        gen_random_uuid(),
        'message',
        $1,
        'user',
        mention_user_id,
        mention_user_id
    FROM UNNEST($2::text[]) AS mention_user_id
    ON CONFLICT DO NOTHING
    "#,
    message_id,
    &mentioned_user_ids,
)
.execute(&mut tx)
.await?;

The UNNEST operator expands a Rust Vec<String> into SQL rows, and the ON CONFLICT clause ensures idempotency—rerunning the same mention set creates no duplicates.

Deleting Edges: delete_entity_mentions_by_source.rs

When a source entity is removed (e.g., message deletion), its outgoing edges must disappear to maintain graph consistency. The delete_entity_mentions_by_source function in crates/comms_db_client/src/entity_mentions/delete_entity_mentions_by_source.rs handles this with a single ANY($1) query:

// crates/comms_db_client/src/entity_mentions/delete_entity_mentions_by_source.rs
sqlx::query!(
    r#"
    DELETE FROM comms_entity_mentions
    WHERE source_entity_id = ANY($1)
    "#,
    &source_entity_id,
)
.execute(executor)
.await?;

This accepts a slice of source IDs, enabling efficient batch cleanup when entire threads or channels are deleted.

Traversing the Graph: Outgoing and Incoming Queries

The bidirectional design shines in read patterns. Both directions use the same table with different WHERE clauses.

Outgoing Edges: What a Node Mentions

Queries targeting source_entity_type + source_entity_id retrieve everything a node references. For example, get_channel_message.rs joins comms_entity_mentions to hydrate mentions attached to a retrieved message.

Incoming Edges: What Mentions a Node

The reverse lookup—essential for notifications, participant lists, and attachment resolution—queries entity_type + entity_id:

• get_participants.rs (crates/comms_db_client/src/participants/get_participants.rs): Finds all users mentioned in a thread, enabling "who is involved" logic without scanning message bodies.

• get_attachment_references.rs (crates/comms_db_client/src/attachments/get_attachment_references.rs): Resolves which documents are attached to a message by querying document-to-message mention relationships.

Both operations hit the same (entity_type, entity_id) index, maintaining symmetric performance characteristics.

Practical Examples

Insert mentions for a new message

use comms_db_client::messages::create_message_mentions::create_message_mentions;

let rows = create_message_mentions(&mut tx, message_id, mentioned_user_ids).await?;
println!("Inserted {} mention rows", rows);

Remove all mentions for deleted messages

use comms_db_client::entity_mentions::delete_entity_mentions_by_source;

let message_ids = vec!["msg-1".into(), "msg-2".into()];
let deleted = delete_entity_mentions_by_source(&mut tx, message_ids).await?;
println!("Removed {} outgoing mention edges", deleted);

Find participants via incoming mentions

use comms_db_client::participants::get_participants::get_participants;

let participants = get_participants(&pool, thread_id).await?;
for user in participants {
    println!("User {} participates via mention", user.id);
}

Resolve document attachments

use comms_db_client::attachments::get_attachment_references::get_attachment_references;

let docs = get_attachment_references(&pool, message_id).await?;
println!("Message {} references {} docs", message_id, docs.len());

Consistency Guarantees

Mechanism	Purpose
ON CONFLICT DO NOTHING	Prevents duplicate edges without expensive pre-check queries
Application-level cascade delete	Removes outgoing edges when sources are deleted; no database foreign-key cascades needed
Loose coupling	Entities can be deleted independently; dangling references simply return empty sets
Dual composite indexes	O(log N) lookups for both (source_type, source_id) and (entity_type, entity_id)

Summary

• Single-table design: comms_entity_mentions stores every graph edge with complete source and target metadata.
• True bidirectionality: Both (source_type, source_id) and (entity_type, entity_id) are queryable, enabling symmetric traversal without separate tables.
• Idempotent inserts: ON CONFLICT DO NOTHING makes mention creation safe to retry.
• Efficient cleanup: delete_entity_mentions_by_source prunes outgoing edges in bulk via ANY($1).
• Rust implementation: All operations live in crates/comms_db_client, with clear separation between insertion (create_message_mentions.rs), deletion (delete_entity_mentions_by_source.rs), and traversal (get_participants.rs, get_attachment_references.rs).

Frequently Asked Questions

Why not use a separate table per relationship type?

The entity mentions system deliberately avoids schema proliferation. By storing source_entity_type and entity_type as columns, one table handles message→user mentions, document→message attachments, and any future relationship without migrations. This polymorphic approach trades some type safety for extreme flexibility.

How does the system prevent duplicate mentions?

The ON CONFLICT DO NOTHING clause in create_message_mentions.rs treats (source_entity_type, source_entity_id, entity_type, entity_id) as an implicit unique constraint. If the same mention is inserted twice—whether from retries or race conditions—the second insert is silently discarded.

What happens to mentions when a message is deleted?

Application code calls delete_entity_mentions_by_source with the message's ID before (or during) message deletion. No database-level ON DELETE CASCADE exists; the graph is intentionally loose to avoid coupling between independent subsystems. Dangling target-side references simply return empty sets when queried.

How performant are bidirectional queries?

Both directions hit composite indexes: (source_entity_type, source_entity_id) for outgoing edges and (entity_type, entity_id) for incoming edges. According to the Macro source code, these indexes ensure logarithmic lookup time regardless of graph size or traversal direction.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}