Add BRIN support for spoint and sbox

[vitcpp]

This is the adaptation of the patch introduced in https://github.com/akorotkov/pgsphere/pull/8 by @gbroccolo with some small fixes. I appreciate any help with reviewing and testing of this patch.

[gbroccolo]

Some minor tweaks, but otherwise looks good to me.

It would be nice if BRINs supported scircles and the other s-types as well, but maybe in a follow-up PR if there's interest.

Yes, it is possible to add the support for the other s-types, it's just enough to use the conversion to the 3D-MBR of the spherical geometry defined in src/key.c.

But we should add all the BRIN support functions for each type, so maybe it's better to create single PR for each of it.

Also (and this can be considered an additional note for this PR) it might be worth to create different source files for each data type in order to avoid that src/brin.c could end in thousands of line of code in a single file.

[vitcpp]

It would be nice if BRINs supported scircles and the other s-types as well, but maybe in a follow-up PR if there's interest.

I agree, lets do it as a separate task.

[vitcpp]

Some minor tweaks, but otherwise looks good to me. It would be nice if BRINs supported scircles and the other s-types as well, but maybe in a follow-up PR if there's interest.

Yes, it is possible to add the support for the other s-types, it's just enough to use the conversion to the 3D-MBR of the spherical geometry defined in src/key.c.

But we should add all the BRIN support functions for each type, so maybe it's better to create single PR for each of it.

Also (and this can be considered an additional note for this PR) it might be worth to create different source files for each data type in order to avoid that src/brin.c could end in thousands of line of code in a single file.

I like the idea to add support in different PR. Lets compete and deliver this PR. I also like the idea to create different source files for each data type. I would prefer to have a big number of small files with clear names, than to have one file with a lot of code. I propose to keep this PR unchanged and make such work in the future PRs.

[vitcpp]

@esabol, @gbroccolo I did some fixes. Thank you! I also rebased the branch. I removed the unnecessary braces in the original sentense: (Note that the size of the BRINs increases as well.). Please, let me know if I did wrong. I will rollback it.

[gbroccolo]

@vitcpp for me the PR is fine and can be merged by any committer of this repo at any moment.

[vitcpp]

I propose to add a test for sbox BRIN as well. I've added a test for sbox BRIN index but I do not see that the index was selected by the planner. Sequential scan is still used. I just copied the test for spoint with some trivial changes. I haven't digged deeply how the test works. May be I missed something.

[esabol]

I've added a test for sbox BRIN index but I do not see that the index was selected by the planner. Sequential scan is still used. I just copied the test for spoint with some trivial changes. I haven't digged deeply how the test works. May be I missed something.

I think the table needs to be clustered on the parameter on which you have created the BRIN index.

[vitcpp]

@esabol I think, BRIN index should be created without clustering but I'm not sure about it. BRIN index is not used in the test brin_sbox. Seq scan is used instead. I still can't achieve it in the test. We may marge PR as it is now but later sbox_brin should be improved.

[esabol]

The few examples of BRIN usage I can find on the Internet all cluster the table. :shrug:

Apparently, you can SET LOCAL enable_seqscan = OFF; to force the BRIN index to be used?

https://postgrespro.com/list/thread-id/2638982

[esabol]

And the StackOverflow answers here all say that "the BRIN index key has to correspond to the physical ordering of the data," which is what clustering achieves.

https://stackoverflow.com/questions/72614493/brin-index-usage

[vitcpp]

@esabol Yes, you are right in general. BRIN index follows the physical ordering of the data. But BRIN index is created after the table is populated with some data. If you think to use CLUSTER command, it is not the case. This command requires already created index and it clusters the data in the table in according with the already created index.

As I know, the basic idea of BRIN index is to separate the whole table into a number of ranges. Each range may contain one or more pages (blocks). BRIN index contains some summary of each range: min/max values or bounding rectangle of the geometrical data, stored in the pages of the range. Such separation allows to select ranges for seq scan or ignore it very fast. It is why bitmap scan is used with BRIN index. Such indexing works well then table data are already sorted well because BRIN index operates by pages (blocks).

I guess, there are two possible sources of the problem:

• data is too small - optimizer selects seq scan unconditionally
• the definition of sbox BRIN index is not complete

[esabol]

@esabol Yes, you are right in general. BRIN index follows the physical ordering of the data. But BRIN index is created after the table is populated with some data. If you think to use CLUSTER command, it is not the case. This command requires already created index and it clusters the data in the table in according with the already created index.

