3 ms·

I don't understand why ``` SELECT total(amount) FROM orders WHERE createdAt BETWEEN '2020-01-01 00:00:00' AND '2020-12-31 23:59:59'; ``` would do a ful

I don't understand why ``` SELECT total(amount) FROM orders WHERE createdAt BETWEEN '2020-01-01 00:00:00' AND '2020-12-31 23:59:59'; ``` would do a full table scan. Wouldn't the engine be able to use the index to find just the correct rows and then only do the total on those?

tomnipotent 5y ago
Statistics. The query planner has decided that it's going to have to visit a lot of pages regardless, so rather than reading the index AND most of the table it can get the job done with less by just scanning the table.
- WJW 5y ago
  To elaborate on this with a concrete example: if ALL rows were created between 2020-01-01 00:00:00 and 2020-12-31 23:59:59, going to the index is pure overhead.
  - tomnipotent 5y ago
    Or even if it's most of the rows. The optimizer will determine a cost which includes data distribution, and the cumulative cost of an index scan + table seeks could still exceed just the cost of a table scan.
  - da_chicken 5y ago
    How do you know that's when the rows were created? Maybe it means when the orders were created, but the records are from a foreign system and they were inserted in a completely different order. More relevantly, how does the query engine know that the `createdAt` field has anything to do with the order of records stored on disk?
    - tomnipotent 5y ago
      > how does the query engine know It doesn't, really. When a query planner is deciding the best path for answering a query, it will generate many different plans with different costs. Estimations are sometimes wrong, so planners may try several different plans for the same query over time and eventually settle on the one that actually did the best. Databases are also constantly collecting statistics on the values in each column, such as min/max, distribution, cardinality, rows per page/block, values at different percentiles. It's possible for these statistics to change over time, either suddenly or slowly, and this can mean the cached plan is sub-optimal. Or maybe you're adding/removing indexes. Plans become stale, and new plans will need to be tested. So let's say you create an index on `createdAt`. When you ask for rows `WHERE createdAt >= '2020-01-01' AND createdAt < '2020-04-01'`, it's going to generate plans considering that index and compare it against a plan without that index. Because the index is sorted and we have a range query (min/max), the planner knows it can very quickly find the inner b-tree nodes that contain all rows that match the query and how many pages may need to be read from disk and how many rows that will include. It will then know exactly what data pages we need to scan to find the rows we're interested in. Without that index, it has no idea about the distribution of values of `createdAt`. It's very possible that 99% of all rows are sorted, but for whatever reason 1 row is completely out of place (should be row #100, but is row #10,000). Every row will need to be scanned to be sure. Even with the index, the database statistics include min/max values. Let's say we change our query to `WHERE createdAt >= '1900-01-01' AND createdAt < '2100-01-01'`, and it includes EVERY row in the table. The query planner will be able to figure this out, and will generate a less costly plan that just does a full table scan instead and skips the index.
dboreham 5y ago
Indexing isn't magic. You can define an ordered index on the createdAt field and your query could use that index if it feels by its notion of the best thing to do that it'd be worthwhile. You can do things to persuade it what to do. It's up to you.
- masklinn 5y ago
  The problem is that the article's explanation makes absolutely no sense: it claims that a full scan is performed because of the computation (function call) in the `select` clause. And worse, that indexing the column used in the function call fixes it: > But, It will still do a full table scan because we are using "amount" column to calculate the total. So, we need to put an index on "amount" column too. Seems to me like TFA tried it, saw that the index was not used, and invented a justification for it. And after adding the second index the query planner had collected the relevant information and started using the index, or something.
