6

I understand that index seek allows the server to quickly go to the desired page(s) by looking up the index, therefore the benefit is obtained by not having to read all pages of the queried table from disk into memory.

This question is assuming:

  1. there is huge memory for the entire db to live in memory,
  2. the table being queried has no indexing,
  3. the query is to SELECT data from a table where say rate>100
  4. the 1st query with above WHERE clause will do a scan to pull entire table's data pages from disk into memory (since there is no index on rate).

In this scenario, my question is to ask - for the subsequent queries on this table with the same WHERE clause (rate>50), the SQL engine will perform table scan on pages that already reside in memory. Does having an index or not on the rate column have any benefit to the 2nd query onwards when the entire table lives in memory and there is no need to access the disk?

0

7 Answers 7

23

Doing less work is almost always faster than doing more work.

Assuming both the base table and index are fully present in memory, the index seek will do a lot less work if the table is large.

This work manifests primarily as CPU time and waiting on memory fetches. Memory is fast compared with most persistent storage, but it's still very slow compared with a CPU.

The table scan will have to access many more memory pages, and test more rows to see if rate > x or not. Performing these comparison tests consumes CPU.

The index seek will locate the first matching row efficiently (by navigating down the b-tree), then scan to the end of the index following next-page pointers. It never needs to test individual rows to see if rate > x or not. The ordering of the index guarantees all rows found will match the predicate without making any value comparisons.

Assuming a rowstore layout, the base table will have the minimum possible number of rows per 8KB page—all in-row columns are present on the page.

The index is likely to be more dense than the base table, since it only contains the indexed data. With more rows per 8KB page, fewer page accesses are needed, compared to the base table case.

There are additional considerations, like how pages belonging to the target (table or index) are located in the first place. For a heap table, this is done using IAM pages. An index seek locates the root of the b-tree from metadata, then navigates as already described. These methods are different, but for a completely in-memory situation there are unlikely to be very measurable differences between the two.

Scanning the whole table will also require more locks and page latches to be taken, consuming CPU and potentially blocking concurrent writers.

Remember an index is a separate subset of the base data sorted differently. The trade-off for the more efficient searching is additional storage and index maintenance when the base data changes.

If you're concerned about a particular situation on particular hardware, run a benchmark.

19

Exactly the same arguments apply, only the speeds involved are much higher. Data still has to move from memory to CPU cache and into registers. The less data that has to move the sooner it completes. An index eliminates data from this movement.

Before, the disk to memory speed was the limiting factor. Memory to CPU was, in comparison, insignificant. Now disk reads have been eliminated reading RAM is the limiting factor. An index can help with this.

0
3

I see that other answers haven't covered an important aspect of indexes that you may not be familiar with - how indexes work and what they are.

This is obviously an oversimplification, but here's roughly what's going on:

Imagine you have a phone book with 100,000 entries. Each entry has a name, an address, and a phone number. The entries are sorted by names and then by addresses.

When you want to look up the phone number of John Smith in New York, it's fairly easy - you open a random place and see if you're too far in the book or not far enough. Then you take that halve and open that in a random place, etc. Executed perfectly, you only need to examine at most 17 entries before you've found your John.

Now imagine you want to find out who owns the phone number 12345678. You have no other option than to just go through all 100,000 entries and hope to find it.

Something quite similar happens with database tables. All rows in a table are logically sorted by the clustered index (often the primary key), so looking up by that is quick. But if you want to find rows by any other column, SQL Server must examine each and every one of them to find those that match.

This is where indexes come in. Each index is like a mini-table which copies the main table, but the rows are sorted by the indexed columns. Well, OK, an index is not a table, it's actually a special data structure called a "B-tree", which is even more efficient, but you can think of it as a mini-table.

An index doesn't usually contain ALL the columns in the main table - just the ones that are needed for sorting and predicate matching, plus the clustered index columns (if a table doesn't have a clustered index, it uses an internal row identifier instead). When you look things up by an index, SQL Server quickly finds the matching rows in the index and then uses the values in the clustered index columns to quickly find those rows in the main table and get the rest of the data from there.

