Correlated subquery

Short description: Computer query in SQL

In a SQL database query, a correlated subquery (also known as a synchronized subquery) is a subquery (a query nested inside another query) that uses values from the outer query. This can have major impact on performance because the correlated subquery might get recomputed every time for each row of the outer query is processed. A correlated subquery can contain another correlated subquery.

## Contents

* 1 Examples
* 1.1 Correlated subqueries in the WHERE clause
* 1.2 Correlated subqueries in the SELECT clause
* 1.3 Correlated subqueries in the FROM clause
* 2 Computation of correlated subqueries
* 3 References
* 4 External links

## Examples

### Correlated subqueries in the WHERE clause

Here is an example for a typical correlated subquery. In this example, the objective is to find all employees whose salary is above average for their department.

SELECT employee_number, name
FROM employees emp
WHERE salary > (
SELECT AVG(salary)
FROM employees
WHERE department = emp.department);

In the above query the outer query is

SELECT employee_number, name
FROM employees emp
WHERE salary > ...

and the inner query (the correlated subquery) is

SELECT AVG(salary)
FROM employees
WHERE department = emp.department

In the above nested query the inner query has to be re-executed for each employee. (A sufficiently smart implementation may cache the inner query's result on a department-by-department basis, but even in the best case the inner query must be executed once per department.)

### Correlated subqueries in the SELECT clause

SELECT employee_number,
name,
(SELECT AVG(salary)
FROM employees
WHERE department = emp.department) AS department_average
FROM employees emp

### Correlated subqueries in the FROM clause

It is generally meaningless to have a correlated subquery in the FROM clause because the table in the FROM clause is needed to evaluate the outer query, but the correlated subquery in the FROM clause can't be evaluated before the outer query is evaluated, causing a chicken-and-egg problem. Specifically, MariaDB lists this as a limitation in its documentation.[1]

However, in some database systems, it is allowed to use correlated subqueries while joining in the FROM clause, referencing the tables listed before the join using a specified keyword, producing a number of rows in the correlated subquery and joining it to the table on the left. For example, in PostgreSQL, adding the keyword LATERAL before the right-hand subquery,[2] or in Microsoft SQL Server, using the keyword CROSS APPLY or OUTER APPLY instead of JOIN[3] achieves the effect.

## Computation of correlated subqueries

A commonly used computational method for a correlated subquery is to rewrite it into an equivalent flat query[4] (a process known as flattening[5] [6] [7] [8] or unnesting [9][10]). The algorithm development in this direction has an advantage of low complexity. Because this is a customized approach, existing database systems cannot flatten arbitrary correlated subqueries by following certain general rules. In addition, this approach requires high engineering efforts to implement flattening algorithms into a database engine. A general computational approach is to directly execute the nested loop by iterating all tuples of the correlated columns from the outer query block and executing the subquery as many times as the number of outer-loop tuples.[11] This simple approach has an advantage of general-purpose because it is not affected by the type of correlated operators or subquery structures. However, it has a high computational complexity. A GPU acceleration approach is used to significantly improve the performance of the nested method of high algorithmic complexity by exploiting massive parallelism and device memory locality on GPU,[12] which accomplishes the goal for both general-purpose software design and implementation and high performance in subquery processing.

## References

1. ↑ "Subquery Limitations". MariaDB Knowledgebase. https://mariadb.com/kb/en/subquery-limitations/#correlated-subqueries.
2. ↑ "Table Expressions - LATERAL Subqueries". https://www.postgresql.org/docs/current/queries-table-expressions.html#QUERIES-LATERAL.
3. ↑ "FROM clause plus JOIN, APPLY, PIVOT (Transact-SQL)". 2019-06-01. https://docs.microsoft.com/en-us/sql/t-sql/queries/from-transact-sql?view=sql-server-ver15.
4. ↑ Kim, Won (September 1982). "On Optimizing an SQL-like Nested Query". ACM Transactions on Database Systems 7 (3): 443–469. doi:10.1145/319732.319745.
5. ↑ "The SQLite Query Optimizer Overview - 11. Subquery Flattening". SQLite. https://www.sqlite.org/optoverview.html#subquery_flattening. "When a subquery occurs in the FROM clause of a SELECT, the simplest behavior is to evaluate the subquery into a transient table, then run the outer SELECT against the transient table. Such a plan can be suboptimal since the transient table will not have any indexes and the outer query (which is likely a join) will be forced to do a full table scan on the transient table. To overcome this problem, SQLite attempts to flatten subqueries in the FROM clause of a SELECT. This involves inserting the FROM clause of the subquery into the FROM clause of the outer query and rewriting expressions in the outer query that refer to the result set of the subquery. ..."
6. ↑ "Flattening FROM Clause Subqueries". Vertica. https://www.vertica.com/docs/latest/HTML/Content/Authoring/AnalyzingData/Queries/Subqueries/FlatteningFROMClauseSubqueriesAndViews.htm. "FROM clause subqueries are always evaluated before their containing query. In some cases, the optimizer flattens FROM clause subqueries so the query can execute more efficiently."
7. ↑ "Flattening a subquery into a normal join". Apache Derby. https://db.apache.org/derby/docs/10.16/tuning/ctuntransform36368.html. "Statements that include such subqueries can be flattened into joins only if the subquery does not introduce any duplicates into the result set..."
8. ↑ "Chapter 15: Abstract Query Plan Guide - Flattened subqueries". Sybase. https://infocenter.sybase.com/help/index.jsp?topic=/com.sybase.dc20023_1251/html/optimizer/X21240.htm. "Some subqueries can be flattened into joins. ..."
9. ↑ Neumann, Thomas; Kemper, Alfons (2015). "Unnesting Arbitrary Queries". Datenbanksysteme für Business, Technologie und Web (BTW 2015) (Gesellschaft für Informatik, Bonn): 383-402. ISSN 1617-5468. https://dblp.org/rec/conf/btw/0001K15.html.
10. ↑ Neumann, Thomas (2025). "Improving Unnesting of Complex Queries". Datenbanksysteme für Business, Technologie und Web (BTW 2025) (Gesellschaft für Informatik, Bonn): 25-47. doi:10.18420/BTW2025-01. ISSN 2944-7682. https://dblp.org/rec/conf/btw/000125.html.
11. ↑ Selinger, P. Griffiths; Astrahan, M. M.; Chamberlin, D. D.; Lorie, R. A.; Price, T. G. (1979). "Access path selection in a relational database management system". Proceedings of the 1979 ACM SIGMOD international conference on Management of data - SIGMOD '79. New York, NY, USA: Association for Computing Machinery. pp. 23–34. doi:10.1145/582095.582099. ISBN 089791001X.
12. ↑ Floratos, Sofoklis; Xiao, Mengbai; Wang, Hao; Guo, Chengxin; Yuan, Yuan; Lee, Rubao; Zhang, Xiaodong (2021). "NestGPU: Nested Query Processing on GPU". IEEE 37th International Conference on Data Engineering. pp. 1008–1019. https://ieeexplore.ieee.org/document/9458769.

## External links

* Correlated subquery with examples

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Correlated subquery. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Correlated_subquery&oldid=4229073"