Are there any descriptions of search algorithms in the database for a non-key attribute?

Question

SQL

Please tell me where you can read about database search algorithms both by key and by non-key attribute. At the same time, it is interesting how the Index is used in the second case. There are suspicions that these algorithms differ in each DBMS, but any information will fit.

Answer 1

www.ozon.ru/context/detail/id/6573935 - a cool book on muscle. Explains how and what is searched + much more. According to postgres, it is better than the official docks, unfortunately, I did not find anything + there are various extensions that you need to read about separately. On monga - 10gen has good free courses that explain how and what happens inside mongo ( https://education.mongodb.com/ )

Answer 2

The principle is the same everywhere: if it is possible to use an index, it is used, but if there is no index or the database considers its use not rational, a full scan is performed.
Algorithms, as well as the types of indexes themselves, are different, mainly a B-tree, a hash table, sometimes an R-tree (maybe a kd tree also occurs, I didn’t go deep enough).
So, are you interested in these very algorithms? Then read "The Art of Programming" by Donald Knuth. If you need specific implementations in database servers, then the official documentation for the database you are interested in (do not forget that the best documentation is the source code).

Answer 3

There is a good book: Dan Toe - SQL Tuning for Professionals . The examples are built on Oracle, but all the principles are explained.
And here is another great book on all databases: use-the-index-luke.com

Answer 4

The way the database should decompose the query into elementary data access operations is decided by the so-called. Optimizer . MySQL also has it. Keywords mysql cost based optimizer.
Each database has its own optimizer, the algorithms are partially described in the documentation, and they have input parameters available to the user, for example, the so-called. "hints" (hints) - indications of the form "in this table you go to such and such an index, and in this one read all the data, but be sure to do it in a row." Keywordsmysql hints

Answer 5

I would recommend the book Database Systems. Full course . It describes various aspects of databases in some detail (and with examples) without being tied to specific systems.