The Hidden Performance Cost of OR Conditions in SQL JOINs

Introduction

Have you ever written a SQL query with an OR condition in a JOIN clause and noticed it’s running slower than expected? You’re not alone. This seemingly innocent pattern can cause significant performance degradation, especially when dealing with hierarchical or complex relationships.

In this post, we’ll explore a real-world case study where a query using OR in an INNER JOIN was running significantly slower than expected, and how we optimized it by restructuring the query using a Common Table Expression (CTE), achieving substantial performance improvements.

The Problem: Why OR in JOINs is Problematic

Using OR conditions in JOIN clauses often creates performance issues, especially in hierarchical or many-to-many joins:

1. Index Usage Limitations

When you use OR in a join condition, the database query optimizer often cannot efficiently use indexes. Instead of using a simple index scan, it may need to:

Create multiple bitmaps (one for each condition)
Combine them using BitmapOr operations
Access the heap table to fetch actual data

This is significantly more expensive than a straightforward index scan.

2. Complex Execution Plans

The query optimizer struggles with OR conditions because it needs to evaluate multiple paths. This leads to:

More complex execution plans
Higher memory usage
Increased CPU overhead
Larger intermediate result sets

3. Cartesian Product Risks

OR conditions can create unintended Cartesian products, especially when combined with other joins. The OR predicate forces the planner to evaluate multiple join paths per row, multiplying intermediate cardinality before aggregation. This can cause the number of intermediate rows to explode, making subsequent operations (sorts, aggregations) much more expensive.

4. Predicate Pushdown Issues

The optimizer may not be able to push down filters early in the execution plan when OR conditions are present, meaning more rows are processed than necessary.

Real-World Case Study

Let’s examine a concrete example dealing with hierarchical data. Imagine we have a company structure with departments that can have sub-departments, and employees belong to departments. We need to get all employees for a department and its sub-departments.

The Problematic Query (First Approach)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


EXPLAIN ANALYZE
SELECT
    d.id AS department_id,
    d.name AS department_name,
    COUNT(e.id) AS employee_count,
    AVG(e.salary) AS avg_salary
FROM
    departments d
LEFT JOIN departments AS sub_dept ON d.id = sub_dept.parent_department_id
INNER JOIN employees e ON d.id = e.department_id OR e.department_id = sub_dept.id
GROUP BY
    d.id, d.name

Performance Characteristics:

Execution Time: Significantly slower due to complex bitmap operations
Rows Processed: Large number of intermediate rows
Employee Table Rows: Processes many unnecessary rows from the employees table
Memory Usage: High memory consumption for sorting operations
Index Usage: BitmapOr operations combined with heap access become expensive at scale

How the First Query Works (And Why It’s Slow)

Complex JOIN Logic: The query uses an OR condition (d.id = e.department_id OR e.department_id = sub_dept.id) to join employees to departments.
BitmapOr Operation: For each department, PostgreSQL creates two bitmaps:
- One for employees where d.id = e.department_id
- One for employees where e.department_id = sub_dept.id
- These are combined using BitmapOr, which is computationally expensive
Many Intermediate Rows: The query processes a large number of rows from the employees table before grouping, creating a large intermediate result set.
Memory Intensive: The query uses significant memory for hash operations and sorts many rows, consuming substantial memory resources.
Cartesian-like Products: The execution plan shows inefficient row multiplication, with many rows processed per loop iteration, indicating poor optimization.

The Optimized Query (Second Approach)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


EXPLAIN ANALYZE
WITH department_scope AS (
    SELECT id AS parent_id, id AS source_id
    FROM departments
    UNION ALL
    SELECT parent_department_id AS parent_id, id AS source_id
    FROM departments
    WHERE parent_department_id IS NOT NULL
)
SELECT
    d.id AS department_id,
    d.name AS department_name,
    COUNT(e.id) AS employee_count,
    AVG(e.salary) AS avg_salary
FROM
    departments d
