Efficient Indexing Techniques for Database Optimization
Explore the basics of indexes, their high-level concepts, and the benefits they offer in efficient data retrieval. Learn about the structure of indexes, how they enhance search key fields, and their role in speeding up data selections. Dive into examples of composite keys and range queries, understanding how indexes can improve performance in database operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture 26: Index Professor Xiannong Meng Spring 2018 Lecture and activity contents are based on what Prof Chris R of Stanford used in his CS 145 in the fall 2016 term with permission
If you dont find it in the index, look very carefully through the entire catalog - Sears, Roebuck and Co., Consumers Guide, 1897 2
What you will learn about in this section 1. Indexes: Basics 2. ACTIVITY: Creating indexes 3
Indexes: High-level An index on a file speeds up selections on the search key fields for the index. Search key properties Any subset of attributes is not the same as key of a relation Example: On which attributes would you build indexes? Product(name, maker, price)
More precisely An index is a data structure mapping of a tuple of search keys to sets of rows in a database table Provides efficient lookup & retrieval by search key value- usually much faster than searching through all the rows of the database table Remember: a search key is not necessarily a primary key. They are in different domains. An index can store the full rows it points to (primary index) or pointers to those rows (secondary index) We ll mainly consider secondary indexes
Conceptual Example Russian_Novels What if we want to return all books published after 1867? The above table might be very expensive to search over row-by- row BID Title Author Published Full_text 001 War and Peace Tolstoy 1869 002 Crime and Punishment Dostoyevsky 1866 003 Anna Karenina Tolstoy 1877 SELECT * FROM Russian_Novels WHERE Published > 1867
Composite Keys Equality Query: Age = 12 and Sal = 90? 11 80 Name Age Sal 12 10 Bob 12 10 12 20 Range Query: Age = 5 and Sal > 5? Cal 11 80 13 75 <age,sal> not equal to <sal,age> Luda Tara 12 13 20 75 <Age, Sal> Composite keys in Dictionary Order. 10 20 12 12 10 20 11 12 12 13 75 13 75 80 11 80 On which attributes can we do range queries? <Sal, Age> <Age> <Sal>
Composite Keys Pro: When they work they work well We ll see a good case called index-only plans or covering indexes. Con: Guesses? (time and space) How to determine which index should be built?
Covering Indexes We say that an index is covering if the index contains all the needed attributes- meaning the query can be answered using the index meaning the query can be answered using the index alone without going into alone without going into the tables! the tables! covering for a specific query By_Yr_Index Published BID 1866 002 The needed attributes are the union of those in the SELECT and WHERE clauses 1869 001 1877 003 SELECT Published, BID FROM Russian_Novels WHERE Published > 1867 Example:
