# How the Entity Mentions System Implements a Bidirectional Graph in Macro

> Discover how the Macro entity mentions system uses a bidirectional graph with dual-keyed rows for O(log N) traversal. Learn about its efficient implementation.

- Repository: [Macro/macro](https://github.com/macro-inc/macro)
- Tags: internals
- Published: 2026-08-14

---

**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`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/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`.

```rust
// 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`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/crates/comms_db_client/src/entity_mentions/delete_entity_mentions_by_source.rs) handles this with a single `ANY($1)` query:

```rust
// 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`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/get_participants.rs)** ([`crates/comms_db_client/src/participants/get_participants.rs`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/get_attachment_references.rs)** ([`crates/comms_db_client/src/attachments/get_attachment_references.rs`](https://github.com/macro-inc/macro/blob/main/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

```rust
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

```rust
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

```rust
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

```rust
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`](https://github.com/macro-inc/macro/blob/main/create_message_mentions.rs)), deletion ([`delete_entity_mentions_by_source.rs`](https://github.com/macro-inc/macro/blob/main/delete_entity_mentions_by_source.rs)), and traversal ([`get_participants.rs`](https://github.com/macro-inc/macro/blob/main/get_participants.rs), [`get_attachment_references.rs`](https://github.com/macro-inc/macro/blob/main/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`](https://github.com/macro-inc/macro/blob/main/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.