masklinn 5y ago
> Wouldn't the engine be able to use the index to find just the correct rows and then only do the total on those? Yeah, the explanation doesn't really make sense in general, though computing anything might be sufficient to throw off mysql's query optimiser.
CapriciousCptl 5y ago
I was curious so I tried it in postgres 13. Postgres, at least, uses the index to form a bitmap and scans that when aggregating in the first case (10% rows in the bitmap) and not in a second case WHERE "createdAt" BETWEEN '1990-01-01 00:00:00' AND '2020-12-31 23:59:59'; (100% rows in the bitmap, obviating the need for the intermediate step). I also tried ~20% rows (2019-2020) and the planner skipped the index. ''' CREATE TABLE temp (id SERIAL PRIMARY KEY, amount MONEY, "createdAt" TIMESTAMPTZ); CREATE INDEX ON temp ("createdAt"); INSERT INTO temp(id, "createdAt", amount) SELECT generate_series(1,1000000) AS id, NOW() + (random() * (interval '10 years')) - interval '10 years' AS createdAt, random() * 100::money AS amount. EXPLAIN SELECT sum(amount) FROM temp WHERE "createdAt" BETWEEN '2020-01-01 00:00:00' AND '2020-12-31 23:59:59'; Aggregate (cost=10286.06..10286.07 rows=1 width=8) -> Bitmap Heap Scan on temp (cost=2148.00..10033.48 rows=101032 width=8) Recheck Cond: (("createdAt" >= '2020-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone)) -> Bitmap Index Scan on "temp_createdAt_idx" (cost=0.00..2122.75 rows=101032 width=0) Index Cond: (("createdAt" >= '2020-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone)) And when running a longer query: Finalize Aggregate (cost=14596.71..14596.72 rows=1 width=8) -> Gather (cost=14596.49..14596.70 rows=2 width=8) Workers Planned: 2 -> Partial Aggregate (cost=13596.49..13596.50 rows=1 width=8) -> Parallel Seq Scan on temp (cost=0.00..12620.00 rows=390597 width=8) Filter: (("createdAt" >= '1990-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone))
- masklinn 5y ago
  FWIW you can indent with 4 spaces for a preformatted block e.g. CREATE TABLE temp (id SERIAL PRIMARY KEY, amount MONEY, "createdAt" TIMESTAMPTZ); CREATE INDEX ON temp ("createdAt"); INSERT INTO temp(id, "createdAt", amount) SELECT generate_series(1,1000000) AS id, NOW() + (random() * (interval '10 years')) - interval '10 years' AS createdAt, random() * 100::money AS amount;
- tomnipotent 5y ago
  Buffer pool plays a big part. Very possible all the data is already in-memory, and for certain data sizes it'll be faster to just follow leaf nodes start-to-finish than it is to determine what pages you can skip. Postgres buffer pool is a ring, and relies on "clock sweep" to decide what pages it can evict on each iteration. It has a shared buffer, and per-query buffers to eliminate shared buffer evictions (for costly queries). When doing index scans, worst-case the same page is being accessed in random order multiple times and it's evicted between those accesses so we end up with redundant disk I/O. Bitmap scans ensure each page is only scanned once and in-order, so it's a great solution when you need more than an index scan but less than a full table scan (worth of data), not to mention multiple indexes can be combined into one bitmap scan. If every page is already in memory, the query planner may pick plans that look sub-optimal if you factor in disk I/O but are otherwise very efficient in-memory.
da_chicken 5y ago
It depends on a lot of factors. It's almost always down to cardinality and organization. How many records are in the table, and what proportion of records are estimated to be necessary to read? If it's more than a given threshold, then the query engine may decide to just read everything than waste time sorting out which pages it needs and which it doesn't. I/O is slow, but CPU is not free. Is the table clustered on the `createdAt` field? If not, the system will not assume that the table records are going to be stored in any particular order that benefits the query execution. After all, the field may not represent when the record was created in this particular system. It will then estimate how many pages it thinks it will need to read. Again, at a certain threshold it will decide to just read every page in the table. Sometimes it's more expensive to figure out what to read and still end up reading 50% of the table instead of just reading everything and scanning through it quickly. Remember, databases almost always read from disk in pages that contain multiple records. They can't read just one record. They read the whole page and then read the records out of that. That's the smallest unit of I/O. If records are evenly distributed, then the system will need to read almost every page anyways. That's why clustering indexes help so much, but you can only cluster on one set of fields. As an aside for datetime thresholds it's a better idea to specify `WHERE createdAt >= '2020-01-01 00:00:00' AND createdAt < '2021-01-01 00:00:00'`. Different systems have different time precision. You don't want to miss records because of fractional seconds. Yes, it probably won't matter, but you can also just write it this way and not have a hole in your logic. BETWEEN is just syntactic sugar, too.

tomnipotent 5y ago

Statistics. The query planner has decided that it's going to have to visit a lot of pages regardless, so rather than reading the index AND most of the table it can get the job done with less by just scanning the table.

WJW 5y ago
To elaborate on this with a concrete example: if ALL rows were created between 2020-01-01 00:00:00 and 2020-12-31 23:59:59, going to the index is pure overhead.
- tomnipotent 5y ago
  Or even if it's most of the rows. The optimizer will determine a cost which includes data distribution, and the cumulative cost of an index scan + table seeks could still exceed just the cost of a table scan.
- da_chicken 5y ago
  How do you know that's when the rows were created? Maybe it means when the orders were created, but the records are from a foreign system and they were inserted in a completely different order. More relevantly, how does the query engine know that the `createdAt` field has anything to do with the order of records stored on disk?
  - tomnipotent 5y ago
    > how does the query engine know It doesn't, really. When a query planner is deciding the best path for answering a query, it will generate many different plans with different costs. Estimations are sometimes wrong, so planners may try several different plans for the same query over time and eventually settle on the one that actually did the best. Databases are also constantly collecting statistics on the values in each column, such as min/max, distribution, cardinality, rows per page/block, values at different percentiles. It's possible for these statistics to change over time, either suddenly or slowly, and this can mean the cached plan is sub-optimal. Or maybe you're adding/removing indexes. Plans become stale, and new plans will need to be tested. So let's say you create an index on `createdAt`. When you ask for rows `WHERE createdAt >= '2020-01-01' AND createdAt < '2020-04-01'`, it's going to generate plans considering that index and compare it against a plan without that index. Because the index is sorted and we have a range query (min/max), the planner knows it can very quickly find the inner b-tree nodes that contain all rows that match the query and how many pages may need to be read from disk and how many rows that will include. It will then know exactly what data pages we need to scan to find the rows we're interested in. Without that index, it has no idea about the distribution of values of `createdAt`. It's very possible that 99% of all rows are sorted, but for whatever reason 1 row is completely out of place (should be row #100, but is row #10,000). Every row will need to be scanned to be sure. Even with the index, the database statistics include min/max values. Let's say we change our query to `WHERE createdAt >= '1900-01-01' AND createdAt < '2100-01-01'`, and it includes EVERY row in the table. The query planner will be able to figure this out, and will generate a less costly plan that just does a full table scan instead and skips the index.

dboreham 5y ago

Indexing isn't magic. You can define an ordered index on the createdAt field and your query could use that index if it feels by its notion of the best thing to do that it'd be worthwhile. You can do things to persuade it what to do. It's up to you.

masklinn 5y ago
The problem is that the article's explanation makes absolutely no sense: it claims that a full scan is performed because of the computation (function call) in the `select` clause. And worse, that indexing the column used in the function call fixes it: > But, It will still do a full table scan because we are using "amount" column to calculate the total. So, we need to put an index on "amount" column too. Seems to me like TFA tried it, saw that the index was not used, and invented a justification for it. And after adding the second index the query planner had collected the relevant information and started using the index, or something.

masklinn 5y ago

> Wouldn't the engine be able to use the index to find just the correct rows and then only do the total on those? Yeah, the explanation doesn't really make sense in general, though computing anything might be sufficient to throw off mysql's query optimiser.

CapriciousCptl 5y ago

I was curious so I tried it in postgres 13. Postgres, at least, uses the index to form a bitmap and scans that when aggregating in the first case (10% rows in the bitmap) and not in a second case WHERE "createdAt" BETWEEN '1990-01-01 00:00:00' AND '2020-12-31 23:59:59'; (100% rows in the bitmap, obviating the need for the intermediate step). I also tried ~20% rows (2019-2020) and the planner skipped the index. ''' CREATE TABLE temp (id SERIAL PRIMARY KEY, amount MONEY, "createdAt" TIMESTAMPTZ); CREATE INDEX ON temp ("createdAt"); INSERT INTO temp(id, "createdAt", amount) SELECT generate_series(1,1000000) AS id, NOW() + (random() * (interval '10 years')) - interval '10 years' AS createdAt, random() * 100::money AS amount. EXPLAIN SELECT sum(amount) FROM temp WHERE "createdAt" BETWEEN '2020-01-01 00:00:00' AND '2020-12-31 23:59:59'; Aggregate (cost=10286.06..10286.07 rows=1 width=8) -> Bitmap Heap Scan on temp (cost=2148.00..10033.48 rows=101032 width=8) Recheck Cond: (("createdAt" >= '2020-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone)) -> Bitmap Index Scan on "temp_createdAt_idx" (cost=0.00..2122.75 rows=101032 width=0) Index Cond: (("createdAt" >= '2020-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone)) And when running a longer query: Finalize Aggregate (cost=14596.71..14596.72 rows=1 width=8) -> Gather (cost=14596.49..14596.70 rows=2 width=8) Workers Planned: 2 -> Partial Aggregate (cost=13596.49..13596.50 rows=1 width=8) -> Parallel Seq Scan on temp (cost=0.00..12620.00 rows=390597 width=8) Filter: (("createdAt" >= '1990-01-01 00:00:00-05'::timestamp with time zone) AND ("createdAt" <= '2020-12-31 23:59:59-05'::timestamp with time zone))

