class: center, middle, inverse, title-slide # Database Querying with SQL ## Searching efficiently ### Ben Baumer ### SDS 192</br>April 22nd, 2020</br>(<a href="http://beanumber.github.io/sds192/lectures/mdsr_sql_05-keys.html" class="uri">http://beanumber.github.io/sds192/lectures/mdsr_sql_05-keys.html</a>) --- class: center, middle, inverse # Keys and Indexes --- background-image: url(http://static.libsyn.com/p/assets/c/2/1/b/c21be1062e52949b/Unused-Indexes-vs-Foreign-Keys.png) background-size: contain --- ## Keys and Indexes .footnote[https://en.wikipedia.org/wiki/Primary_key] - Keys: - `PRIMARY KEY`: unique, non-`NULL`, only one per table - `UNIQUE KEY`: unique, may include `NULL` - [`FOREIGN KEY`](https://en.wikipedia.org/wiki/Foreign_key): references primary key in another table -- - Indexes: - No constraints, just about speed - Take up space on disk - Will they be used? -- - A `PRIMARY KEY` is always indexed --- background-image: url(https://i.imgur.com/pDq0n.png) background-size: contain --- ## A DB without indexes is like Dory .center[] --- ## An index is a lookup table .center[] .footnote[https://en.wikipedia.org/wiki/Database_index] --- ## Consider a book index... .pull-left[  ] -- .pull-right[ - Helps us avoid checking each row (i.e., [table scan](https://en.wikipedia.org/wiki/Full_table_scan)) - Takes time to build! - Good index will reduce search time from `\(O(n)\)` to `\(O(log(n))\)` .footnote[https://en.wikipedia.org/wiki/Big_O_notation] ] --- ## What would be a good index for this class? .pull-left[  ] .pull-right[ - 60 students - last name? - home institution? - first name? - class year? ] --- ## So why not just build indexes on all the columns? .pull-left[  ] .pull-right[ - Takes up space on disk - Takes time to build - Slows down inserts - Not always that big of an improvement - What if index is length `\(n\)`? Or 1? ] --- background-image: url(http://static.libsyn.com/p/assets/c/2/1/b/c21be1062e52949b/Unused-Indexes-vs-Foreign-Keys.png) background-size: contain