Performance

Melange is designed for high-performance permission checking at scale. This page explains the performance characteristics you can expect and how to optimize your setup.

Performance Overview

Melange achieves sub-millisecond permission checks through:

1. Specialized SQL functions: Purpose-built functions generated for each relation
2. Precomputed closures: Role hierarchies resolved at migration time, not runtime
3. Index utilization: Generated SQL optimized for efficient index scans
4. In-database execution: No network round-trips for authorization

Pattern Complexity Benchmarks

All benchmarks run on Apple M2 Pro with PostgreSQL 16. These results show performance across different authorization patterns from the OpenFGA compatibility test suite.

Performance by Pattern Type

Typical latencies across all scales (1K-1M tuples). Real-world p95 latencies may be 30-50% higher with network and connection pool overhead.

Complex Pattern Performance

More complex patterns combining multiple features (typical ranges):

Expensive Operations

Some patterns have significantly higher latency:

Validation Performance

Invalid requests are rejected immediately without database queries:

Scale Benchmarks

These benchmarks test performance at different tuple volumes using a GitHub-like authorization model.

Test Schema

The scale benchmarks use a model with organizations, repositories, and pull requests:

type organization
  relations
    define owner: [user]
    define admin: [user] or owner
    define member: [user] or admin
    define can_read: member

type repository
  relations
    define org: [organization]
    define reader: [user] or can_read from org
    define writer: [user] or reader
    define can_read: reader
    define can_write: writer
    define can_review: can_read but not author

type pull_request
  relations
    define repo: [repository]
    define author: [user]
    define can_read: can_read from repo
    define can_review: can_read from repo but not author

Test Data Configuration

Tuples include: org memberships, repo→org relationships, PR→repo relationships, and PR→author relationships.

Check Operations

Check operations execute specialized SQL functions and scale with O(1) constant time regardless of tuple count:

Key insight: All check operations maintain constant time regardless of dataset size. This is achieved through specialized SQL code generation that eliminates runtime schema interpretation.

List Operations

List operations find all objects a subject can access (or all subjects with access to an object). Performance characteristics vary significantly by result set size, not total dataset size.

Performance Depends on Result Set Size, Not Total Data

The most important finding: query time is determined by how many results match, not how many tuples exist in the database.

ListObjects (find objects a user can access):

ListSubjects (find users with access):

Key insight: Small result sets are fast regardless of total dataset size. At 1M tuples, listing organizations (5 results) takes 204µs while listing PRs (1M results) takes 629ms. The recursive CTE must evaluate all potential permission paths, making query time proportional to the number of accessible objects.

Page Size Has Minimal Impact

Page size has almost no effect on query execution time - the database walks the entire permission graph regardless of LIMIT:

ListObjects performance at 10K scale (500 total repos):

Recommendation: Use page sizes of 10-100 for API responses. Since query time is constant, smaller pages reduce response size without performance penalty.

Pagination Overhead is Negligible

Walking through multiple pages adds almost no overhead:

Note: At very large result sets (10K+), pagination overhead becomes significant due to cursor-based resumption. For full dataset downloads, use a single large page. For interactive APIs, use small pages for better UX.

Parallel Operations

Permission checks are fully parallelizable since each check is independent:

At 12 parallel workers, throughput increases approximately 3-4x compared to sequential checks, demonstrating excellent concurrency characteristics for high-load scenarios.

Caching

The optional in-memory cache provides dramatic speedups for repeated checks:

Enable caching in your application:

cache := melange.NewCache(
    melange.WithTTL(time.Minute),
    melange.WithMaxSize(10000),
)
checker := melange.NewChecker(db, melange.WithCache(cache))

When to use caching:

• High read-to-write ratio (permissions checked frequently, changed rarely)
• Acceptable staleness window (typically 30s-5min depending on application)
• Memory budget available for cache storage

When to skip caching:

• Permissions change frequently
• Strict real-time consistency required
• Memory-constrained environments

Optimizing Performance

1. Design Efficient Schemas

Schema design has the biggest impact on query performance. The benchmarks show clear patterns:

Performance tiers by pattern:

Minimize intersections: Intersection is one of the more expensive set operations (~400-800 µs for checks, 500-1500 µs for lists), especially for ListObjects and ListUsers:

# Slower: Intersection requires evaluating multiple paths (~600 µs check)
type document
  relations
    define viewer: writer and editor

# Faster: Union is much cheaper (~350 µs check)
type document
  relations
    define viewer: writer or editor

Prefer shallow hierarchies: Deep parent traversals increase query complexity:

