Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How does database indexing work? (2008)

stackoverflow.com

Post reply on HN
Print view View original

51–60 of 62 posts

Re: How does database indexing work? (2008)

#51

Post by fabian2k »

snake_plissken wrote: post #45

Can someone expand on this statement (from the top answer, last paragraph): "Since indices are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided." Specifically "indexing fields used only for output", what…

That part is wrong if your database can perform index-only queries. In that case if all columns you query are part of the index the query can be answered from the index alone, so you don't have to read any parts of the actual table.

Re: How does database indexing work? (2008)

#52

Post by [deleted] »

geophile wrote: post #48
snake_plissken wrote: post #45

Can someone expand on this statement (from the top answer, last paragraph): "Since indices are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided." Specifically "indexing fields used only for output", what…

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…

[deleted]

Re: How does database indexing work? (2008)

#53

Post by uhoh-itsmaciek »

geophile wrote: post #48
snake_plissken wrote: post #45

Can someone expand on this statement (from the top answer, last paragraph): "Since indices are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided." Specifically "indexing fields used only for output", what…

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

Re: How does database indexing work? (2008)

#55

Post by unemphysbro »

eatonphil wrote: post #18

If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/

Phil, These are great! Thank you!

Re: How does database indexing work? (2008)

#56

Post by yardshop »

leto_ii wrote: post #54

Completely besides the important point, but is it the same guy who asked and answered the question? What am I missing?

I've seen it happen a bunch. Since StackOverflow is a Q&A format, if someone knows that many people will ask a question they know the answer to, they will write both. Preemptive questioning perhaps!

He also wrote the other question that he links to, How to index a database column, with the request to get answers for each major type of database. So he's asking not so much to learn the answer but to provide a place for others to provide a catalog of answers.

This is different of course from the case where someone asks a genuine question then comes back and writes an answer to themselves when they have learned it. This happens a lot too.

Re: How does database indexing work? (2008)

#57

Post by eatonphil »

unemphysbro wrote: post #55
eatonphil wrote: post #18

If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/

Phil, These are great! Thank you!

Thank you!

Re: How does database indexing work? (2008)

#58

Post by zerr »

eatonphil wrote: post #18

If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/

Do you implement transactions/ACID?

Re: How does database indexing work? (2008)

#59

Post by eatonphil »

zerr wrote: post #58
eatonphil wrote: post #18

If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/

Do you implement transactions/ACID?

Nope. It was a bad idea not to build in transaction support up front. It gets harder to build in later.

Re: How does database indexing work? (2008)

#60

Post by zaphirplane »

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

Post reply on HN