public inbox for [email protected]help / color / mirror / Atom feed
Re: Custom explain options 9+ messages / 5 participants [nested] [flat]
* Re: Custom explain options @ 2024-01-14 21:47 Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Tomas Vondra @ 2024-01-14 21:47 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; pgsql-hackers On 1/13/24 17:13, Konstantin Knizhnik wrote: > > On 13/01/2024 4:51 pm, Tomas Vondra wrote: >> >> On 1/12/24 20:30, Konstantin Knizhnik wrote: >>> On 12/01/2024 7:03 pm, Tomas Vondra wrote: >>>> On 10/21/23 14:16, Konstantin Knizhnik wrote: >>>>> Hi hackers, >>>>> >>>>> EXPLAIN statement has a list of options (i.e. ANALYZE, BUFFERS, >>>>> COST,...) which help to provide useful details of query execution. >>>>> In Neon we have added PREFETCH option which shows information about >>>>> page >>>>> prefetching during query execution (prefetching is more critical for >>>>> Neon >>>>> architecture because of separation of compute and storage, so it is >>>>> implemented not only for bitmap heap scan as in Vanilla Postgres, but >>>>> also for seqscan, indexscan and indexonly scan). Another possible >>>>> candidate for explain options is local file cache (extra caching >>>>> layer >>>>> above shared buffers which is used to somehow replace file system >>>>> cache >>>>> in standalone Postgres). >>>> Not quite related to this patch about EXPLAIN options, but can you >>>> share >>>> some details how you implemented prefetching for the other nodes? >>>> >>>> I'm asking because I've been working on prefetching for index scans, so >>>> I'm wondering if there's a better way to do this, or how to do it in a >>>> way that would allow neon to maybe leverage that too. >>>> >>>> regards >>>> >>> Yes, I am looking at your PR. What we have implemented in Neon is more >>> specific to Neon architecture where storage is separated from compute. >>> So each page not found in shared buffers has to be downloaded from page >>> server. It adds quite noticeable latency, because of network roundtrip. >>> While vanilla Postgres can rely on OS file system cache when page is not >>> found in shared buffer (access to OS file cache is certainly slower than >>> to shared buffers >>> because of syscall and copying of page, but performance penaly is not >>> very large - less than 15%), Neon has no local files and so has to send >>> request to the socket. >>> >>> This is why we have to perform aggressive prefetching whenever it is >>> possible (when it it is possible to predict order of subsequent pages). >>> Unlike vanilla Postgres which implements prefetch only for bitmap heap >>> scan, we have implemented it for seqscan, index scan, indexonly scan, >>> bitmap heap scan, vacuum, pg_prewarm. >>> The main difference between Neon prefetch and vanilla Postgres prefetch >>> is that first one is backend specific. So each backend prefetches only >>> pages which it needs. >>> This is why we have to rewrite prefetch for bitmap heap scan, which is >>> using `fadvise` and assumes that pages prefetched by one backend in file >>> cache, can be used by any other backend. >>> >> I do understand why prefetching is important in neon (likely more than >> for core postgres). I'm interested in how it's actually implemented, >> whether it's somehow similar to how my patch does things or in some >> different (perhaps neon-specific way), and if the approaches are >> different then what are the pros/cons. And so on. >> >> So is it implemented in the neon-specific storage, somehow, or where/how >> does neon issue the prefetch requests? > > Neon mostly preservers Postgres prefetch mechanism, so we are using > PrefetchBuffer which checks if page is present in shared buffers > and if not - calls smgrprefetch. We are using own storage manager > implementation which instead of reading pages from local disk, download > them from page server. > And prefetch implementation in Neon storager manager is obviously also > different from one in vanilla Postgres which uses posix_fadvise. > Neon prefetch implementation inserts prefetch request in ring buffer and > sends it to the server. When read operation is performed we check if > there is correspondent prefetch request in ring buffer and if so - waits > its completion. > Thanks. Sure, neon has to use some custom prefetch implementation, considering not posix_fadvise, considering there's no local page cache in the architecture. The thing that was not clear to me is who decides what to prefetch, which code issues the prefetch requests etc. In the github links you shared I see it happens in the index AM code (in nbtsearch.c). That's interesting, because that's what my first prefetching patch did too - not the same way, ofc, but in the same layer. Simply because it seemed like the simplest way to do that. But the feedback was that's the wrong layer, and that it should happen in the executor. And I agree with that - the reasons are somewhere in the other thread. Based on what I saw in the neon code, I think it should be possible for neon to use "my" approach too, but that only works for the index scans, ofc. Not sure what to do about the other places. > As I already wrote - prefetch is done locally for each backend. And each > backend has its own connection with page server. It can be changed in > future when we implement multiplexing of page server connections. But > right now prefetch is local. And certainly prefetch can improve > performance only if we correctly predict subsequent page requests. > If not - then page server does useless jobs and backend has to waity and > consume all issues prefetch requests. This is why in prefetch > implementation for most of nodes we start with minimal prefetch > distance and then increase it. It allows to perform prefetch only for > such queries where it is really efficient (OLAP) and doesn't degrade > performance of simple OLTP queries. > Not sure I understand what's so important about prefetches being "local" for each backend. I mean even in postgres each backend prefetches it's own buffers, no matter what the other backends do. Although, neon probably doesn't have the cross-backend sharing through shared buffers etc. right? FWIW I certainly agree with the goal to not harm queries that can't benefit from prefetching. Ramping-up the prefetch distance is something my patch does too, for exactly this reason. > Out prefetch implementation is also compatible with parallel plans, but > here we need to preserve some range of pages for each parallel workers > instead of picking page from some shared queue on demand. It is one of > the major difference with Postgres prefetch using posix_fadvise: each > backend shoudl prefetch only those pages which it will going to read. > Understood. I have no opinion on this, though. >>> Concerning index scan we have implemented two different approaches: for >>> index only scan we try to prefetch leave pages and for index scan we >>> prefetch referenced heap pages. >> In my experience the IOS handling (only prefetching leaf pages) is very >> limiting, and may easily lead to index-only scans being way slower than >> regular index scans. Which is super surprising for users. It's why I >> ended up improving the prefetcher to optionally look at the VM etc. > > Well, my assumption was the following: prefetch is most efficient for > OLAP queries. > Although HTAP (hybrid transactional/analytical processing) is popular > trend now, > classical model is that analytic queries are performed on "historical" > data, which was already proceeded by vacuum and all-visible bits were > set in VM. > May be this assumption is wrong but it seems to me that if most heap > pages are not marked as all-visible, then optimizer should prefetch > bitmap scan to index-only scan. I think this assumption is generally reasonable, but it hinges on the assumption that OLAP queries have most indexes recently vacuumed and all-visible. I'm not sure it's wise to rely on that. Without prefetching it's not that important - the worst thing that would happen is that the IOS degrades into regular index-scan. But with prefetching these plans can "invert" with respect to cost. I'm not saying it's terrible or that IOS must have prefetching, but I think it's something users may run into fairly often. And it led me to rework the prefetching so that IOS can prefetch too ... > And for combination of index and heap bitmap scans we can efficiently > prefetch both index and heap pages. > >>> In both cases we start from prefetch distance 0 and increase it until it >>> reaches `effective_io_concurrency` for this relation. Doing so we try to >>> avoid prefetching of useless pages and slowdown of "point" lookups >>> returning one or few records. >>> >> Right, the regular prefetch ramp-up. My patch does the same thing. >> >>> If you are interested, you can look at our implementation in neon repo: >>> all source are available. But briefly speaking, each backend has its own >>> prefetch ring (prefetch requests which are waiting for response). The >>> key idea is that we can send several prefetch requests to page server >>> and then receive multiple replies. It allows to increased speed of OLAP >>> queries up to 10 times. >>> >> Can you point me to the actual code / branch where it happens? I did >> check the github repo, but I don't see anything relevant in the default >> branch (REL_15_STABLE_neon). There are some "prefetch" branches, but >> those seem abandoned. > > Implementation of prefetch mecnahism is in Neon extension: > https://github.com/neondatabase/neon/blob/60ced06586a6811470c16c6386daba79ffaeda13/pgxn/neon/pagesto... > > But concrete implementation of prefetch for particular nodes is > certainly inside Postgres. > For example, if you are interested how it is implemented for index scan, > then please look at: > https://github.com/neondatabase/postgres/blob/c1c2272f436ed9231f6172f49de219fe71a9280d/src/backend/a... > https://github.com/neondatabase/postgres/blob/c1c2272f436ed9231f6172f49de219fe71a9280d/src/backend/a... > https://github.com/neondatabase/postgres/blob/c1c2272f436ed9231f6172f49de219fe71a9280d/src/backend/a... > https://github.com/neondatabase/postgres/blob/c1c2272f436ed9231f6172f49de219fe71a9280d/src/backend/a... > https://github.com/neondatabase/postgres/blob/c1c2272f436ed9231f6172f49de219fe71a9280d/src/backend/a... > Thanks! Very helpful. As I said, I ended up moving the prefetching to the executor. For indexscans I think it should be possible for neon to benefit from that (in a way, it doesn't need to do anything except for overriding what PrefetchBuffer does). Not sure about the other places where neon needs to prefetch, I don't have ambition to rework those. > >> >>> Heikki thinks that prefetch can be somehow combined with async-io >>> proposal (based on io_uring). But right now they have nothing in common. >>> >> I can imagine async I/O being useful here, but I find the flow of I/O >> requests is quite complex / goes through multiple layers. Or maybe I >> just don't understand how it should work. > I also do not think that it will be possible to marry this two approaches. I didn't actually say it would be impossible - I think it seems like a use case where async I/O should be a natural fit. But I'm not sure to do that in a way that would not be super confusing and/or fragile when something unexpected happens (like a rescan, or maybe some change to the index structure - page split, etc.) regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> @ 2024-01-15 14:22 ` Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Konstantin Knizhnik @ 2024-01-15 14:22 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; pgsql-hackers On 14/01/2024 11:47 pm, Tomas Vondra wrote: > The thing that was not clear to me is who decides what to prefetch, > which code issues the prefetch requests etc. In the github links you > shared I see it happens in the index AM code (in nbtsearch.c). It is up to the particular plan node (seqscan, indexscan,...) which pages to prefetch. > > That's interesting, because that's what my first prefetching patch did > too - not the same way, ofc, but in the same layer. Simply because it > seemed like the simplest way to do that. But the feedback was that's the > wrong layer, and that it should happen in the executor. And I agree with > that - the reasons are somewhere in the other thread. > I read the arguments in https://www.postgresql.org/message-id/flat/8c86c3a6-074e-6c88-3e7e-9452b6a37b9b%40enterprisedb.com#f... Separating prefetch info in index scan descriptor is really good idea. It will be amazing to have generic prefetch mechanism for all indexes. But unfortunately I do not understand how it is possible. The logic of index traversal is implemented inside AM. Executor doesn't know it. For example for B-Tree scan we can prefetch: - intermediate pages - leave pages - referenced by TID heap pages Before we load next intermediate page, we do not know next leave pages. And before we load next leave page, we can not find out TIDs from this page. Another challenge - is how far we should prefetch (as far as I understand both your and our approach using dynamically extended prefetch window) > Based on what I saw in the neon code, I think it should be possible for > neon to use "my" approach too, but that only works for the index scans, > ofc. Not sure what to do about the other places. We definitely need prefetch for heap scan (it gives the most advantages in performance), for vacuum and also for pg_prewarm. Also I tried to implement it for custom indexes such as pg_vector. I still not sure whether it is possible to create some generic solution which will work for all indexes. I have also tried to implement alternative approach for prefetch based on access statistic. It comes from use case of seqscan of table with larger toasted records. So for each record we have to extract its TOAST data. It is done using standard index scan, but unfortunately index prefetch doesn't help much here: there is usually just one TOAST segment and so prefetch just have no chance to do something useful. But as far as heap records are accessed sequentially, there is good chance that toast table will also be accessed mostly sequentially. So we just can count number of sequential requests to each relation and if ratio or seq/rand accesses is above some threshold we can prefetch next pages of this relation. This is really universal approach but ... working mostly for TOAST table. >> As I already wrote - prefetch is done locally for each backend. And each >> backend has its own connection with page server. It can be changed in >> future when we implement multiplexing of page server connections. But >> right now prefetch is local. And certainly prefetch can improve >> performance only if we correctly predict subsequent page requests. >> If not - then page server does useless jobs and backend has to waity and >> consume all issues prefetch requests. This is why in prefetch >> implementation for most of nodes we start with minimal prefetch >> distance and then increase it. It allows to perform prefetch only for >> such queries where it is really efficient (OLAP) and doesn't degrade >> performance of simple OLTP queries. >> > Not sure I understand what's so important about prefetches being "local" > for each backend. I mean even in postgres each backend prefetches it's > own buffers, no matter what the other backends do. Although, neon > probably doesn't have the cross-backend sharing through shared buffers > etc. right? Sorry if my explanation was not clear:( > I mean even in postgres each backend prefetches it's own buffers, no matter what the other backends do. This is exactly the difference. In Neon such approach doesn't work. Each backend maintains it's own prefetch ring. And if prefetched page was not actually received, then the whole pipe is lost. I.e. backend prefetched pages 1,5,10. Then it need to read page 2. So it has to consume responses for 1,5,10 and issue another request for page 2. Instead of improving speed we are just doing extra job. So each backend should prefetch only those pages which it is actually going to read. This is why prefetch approach used in Postgres for example for parallel bitmap heap scan doesn't work for Neon. If you do `posic_fadvise` then prefetched page is placed in OS cache and can be used by any parallel worker. But in Neon each parallel worker should be given its own range of pages to scan and prefetch only this pages. > >> Well, my assumption was the following: prefetch is most efficient forOLAP queries. >> Although HTAP (hybrid transactional/analytical processing) is popular >> trend now, >> classical model is that analytic queries are performed on "historical" >> data, which was already proceeded by vacuum and all-visible bits were >> set in VM. >> May be this assumption is wrong but it seems to me that if most heap >> pages are not marked as all-visible, then optimizer should prefetch >> bitmap scan to index-only scan. > I think this assumption is generally reasonable, but it hinges on the > assumption that OLAP queries have most indexes recently vacuumed and > all-visible. I'm not sure it's wise to rely on that. > > Without prefetching it's not that important - the worst thing that would > happen is that the IOS degrades into regular index-scan. > I think that it is also problem without prefetch. There are cases where seqscan or bitmap heap scan are really much faster then IOS because last one has to perform a lot of visibility checks. Yes, certainly optimizer takes in account percent of all-visible pages.But with it is not tricial to adjust optimizer parameters so that it can really choose fastest plan. > But withprefetching these plans can "invert" with respect to cost. > > I'm not saying it's terrible or that IOS must have prefetching, but I > think it's something users may run into fairly often. And it led me to > rework the prefetching so that IOS can prefetch too ... > > I think that inspecting VM for prefetch is really good idea. > Thanks! Very helpful. As I said, I ended up moving the prefetching to > the executor. For indexscans I think it should be possible for neon to > benefit from that (in a way, it doesn't need to do anything except for > overriding what PrefetchBuffer does). Not sure about the other places > where neon needs to prefetch, I don't have ambition to rework those. > Once your PR will be merged, I will rewrite Neon prefetch implementation fopr indexces using your approach. ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> @ 2024-01-15 15:08 ` Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Tomas Vondra @ 2024-01-15 15:08 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; pgsql-hackers On 1/15/24 15:22, Konstantin Knizhnik wrote: > > On 14/01/2024 11:47 pm, Tomas Vondra wrote: >> The thing that was not clear to me is who decides what to prefetch, >> which code issues the prefetch requests etc. In the github links you >> shared I see it happens in the index AM code (in nbtsearch.c). > > > It is up to the particular plan node (seqscan, indexscan,...) which > pages to prefetch. > > >> >> That's interesting, because that's what my first prefetching patch did >> too - not the same way, ofc, but in the same layer. Simply because it >> seemed like the simplest way to do that. But the feedback was that's the >> wrong layer, and that it should happen in the executor. And I agree with >> that - the reasons are somewhere in the other thread. >> > I read the arguments in > > https://www.postgresql.org/message-id/flat/8c86c3a6-074e-6c88-3e7e-9452b6a37b9b%40enterprisedb.com#f... > > Separating prefetch info in index scan descriptor is really good idea. > It will be amazing to have generic prefetch mechanism for all indexes. > But unfortunately I do not understand how it is possible. The logic of > index traversal is implemented inside AM. Executor doesn't know it. > For example for B-Tree scan we can prefetch: > > - intermediate pages > - leave pages > - referenced by TID heap pages > My patch does not care about prefetching internal index pages. Yes, it's a limitation, but my assumption is the internal pages are maybe 0.1% of the index, and typically very hot / cached. Yes, if the index is not used very often, this may be untrue. But I consider it a possible future improvement, for some other patch. FWIW there's a prefetching patch for inserts into indexes (which only prefetches just the index leaf pages). > Before we load next intermediate page, we do not know next leave pages. > And before we load next leave page, we can not find out TIDs from this > page. > Not sure I understand what this is about. The patch simply calls the index AM function index_getnext_tid() enough times to fill the prefetch queue. It does not prefetch the next index leaf page, it however does prefetch the heap pages. It does not "stall" at the boundary of the index leaf page, or something. > Another challenge - is how far we should prefetch (as far as I > understand both your and our approach using dynamically extended > prefetch window) > By dynamic extension of prefetch window you mean the incremental growth of the prefetch distance from 0 to effective_io_concurrency? I don't think there's a better solution. There might be additional information that we could consider (e.g. expected number of rows for the plan, earlier executions of the scan, ...) but each of these has a failure more. >> Based on what I saw in the neon code, I think it should be possible for >> neon to use "my" approach too, but that only works for the index scans, >> ofc. Not sure what to do about the other places. > We definitely need prefetch for heap scan (it gives the most advantages > in performance), for vacuum and also for pg_prewarm. Also I tried to > implement it for custom indexes such as pg_vector. I still not sure > whether it is possible to create some generic solution which will work > for all indexes. > I haven't tried with pgvector, but I don't see why my patch would not work for all index AMs that cna return TID. > I have also tried to implement alternative approach for prefetch based > on access statistic. > It comes from use case of seqscan of table with larger toasted records. > So for each record we have to extract its TOAST data. > It is done using standard index scan, but unfortunately index prefetch > doesn't help much here: there is usually just one TOAST segment and so > prefetch just have no chance to do something useful. But as far as heap > records are accessed sequentially, there is good chance that toast table > will also be accessed mostly sequentially. So we just can count number > of sequential requests to each relation and if ratio or seq/rand > accesses is above some threshold we can prefetch next pages of this > relation. This is really universal approach but ... working mostly for > TOAST table. > Are you're talking about what works / doesn't work in neon, or about postgres in general? I'm not sure what you mean by "one TOAST segment" and I'd also guess that if both tables are accessed mostly sequentially, the read-ahead will do most of the work (in postgres). It's probably true that as we do a separate index scan for each TOAST-ed value, that can't really ramp-up the prefetch distance fast enough. Maybe we could have a mode where we start with the full distance? > >>> As I already wrote - prefetch is done locally for each backend. And each >>> backend has its own connection with page server. It can be changed in >>> future when we implement multiplexing of page server connections. But >>> right now prefetch is local. And certainly prefetch can improve >>> performance only if we correctly predict subsequent page requests. >>> If not - then page server does useless jobs and backend has to waity and >>> consume all issues prefetch requests. This is why in prefetch >>> implementation for most of nodes we start with minimal prefetch >>> distance and then increase it. It allows to perform prefetch only for >>> such queries where it is really efficient (OLAP) and doesn't degrade >>> performance of simple OLTP queries. >>> >> Not sure I understand what's so important about prefetches being "local" >> for each backend. I mean even in postgres each backend prefetches it's >> own buffers, no matter what the other backends do. Although, neon >> probably doesn't have the cross-backend sharing through shared buffers >> etc. right? > > > Sorry if my explanation was not clear:( > >> I mean even in postgres each backend prefetches it's own buffers, no >> matter what the other backends do. > > This is exactly the difference. In Neon such approach doesn't work. > Each backend maintains it's own prefetch ring. And if prefetched page > was not actually received, then the whole pipe is lost. > I.e. backend prefetched pages 1,5,10. Then it need to read page 2. So it > has to consume responses for 1,5,10 and issue another request for page 2. > Instead of improving speed we are just doing extra job. > So each backend should prefetch only those pages which it is actually > going to read. > This is why prefetch approach used in Postgres for example for parallel > bitmap heap scan doesn't work for Neon. > If you do `posic_fadvise` then prefetched page is placed in OS cache and > can be used by any parallel worker. > But in Neon each parallel worker should be given its own range of pages > to scan and prefetch only this pages. > I still don't quite see/understand the difference. I mean, even in postgres each backend does it's own prefetches, using it's own prefetch ring. But I'm not entirely sure about the neon architecture differences. Does this mean neon can do prefetching from the executor in principle? Could you perhaps describe a situation where the bitmap can prefetching (as implemented in Postgres) does not work for neon? >> >>> Well, my assumption was the following: prefetch is most efficient >>> forOLAP queries. >>> Although HTAP (hybrid transactional/analytical processing) is popular >>> trend now, >>> classical model is that analytic queries are performed on "historical" >>> data, which was already proceeded by vacuum and all-visible bits were >>> set in VM. >>> May be this assumption is wrong but it seems to me that if most heap >>> pages are not marked as all-visible, then optimizer should prefetch >>> bitmap scan to index-only scan. >> I think this assumption is generally reasonable, but it hinges on the >> assumption that OLAP queries have most indexes recently vacuumed and >> all-visible. I'm not sure it's wise to rely on that. >> >> Without prefetching it's not that important - the worst thing that would >> happen is that the IOS degrades into regular index-scan. >> > I think that it is also problem without prefetch. There are cases where > seqscan or bitmap heap scan are really much faster then IOS because last > one has to perform a lot of visibility checks. Yes, certainly optimizer > takes in account percent of all-visible pages.But with it is not tricial > to adjust optimizer parameters so that it can really choose fastest plan. True. There's more cases where it can happen, no doubt about it. But I think those cases are somewhat less likely. >> But withprefetching these plans can "invert" with respect to cost. >> >> I'm not saying it's terrible or that IOS must have prefetching, but I >> think it's something users may run into fairly often. And it led me to >> rework the prefetching so that IOS can prefetch too ... >> >> > > I think that inspecting VM for prefetch is really good idea. > >> Thanks! Very helpful. As I said, I ended up moving the prefetching to >> the executor. For indexscans I think it should be possible for neon to >> benefit from that (in a way, it doesn't need to do anything except for >> overriding what PrefetchBuffer does). Not sure about the other places >> where neon needs to prefetch, I don't have ambition to rework those. >> > Once your PR will be merged, I will rewrite Neon prefetch implementation > fopr indexces using your approach. > Well, maybe you could try doing rewriting it now, so that you can give some feedback to the patch. I'd appreciate that. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> @ 2024-01-15 20:42 ` Konstantin Knizhnik <[email protected]> 2024-01-16 15:38 ` Re: Custom explain options Tomas Vondra <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Konstantin Knizhnik @ 2024-01-15 20:42 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; pgsql-hackers On 15/01/2024 5:08 pm, Tomas Vondra wrote: > > My patch does not care about prefetching internal index pages. Yes, it's > a limitation, but my assumption is the internal pages are maybe 0.1% of > the index, and typically very hot / cached. Yes, if the index is not > used very often, this may be untrue. But I consider it a possible future > improvement, for some other patch. FWIW there's a prefetching patch for > inserts into indexes (which only prefetches just the index leaf pages). We have to prefetch pages at height-1 level (parents of leave pages) for IOS because otherwise prefetch pipeline is broken at each transition to next leave page. When we start with new leave patch we have to fill prefetch ring from the scratch which certainly has negative impact on performance. > Not sure I understand what this is about. The patch simply calls the > index AM function index_getnext_tid() enough times to fill the prefetch > queue. It does not prefetch the next index leaf page, it however does > prefetch the heap pages. It does not "stall" at the boundary of the > index leaf page, or something. Ok, now I fully understand your approach. Looks really elegant and works for all indexes. There is still issue with IOS and seqscan. > >> Another challenge - is how far we should prefetch (as far as I >> understand both your and our approach using dynamically extended >> prefetch window) >> > By dynamic extension of prefetch window you mean the incremental growth > of the prefetch distance from 0 to effective_io_concurrency? Yes > I don't > think there's a better solution. I tried one more solution: propagate information about expected number of fetched rows to AM. Based on this information it is possible to choose proper prefetch distance. Certainly it is not quote precise: we can scan large number rows but filter only few of them. This is why this approach was not committed in Neon. But I still think that using statistics for determining prefetch window is not so bad idea. May be it needs better thinking. > > There might be additional information that we could consider (e.g. > expected number of rows for the plan, earlier executions of the scan, > ...) but each of these has a failure more. I wrote reply above before reading next fragment:) So I have already tried it. > I haven't tried with pgvector, but I don't see why my patch would not > work for all index AMs that cna return TID. Yes, I agree. But it will be efficient only if getting next TIS is cheap - it is located on the same leaf page. > >> I have also tried to implement alternative approach for prefetch based >> on access statistic. >> It comes from use case of seqscan of table with larger toasted records. >> So for each record we have to extract its TOAST data. >> It is done using standard index scan, but unfortunately index prefetch >> doesn't help much here: there is usually just one TOAST segment and so >> prefetch just have no chance to do something useful. But as far as heap >> records are accessed sequentially, there is good chance that toast table >> will also be accessed mostly sequentially. So we just can count number >> of sequential requests to each relation and if ratio or seq/rand >> accesses is above some threshold we can prefetch next pages of this >> relation. This is really universal approach but ... working mostly for >> TOAST table. >> > Are you're talking about what works / doesn't work in neon, or about > postgres in general? > > I'm not sure what you mean by "one TOAST segment" and I'd also guess > that if both tables are accessed mostly sequentially, the read-ahead > will do most of the work (in postgres). Yes, I agree: in case of vanilla Postgres OS will do read-ahead. But not in Neon. By one TOAST segment I mean "one TOAST record - 2kb. > It's probably true that as we do a separate index scan for each TOAST-ed > value, that can't really ramp-up the prefetch distance fast enough. > Maybe we could have a mode where we start with the full distance? Sorry, I do not understand. Especially in this case large prefetch window is undesired. Most of records fits in 2kb, so we need to fetch onely one head (TOAST) record per TOAST index search. >> This is exactly the difference. In Neon such approach doesn't work. >> Each backend maintains it's own prefetch ring. And if prefetched page >> was not actually received, then the whole pipe is lost. >> I.e. backend prefetched pages 1,5,10. Then it need to read page 2. So it >> has to consume responses for 1,5,10 and issue another request for page 2. >> Instead of improving speed we are just doing extra job. >> So each backend should prefetch only those pages which it is actually >> going to read. >> This is why prefetch approach used in Postgres for example for parallel >> bitmap heap scan doesn't work for Neon. >> If you do `posic_fadvise` then prefetched page is placed in OS cache and >> can be used by any parallel worker. >> But in Neon each parallel worker should be given its own range of pages >> to scan and prefetch only this pages. >> > I still don't quite see/understand the difference. I mean, even in > postgres each backend does it's own prefetches, using it's own prefetch > ring. But I'm not entirely sure about the neon architecture differences > I am not speaking about your approach. It will work with Neon as well. I am describing why implementation of prefetch for heap bitmap scan doesn't work for Neon: it issues prefetch requests for pages which never accessed by this parallel worker. > Does this mean neon can do prefetching from the executor in principle? > > Could you perhaps describe a situation where the bitmap can prefetching > (as implemented in Postgres) does not work for neon? > I am speaking about prefetch implementation in nodeBitmpapHeapScan. Prefetch iterator is not synced with normal iterator, i.e. they can return different pages. > > Well, maybe you could try doing rewriting it now, so that you can give > some feedback to the patch. I'd appreciate that. I will try. Best regards, Konstantin ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> @ 2024-01-16 15:38 ` Tomas Vondra <[email protected]> 2024-01-16 16:07 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Tomas Vondra @ 2024-01-16 15:38 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; pgsql-hackers On 1/15/24 21:42, Konstantin Knizhnik wrote: > > On 15/01/2024 5:08 pm, Tomas Vondra wrote: >> >> My patch does not care about prefetching internal index pages. Yes, it's >> a limitation, but my assumption is the internal pages are maybe 0.1% of >> the index, and typically very hot / cached. Yes, if the index is not >> used very often, this may be untrue. But I consider it a possible future >> improvement, for some other patch. FWIW there's a prefetching patch for >> inserts into indexes (which only prefetches just the index leaf pages). > > We have to prefetch pages at height-1 level (parents of leave pages) for > IOS because otherwise prefetch pipeline is broken at each transition to > next leave page. > When we start with new leave patch we have to fill prefetch ring from > the scratch which certainly has negative impact on performance. > By "broken" you mean that you prefetch items only from a single leaf page, so immediately after reading the next one nothing is prefetched. Correct? Yeah, I had this problem initially too, when I did the prefetching in the index AM code. One of the reasons why it got moved to the executor. > >> Not sure I understand what this is about. The patch simply calls the >> index AM function index_getnext_tid() enough times to fill the prefetch >> queue. It does not prefetch the next index leaf page, it however does >> prefetch the heap pages. It does not "stall" at the boundary of the >> index leaf page, or something. > > Ok, now I fully understand your approach. Looks really elegant and works > for all indexes. > There is still issue with IOS and seqscan. > Not sure. For seqscan, I think this has nothing to do with it. Postgres relies on read-ahad to do the work - of course, if that doesn't work (e.g. for async/direct I/O that'd be the case), an improvement will be needed. But it's unrelated to this patch, and I'm certainly not saying this patch does that. I think Thomas/Andres did some work on that. For IOS, I think the limitation that this does not prefetch any index pages (especially the leafs) is there, and it'd be nice to do something about it. But I see it as a separate thing, which I think does need to happen in the index AM layer (not in the executor). > > >> >>> Another challenge - is how far we should prefetch (as far as I >>> understand both your and our approach using dynamically extended >>> prefetch window) >>> >> By dynamic extension of prefetch window you mean the incremental growth >> of the prefetch distance from 0 to effective_io_concurrency? > > Yes > >> I don't >> think there's a better solution. > > I tried one more solution: propagate information about expected number > of fetched rows to AM. Based on this information it is possible to > choose proper prefetch distance. > Certainly it is not quote precise: we can scan large number rows but > filter only few of them. This is why this approach was not committed in > Neon. > But I still think that using statistics for determining prefetch window > is not so bad idea. May be it needs better thinking. > I don't think we should rely on this information too much. It's far too unreliable - especially the planner estimates. The run-time data may be more accurate, but I'm worried it may be quite variable (e.g. for different runs of the scan). My position is to keep this as simple as possible, and prefer to be more conservative when possible - that is, shorter prefetch distances. In my experience the benefit of prefetching is subject to diminishing returns, i.e. going from 0 => 16 is way bigger difference than 16 => 32. So better to stick with lower value instead of wasting resources. > >> >> There might be additional information that we could consider (e.g. >> expected number of rows for the plan, earlier executions of the scan, >> ...) but each of these has a failure more. > > I wrote reply above before reading next fragment:) > So I have already tried it. > >> I haven't tried with pgvector, but I don't see why my patch would not >> work for all index AMs that cna return TID. > > > Yes, I agree. But it will be efficient only if getting next TIS is > cheap - it is located on the same leaf page. > Maybe. I haven't tried/thought about it, but yes - if it requires doing a lot of work in between the prefetches, the benefits of prefetching will diminish naturally. Might be worth doing some experiments. > >> >>> I have also tried to implement alternative approach for prefetch based >>> on access statistic. >>> It comes from use case of seqscan of table with larger toasted records. >>> So for each record we have to extract its TOAST data. >>> It is done using standard index scan, but unfortunately index prefetch >>> doesn't help much here: there is usually just one TOAST segment and so >>> prefetch just have no chance to do something useful. But as far as heap >>> records are accessed sequentially, there is good chance that toast table >>> will also be accessed mostly sequentially. So we just can count number >>> of sequential requests to each relation and if ratio or seq/rand >>> accesses is above some threshold we can prefetch next pages of this >>> relation. This is really universal approach but ... working mostly for >>> TOAST table. >>> >> Are you're talking about what works / doesn't work in neon, or about >> postgres in general? >> >> I'm not sure what you mean by "one TOAST segment" and I'd also guess >> that if both tables are accessed mostly sequentially, the read-ahead >> will do most of the work (in postgres). > > Yes, I agree: in case of vanilla Postgres OS will do read-ahead. But not > in Neon. > By one TOAST segment I mean "one TOAST record - 2kb. > Ah, you mean "TOAST chunk". Yes, if a record fits into a single TOAST chunk, my prefetch won't work. Not sure what to do for neon ... > >> It's probably true that as we do a separate index scan for each TOAST-ed >> value, that can't really ramp-up the prefetch distance fast enough. >> Maybe we could have a mode where we start with the full distance? > > Sorry, I do not understand. Especially in this case large prefetch > window is undesired. > Most of records fits in 2kb, so we need to fetch onely one head (TOAST) > record per TOAST index search. > Yeah, I was confused what you mean by "segment". My point was that if a value is TOAST-ed into multiple chunks, maybe we should allow more aggressive prefetching instead of the slow ramp-up ... But yeah, if there's just one TOAST chunk, that does not help. > >>> This is exactly the difference. In Neon such approach doesn't work. >>> Each backend maintains it's own prefetch ring. And if prefetched page >>> was not actually received, then the whole pipe is lost. >>> I.e. backend prefetched pages 1,5,10. Then it need to read page 2. So it >>> has to consume responses for 1,5,10 and issue another request for >>> page 2. >>> Instead of improving speed we are just doing extra job. >>> So each backend should prefetch only those pages which it is actually >>> going to read. >>> This is why prefetch approach used in Postgres for example for parallel >>> bitmap heap scan doesn't work for Neon. >>> If you do `posic_fadvise` then prefetched page is placed in OS cache and >>> can be used by any parallel worker. >>> But in Neon each parallel worker should be given its own range of pages >>> to scan and prefetch only this pages. >>> >> I still don't quite see/understand the difference. I mean, even in >> postgres each backend does it's own prefetches, using it's own prefetch >> ring. But I'm not entirely sure about the neon architecture differences >> > I am not speaking about your approach. It will work with Neon as well. > I am describing why implementation of prefetch for heap bitmap scan > doesn't work for Neon: > it issues prefetch requests for pages which never accessed by this > parallel worker. > >> Does this mean neon can do prefetching from the executor in principle? >> >> Could you perhaps describe a situation where the bitmap can prefetching >> (as implemented in Postgres) does not work for neon? >> > > I am speaking about prefetch implementation in nodeBitmpapHeapScan. > Prefetch iterator is not synced with normal iterator, i.e. they can > return different pages. > Ah, now I think I understand. The workers don't share memory, so the pages prefetched by one worker are wasted if some other worker ends up processing them. >> >> Well, maybe you could try doing rewriting it now, so that you can give >> some feedback to the patch. I'd appreciate that. > > I will try. > Thanks! -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-16 15:38 ` Re: Custom explain options Tomas Vondra <[email protected]> @ 2024-01-16 16:07 ` Konstantin Knizhnik <[email protected]> 2024-01-24 01:54 ` Re: Custom explain options David G. Johnston <[email protected]> 2024-07-22 15:10 ` Re: Custom explain options Pavel Stehule <[email protected]> 0 siblings, 2 replies; 9+ messages in thread From: Konstantin Knizhnik @ 2024-01-16 16:07 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; pgsql-hackers On 16/01/2024 5:38 pm, Tomas Vondra wrote: > By "broken" you mean that you prefetch items only from a single leaf > page, so immediately after reading the next one nothing is prefetched. > Correct? Yes, exactly. It means that reading first heap page from next leaf page will be done without prefetch which in case of Neon means roundtrip with page server (~0.2msec within one data center). > Yeah, I had this problem initially too, when I did the > prefetching in the index AM code. One of the reasons why it got moved to > the executor. Yeh, it works nice for vanilla Postgres. You call index_getnext_tid() and when it reaches end of leaf page it reads next read page. Because of OS read-ahead this read is expected to be fast even without prefetch. But not in Neon case - we have to download this page from page server (see above). So ideal solution for Neon will be to prefetch both leave pages and referenced heap pages. And prefetch of last one should be initiated as soon as leaf page is loaded. Unfortunately it is non-trivial to implement and current index scan prefetch implementation for Neon is not doing it. ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-16 15:38 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-16 16:07 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> @ 2024-01-24 01:54 ` David G. Johnston <[email protected]> 1 sibling, 0 replies; 9+ messages in thread From: David G. Johnston @ 2024-01-24 01:54 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; +Cc: Tomas Vondra <[email protected]>; pgsql-hackers Came across this while looking for patches to review. IMO this thread has been hijacked to the point of being not useful for the subject. I suggest this discussion regarding prefetch move to its own thread and this thread and commitfest entry be ended/returned with feedback. Also IMO, the commitfest is not for early stage idea patches. The stuff on there that is ready for review should at least be thought of by the original author as something they would be willing to commit. I suggest you post the most recent patch and a summary of the discussion to a new thread that hopefully won't be hijacked. Consistent and on-topic replies will keep the topic front-and-center on the lists until a patch is ready for consideration. David J. ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: Custom explain options 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> 2024-01-16 15:38 ` Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-16 16:07 ` Re: Custom explain options Konstantin Knizhnik <[email protected]> @ 2024-07-22 15:10 ` Pavel Stehule <[email protected]> 1 sibling, 0 replies; 9+ messages in thread From: Pavel Stehule @ 2024-07-22 15:10 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; +Cc: Tomas Vondra <[email protected]>; pgsql-hackers Hi po 22. 7. 2024 v 17:08 odesílatel Konstantin Knizhnik <[email protected]> napsal: > > On 16/01/2024 5:38 pm, Tomas Vondra wrote: > > By "broken" you mean that you prefetch items only from a single leaf > > page, so immediately after reading the next one nothing is prefetched. > Correct? > > > Yes, exactly. It means that reading first heap page from next leaf page > will be done without prefetch which in case of Neon means roundtrip with > page server (~0.2msec within one data center). > > > Yeah, I had this problem initially too, when I did the > prefetching in the index AM code. One of the reasons why it got moved to > the executor. > > Yeh, it works nice for vanilla Postgres. You call index_getnext_tid() and > when it reaches end of leaf page it reads next read page. Because of OS > read-ahead this read is expected to be fast even without prefetch. But not > in Neon case - we have to download this page from page server (see above). > So ideal solution for Neon will be to prefetch both leave pages and > referenced heap pages. And prefetch of last one should be initiated as soon > as leaf page is loaded. Unfortunately it is non-trivial to implement and > current index scan prefetch implementation for Neon is not doing it. > What is the current state of this patch - it is abandoned? It needs a rebase. Regards Pavel ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v7 06/13] table_scan_bitmap_next_block() returns lossy or exact @ 2024-02-27 01:34 Melanie Plageman <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Melanie Plageman @ 2024-02-27 01:34 UTC (permalink / raw) Future commits will remove the TBMIterateResult from BitmapHeapNext() -- pushing it into the table AM-specific code. So, the table AM must inform BitmapHeapNext() whether or not the current block is lossy or exact for the purposes of the counters used in EXPLAIN. --- src/backend/access/heap/heapam_handler.c | 5 ++++- src/backend/executor/nodeBitmapHeapscan.c | 10 +++++----- src/include/access/tableam.h | 14 ++++++++++---- 3 files changed, 19 insertions(+), 10 deletions(-) diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index c9b9b4c00f1..10c1c3b616b 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2112,7 +2112,8 @@ heapam_estimate_rel_size(Relation rel, int32 *attr_widths, static bool heapam_scan_bitmap_next_block(TableScanDesc scan, - TBMIterateResult *tbmres) + TBMIterateResult *tbmres, + bool *lossy) { HeapScanDesc hscan = (HeapScanDesc) scan; BlockNumber block = tbmres->blockno; @@ -2240,6 +2241,8 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, Assert(ntup <= MaxHeapTuplesPerPage); hscan->rs_ntuples = ntup; + *lossy = tbmres->ntuples < 0; + return ntup > 0; } diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index a6b98fa12a1..b2397fe2054 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -211,7 +211,7 @@ BitmapHeapNext(BitmapHeapScanState *node) for (;;) { - bool valid; + bool valid, lossy; CHECK_FOR_INTERRUPTS(); @@ -232,12 +232,12 @@ BitmapHeapNext(BitmapHeapScanState *node) BitmapAdjustPrefetchIterator(node, tbmres->blockno); - valid = table_scan_bitmap_next_block(scan, tbmres); + valid = table_scan_bitmap_next_block(scan, tbmres, &lossy); - if (tbmres->ntuples >= 0) - node->exact_pages++; - else + if (lossy) node->lossy_pages++; + else + node->exact_pages++; if (!valid) { diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index c43a8b3dea5..f1d0d4b78e3 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -796,6 +796,9 @@ typedef struct TableAmRoutine * on the page have to be returned, otherwise the tuples at offsets in * `tbmres->offsets` need to be returned. * + * lossy indicates whether or not the block's representation in the bitmap + * is lossy or exact. + * * XXX: Currently this may only be implemented if the AM uses md.c as its * storage manager, and uses ItemPointer->ip_blkid in a manner that maps * blockids directly to the underlying storage. nodeBitmapHeapscan.c @@ -811,7 +814,8 @@ typedef struct TableAmRoutine * scan_bitmap_next_tuple need to exist, or neither. */ bool (*scan_bitmap_next_block) (TableScanDesc scan, - struct TBMIterateResult *tbmres); + struct TBMIterateResult *tbmres, + bool *lossy); /* * Fetch the next tuple of a bitmap table scan into `slot` and return true @@ -1951,14 +1955,16 @@ table_relation_estimate_size(Relation rel, int32 *attr_widths, * Prepare to fetch / check / return tuples from `tbmres->blockno` as part of * a bitmap table scan. `scan` needs to have been started via * table_beginscan_bm(). Returns false if there are no tuples to be found on - * the page, true otherwise. + * the page, true otherwise. lossy is set to true if bitmap is lossy for the + * selected block and false otherwise. * * Note, this is an optionally implemented function, therefore should only be * used after verifying the presence (at plan time or such). */ static inline bool table_scan_bitmap_next_block(TableScanDesc scan, - struct TBMIterateResult *tbmres) + struct TBMIterateResult *tbmres, + bool *lossy) { /* * We don't expect direct calls to table_scan_bitmap_next_block with valid @@ -1969,7 +1975,7 @@ table_scan_bitmap_next_block(TableScanDesc scan, elog(ERROR, "unexpected table_scan_bitmap_next_block call during logical decoding"); return scan->rs_rd->rd_tableam->scan_bitmap_next_block(scan, - tbmres); + tbmres, lossy); } /* -- 2.40.1 --kqqpqghcwbcc3dt5 Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v7-0007-Reduce-scope-of-BitmapHeapScan-tbmiterator-local-.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
end of thread, other threads:[~2024-07-22 15:10 UTC | newest] Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2024-01-14 21:47 Re: Custom explain options Tomas Vondra <[email protected]> 2024-01-15 14:22 ` Konstantin Knizhnik <[email protected]> 2024-01-15 15:08 ` Tomas Vondra <[email protected]> 2024-01-15 20:42 ` Konstantin Knizhnik <[email protected]> 2024-01-16 15:38 ` Tomas Vondra <[email protected]> 2024-01-16 16:07 ` Konstantin Knizhnik <[email protected]> 2024-01-24 01:54 ` David G. Johnston <[email protected]> 2024-07-22 15:10 ` Pavel Stehule <[email protected]> 2024-02-27 01:34 [PATCH v7 06/13] table_scan_bitmap_next_block() returns lossy or exact Melanie Plageman <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox