How does database indexing work? (2008)

Post by geophile » Thu, Mar 10, 2022, 4:15 PM UTC

uhoh-itsmaciek wrote: post #53

geophile wrote: post #48

Earlier quoted context omitted.

I think that advice is not necessarily correct. Suppose you have this query: select a, b from T where x = 1 And suppose you have an index on x. You can locate the x=1 INDEX records using the index quickly (probably no more than 1-3 disk accesses). But then the qualifying TABLE records have to be retrieved. That index lookup could turn up thousands of qualifying records, and now you have to retrieve each record to get…

Right, Postgres supports this use case explicitly with INCLUDE [1], which can be more efficient than just indexing all the columns you need. Pretty sure SQL Server has something similar. [1]: https://www.postgresql.org/docs/current/sql-createindex.html

Yes, Postgres has been playing various tricks in the last few years, to make this optimization actually optimize things, but the Postgres MVCC approach makes it difficult. The problem is that index information can be stale, and that you often have to go to the indexed page to determine current state. They've made progress to lessen that "often" to "sometimes", but unless version information is added to indexes, they won't be able to fix this completely.

I was teaching a database course a couple of years ago, using Postgres, and in exercises on query optimization, I found it surprisingly difficult to get columns added to indexes to produce a convincing improvement.

Post by tonymet » Sat, Mar 12, 2022, 5:47 PM UTC

zaphirplane wrote: post #60

tonymet wrote: post #42

Take a large unordered text file and then create an ordered index in a separate file of word ==> line write a brief binary search algo to search the index. Compare searching the words with a "table scan" on the first file using grep, vs the binary search on the index. You will find the table scan is O(n) and your binary search is roughly O(log n) In 60 minutes you'll understand more about indexing than reading stack…

Now picture someone is updating the file at the same time you are searching and someone updating the index while you are searching and return to step 1 Lol

good follow up exercise. set up a mutex between reader and writer.

Re: How does database indexing work? (2008)

Re: How does database indexing work? (2008)