Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On Mon, 15 Jan 2024 at 04:45, Tomas Vondra wrote: > > On 1/14/24 12:18, vignesh C wrote: > > On Fri, 14 Jul 2023 at 20:17, Tomas Vondra > > wrote: > >> > >> On 7/9/23 23:44, Tomas Vondra wrote: > >>> ... > > Yes, my previous message was mostly about backwards compatibility, and > > this may seem a bit like an argument against it. But that message was > > more a question "If we do this, is it actually backwards compatible the > > way we want/need?") > > > > Anyway, I think the BrinDesc scratch space is a neat idea, I'll try > > doing it that way and report back in a couple days. > > Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you > used the preprocess function to pre-calculate the scankey's hash, even > for scalars. You could use the scratch space in BrinDesc for that, > before doing anything with SEARCHARRAYs. > > >>> > >>> Yeah, that's a good idea. > >>> > >> > >> I started looking at this (the scratch space in BrinDesc), and it's not > >> as straightforward. The trouble is BrinDesc is "per attribute" but the > >> scratch space is "per scankey" (because we'd like to sort values from > >> the scankey array). > >> > >> With the "new" consistent functions (that get all scan keys at once) > >> this probably is not an issue, because we know which scan key we're > >> processing and so we can map it to the scratch space. But with the old > >> consistent function that's not the case. Maybe we should support this > >> only with the "new" consistent function variant? > >> > >> This would however conflict with the idea to have a separate consistent > >> function for arrays, which "splits" the scankeys into multiple groups > >> again. There could be multiple SAOP scan keys, and then what? > >> > >> I wonder if the scratch space should be in the ScanKey instead? > > > > Are we planning to post an updated patch for this? If the interest has > > gone down and if there are no plans to handle this I'm thinking of > > returning this commitfest entry in this commitfest and can be opened > > when there is more interest. > > > > I still think the patch is a good idea and plan to get back to it, but > probably not in this CF. Given that the last update if from July, it's > fair to bump it - either RWF or just move to the next CF. Up to you. I have changed the status to RWF, feel free to update the commitfest after handling the comments. Regards, Vignesh
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 1/14/24 12:18, vignesh C wrote: > On Fri, 14 Jul 2023 at 20:17, Tomas Vondra > wrote: >> >> On 7/9/23 23:44, Tomas Vondra wrote: >>> ... > Yes, my previous message was mostly about backwards compatibility, and > this may seem a bit like an argument against it. But that message was > more a question "If we do this, is it actually backwards compatible the > way we want/need?") > > Anyway, I think the BrinDesc scratch space is a neat idea, I'll try > doing it that way and report back in a couple days. Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you used the preprocess function to pre-calculate the scankey's hash, even for scalars. You could use the scratch space in BrinDesc for that, before doing anything with SEARCHARRAYs. >>> >>> Yeah, that's a good idea. >>> >> >> I started looking at this (the scratch space in BrinDesc), and it's not >> as straightforward. The trouble is BrinDesc is "per attribute" but the >> scratch space is "per scankey" (because we'd like to sort values from >> the scankey array). >> >> With the "new" consistent functions (that get all scan keys at once) >> this probably is not an issue, because we know which scan key we're >> processing and so we can map it to the scratch space. But with the old >> consistent function that's not the case. Maybe we should support this >> only with the "new" consistent function variant? >> >> This would however conflict with the idea to have a separate consistent >> function for arrays, which "splits" the scankeys into multiple groups >> again. There could be multiple SAOP scan keys, and then what? >> >> I wonder if the scratch space should be in the ScanKey instead? > > Are we planning to post an updated patch for this? If the interest has > gone down and if there are no plans to handle this I'm thinking of > returning this commitfest entry in this commitfest and can be opened > when there is more interest. > I still think the patch is a good idea and plan to get back to it, but probably not in this CF. Given that the last update if from July, it's fair to bump it - either RWF or just move to the next CF. Up to you. As for the patch, I wonder if Heikki has some idea what to do about the scratch space? I got stuck on thinking about how to do this with the two types of consistent functions we support/allow. To articulate the issue more clearly - the scratch space is "per index" but we need scratch space "per index key". That's fine - we can simply have pointers to multiple scratch spaces, I think. But we have two ways to do consistent functions - the "old" gets scan keys one attribute at a time, "new" gets all at once. For the "new" it's not a problem, it's simple to identify the right scratch space. But for the "old" one, how would that happen? The consistent function has no idea which index key it's operating on, and how to identify the correct scratch space. I can think of two ways to deal with this: 1) Only allow SK_SEARCHARRAY for indexes supporting new-style consistent functions (but I'm not sure how, considering amsearcharray is set way before we know what the opclass does, or whether it implements the old or new consistent function). 2) Allow SK_SEARCHARRAY even with old consistent function, but do some dance in bringetbitmap() so to set the scratch space accordingly before the call. Now that I read Heikki's messages again, I see he suggested assigning a new procnum to a consistent function supporting SK_SEARCHARRAY, which seems to be very close to (1). Except that we'd now have 3 ways to define a consistent function, and that sounds a bit ... too much? Anyway, thinking about (1), I'm still not sure what to do about existing opclasses - it'd be nice to have some backwards compatible solution, without breaking everything and forcing everyone to implement all the new stuff. Which is kinda why we already have two ways to do consistent functions. Presumably we'd have to implement some "default" handling by translating the SK_SEARCHARRAY key into simple equality keys ... regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On Fri, 14 Jul 2023 at 20:17, Tomas Vondra wrote: > > On 7/9/23 23:44, Tomas Vondra wrote: > > ... > >>> Yes, my previous message was mostly about backwards compatibility, and > >>> this may seem a bit like an argument against it. But that message was > >>> more a question "If we do this, is it actually backwards compatible the > >>> way we want/need?") > >>> > >>> Anyway, I think the BrinDesc scratch space is a neat idea, I'll try > >>> doing it that way and report back in a couple days. > >> > >> Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you > >> used the preprocess function to pre-calculate the scankey's hash, even > >> for scalars. You could use the scratch space in BrinDesc for that, > >> before doing anything with SEARCHARRAYs. > >> > > > > Yeah, that's a good idea. > > > > I started looking at this (the scratch space in BrinDesc), and it's not > as straightforward. The trouble is BrinDesc is "per attribute" but the > scratch space is "per scankey" (because we'd like to sort values from > the scankey array). > > With the "new" consistent functions (that get all scan keys at once) > this probably is not an issue, because we know which scan key we're > processing and so we can map it to the scratch space. But with the old > consistent function that's not the case. Maybe we should support this > only with the "new" consistent function variant? > > This would however conflict with the idea to have a separate consistent > function for arrays, which "splits" the scankeys into multiple groups > again. There could be multiple SAOP scan keys, and then what? > > I wonder if the scratch space should be in the ScanKey instead? Are we planning to post an updated patch for this? If the interest has gone down and if there are no plans to handle this I'm thinking of returning this commitfest entry in this commitfest and can be opened when there is more interest. Regards, Vignesh
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 7/9/23 23:44, Tomas Vondra wrote: > ... >>> Yes, my previous message was mostly about backwards compatibility, and >>> this may seem a bit like an argument against it. But that message was >>> more a question "If we do this, is it actually backwards compatible the >>> way we want/need?") >>> >>> Anyway, I think the BrinDesc scratch space is a neat idea, I'll try >>> doing it that way and report back in a couple days. >> >> Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you >> used the preprocess function to pre-calculate the scankey's hash, even >> for scalars. You could use the scratch space in BrinDesc for that, >> before doing anything with SEARCHARRAYs. >> > > Yeah, that's a good idea. > I started looking at this (the scratch space in BrinDesc), and it's not as straightforward. The trouble is BrinDesc is "per attribute" but the scratch space is "per scankey" (because we'd like to sort values from the scankey array). With the "new" consistent functions (that get all scan keys at once) this probably is not an issue, because we know which scan key we're processing and so we can map it to the scratch space. But with the old consistent function that's not the case. Maybe we should support this only with the "new" consistent function variant? This would however conflict with the idea to have a separate consistent function for arrays, which "splits" the scankeys into multiple groups again. There could be multiple SAOP scan keys, and then what? I wonder if the scratch space should be in the ScanKey instead? regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 7/9/23 20:05, Heikki Linnakangas wrote: > On 09/07/2023 19:16, Tomas Vondra wrote: >> On 7/8/23 23:57, Heikki Linnakangas wrote: >>> The new preprocess support function feels a bit too inflexible to me. >>> True, you can store whatever you want in the ScanKey that it returns, >>> but since that's the case, why not just make it void * ? It seems that >>> the constraint here was that you need to pass a ScanKey to the >>> consistent function, because the consistent function's signature is what >>> it is. But we can change the signature, if we introduce a new support >>> amproc number for it. >> >> Now sure I follow - what should be made (void *)? Oh, you mean not >> passing the preprocessed array as a scan key at all, and instead passing >> it as a new (void*) parameter to the (new) consistent function? > > Right. > >>> It would be unpleasant to force all BRIN opclasses to immediately >>> implement the searcharray-logic. If we don't want to do that, we need to >>> implement generic SK_SEARCHARRAY handling in BRIN AM itself. That would >>> be pretty easy, right? Just call the regular consistent function for >>> every element in the array. >> >> True, although the question is how many out-of-core opclasses are there. >> My impression is the number is pretty close to 0, in which case we're >> making ourselves to jump through all kinds of hoops, making the code >> more complex, with almost no benefit in the end. > > Perhaps. How many of the opclasses can do something smart with > SEARCHARRAY? If the answer is "all" or "almost all", then it seems > reasonable to just require them all to handle it. If the answer is > "some", then it would still be nice to provide a naive default > implementation in the AM itself. Otherwise all the opclasses need to > include a bunch of boilerplate to support SEARCHARRAY. > For the built-in, I think all can do something smart. For external, hard to say - my guess is they could do something interesting too. >>> If an opclass wants to provide a faster/better implementation, it can >>> provide a new consistent support procedure that supports that. Let's >>> assign a new amproc number for new-style consistent function, which must >>> support SK_SEARCHARRAY, and pass it some scratch space where it can >>> cache whatever per-scankey data. Because it gets a new amproc number, we >>> can define the arguments as we wish. We can pass a pointer to the >>> per-scankey scratch space as a new argument, for example. >>> >>> We did this backwards-compatibility dance with the 3/4-argument variants >>> of the current consistent functions. But I think assigning a whole new >>> procedure number is better than looking at the number of arguments. >> >> I actually somewhat hate the 3/4-argument dance, and I'm opposed to >> doing that sort of thing again. First, I'm not quite convinced it's >> worth the effort to jump through this hoop (I recall this being one of >> the headaches when fixing the BRIN NULL handling). Second, it can only >> be done once - imagine we now need to add a new optional parameter. >> Presumably, we'd need to keep the existing 3/4 variants, and add new 4/5 >> variants. At which point 4 is ambiguous. > > My point is that we should assign a new amproc number to distinguish the > new variant, instead of looking at the number of arguments. That way > it's not ambiguous, and you can define whatever arguments you want for > the new variant. > Right, I agree. > Yet another idea is to introduce a new amproc for a consistent function > that *only* handles the SEARCHARRAY case, and keep the old consistent > function as it is for the scalars. So every opclass would need to > implement the current consistent function, just like today. But if an > opclass wants to support SEARCHARRAY, it could optionally also provide > an "consistent_array" function. > Hmm, we probably need to do something like this anyway. Because even with the scratch space in BrinDesc, we still need to track whether the opclass can process arrays or not. And if it can't we need to emulate it in brin.c. >> Yes, my previous message was mostly about backwards compatibility, and >> this may seem a bit like an argument against it. But that message was >> more a question "If we do this, is it actually backwards compatible the >> way we want/need?") >> >> Anyway, I think the BrinDesc scratch space is a neat idea, I'll try >> doing it that way and report back in a couple days. > > Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you > used the preprocess function to pre-calculate the scankey's hash, even > for scalars. You could use the scratch space in BrinDesc for that, > before doing anything with SEARCHARRAYs. > Yeah, that's a good idea. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 09/07/2023 19:16, Tomas Vondra wrote: On 7/8/23 23:57, Heikki Linnakangas wrote: The new preprocess support function feels a bit too inflexible to me. True, you can store whatever you want in the ScanKey that it returns, but since that's the case, why not just make it void * ? It seems that the constraint here was that you need to pass a ScanKey to the consistent function, because the consistent function's signature is what it is. But we can change the signature, if we introduce a new support amproc number for it. Now sure I follow - what should be made (void *)? Oh, you mean not passing the preprocessed array as a scan key at all, and instead passing it as a new (void*) parameter to the (new) consistent function? Right. It would be unpleasant to force all BRIN opclasses to immediately implement the searcharray-logic. If we don't want to do that, we need to implement generic SK_SEARCHARRAY handling in BRIN AM itself. That would be pretty easy, right? Just call the regular consistent function for every element in the array. True, although the question is how many out-of-core opclasses are there. My impression is the number is pretty close to 0, in which case we're making ourselves to jump through all kinds of hoops, making the code more complex, with almost no benefit in the end. Perhaps. How many of the opclasses can do something smart with SEARCHARRAY? If the answer is "all" or "almost all", then it seems reasonable to just require them all to handle it. If the answer is "some", then it would still be nice to provide a naive default implementation in the AM itself. Otherwise all the opclasses need to include a bunch of boilerplate to support SEARCHARRAY. If an opclass wants to provide a faster/better implementation, it can provide a new consistent support procedure that supports that. Let's assign a new amproc number for new-style consistent function, which must support SK_SEARCHARRAY, and pass it some scratch space where it can cache whatever per-scankey data. Because it gets a new amproc number, we can define the arguments as we wish. We can pass a pointer to the per-scankey scratch space as a new argument, for example. We did this backwards-compatibility dance with the 3/4-argument variants of the current consistent functions. But I think assigning a whole new procedure number is better than looking at the number of arguments. I actually somewhat hate the 3/4-argument dance, and I'm opposed to doing that sort of thing again. First, I'm not quite convinced it's worth the effort to jump through this hoop (I recall this being one of the headaches when fixing the BRIN NULL handling). Second, it can only be done once - imagine we now need to add a new optional parameter. Presumably, we'd need to keep the existing 3/4 variants, and add new 4/5 variants. At which point 4 is ambiguous. My point is that we should assign a new amproc number to distinguish the new variant, instead of looking at the number of arguments. That way it's not ambiguous, and you can define whatever arguments you want for the new variant. Yet another idea is to introduce a new amproc for a consistent function that *only* handles the SEARCHARRAY case, and keep the old consistent function as it is for the scalars. So every opclass would need to implement the current consistent function, just like today. But if an opclass wants to support SEARCHARRAY, it could optionally also provide an "consistent_array" function. Yes, my previous message was mostly about backwards compatibility, and this may seem a bit like an argument against it. But that message was more a question "If we do this, is it actually backwards compatible the way we want/need?") Anyway, I think the BrinDesc scratch space is a neat idea, I'll try doing it that way and report back in a couple days. Cool. In 0005-Support-SK_SEARCHARRAY-in-BRIN-bloom-20230702.patch, you used the preprocess function to pre-calculate the scankey's hash, even for scalars. You could use the scratch space in BrinDesc for that, before doing anything with SEARCHARRAYs. -- Heikki Linnakangas Neon (https://neon.tech)
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 7/8/23 23:57, Heikki Linnakangas wrote: > On 02/07/2023 19:09, Tomas Vondra wrote: >> Here's an updated version of the patch series. >> >> I've polished and pushed the first three patches with cleanup, tests to >> improve test coverage and so on. I chose not to backpatch those - I >> planned to do that to make future backpatches simpler, but the changes >> ended up less disruptive than expected. >> >> The remaining patches are just about adding SK_SEARCHARRAY to BRIN. >> >> 0001 - adds the optional preprocess procedure, calls it from brinrescan >> >> 0002 to 0005 - adds the support to the existing BRIN opclasses > > Could you implement this completely in the consistent-function, by > caching the sorted array in fn_extra, without adding the new preprocess > procedure? On first call, when fn_extra == NULL, sort the array and > stash it in fn_extra. > > I don't think that works, because fn_extra isn't reset when the scan > keys change on rescan. We could reset it, and document that you can use > fn_extra for per-scankey caching. There's some precedence for not > resetting it though, see commit d22a09dc70f. But we could provide an > opaque per-scankey scratch space like that somewhere else. In BrinDesc, > perhaps. > Hmm, yeah. BrinDesc seems like a good place for such scratch space ... And it's seem to alleviate most of the compatibility issues, because it'd make the preprocessing a responsibility of the consistent function, instead of doing it in a separate optional procedure (and having to deal with cases when it does not exist). If would not even need a separate procnum. > The new preprocess support function feels a bit too inflexible to me. > True, you can store whatever you want in the ScanKey that it returns, > but since that's the case, why not just make it void * ?It seems that > the constraint here was that you need to pass a ScanKey to the > consistent function, because the consistent function's signature is what > it is. But we can change the signature, if we introduce a new support > amproc number for it. > Now sure I follow - what should be made (void *)? Oh, you mean not passing the preprocessed array as a scan key at all, and instead passing it as a new (void*) parameter to the (new) consistent function? Yeah, I was trying to stick to the existing signature of the consistent function, to minimize the necessary changes. >> The main open question I have is what exactly does it mean that the >> procedure is optional. In particular, should it be supported to have a >> BRIN opclass without the "preprocess" procedure but using the other >> built-in support procedures? >> >> For example, imagine you have a custom BRIN opclass in an extension (for >> a custom data type or something). This does not need to implement any >> procedures, it can just call the existing built-in ones. Of course, this >> won't get the "preprocess" procedure automatically. >> >> Should we support such opclasses or should we force the extension to be >> updated by adding a preprocess procedure? I'd say "optional" means we >> should support (otherwise it'd not really optional). >> >> The reason why this matters is that "amsearcharray" is AM-level flag, >> but the support procedure is defined by the opclass. So the consistent >> function needs to handle SK_SEARCHARRAY keys both with and without >> preprocessing. >> >> That's mostly what I did for all existing BRIN opclasses (it's a bit >> confusing that opclass may refer to both the "generic" minmax or the >> opclass defined for a particular data type). All the opclasses now >> handle three cases: >> >> 1) scalar keys (just like before, with amsearcharray=fase) >> >> 2) array keys with preprocessing (sorted array, array of hashes, ...) >> >> 3) array keys without preprocessing (for compatibility with old >> opclasses missing the optional preprocess procedure) >> >> The current code is a bit ugly, because it duplicates a bunch of code, >> because the option (3) mostly does (1) in a loop. I'm confident this can >> be reduced by refactoring and reusing some of the "shared" code. >> >> The question is if my interpretation of what "optional" procedure means >> is reasonable. Thoughts? >> >> The other thing is how to test this "compatibility" code. I assume we >> want to have the procedure for all built-in opclasses, so that won't >> exercise it. I did test it by temporarily removing the procedure from a >> couple pg_amproc.dat entries. I guess creating a custom opclass in the >> regression test is the right solution. > > It would be unpleasant to force all BRIN opclasses to immediately > implement the searcharray-logic. If we don't want to do that, we need to > implement generic SK_SEARCHARRAY handling in BRIN AM itself. That would > be pretty easy, right? Just call the regular consistent function for > every element in the array. > True, although the question is how many out-of-core opclasses are there. My impression is the number is pretty close to 0, in which case
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 02/07/2023 19:09, Tomas Vondra wrote: Here's an updated version of the patch series. I've polished and pushed the first three patches with cleanup, tests to improve test coverage and so on. I chose not to backpatch those - I planned to do that to make future backpatches simpler, but the changes ended up less disruptive than expected. The remaining patches are just about adding SK_SEARCHARRAY to BRIN. 0001 - adds the optional preprocess procedure, calls it from brinrescan 0002 to 0005 - adds the support to the existing BRIN opclasses Could you implement this completely in the consistent-function, by caching the sorted array in fn_extra, without adding the new preprocess procedure? On first call, when fn_extra == NULL, sort the array and stash it in fn_extra. I don't think that works, because fn_extra isn't reset when the scan keys change on rescan. We could reset it, and document that you can use fn_extra for per-scankey caching. There's some precedence for not resetting it though, see commit d22a09dc70f. But we could provide an opaque per-scankey scratch space like that somewhere else. In BrinDesc, perhaps. The new preprocess support function feels a bit too inflexible to me. True, you can store whatever you want in the ScanKey that it returns, but since that's the case, why not just make it void * ?It seems that the constraint here was that you need to pass a ScanKey to the consistent function, because the consistent function's signature is what it is. But we can change the signature, if we introduce a new support amproc number for it. The main open question I have is what exactly does it mean that the procedure is optional. In particular, should it be supported to have a BRIN opclass without the "preprocess" procedure but using the other built-in support procedures? For example, imagine you have a custom BRIN opclass in an extension (for a custom data type or something). This does not need to implement any procedures, it can just call the existing built-in ones. Of course, this won't get the "preprocess" procedure automatically. Should we support such opclasses or should we force the extension to be updated by adding a preprocess procedure? I'd say "optional" means we should support (otherwise it'd not really optional). The reason why this matters is that "amsearcharray" is AM-level flag, but the support procedure is defined by the opclass. So the consistent function needs to handle SK_SEARCHARRAY keys both with and without preprocessing. That's mostly what I did for all existing BRIN opclasses (it's a bit confusing that opclass may refer to both the "generic" minmax or the opclass defined for a particular data type). All the opclasses now handle three cases: 1) scalar keys (just like before, with amsearcharray=fase) 2) array keys with preprocessing (sorted array, array of hashes, ...) 3) array keys without preprocessing (for compatibility with old opclasses missing the optional preprocess procedure) The current code is a bit ugly, because it duplicates a bunch of code, because the option (3) mostly does (1) in a loop. I'm confident this can be reduced by refactoring and reusing some of the "shared" code. The question is if my interpretation of what "optional" procedure means is reasonable. Thoughts? The other thing is how to test this "compatibility" code. I assume we want to have the procedure for all built-in opclasses, so that won't exercise it. I did test it by temporarily removing the procedure from a couple pg_amproc.dat entries. I guess creating a custom opclass in the regression test is the right solution. It would be unpleasant to force all BRIN opclasses to immediately implement the searcharray-logic. If we don't want to do that, we need to implement generic SK_SEARCHARRAY handling in BRIN AM itself. That would be pretty easy, right? Just call the regular consistent function for every element in the array. If an opclass wants to provide a faster/better implementation, it can provide a new consistent support procedure that supports that. Let's assign a new amproc number for new-style consistent function, which must support SK_SEARCHARRAY, and pass it some scratch space where it can cache whatever per-scankey data. Because it gets a new amproc number, we can define the arguments as we wish. We can pass a pointer to the per-scankey scratch space as a new argument, for example. We did this backwards-compatibility dance with the 3/4-argument variants of the current consistent functions. But I think assigning a whole new procedure number is better than looking at the number of arguments. -- Heikki Linnakangas Neon (https://neon.tech)
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
On 2/24/23 22:07, Heikki Linnakangas wrote: > I had a quick look at just the preliminary cleanup patches: > >> 0001-BRIN-bloom-cleanup-20230218.patch > > Looks good to me > >> 0002-BRIN-minmax-multi-cleanup-20230218.patch > > Looks good, although it would feel more natural to me to do it the other > way round, and define 'matches' as 'bool matches', and use DatumGetBool. > Yeah, probably. I was trying to only do the minimal change because of (maybe) backpatching this. > Not new with this patch, but I find the 'matches' and 'matching' > variables a bit strange. Wouldn't it be simpler to have just one variable? > True. I don't recall why we did it this way. >> 0003-Introduce-bloom_filter_size-20230218.patch > > Looks good > >> 0004-Add-minmax-multi-inequality-tests-20230218.patch > > Looks good > >> +SELECT i/5 + mod(911 * i + 483, 25), >> + i/10 + mod(751 * i + 221, 41) > > Peculiar formulas. Was there a particular reason for these values? > No, not really. I simply wanted a random-looking data, but reproducible and deterministic. And linear congruential generator is a simple way to do that. I just picked a couple co-prime numbers, and that's it. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
I had a quick look at just the preliminary cleanup patches: 0001-BRIN-bloom-cleanup-20230218.patch Looks good to me 0002-BRIN-minmax-multi-cleanup-20230218.patch Looks good, although it would feel more natural to me to do it the other way round, and define 'matches' as 'bool matches', and use DatumGetBool. Not new with this patch, but I find the 'matches' and 'matching' variables a bit strange. Wouldn't it be simpler to have just one variable? 0003-Introduce-bloom_filter_size-20230218.patch Looks good 0004-Add-minmax-multi-inequality-tests-20230218.patch Looks good +SELECT i/5 + mod(911 * i + 483, 25), + i/10 + mod(751 * i + 221, 41) Peculiar formulas. Was there a particular reason for these values? - Heikki
BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
Hi, while experimenting with BRIN indexes after a couple FOSDEM discussions, I ran into the existing limitation that BRIN indexes don't handle array scan keys. So BRIN indexes can be used for conditions like WHERE a IN (1,2,3,4,5) but we essentially treat the values as individual scan keys, and for each one we scan the BRIN index and build/update the bitmap. Which for large indexes may be fairly expensive - the cost is proportional to the number of values, so if building the bitmap for 1 value takes 10ms, for 100 values it'll take ~1000ms. It's not hard to construct cases like this (e.g. when using indexes with small pages_per_range values) etc. Of course, if the query does a lot of other expensive stuff, this cost may be insignificant. I'm not sure how often people do queries with such conditions. But I've been experimenting with features that'd build such paths, so I took a stab at a PoC, which can significantly reduce the time needed to build the bitmaps. And there's a couple more interesting opportunities. 0001 - Support SK_SEARCHARRAY in BRIN minmax The 0001 part does a "naive" SK_SEARCHARRAY implementation for minmax. It simply sets amsearcharray=true and then tweaks the consistent function to handle both the scalar and array scan keys. This is obviously rather inefficient, because the array is searched linearly. So yes, we don't walk the index repeatedly, but we have to compare each range to (almost-)all values. 0002 - Sort the array in brinrescan() and do binsearch -- There's a simple way to optimize the naive approach by sorting the array and then searching in this array. If the array is sorted, we can search for the first value >= minvalue, and see if that is consistent (i.e. if it's <= maxval). In my experiments this cuts the time needed to build the bitmap for array to pretty much the same as for a single value. I think this is similar to the preprocessing of scan keys in b-tree, so brinrescan() is a natural way to do the sort. The problem however is where to store the result. Ideally, we'd store it in BrinOpaque (just like BTScanOpaque in btree), but the problem is we don't pass that to the consistent functions. Those only get the ScanKeys and stuff extracted from BrinOpaque. We might add a parameter to the "consistent" function, but that conflicts with not wanting to break existing extensions implementing their own BRIN indexes. We allow the opclasses to define "consistent" with either 4 or 5 arguments. Adding an argument would mean 5 or 6 arguments, but because of the backwards compatibility we'd need to support existing opclasses, and 5 is ambiguous :-/ In hindsight, I would probably not chose supporting both 4 and 5 arguments again. It makes it harder for us to maintain the code to make life easier for extensions, but I'm not aware of any out-of-core BRIN opclasses anyway. So I'd probably just change the API, it's pretty easy to update existing extensions. This patch however does a much simpler thing - it just replaces the array in the SK_SEARCHARRAY scan key with a sorted one. That works for for minmax, but not for bloom/inclusion, because those are not based on sorting. And the ArrayType is not great for minmax either, because it means we need to deconstruct it again and again, for each range. It'd be much better to deconstruct the array once. I'll get back to this ... 0003 - Support SK_SEARCHARRAY in BRIN inclusion --- Trivial modification to support array scan keys, can't benefit from sorting the array. 0004 - Support SK_SEARCHARRAY in BRIN bloom --- Trivial modification to support array scan keys, can't benefit from sorted array either. But we might "preprocess" the keys in a different way - bloom needs to calculate two hashes per key, and at the moment it happens again and again for each range. So if you have 1M ranges, and SK_SEARCHARRAY query with 100 values, we'll do 100M calls to PROCNUM_HASH and 200M calls to hash_uint32_extended(). And our hash functions are pretty expensive, certainly compared to the fast functions often used for bloom filters. So the preprocessing might actually calculate the hash functions once, and then only reuse those in the "consistent" function. 0005 is a dirty PoC illustrating the benefit of caching the hashes. Unfortunately, this complicates things, because it means: * The scan key preprocessing is not universal for all BRIN opclasses, because some opclasses, i.e. each BRIN opclass might have optional BRIN_PROCNUM_PREPROCESS which would preprocess the keys the way the opclass would like. * We can simply replace the array in the scan key the way minmax does that with the sorted array, because the data type is not the same (hashes are uint64). When I started to write this e-mail I thought there's pretty much just one way to move this