masklinn 5y ago
FWIW you can indent with 4 spaces for a preformatted block e.g. CREATE TABLE temp (id SERIAL PRIMARY KEY, amount MONEY, "createdAt" TIMESTAMPTZ); CREATE INDEX ON temp ("createdAt"); INSERT INTO temp(id, "createdAt", amount) SELECT generate_series(1,1000000) AS id, NOW() + (random() * (interval '10 years')) - interval '10 years' AS createdAt, random() * 100::money AS amount;
tomnipotent 5y ago
Buffer pool plays a big part. Very possible all the data is already in-memory, and for certain data sizes it'll be faster to just follow leaf nodes start-to-finish than it is to determine what pages you can skip. Postgres buffer pool is a ring, and relies on "clock sweep" to decide what pages it can evict on each iteration. It has a shared buffer, and per-query buffers to eliminate shared buffer evictions (for costly queries). When doing index scans, worst-case the same page is being accessed in random order multiple times and it's evicted between those accesses so we end up with redundant disk I/O. Bitmap scans ensure each page is only scanned once and in-order, so it's a great solution when you need more than an index scan but less than a full table scan (worth of data), not to mention multiple indexes can be combined into one bitmap scan. If every page is already in memory, the query planner may pick plans that look sub-optimal if you factor in disk I/O but are otherwise very efficient in-memory.

da_chicken 5y ago

It depends on a lot of factors. It's almost always down to cardinality and organization. How many records are in the table, and what proportion of records are estimated to be necessary to read? If it's more than a given threshold, then the query engine may decide to just read everything than waste time sorting out which pages it needs and which it doesn't. I/O is slow, but CPU is not free. Is the table clustered on the `createdAt` field? If not, the system will not assume that the table records are going to be stored in any particular order that benefits the query execution. After all, the field may not represent when the record was created in this particular system. It will then estimate how many pages it thinks it will need to read. Again, at a certain threshold it will decide to just read every page in the table. Sometimes it's more expensive to figure out what to read and still end up reading 50% of the table instead of just reading everything and scanning through it quickly. Remember, databases almost always read from disk in pages that contain multiple records. They can't read just one record. They read the whole page and then read the records out of that. That's the smallest unit of I/O. If records are evenly distributed, then the system will need to read almost every page anyways. That's why clustering indexes help so much, but you can only cluster on one set of fields. As an aside for datetime thresholds it's a better idea to specify `WHERE createdAt >= '2020-01-01 00:00:00' AND createdAt < '2021-01-01 00:00:00'`. Different systems have different time precision. You don't want to miss records because of fractional seconds. Yes, it probably won't matter, but you can also just write it this way and not have a hole in your logic. BETWEEN is just syntactic sugar, too.