# Query rewriting

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Query_rewriting
> Markdown URL: https://mediated.wiki/source/Query_rewriting.md
> Source: https://en.wikipedia.org/wiki/Query_rewriting
> Source revision: 1356713796
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

'''Query rewriting''' is a typically automatic transformation that takes a set of [database](/source/database) tables, [views](/source/View_(SQL)), and/or [queries](/source/Query_language), usually [indices](/source/Database_index), often gathered data and query statistics, and other [metadata](/source/metadata), and yields a set of different queries, which produce the same results but execute with better performance (for example, faster, or with lower memory use).<ref>{{Cite book | doi=10.1007/978-0-387-39940-9_863|chapter = Query Rewriting|title = Encyclopedia of Database Systems| pages=2308–2309|year = 2009|last1 = Vassilakopoulos|first1 = Michael| last2=Tzouramanis| first2=Theodoros| last3=Terenziani| first3=Paolo| last4=Patel| first4=Chintan| last5=Weng| first5=Chunhua| last6=Romero| first6=Rafael| last7=Mazón| first7=Jose-Norberto| last8=Trujillo| first8=Juan| last9=Serrano| first9=Manuel| last10=Piattini| first10=Mario| last11=Buragohain| first11=Chiranjeeb| last12=Suri| first12=Subhash| last13=Zhu| first13=Xingquan| last14=Risch| first14=Tore| last15=Bu| first15=Yingyi| last16=Chi-Wing Wong| first16=Raymond| last17=Fu| first17=Ada Wai-Chee| last18=Chirkova| first18=Rada| last19=Gupta| first19=Amarnath| last20=Vechtomova| first20=Olga| last21=He| first21=Ben| last22=Risch| first22=Tore| last23=Tata| first23=Sandeep| last24=Patel| first24=Jignesh M.| last25=Lacroix| first25=Zoé| last26=Bouganim| first26=Luc| last27=Pitoura| first27=Evaggelia| last28=Neumann| first28=Thomas| last29=Tan| first29=Kian-Lee| last30=Pitoura| first30=Evaggelia| display-authors=29| isbn=978-0-387-35544-3}}</ref> Query rewriting can be based on [relational algebra](/source/relational_algebra) or an extension thereof (e.g. multiset relational algebra with sorting, aggregation and three-valued predicates i.e. NULLs as in the case of [SQL](/source/SQL)). The [equivalence rules](/source/Logical_equivalence) of relational algebra are exploited, in other words, different [query structure](/source/query_structure)s and orderings can be mathematically proven to yield the same result. For example, filtering on fields A and B, or cross joining R and S can be done in any order, but there can be a performance difference. Multiple operations may be combined, and operation orders may be altered.

The result of query rewriting may not be at the same [abstraction level](/source/abstraction_level) or [application programming interface](/source/application_programming_interface) (API) as the original set of queries (though often is). For example, the input queries may be in relational algebra or SQL, and the rewritten queries may be closer to the physical representation of the data, e.g. array operations. Query rewriting can also involve [materialization of views](/source/Materialized_view) and other subqueries; operations that may or may not be available to the API user. The query rewriting transformation can be [https://www.ibm.com/support/knowledgecenter/en/SSEPGG_10.1.0/com.ibm.db2.luw.admin.perf.doc/doc/c0024525.html aided by] creating indices from which the optimizer can choose (some database systems create their own indexes if deemed useful), mandating the use of specific indices, creating materialized and/or denormalized views, or helping a database system gather statistics on the data and query use, as the optimality depends on patterns in data and typical query usage.

Query rewriting may be rule based<ref>{{Cite web|url=http://citeseerx.ist.psu.edu/messages/downloadsexceeded.html|title=Extensible/Rule Based Query Rewrite Optimization in Starburst|last1=Pirahesh|first1=Hamid|last2=Hellerstein|first2=Joseph M.|access-date=2020-04-06}}</ref> or optimizer based. Some sources discuss query rewriting as a distinct step prior to optimization, operating at the level of the user accessible algebra API (e.g. SQL).{{Citation needed|date=April 2020}}

There are other, largely unrelated concepts also named similarly, for example, query rewriting by [search engines](/source/search_engines).<ref>{{Cite web|url=https://hughewilliams.com/2012/03/19/query-rewriting-in-search-engines/|title=Query Rewriting in Search Engines|last=Williams|first=Hugh E.|date=2012-03-20|website=Hugh E. Williams|language=en|access-date=2020-04-06}}</ref>

==See also==
* [Query optimization](/source/Query_optimization)

==References==
<references/>

{{Databases}}

{{DEFAULTSORT:Query Rewriting}}
Category:Data management
Category:Database management systems

---
Adapted from the Wikipedia article [Query rewriting](https://en.wikipedia.org/wiki/Query_rewriting) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Query_rewriting?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.