Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

System-R Optimizer: Query Optimization and Cost Estimation

In course

CS-422: Database systems

This course is intended for students who want to understand modern large-scale data analysis systems and database systems. It covers a wide range of topics and technologies, and will prepare students to be able to build such systems as well as read and und ...

Description

This lecture covers the System-R Optimizer, a seminal project from the 70s with a significant influence on subsequent database systems. It explains the high-level idea of iterating over possible plans, estimating costs, and returning the cheapest to the user. The lecture details the steps involved in breaking queries into blocks, generating logical operators, and selecting the best access paths for tables. It also delves into join orderings, cost estimation, and the principle of optimality in query optimization. The instructor emphasizes the importance of interesting orders, selectivity estimates, and the challenges in cardinality estimation. The lecture concludes with a summary of the System R optimizer, highlighting its reliance on heuristics and cost-based optimization.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Anastasia Ailamaki

Official source

Related concepts (32)

Query optimization

Query optimization is a feature of many relational database management systems and other databases such as NoSQL and graph databases. The query optimizer attempts to determine the most efficient way to execute a given query by considering the possible query plans. Generally, the query optimizer cannot be accessed directly by users: once queries are submitted to the database server, and parsed by the parser, they are then passed to the query optimizer where optimization occurs.

Join (SQL)

A join clause in the Structured Query Language (SQL) combines columns from one or more tables into a new table. The operation corresponds to a join operation in relational algebra. Informally, a join stitches two tables and puts on the same row records with matching fields : INNER, LEFT OUTER, RIGHT OUTER, FULL OUTER and CROSS. To explain join types, the rest of this article uses the following tables: Department.DepartmentID is the primary key of the Department table, whereas Employee.DepartmentID is a foreign key.

Query plan

A query plan (or query execution plan) is a sequence of steps used to access data in a SQL relational database management system. This is a specific case of the relational model concept of access plans. Since SQL is declarative, there are typically many alternative ways to execute a given query, with widely varying performance. When a query is submitted to the database, the query optimizer evaluates some of the different, correct possible plans for executing the query and returns what it considers the best option.

Database

In computing, a database is an organized collection of data (also known as a data store) stored and accessed electronically through the use of a database management system. Small databases can be stored on a , while large databases are hosted on computer clusters or cloud storage. The design of databases spans formal techniques and practical considerations, including data modeling, efficient data representation and storage, query languages, security and privacy of sensitive data, and distributed computing issues, including supporting concurrent access and fault tolerance.

Sort-merge join

The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time.

Related lectures (48)

Common Multiplicand Speedup

Explores common multiplicand speedup through logical operations like bitwise AND and XOR to optimize the multiplication process.

Query Fusion, Nested Queries MOOC: Geographical Information Systems 1

Covers query fusion, nested queries, and SQL operators in a geographical context.

NoSQL Databases: Origins and Types MOOC: Geographical Information Systems 1

Covers the origins and types of NoSQL databases, focusing on MongoDB and CRUD operations.

Numbers and Booleans

Introduces numbers and booleans in Python, covering numeric types, arithmetic operations, logical operations, and comparisons.

Raster - Raster MOOC: Geographical Information Systems 2