Plus, considerations in updating one of GitHub’s oldest and most heavily used features.
Overview
This article details how GitHub rebuilt its Issues search system to support nested queries with boolean AND/OR operators and parentheses. The engineering team replaced the flat query parser with an Abstract Syntax Tree (AST)-based parser using PEG grammar, mapped it to Elasticsearch bool queries, and carefully rolled out the feature using dark-shipping, performance comparison with the Scientist library, and incremental deployment to handle nearly 2,000 queries per second without breaking backward compatibility.
What You'll Learn
1
How to parse complex nested search queries using PEG grammar and Abstract Syntax Trees
2
How to map boolean search operators (AND/OR/NOT) to Elasticsearch bool query clauses (must/should/must_not)
3
How to safely refactor a high-traffic search system using dark-shipping and the Scientist library for production validation
4
Why backward compatibility testing through dual-execution and result comparison is critical for search system rewrites
5
How to incrementally roll out a major feature change to minimize risk for millions of daily users
Prerequisites & Requirements
- Understanding of search query syntax and how search systems work at a high level
- Familiarity with Elasticsearch and its query DSL, particularly bool queries
- Basic understanding of parsing concepts including Abstract Syntax Trees and grammars
- Experience with backend systems handling high query volumes(optional)
Key Questions Answered
How did GitHub implement boolean AND/OR operators in Issues search?
GitHub replaced the flat IssuesQuery module with a new ConditionalIssuesQuery module that parses search strings into an Abstract Syntax Tree using the parslet library with a PEG grammar. The AST is then recursively traversed to generate Elasticsearch bool queries, where AND maps to 'must' clauses, OR maps to 'should' clauses, and NOT maps to 'must_not' clauses.
Why did GitHub switch from flat list parsing to an AST for search queries?
The previous flat list parsing could only handle implicitly AND-joined query terms, which limited search flexibility. Since nested queries with boolean operators are inherently recursive structures, an Abstract Syntax Tree was needed to properly represent the hierarchical relationships between query terms, operators, and parenthesized groups that users had been requesting for nearly a decade.
How did GitHub ensure backward compatibility when rebuilding Issues search?
GitHub used extensive unit and integration testing by running the new search module against all existing tests. They also employed dark-shipping, running 1% of production searches against both old and new systems in background jobs and logging differences in result counts. This allowed them to identify and fix bugs and edge cases before users encountered them.
What is dark-shipping and how does GitHub use it to validate search changes?
Dark-shipping is a technique where new code runs in production alongside existing code without affecting users. GitHub ran 1% of issue searches against both the old and new search systems simultaneously, comparing result counts to detect discrepancies. Searches returning different numbers of results within a second indicated potential bugs in the new system that needed fixing before rollout.
How does GitHub handle performance testing when refactoring critical search paths?
GitHub used their open-source Scientist Ruby library to compare performance of equivalent queries between the old and new search systems on 1% of production traffic. This allowed them to establish realistic baselines for nested queries while ensuring no regression in simpler query performance, all at a scale of nearly 2,000 queries per second.
What limits does GitHub impose on nested search query complexity?
GitHub limits nested queries to a maximum of five levels of nesting depth. This limit was determined through customer interviews and represents a balance between search utility and usability. The UI also provides helpful cues like AND/OR keyword highlighting and auto-complete features for filter terms to maintain the user experience.
How does the parslet PEG grammar handle operator precedence in boolean search queries?
The parslet PEG grammar handles operator precedence by structuring rules hierarchically. The parser starts at the lowest precedence rule (or_operation), which contains and_operation, which in turn contains primary expressions. Primary expressions handle parenthesized sub-expressions, allowing users to override default precedence. AND binds tighter than OR, matching standard boolean algebra conventions.
What was GitHub's rollout strategy for the new Issues search system?
GitHub used a phased rollout: first testing internally with their own team during development, then gradually expanding to all GitHub employees, then to trusted external partners for feedback. They initially limited integration to only the GraphQL API and repository Issues tab UI, later expanding to the Issues dashboard and REST API once confident in performance and correctness.
Key Statistics & Figures
Issues search query volume
~2,000 queries per second
QPS
Daily search queries
~160 million queries per day
Total daily volume of Issues search queries
Dark-shipping sample rate
1%
Percentage of production searches run against both old and new systems for validation
Maximum nesting depth
5 levels
Maximum number of nested parentheses levels allowed in a search query
Community request age
Nearly a decade
How long the developer community had been requesting boolean operator support in Issues search
Technologies & Tools
Some links below are affiliate links. We may earn a commission if you make a purchase.
Search Engine
Elasticsearch
Backend search infrastructure that executes the parsed and transformed search queries using bool query DSL
Programming Language
Ruby
Language used for the search module implementation, parsing, and query generation
Parsing Library
Parslet
Ruby PEG parsing library used to parse search strings into Abstract Syntax Trees
Testing Library
Scientist
GitHub's open-source Ruby library for safely refactoring critical paths by comparing old and new implementations in production
API
Graphql API
First API surface where the new nested search was integrated and tested
API
REST API
Second API surface where nested search was rolled out after initial validation
Key Actionable Insights
1When rewriting a high-traffic search system, use dark-shipping to validate correctness by running a small percentage of production queries against both old and new systems simultaneously. Compare result counts as a first approximation of correctness before deeper validation.GitHub ran 1% of issue searches through both systems and compared the number of results returned. Differences in result count within a short time window indicated bugs that needed fixing before user-facing rollout.
2Use PEG (Parsing Expression Grammar) and AST-based parsing when your query language needs to support recursive or nested structures like boolean operators with parentheses. Flat list parsing is insufficient for anything beyond simple AND-joined filters.GitHub used the parslet Ruby library to define a PEG grammar that supports both legacy flat queries and new nested boolean queries, ensuring backward compatibility while enabling the new syntax.
3Map boolean search operators directly to Elasticsearch's bool query clauses: AND to 'must', OR to 'should', and NOT to 'must_not'. Recursively traverse your AST to build the nested query document, reusing existing filter-to-query building blocks.This mapping provides a natural translation from user-facing search syntax to Elasticsearch's native query DSL, allowing complex nested queries without requiring a custom query execution engine.
4Use a library like GitHub's open-source Scientist to safely refactor critical code paths by running old and new implementations side-by-side in production and comparing results and performance without affecting users.Scientist enabled GitHub to compare query performance between the old and new search systems on live traffic, establishing baselines for new nested queries while catching regressions in existing simple queries.
5When rolling out risky changes to high-traffic features, limit blast radius by deploying to a subset of interfaces first (e.g., only the GraphQL API and one UI surface) before expanding to all consumers like REST APIs and dashboards.GitHub first shipped the new search only in the GraphQL API and repository Issues tab, collecting feedback and fixing issues before rolling out to the Issues dashboard and REST API, protecting millions of daily users.
6Impose practical limits on query complexity based on user research rather than arbitrary technical constraints. Customer interviews can reveal the right balance between power and usability for features like nested search.GitHub limited nesting depth to five levels after conducting customer interviews, finding this to be the sweet spot where users had sufficient flexibility without creating overly complex, hard-to-understand queries.
Common Pitfalls
1
Attempting to support nested boolean queries using flat list parsing. A flat list structure cannot represent the recursive, hierarchical nature of queries with parenthesized groups and mixed AND/OR operators, leading to incorrect query interpretation.
The team had to move from flat list parsing to AST-based parsing specifically because the previous approach could not handle the new recursive query structure.
2
Rolling out search system changes to all API surfaces and UI simultaneously without phased deployment. When a feature handles millions of daily users and thousands of queries per second, a broad rollout magnifies the impact of any bugs or performance regressions.
GitHub mitigated this by first deploying only to the GraphQL API and repository Issues tab, then expanding to the Issues dashboard and REST API after gaining confidence.
3
Not defining what constitutes a 'difference' when comparing old and new search system results during dark-shipping. Without a clear metric, it's difficult to determine whether the new system produces correct results.
GitHub initially wasn't sure how to define differences but settled on comparing 'number of results' as a practical first metric, reasoning that different result counts for the same query run within a second indicated a problem.
4
Allowing unlimited nesting depth in search queries, which could lead to overly complex queries that degrade performance, confuse users, and generate expensive Elasticsearch queries consuming excessive backend resources.
GitHub conducted customer interviews and determined that five levels of nesting was the sweet spot for balancing utility and usability, preventing both performance issues and user confusion.
Related Concepts
Abstract Syntax Trees (ast)
Parsing Expression Grammar (peg)
Elasticsearch Bool Queries
Dark-shipping
Feature Flags
Backward Compatibility Testing
Query Language Design
Boolean Algebra
Recursive Descent Parsing
Search Query Optimization
Gradual Rollout Strategies
A/B Testing In Production