Correct, but you can drop the index that you use to cluster the table with after the clustering is done, like this:

CREATE INDEX idx_sometable_someparam ON sometable(someparam);
CLUSTER sometable USING idx_sometable_someparam;
DROP INDEX idx_sometable_someparam;
CREATE INDEX idxbrin_sometable_someparam ON sometable USING brin(someparam);

If sometable is already ordered when loaded into the database, then you don't need to do this, but lots of BRIN examples do exactly this. Some examples also suggest VACUUM-ing and ANALYZE-ing the table as well.

Did you try SET LOCAL enable_seqscan = OFF;?

[vitcpp]

@esabol I did what you proposed. I clustered the table first then I created the BRIN index. I also increased the amount of the data in the table. I duplicated the original set of rows many times. The same result - I didn't see that BRIN index was applied.

[gbroccolo]

@esabol I did what you proposed. I clustered the table first then I created the BRIN index. I also increased the amount of the data in the table. I duplicated the original set of rows many times. The same result - I didn't see that BRIN index was applied.

Hi @esabol and @vitcpp, sorry for my late reply here, but it's kind of busy period for me in these days.

Regarding your test: you are both right saying that BRINs perform well at the moment that the data is phisically organised in the 8kB pages in order to avoid to have block of pages would correspond to similar MBRs including their entries, as I tried to explain here. Note also that CLUSTER on preexisting indexes is not the only way to achieve this: also VACUUM and autovacuum bring to the same result, because both of them trigger pages' resumming as explained here.

However, this is not going to solve the problem: here BRINs are not used simply because they are not convenient (in terms of I/O and access to memory operations) from PostgreSQL point of view: for small datasets, inspecting the index and select the single blocks of pages to be then sequentially scanned (what is called bitmapscan in the planner) is generally more expensive than a direct sequential scan of all pages of a table (seqscan). It is something that generally happens also for GiST indexes, where for small datasets an indexscan is more expensive than a seqscan.

Now, we have to think about what we want to achieve here: for a regression test is not required to test when the planner choose a plan rather than another (which is something that depends on a lot of factors: underlying hardware, size of the data, nature of the data, configuration of the PostgreSQL engine, ...), but to check that the result obtained through the index would be identical to the one obtained by the sequential scan. This is what I tried to achieve for example in this test I wrote for spoint: I filled a test table with 77 spherical point (more or less close to each other, just to have a good summarization as starting point, but it's not necessary for the purpose of the test) then I was checking if the result with a sequential scan is identical to the one through a bitmap scan.

Hope I helped with this long comment.

[vitcpp]

@esabol , @gbroccolo It seems I've found and fixed the problem with sbox support for BRIN index. Some operators in brin_inclusion_spheric_ops were absent (please, see my last commit). Now the BRIN index seems to be chosen by the planner.

[esabol]

It seems I've found and fixed the problem with sbox support for BRIN index.

Fantastic! Great work, @vitcpp !

[vitcpp]

@esabol , @gbroccolo I've prepared the PR for merge. I squashed my commits into one. I did no more changes except of adding sbox_brin to the list of tests of installcheck rule. I think the PR is ready for merge. If everything is ok, I will merge. Thank you very much for your help!

[vitcpp]

Not sure, what hapenned, but moc100 test is failed now unfortunately.

[esabol]

Not sure, what happened, but moc100 test is failed now unfortunately.

Did the PostgreSQL version used in the PG16 build change? 16 beta 3 was released on August 10. When was the last time the PG16 build passed? Maybe it took 2 weeks before 16 beta 3 showed up in Travis CI? If the only reason for the failure is going from 16 beta 2 to beta 3, then this change in the output might need to be reported to the PostgreSQL dev team.

My first thought was that it was due to a side effect of the SQL in the BRIN test, but that can't be since PR #56 also failed its PG16 build.

If this is an intentional change by the PostgreSQL developers in PostgreSQL 16, then we're going to need different expected outputs for pre-16 and 16+. (How annoying!)

[vitcpp]

@esabol I did some changes in the PR 2 days ago and PG16 tests were passed ok. My last change is to squash my commits. I guess, something is changed on travis-ci. Furthermore, my last PR #56 is failed as well. I will try to fix the differences in the output - we do not need to validate the behaviour of postgresql here. If we fix the current behaviour we can see some changes in the future.

[vitcpp]

@esabol I adjusted expected/moc100_4.out file which fixed the issue. I'm going to do this change in a separate PR. I propose to fix moc100 first, then rebase and merge this PR.