Tags:concept database selectivity selection query Status:🟩

Query Selections

Summary

Query selection focuses on optimizing how databases retrieve data based on specific conditions. It involves choosing efficient methods, often using indexes, to filter and access relevant rows. The effectiveness of a query is influenced by selectivity, which measures how restrictive a condition is in narrowing down the results. High selectivity conditions return fewer rows, while low selectivity conditions return more. Simple selections involve single conditions, while complex selections handle multiple conditions, using techniques like conjunctions (AND) or disjunctions (OR) to optimize query performance.

Details

Query selection is about optimizing how queries retrieve data based on specific conditions. When a query asks for rows meeting a criteria (like year = 2024), the database must decide how to access this data most efficiently.

To do this, databases uses different types of indexes.

Selectivity

Selectivity is a measure of how restrictive or non-restrictive a condition is when filtering data. It refers to the fraction of rows in a table that match a given query condition.

High Selectivity

A condition is said to have high selectivity when it returns a small number of rows, meaning the condition significantly narrows down the result set. For example, querying for a specific, unique value or a rare combination of attributes.

SELECT * FROM Employees WHERE employeeID = 12345;

Low Selectivity

A condition has low selectivity when it returns a large portion of the table’s rows, meaning the condition is less restrictive. For example, querying for a broad range of values or common attributes.

SELECT * FROM Employees WHERE department = 'Sales';

Simple selections

Simple selections are queries that filter data based on a single table and condition, such as year = 1990 or studioName = 'Disney'. The processing strategies for simple selections depend on the availability and type of indexes:

For clustered indexes, point and range queries are efficiently processed using index seeks or scans.
For unclustered indexes, they are best used with high selectivity queries (queries that return fewer results).
No index: If no relevant index exists, a full table scan is required.
No good index: If no suitable or highly selective index exists, a full table scan is often preferred.

The database will typically prefer using an index if available to reduce the number of rows to scan. In cases where the condition is highly selective, the use of an index is especially efficient.

Index Seek: The database uses the index to retrieve only the matching tuples.
Filtering with Index: After using the index to retrieve matching rows, the database may apply additional conditions to further narrow the result set.

Complex selections

Complex selections involve queries with multiple conditions, often a combination of AND (conjunction) or OR (disjunction). These queries may require more sophisticated processing techniques to optimize performance:

Conjunction of Equality and Range Conditions: When the conditions are combined with an AND (e.g., year = 1990 AND studioName = 'Disney'), indexes can be used efficiently, with the most selective condition being chosen for index retrieval.
Disjunction (OR): For queries with OR conditions, the database has two primary strategies:
- Full Table Scan: Sometimes, especially when no relevant indexes exist, the entire table is scanned.
- Multiple AND Queries: The database can break the query into multiple AND conditions and process each part separately, using different indexes, then combine the results.

Examples

If we consider this query and these strategies

SELECT title
FROM Movie
WHERE year = 1990
AND studioName = 'Disney';

Different strategies:

Make a scan of the whole relation.
Find movies from 1990 using index, then filter.
Find Disney movies using index, then filter.
Combine two indexes to identify rows fulfilling both conditions.
Use one composite index to find Disney movies from 1990.
Find Disney movies from 1990 and their titles in a composite covering index.

	Here we would use the strategy 4, by finding the intersect between the indexes.
	For this we would use the strategy 6, where we would use the coveringIdx.
	We start by using the strategies are 2 on the index idIdx, and then strategy 4 on the index titleIdx.

INDBS Noter

Explorer