Architecture for a fast, low-noise N+1 Query Linter

[kiarash8112]

Hey everyone,

I've been looking into building a custom static analysis linter to detect N+1 database queries in our Go codebase.

The standard naive approach—finding a for loop and recursively walking the AST/Call Graph for every function call inside it to see if it hits a db.Query—has two fatal flaws:

1. It's incredibly slow: We end up re-tracing the same deep call stacks repeatedly.
2. High false-positive rate: It flags queries that happen to be inside a loop's call stack but don't actually depend on the loop's data (e.g., fetching a static config value inside a loop helper).

I'd like to propose a two-stage architectural approach to solve both the performance and accuracy problems

Stage 1: The Fast Filter (Pre-computed Call Graph)

Goal: Solve the O(N^2) speed problem by doing the heavy lifting once.

Instead of tracing top-down from every loop, we work bottom-up from our database sinks.

1. Identify Sinks: Scan the program once to find all direct callers of *sql.DB, *sql.Tx, etc. (our sinks).
2. Build Reverse Call Graph: Compute the whole-program call graph.
3. Pre-compute Transitive Callers: Do a Breadth-First Search backwards from the sinks. We build a global set: TransitivelyCallsDB = map[funcName]bool.

Now, when our linter visits a loop, checking if myHelperFunc() is dangerous is an instant O(1) map lookup. If it's not in the set, we skip it entirely.

Stage 2: The Accuracy Filter (Dataflow/Taint Tracking)

Goal: Eliminate false positives by proving the loop actually drives the query.

If a function call inside a loop passes Stage 1, we still need to prove it's a true N+1.

We apply basic taint analysis:

1. Source: We "taint" the loop iteration variable (e.g., item in for _, item := range items).
2. Propagate: We track how that tainted data flows through assignments and function arguments.
3. Sink Check: When we hit the database sink, we check its arguments.

If the database query arguments contain tainted data (e.g., db.Query("... id = ?", item.ID)), it is a high-confidence N+1. If the query arguments are clean/static (e.g., db.Query("SELECT version()")), we drop the warning as a false positive.

Questions for the community:

• Do you foresee any edge cases with interfaces or reflection breaking the Stage 1 call graph?

Would love to hear your thoughts on this architecture before starting the implementation.

---