P-Tag Graph Optimization Analysis

Overview

The new pubkey graph indexes can significantly accelerate certain Nostr query patterns, particularly those involving #p tag filters. This document analyzes the optimization opportunities and implementation strategy.

Current vs Optimized Indexes

Current P-Tag Query Path

Filter: {"#p": ["<hex-pubkey>"], "kinds": [1]}

Index Used: TagKind (tkc)

tkc|p|value_hash(8)|kind(2)|timestamp(8)|serial(5) = 27 bytes per entry

Process:

1. Hash the 32-byte pubkey → 8-byte hash
2. Scan tkc|p|<hash>|0001|<timestamp range>|*
3. Returns event serials matching the hash
4. Collision risk: 8-byte hash may have collisions for 32-byte pubkeys

Optimized P-Tag Query Path (NEW)

Index Used: PubkeyEventGraph (peg)

peg|pubkey_serial(5)|kind(2)|direction(1)|event_serial(5) = 16 bytes per entry

Process:

1. Decode hex pubkey → 32 bytes
2. Lookup pubkey serial: pks|pubkey_hash(8)|* → 5-byte serial
3. Scan peg|<serial>|0001|2|* (direction=2 for inbound p-tags)
4. Returns event serials directly from key structure
5. No collisions: Serial is exact, not a hash

Advantages:

• ✅ 41% smaller index: 16 bytes vs 27 bytes
• ✅ No hash collisions: Exact serial match vs 8-byte hash
• ✅ Direction-aware: Can distinguish author vs p-tag relationships
• ✅ Kind-indexed: Built into key structure, no post-filtering needed

Query Pattern Optimization Opportunities

1. P-Tag + Kind Filter

Filter: {"#p": ["<pubkey>"], "kinds": [1]}

Current: tkc index Optimized: peg index

Example: "Find all text notes (kind-1) mentioning Alice"

// Current: tkc|p|hash(alice)|0001|timestamp|serial
// Optimized: peg|serial(alice)|0001|2|serial

Performance Gain: ~50% faster (smaller keys, exact match, no hash)

2. Multiple P-Tags (OR query)

Filter: {"#p": ["<alice>", "<bob>", "<carol>"]}

Current: 3 separate tc- scans with union Optimized: 3 separate peg scans with union

Performance Gain: ~40% faster (smaller indexes)

3. P-Tag + Kind + Multiple Pubkeys

Filter: {"#p": ["<alice>", "<bob>"], "kinds": [1, 6, 7]}

Current: 6 separate tkc scans (3 kinds × 2 pubkeys) Optimized: 6 separate peg scans with 41% smaller keys

Performance Gain: ~45% faster

4. Author + P-Tag Filter

Filter: {"authors": ["<alice>"], "#p": ["<bob>"]}

Current: Uses TagPubkey (tpc) index Potential Optimization: Could use graph to find events where Alice is author AND Bob is mentioned