INNER JOIN department_scope ds ON ds.parent_id = d.id
INNER JOIN employees e ON e.department_id = ds.source_id
WHERE
    d.id IN (...)
GROUP BY
    d.id, d.name

Performance Characteristics:

Execution Time: Significantly faster execution
Rows Processed: Far fewer intermediate rows
Employee Table Rows: Processes many fewer rows from the employees table
Memory Usage: Much lower memory consumption for sorting operations
Index Usage: Index Only Scan (highly efficient)

How the Second Query Works (And Why It’s Fast)

CTE Pre-processing: The department_scope CTE flattens the hierarchical relationship first:
- First part: Maps each department to itself (id AS parent_id, id AS source_id)
- Second part: Maps sub-departments to their parents (parent_department_id AS parent_id, id AS source_id)
Simple JOINs: The query uses clean ON conditions without OR, allowing the optimizer to use efficient index scans.
Efficient Index Usage: The query uses Index Only Scan, which means:
- Data is retrieved directly from the index
- No heap access is required
- Much faster than bitmap operations
Better Row Reduction: The query filters earlier in the execution plan, processing far fewer rows from employees compared to the first query.
Smaller Sorts: The query sorts significantly fewer rows, using much less memory.

Why the CTE Solution Works Better

1. Eliminates OR Conditions

The CTE approach transforms the hierarchical relationship into a flat structure that can use simple, efficient joins. Instead of:

1

ON d.id = e.department_id OR e.department_id = sub_dept.id

We get:

1
2


ON ds.parent_id = d.id
INNER JOIN employees e ON e.department_id = ds.source_id

This allows the optimizer to use straightforward index scans. Important note: The performance gain comes from simplifying join predicates — not from the CTE itself. The CTE here helps by restructuring the query shape, not by acting as an optimization fence.

2. Better Index Utilization

The Index Only Scan on the employees table index is much more efficient than BitmapOr with heap access because:

No heap access: Data comes directly from the index
Sequential reads: Index scans are more cache-friendly
Lower CPU overhead: No bitmap operations needed

Note on Bitmap Scans: Bitmap scans aren’t inherently “bad” — they’re fine for medium selectivity queries. They become expensive when repeated many times, combined with joins, or feeding large aggregates. The issue here is that BitmapOr operations combined with heap access become expensive at scale.

3. Reduces Intermediate Result Sets

By flattening the hierarchy first, the query eliminates the need to process many-to-many relationships multiple times. The CTE creates a clear mapping that the optimizer can use efficiently.

4. Simpler Execution Plan

Fewer complex operations (no BitmapOr) and cleaner join paths make the execution plan easier for the optimizer to handle and more predictable.

5. Better Predicate Pushdown

The filtering happens earlier in the execution plan, reducing the number of rows processed in subsequent operations.

Best Practices

1. Avoid OR in JOIN Conditions

When you need to join on multiple conditions, consider:

CTE approach (as shown above) - Best for hierarchical data
UNION ALL - When you have distinct, non-overlapping conditions
Separate queries - When the logic is fundamentally different
Restructure the data model - Sometimes a junction table or denormalization helps

2. Use CTEs for Complex Hierarchies

CTEs are excellent for:

Flattening hierarchical relationships
Pre-computing complex filters
Creating reusable intermediate results
Improving query readability

3. Profile Your Queries

Always use EXPLAIN ANALYZE to understand:

How many rows are being processed
What indexes are being used (or not used)
Where time is being spent
Memory usage patterns

4. Monitor Index Usage

Look for:

Index Only Scan - Best case scenario
Index Scan - Good, but requires heap access
Bitmap Index Scan - Acceptable, but can be improved
Seq Scan - Usually indicates missing or unused index

5. Consider Materialized Views

For frequently accessed hierarchical queries, consider creating materialized views that pre-compute the flattened relationships.

Alternative Solutions

Solution 1: UNION ALL Approach

If the conditions are mutually exclusive, you can use UNION ALL:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