SQL Server is also smart - if you're only interested in the indexed columns then it might not even touch the main table - it already has all the data it needs in the index itself. And as a developer you can also tell it to include extra columns in the index just for this purpose.

Of course the downside of this is that an index also takes up space and any changes to the main table also need to be reflected in the index (since it needs to be a perfect copy). So more storage used, more RAM used, slower inserts/updates/deletes, but faster selects. It's a trade-off.

This then also answers your question: even if all the rows of the main table fit in RAM, it will still be faster to use an index to look up data, because SQL Server will need to inspect vastly fewer rows. Inspecting 10GB worth of rows is still going to be slow, even if they are all in RAM.

0
0

Speed of retrieval. It is much more efficient to order data than to search for an individual object in a set of unordered data.

0

Generally, needing to access less data is faster -- whether than comes from disk or from memory. There are costs in bringing data from main memory into cache and into the CPU, so reducing this helps access costs.

I would however ask how often this query is needed; to balance the benefits of the index (faster retrieval) with the costs (slower insertion and updating, due to index maintenance) so as to best optimize overall workload.

To get good benefits from an index on Rate, it will need to be sufficiently selective. Selectivity refers to the percentage of rows that an index will match; one guideline is that an index should offer selectivity of 15% or lower to be worthwhile. Ideally your Rate > 100 and Rate > 50 conditions will select only a small proportion of the whole table, and only the data pages containing matched rows will need to be accessed.

One point -- 'Rate' doesn't sound like very much like an address for data, more like a result. Addresses for data are typically primary keys, category selectors, or selective foreign keys.

While putting an index on Rate will give you a reasonably efficient access pattern in a SQL DB, if you're running it often and have the entire dataset in memory it starts to makes me wonder whether this is being used for operational purposes rather than just reporting.

If this did happen to be an operational workload (ie run frequently or/ constantly intra-day) and performance was important, I would ask whether the datastructure really suited -- other possibilities could include maintaining a more specific set of matching rows if the Threshold is static, holding the set in Redis or application memory, considering whether near-time approximate answers are acceptable etc.

-1

You're absolutely right that in small databases, interfacing with humans, there's simply no point fretting over what indexes to put where.

So if you are optimizing for developer/maintainer time, then that's absolutely the right path to take: other than unavoidable primary keys, don't worry about indexes at all.

Indexes are about helping with scaling. When the number of rows, tables and queries get large, non-indexed table-scan searches scale linearly with the size of the database, and their impact scales with (db size * num queries).

That's still non-fatal for trivial queries, since memory allows maybe 20G/sec of throughput. Caching everything in memory, like on SSD, gives you a linear speedup, so it lets you get a certain number of times larger before things become a problem.

With an index on a billion row table, instead of taking up to a billion row reads, it does a max of 30 (because log2(billion) is 30, so a binary search only requires 30 reads). Even then, on your local PC, there's no point: the answer comes up within a few seconds anyway, so it's not worth the investment of time to figure out how to optimize it.

But on a server where you're having to process a lot of queries, having them fast is important.

-1

If there is no index there is also no key into the tables.

If there is no key, every inserts will scan the table to find a page where there is sufficient space to put the data.

Another problem of not having any key in the table is that, you could have duplicates rows that is very difficult to eliminate...

More counter performant will be all UPDATEs and DELETEs... Because without having any key/index, the only technique to be sure to contain concurrency during updates is to lock the entire table, at least temporarily... So it will results into a globally perfomance disaster, because all concurrent users will be waiting till the lock is release (pessimistic locking) or take a snapshot of the data (optimistic locking)- those two cases consuming time!

And finally, the huge amout of memory needed to try such a stupid behaviour, is not to have a RAM close to the size of the database, buch much more... When big queries that needs sorts (ORDER BY), DISTINCTs or GROUP BYs will be executed, temporary table are created by the SQL engine to do so, that needs some extra memory... and also memory is used for several level of caches : query execution plan, metadata, execution stats...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.