• Scan peg|serial(alice)|*|0|* (Alice's authored events)
• Intersect with events mentioning Bob
• Complex: Requires two graph scans + intersection

Recommendation: Keep using existing tpc index for this case

Implementation Strategy

Phase 1: Specialized Query Function (Immediate)

Create query-for-ptag-graph.go that:

1. Detects p-tag filters that can use graph optimization
2. Resolves pubkey hex → serial using GetPubkeySerial
3. Builds peg index ranges
4. Scans graph index instead of tag index

Conditions for optimization:

• Filter has #p tags
• AND filter has kinds (optional but beneficial)
• AND filter does NOT have authors (use existing indexes)
• AND pubkey can be decoded from hex/binary
• AND pubkey serial exists in database

Phase 2: Query Planner Integration

Modify GetIndexesFromFilter or create a query planner that:

1. Analyzes filter before index selection
2. Estimates cost of each index strategy
3. Selects optimal path (graph vs traditional)

Cost estimation:

• Graph: O(log(pubkeys)) + O(matching_events)
• Tag: O(log(tag_values)) + O(matching_events)
• Graph is better when: pubkeys < tag_values (usually true)

Phase 3: Query Cache Integration

The existing query cache should work transparently:

• Cache key includes filter hash
• Cache value includes result serials
• Graph-based queries cache the same way as tag-based queries

Code Changes Required

1. Create query-for-ptag-graph.go

package database

// QueryPTagGraph uses the pubkey graph index for efficient p-tag queries
func (d *D) QueryPTagGraph(f *filter.F) (serials types.Uint40s, err error) {
    // Extract p-tags from filter
    // Resolve pubkey hex → serials
    // Build peg index ranges
    // Scan and return results
}

2. Modify Query Dispatcher

Update the query dispatcher to try graph optimization first:

func (d *D) GetSerialsFromFilter(f *filter.F) (sers types.Uint40s, err error) {
    // Try p-tag graph optimization
    if canUsePTagGraph(f) {
        if sers, err = d.QueryPTagGraph(f); err == nil {
            return
        }
        // Fall through to traditional indexes on error
    }

    // Existing logic...
}

3. Helper: Detect Graph Optimization Opportunity

func canUsePTagGraph(f *filter.F) bool {
    // Has p-tags?
    if f.Tags == nil || f.Tags.Len() == 0 {
        return false
    }

    hasPTags := false
    for _, t := range *f.Tags {
        if len(t.Key()) >= 1 && t.Key()[0] == 'p' {
            hasPTags = true
            break
        }
    }
    if !hasPTags {
        return false
    }

    // No authors filter (that would need different index)
    if f.Authors != nil && f.Authors.Len() > 0 {
        return false
    }

    return true
}

Performance Testing Strategy

Benchmark Scenarios

1. Small relay (1M events, 10K pubkeys):

- Measure: p-tag query latency - Compare: Tag index vs Graph index - Expected: 2-3x speedup

1. Medium relay (10M events, 100K pubkeys):

- Measure: p-tag + kind query latency - Compare: TagKind index vs Graph index - Expected: 3-4x speedup

1. Large relay (100M events, 1M pubkeys):

- Measure: Multiple p-tag queries (fan-out) - Compare: Multiple tag scans vs graph scans - Expected: 4-5x speedup

Benchmark Code

func BenchmarkPTagQuery(b *testing.B) {
    // Setup: Create 1M events, 10K pubkeys
    // Filter: {"#p": ["<alice>"], "kinds": [1]}

    b.Run("TagIndex", func(b *testing.B) {
        // Use existing tag index
    })

    b.Run("GraphIndex", func(b *testing.B) {
        // Use new graph index
    })
}

Migration Considerations

Backward Compatibility

• ✅ Fully backward compatible: Graph indexes are additive
• ✅ Transparent: Queries work same way, just faster
• ✅ Fallback: Can fall back to tag indexes if graph lookup fails

Database Size Impact

Per event with N p-tags:

• Old: N × 27 bytes (tag indexes only)
• New: N × 27 bytes (tag indexes) + N × 16 bytes (graph) = N × 43 bytes
• Increase: ~60% more index storage
• Tradeoff: Storage for speed (typical for indexes)

Mitigation:

• Make graph index optional via config: ORLY_ENABLE_PTAG_GRAPH=true
• Default: disabled for small relays, enabled for medium/large

Backfilling Existing Events

If enabling graph indexes on existing relay:

# Run migration to backfill graph from existing events
./orly migrate --backfill-ptag-graph

# Or via SQL-style approach:
# For each event:
#   - Extract pubkeys (author + p-tags)
#   - Create serials if not exist
#   - Insert graph edges

Estimated time: 10K events/second = 100M events in ~3 hours

Alternative: Hybrid Approach

Instead of always using graph, use cost-based selection:

1. Small p-tag cardinality (<10 pubkeys): Use graph
2. Large p-tag cardinality (>100 pubkeys): Use tag index
3. Medium: Estimate based on database stats

Rationale: Tag index can be faster for very broad queries due to:

• Single sequential scan vs multiple graph seeks
• Better cache locality for wide queries

Recommendations

Immediate Actions

1. ✅ Done: Graph indexes are implemented and populated
2. 🔄 Next: Create query-for-ptag-graph.go with basic optimization
3. 🔄 Next: Add benchmark comparing tag vs graph queries
4. 🔄 Next: Add config flag to enable/disable optimization

Future Enhancements

1. Query planner: Cost-based selection between indexes
2. Statistics: Track graph vs tag query performance
3. Adaptive: Learn which queries benefit from graph
4. Compression: Consider compressing graph edges if storage becomes issue

Example Queries Accelerated

Timeline Queries (Most Common)

{"kinds": [1, 6, 7], "#p": ["<my-pubkey>"]}

Use Case: "Show me mentions and replies" Speedup: 3-4x

Social Graph Queries

{"kinds": [3], "#p": ["<alice>", "<bob>", "<carol>"]}

Use Case: "Who follows these people?" (kind-3 contact lists) Speedup: 2-3x

Reaction Queries

{"kinds": [7], "#p": ["<my-pubkey>"]}

Use Case: "Show me reactions to my events" Speedup: 4-5x

Zap Queries

{"kinds": [9735], "#p": ["<my-pubkey>"]}

Use Case: "Show me zaps sent to me" Speedup: 3-4x