# Better: Direct assignment with union
type document
  relations
    define viewer: [user, team#member]

# Slower: Deep parent chain
type document
  relations
    define viewer: viewer from folder
type folder
  relations
    define viewer: viewer from workspace

Use direct relations where possible: define viewer: [user] (~330 µs) is faster than nested computed usersets (~450 µs).

Be cautious with wildcards in ListObjects/ListUsers: While Check with wildcards is fast (~330 µs), wildcard expansion for list operations can be expensive (5-30 ms in worst cases).

2. Avoid Runtime Contextual Tuples

Contextual tuples add ~3-5ms overhead per operation due to temporary table setup. Use stored tuples when possible:

// Slow: Adds 3-5ms overhead with contextual tuples
checker.CheckWithContextualTuples(ctx, user, "viewer", doc, temporaryPermissions)

// Fast: 300-500µs with stored tuples
checker.Check(ctx, user, "viewer", doc)

If you need contextual tuples frequently, consider batching multiple checks together.

3. Index Your Tuples View

Proper indexing of your melange_tuples view source tables is critical:

-- Object-based lookups (most common pattern)
CREATE INDEX idx_org_members_lookup
    ON organization_members (organization_id, role, user_id);

-- Expression indexes for text ID conversion
CREATE INDEX idx_org_members_text
    ON organization_members ((organization_id::text), (user_id::text));

Without expression indexes, PostgreSQL must perform sequential scans when your view converts integer IDs to text.

See the Tuples View documentation for complete indexing guidance.

4. Use Appropriate Scaling Strategies

See Tuples View Scaling Strategies for implementation details.

5. Use Pagination for Large Result Sets

For list operations with many results, use cursor-based pagination:

// Fetch first page (recommended page size: 10-100)
objects, cursor, err := checker.ListObjects(ctx, user, "viewer", "document",
    melange.PageOptions{Limit: 50})

// Fetch subsequent pages
nextPage, nextCursor, err := checker.ListObjects(ctx, user, "viewer", "document",
    melange.PageOptions{Limit: 50, After: cursor})

Page size recommendations:

• Interactive APIs: 10-50 items (minimize response payload, low query overhead)
• Batch processing: 100-500 items (balance between memory and round-trips)
• Full downloads: Use ListObjectsAll() or single large page

Since query time is roughly constant regardless of page size, smaller pages are better for UX without performance penalty.

6. Monitor Query Performance

Use EXPLAIN ANALYZE to identify slow queries:

EXPLAIN ANALYZE
SELECT check_permission('user', '123', 'viewer', 'document', '456');

Look for:

• Sequential scans: Add indexes to eliminate these
• High row estimates: May indicate missing statistics (ANALYZE your tables)
• Nested loops with high iterations: Consider schema simplification

Performance Comparison

How does Melange compare to alternatives?

Melange provides the consistency guarantees of transactional SQL with performance comparable to simpler RBAC systems, while supporting the full expressiveness of Zanzibar-style authorization.

Summary

Typical performance expectations:

• Check operations: 300-600 µs (O(1) - constant time regardless of dataset size)
  • Simple patterns (direct, union): 300-400 µs
  • Medium complexity (TTU, exclusion): 400-550 µs
  • Complex patterns (intersection, nested TTU): 500-800 µs
  • Very complex (deep chains, recursive): 1-2 ms
• List operations with small results (<10 items): 300-500 µs (O(1) - e.g., listing orgs, writers)
• List operations with large results: Scales with result count, not total data
  • 100 results: ~4-5 ms
  • 1K results: ~10-15 ms
  • 10K results: ~34-37 ms
  • 100K results: ~134-153 ms
  • 1M results: ~672-843 ms
• Page size impact: Minimal (~0-3% variance for different page sizes)
• Pagination overhead: Negligible for <1K results, ~79% for 10K+ results
• Validation errors: ~25-30 ns (instant rejection, no database hit)
• Cache hits: ~83 ns (~5,000x faster than database)
• Parallel throughput: 3-4x improvement with 12 workers

Key insights:

• Check performance is independent of dataset size - 1K tuples vs 1M tuples: same latency
• List performance depends on result count, not total tuples - small result sets are fast at any scale
• Page size has minimal effect on query time - use small pages (10-100) for better UX
• Caching provides 5,000x speedup - critical for repeated checks
• Real-world latencies: Add 30-50% to these numbers for p95 API latencies with network/connection overhead

Patterns to avoid for latency-sensitive paths:

• Deep intersection chains (use union where possible)
• Contextual tuples (use stored tuples, ~3ms overhead)
• Wildcard expansion in ListObjects/ListUsers
• Deeply nested TTU chains

Further Reading

• Tuples View - Detailed indexing and scaling strategies
• Contributing: Benchmarking - Run benchmarks yourself
• How It Works - Architecture details explaining performance characteristics