The query processor makes extensive use of a relational algebra tree representation to model and manipulate SQL queries. At various points within the tree, operations are performed on the data. Each operation is represented as a node in the tree. Nodes can have one or more expressions associated with them to specify columns, conditions, and calculations associated with the operation.

Some of the operators that might be present in the tree are:

  • Restrict — Reduces the number of output rows by eliminating those that fail to satisfy some condition applied to the input. Restrict operators appear in the tree from WHERE clauses and JOINs.
  • Project — Reduces the number of output columns by eliminating columns not present in a project list. Projection operators appear in the tree from SELECT statements, from the list of columns needed for a table, and for aggregations such as SUM.
  • Join — Combines two input tables into a single output table that contains some combination of rows from the inputs. Joins appear in the tree from the use of FROM clauses and from JOIN clauses.
  • Sort — Changes the ordering of rows in an input table to produce an output table in the desired order.
  • Table — Represents a table scan or an index scan, reading data from a given table by either its default index (table scan) or a specific index (index scan).

Leaf nodes of the tree are always references to database tables. The following figure illustrates a tree produced for the query.

Figure 1. Query relational tree model


This query lists the names and order dates for all customers whose orders were shipped on the same day the order was placed: 


SELECT Name, OrderDate
FROM Customer, Order
WHERE Customer.Custnum = Order.Custnum AND Order."OrderDate" = Order."ShipDate";