Time Complexity: How SQL injection exploits queries
O(n)
0
0
How SQL injection exploits queries - Performance & Efficiency
Understanding Time Complexity
We want to understand how the time it takes to run a SQL query changes when someone tries to exploit it with SQL injection.
How does adding malicious input affect the work the database does?
Scenario Under Consideration
Analyze the time complexity of this vulnerable SQL query:
SELECT * FROM users WHERE username = '' OR '1'='1';
This query returns all users because the injected condition always matches.
Identify Repeating Operations
Look at what the database does repeatedly:
- Primary operation: Scanning the users table rows to check the condition.
- How many times: Once for each row in the users table.
How Execution Grows With Input
As the number of users grows, the database checks more rows because the injected condition matches all rows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 row checks |
| 100 | 100 row checks |
| 1000 | 1000 row checks |
Pattern observation: The work grows directly with the number of rows in the table.
Final Time Complexity
Time Complexity: O(n)
This means the database work grows linearly with the number of rows because it must check each one.
Common Mistake
[X] Wrong: "SQL injection only affects security, not performance."
[OK] Correct: Injected queries can cause the database to do much more work, slowing down the system as it checks many rows.
Interview Connect
Understanding how SQL injection affects query time helps you see why protecting queries is important for both security and performance.
Self-Check
"What if the query used an index on username? How would that change the time complexity when under SQL injection?"