Scaling Transit Queries: PostgreSQL Trigram Fuzzy Search and Sub-50ms Redis Caching in Bhara Koto
Handling phonetic Bengali/English bus stop queries and route matrix distance algorithms on low-spec hardware.
1. The Phonetic Spelling Challenge
In Bangladesh, bus stop and station names are spelled inconsistently. A commuter searching for 'Farmgate' might type 'Farmgate', 'Farmget', 'ফার্মগেট', or 'Farm gate'. Traditional exact string matching (`WHERE name = :query`) or simple `LIKE '%query%'` queries result in empty result sets or table scans that freeze the database.
We needed a search architecture that could tolerate spelling variations, perform phonetic proximity scoring, and execute in under 30 milliseconds on modest cloud instances.
2. pg_trgm GIN Indexing in PostgreSQL
We enabled the PostgreSQL `pg_trgm` (trigram) extension. Trigram search breaks strings into three-consecutive-character tokens and calculates similarity using the formula: similarity = (shared trigrams) / (total unique trigrams).
By creating a Generalized Inverted Index (GIN) on the concatenated English and Bengali names, PostgreSQL evaluates similarity without scanning raw table rows, executing fuzzy matching in 8-15ms.
-- Enable trigram extension
CREATE EXTENSION IF NOT EXISTS pg_trgm;
-- Create GIN index across both English and Bengali stop names
CREATE INDEX idx_transit_stops_trgm_search
ON transit_transitstop
USING gin ((name_en || ' ' || name_bn) gin_trgm_ops);
-- High-performance query with similarity threshold filter
SELECT id, name_en, name_bn, latitude, longitude,
similarity((name_en || ' ' || name_bn), %s) AS match_score
FROM transit_transitstop
WHERE (name_en || ' ' || name_bn) %% %s
ORDER BY match_score DESC
LIMIT 10;3. Graph Distance & Fare Band Math
Public transit routes are modeled as ordered sequences of stage nodes. When calculating fares, the system calculates the stage index distance between origin and destination stops, checks the transit mode (Bus, Metro Rail, CNG), applies the government minimum fare floor (e.g. 10 BDT for local buses, 20 BDT for Metro), and computes the per-kilometer rate.
For Dhaka Metro Rail, fare computation follows an exact official formula based on station stages: Base Rate (20 BDT) + (Distance in km × Rate per km), rounded deterministically to the nearest 10 BDT.
4. Sub-50ms Redis Caching Tier
Commuter traffic exhibits extreme locality: the top 200 origin-destination pairs (e.g., Mirpur 10 → Motijheel, Uttara → Farmgate) account for over 70% of all route queries.
We implemented a Redis cache layer where pre-calculated fare bands and route sequences are stored under composite keys `route_fare:{origin_id}:{destination_id}` with a 24-hour TTL. Cache hits resolve in 1.4 milliseconds, bypassing PostgreSQL completely during morning and evening rush hours.
Core Engineering Takeaways
- •Use PostgreSQL pg_trgm GIN indexes for multilingual, phonetic search instead of full table scans.
- •Model transit routes as ordered sequence nodes with deterministic fare band math.
- •Exploit commuter traffic locality by caching top route pairs in Redis for sub-2ms lookups.
- •Design for low-bandwidth mobile environments by minimizing payload JSON sizes.
View the complete architectural case study and source implementation.
View the complete architectural case study and source implementation.
Continue reading technical architecture insights.