SELECT d.id, d.name, COUNT(e.id) AS employee_count
FROM departments d
INNER JOIN employees e ON e.department_id = d.id
WHERE d.id IN (...)

UNION ALL

SELECT d.id, d.name, COUNT(e.id) AS employee_count
FROM departments d
INNER JOIN departments sub ON sub.parent_department_id = d.id
INNER JOIN employees e ON e.department_id = sub.id
WHERE d.id IN (...)

Important: When using UNION ALL with aggregations, you must re-aggregate the results in an outer query if you want accurate counts, otherwise counts will be duplicated across branches.

Pros:

Simple and straightforward
Each branch can use optimal indexes
Good for mutually exclusive conditions

Cons:

Code duplication
More verbose
Requires careful handling of aggregations (must re-aggregate if combining results)

Solution 2: Separate Queries

Sometimes it’s better to run separate queries and combine results in application code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


-- Query 1: Direct department employees
SELECT d.id, COUNT(e.id) FROM departments d
INNER JOIN employees e ON e.department_id = d.id
WHERE d.id IN (...)
GROUP BY d.id

-- Query 2: Sub-department employees
SELECT d.id, COUNT(e.id) FROM departments d
INNER JOIN departments sub ON sub.parent_department_id = d.id
INNER JOIN employees e ON e.department_id = sub.id
WHERE d.id IN (...)
GROUP BY d.id

Pros:

Each query is simple and fast
Easy to cache separately
Can parallelize execution

Cons:

More database round trips
Application-level aggregation needed
More complex application code

Solution 3: Junction Table

For many-to-many relationships, consider a junction table:

1
2
3
4
5
6


CREATE TABLE department_employee_mapping (
    department_id INT,
    employee_id INT,
    is_direct BOOLEAN,
    PRIMARY KEY (department_id, employee_id)
);

Pros:

Simple joins
Easy to maintain
Can add metadata (like is_direct)

Cons:

Requires data synchronization
Additional storage
More complex data model

Solution 4: Recursive CTE (for Deep Hierarchies)

For deeper hierarchies, use a recursive CTE:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


WITH RECURSIVE department_hierarchy AS (
    -- Base case: direct departments
    SELECT id, id AS root_id, 0 AS depth
    FROM departments
    WHERE id IN (...)

    UNION ALL

    -- Recursive case: sub-departments
    SELECT d.id, dh.root_id, dh.depth + 1
    FROM departments d
    INNER JOIN department_hierarchy dh ON d.parent_department_id = dh.id
)
SELECT dh.root_id, COUNT(e.id) AS employee_count
FROM department_hierarchy dh
INNER JOIN employees e ON e.department_id = dh.id
GROUP BY dh.root_id

Pros:

Handles arbitrary depth
Flexible and powerful
Standard SQL pattern

Cons:

Can be slower for very deep hierarchies
More complex to understand
May need depth limits

Conclusion

Using OR conditions in JOIN clauses is a common SQL anti-pattern that can lead to significant performance issues. The key problems are:

Inefficient index usage - BitmapOr operations instead of simple index scans
Large intermediate result sets - Processing more rows than necessary
Complex execution plans - Harder for the optimizer to optimize
Higher memory usage - More expensive sort and hash operations

The solution we demonstrated uses a CTE to flatten hierarchical relationships before joining, which:

Eliminates OR conditions
Enables efficient index usage (Index Only Scan)
Dramatically reduces intermediate result sets
Significantly improves execution time

Key Takeaways:

✅ Avoid OR in JOIN conditions - Restructure the query instead
✅ Use CTEs for hierarchical data - Flatten relationships first
✅ Profile with EXPLAIN ANALYZE - Understand what’s actually happening
✅ Monitor index usage - Index Only Scan is your friend
✅ Consider alternatives - UNION ALL, separate queries, or data model changes

Remember: The best query is not always the shortest one. Sometimes a slightly longer query that the optimizer can understand and optimize is much faster than a clever one-liner with OR conditions.