Re: [HACKERS] KNNGiST for knn-search (WIP)
2010/1/12 Teodor Sigaev teo...@sigaev.ru: Changes: - split patch to several ones - sync with current CVS Patch set is based on 0.5.1 version, difference between 0.5 and 0.6 should be only in planner patch. builtin_knngist_itself-0.6.gz - patch to the gist itself builtin_knngist_proc-0.6.gz - patch for support knnsearch in point_ops builtin_knngist_planner-0.6.gz - planner patch to support knnearch builtin_knngist_contrib_btree_gist-0.6.gz - patch for contrib/btree_gist module patch provides - operation for various scalar types which is exactly abs(a - b) function builtin_knngist_contrib_pg_trgm-0.6.gz - contrib/pg_trgm, like above,patch provides - distance between strings Patch set sill requires rbtree patch and point_ops patch (with Robert's changes) Please update commitfest.postgresql.org. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Changes: - split patch to several ones - sync with current CVS Patch set is based on 0.5.1 version, difference between 0.5 and 0.6 should be only in planner patch. builtin_knngist_itself-0.6.gz - patch to the gist itself builtin_knngist_proc-0.6.gz - patch for support knnsearch in point_ops builtin_knngist_planner-0.6.gz - planner patch to support knnearch builtin_knngist_contrib_btree_gist-0.6.gz - patch for contrib/btree_gist module patch provides - operation for various scalar types which is exactly abs(a - b) function builtin_knngist_contrib_pg_trgm-0.6.gz - contrib/pg_trgm, like above,patch provides - distance between strings Patch set sill requires rbtree patch and point_ops patch (with Robert's changes) -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ builtin_knngist_contrib_btree_gist-0.6.gz Description: Unix tar archive builtin_knngist_contrib_pg_trgm-0.6.gz Description: Unix tar archive builtin_knngist_itself-0.6.gz Description: Unix tar archive builtin_knngist_planner-0.6.gz Description: Unix tar archive builtin_knngist_proc-0.6.gz Description: Unix tar archive -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Robert, On Mon, 4 Jan 2010, Robert Haas wrote: On Mon, Jan 4, 2010 at 5:33 PM, Paul Ramsey pram...@cleverelephant.ca wrote: I'm sure whatever conclusion -hackers comes to in the end will be the best for pgsql, and I'll be supportive. But until then, let me note from the PostGIS point-of-view: sure would be great to get this in for 8.5 :) That's good to know. The current status is that I've been waiting for a patch that applies cleanly for 6 days, and we have 41 days left until the end of the last CommitFest. There's not much I can do to move this along until I have a clean patch to work with. sorry, it's a long holiday in Russia, we'll be able to sync next week. Regards, Oleg _ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: o...@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
I'm sure whatever conclusion -hackers comes to in the end will be the best for pgsql, and I'll be supportive. But until then, let me note from the PostGIS point-of-view: sure would be great to get this in for 8.5 :) P. On Thu, Dec 31, 2009 at 4:26 AM, Greg Stark gsst...@mit.edu wrote: On Wed, Dec 30, 2009 at 4:56 PM, Robert Haas robertmh...@gmail.com wrote: From my point of view, what makes a patch invasive is the likelihood that it might break something other than itself. For example, your patch touches the core planner code and the core GIST code, so it seems possible that adding support for this feature might break something else in one of those areas. It doesn't seem obvious to me that this is a high-risk patch. It's touching the planner which is tricky but it's not the kind of massive overhaul that touches every module that HOT or HS were. I'm really glad HS got in before the end because lots of people with different areas of expertise and different use cases are going to get to exercise it in the time remaining. This patch I would expect relatively few people to need to try it out before any oversights are caught. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
On Mon, Jan 4, 2010 at 5:33 PM, Paul Ramsey pram...@cleverelephant.ca wrote: I'm sure whatever conclusion -hackers comes to in the end will be the best for pgsql, and I'll be supportive. But until then, let me note from the PostGIS point-of-view: sure would be great to get this in for 8.5 :) That's good to know. The current status is that I've been waiting for a patch that applies cleanly for 6 days, and we have 41 days left until the end of the last CommitFest. There's not much I can do to move this along until I have a clean patch to work with. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
On Wed, Dec 30, 2009 at 4:56 PM, Robert Haas robertmh...@gmail.com wrote: From my point of view, what makes a patch invasive is the likelihood that it might break something other than itself. For example, your patch touches the core planner code and the core GIST code, so it seems possible that adding support for this feature might break something else in one of those areas. It doesn't seem obvious to me that this is a high-risk patch. It's touching the planner which is tricky but it's not the kind of massive overhaul that touches every module that HOT or HS were. I'm really glad HS got in before the end because lots of people with different areas of expertise and different use cases are going to get to exercise it in the time remaining. This patch I would expect relatively few people to need to try it out before any oversights are caught. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Robert, On Wed, 30 Dec 2009, Robert Haas wrote: Based on the feedback provided on this patch so far, it looks like some changes are probably needed, but it's not entirely clear whether the feedback provided is sufficient to provide guidance on what changes should be made. It does also need to be updated to CVS HEAD, as it no longer applies cleanly. this is not a problem. I tend to feel that we should probably target this for 8.6 rather than 8.5. We are down to the last CommitFest, and while we don't have a nailed-down criterion for what is too big for the last CommitFest of a given release cycle, this is definitely a big, invasive patch. This patch weights in at over 2400 adds/removes, and it's not boilerplate stuff like updates to pg_proc entries, but real, significant changes. I'm worried that applying something like this late in the release cycle is just not a good idea, especially given the fact that it probably still needs significant revising. However, I'm fairly conservative by nature, so perhaps someone else will have a different opinion, or maybe there is a way to restructure it so that the needed changes are less invasive. the patch adds new strategy of gist tree traverse and doesn't change old one, so there is no risk to ruin old code. I'm all for good conservatism, but this is not the case, else we wouldn't have GiST at all. We are very interested in the KNN to be in the 8.5 and we're ready to fix any issues. From metodological point of view I don't quite understand how to measure the value of development, I mean what'is a big patch, invasive patch. Should we prefer cosmetic pathces, spelling fixes, etc ? Of course, they are easy for refering, but people are waiting from us not just fixes, but new features. For example, KNN-GiST is a big improvement for PostGIS community, which is a big part of postgres users. Actually, it's PostGIS community, which supported our work. Now, what we should say them ? The patch was too big and invasive, so, sorry, wait one year more ? I think it's not good. Robert, I'm not against you, it's your right to have your opinion. I address this to other developers. It's important for us, since we have several other patches ready, for example, long awaited phrase search (http://www.sai.msu.su/~megera/wiki/2009-08-12). We postponed it, since it was supposed that EDB will support it, but, hey, it wont. We did it for our own. Teodor insist to submit it for 8.5, but I'm now begin to hesitate, what if this patch will be also too big. Regards, Oleg _ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: o...@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
On Wed, Dec 30, 2009 at 9:20 AM, Oleg Bartunov o...@sai.msu.su wrote: From metodological point of view I don't quite understand how to measure the value of development, I mean what'is a big patch, invasive patch. I want to speak specifically to this question because I think it's a good one. Of course, I also want to make clear that I have nothing against you or your patch and that it sounds like a really nice feature. From my point of view, what makes a patch invasive is the likelihood that it might break something other than itself. For example, your patch touches the core planner code and the core GIST code, so it seems possible that adding support for this feature might break something else in one of those areas. All things being equal, we would prefer to take that risk at the beginning of a development cycle rather than the end. If your patch was the same size, but consisted mostly of new code with very few changes to what is there now, it might still be difficult to properly review and verify - but any bugs we missed would likely affect only the NEW functionality, not any EXISTING functionality. Please understand that the previous paragraph is intended to be a general statement about software development in general more than a specific commentary on your particular patch. Whether applying your patch in particular will break anything is, of course, something that's difficult to know until we do it and see what happens, and at this point I haven't even reviewed it. It's also possible that I'm doing a poor job estimating the risk of breakage, and I certainly welcome other opinions from other people in a position to make a technical judgement on that point. I might also have a different opinion myself after I review the patch in more detail, so please do post an updated version. Should we prefer cosmetic pathces, spelling fixes, etc ? Of course, they are easy for refering, but people are waiting from us not just fixes, but new features. For example, KNN-GiST is a big improvement for PostGIS community, which is a big part of postgres users. Actually, it's PostGIS community, which supported our work. Now, what we should say them ? The patch was too big and invasive, so, sorry, wait one year more ? I think it's not good. Well, I understand your point, but there is obviously some deadline for patches to be submitted for any particular release. Clearly, after the last CommitFest is over, that deadline is past. However, we have previously discussed having a policy that no new large patches will be accepted for the last CommitFest that were not also submitted for the second-to-last CommitFest. Hopefully it's obvious that I have no desire to keep cool new features away from the PostGIS community, the PostgreSQL community, or anyone else, but we have to weigh that against the desire to have a stable and bug-free release, and applying big patches at the last minute makes that less likely. As an example, the change to run the background writer during recovery and the changes in semi/anti join planning for 8.4 have both resulted in multiple bug reports. The former was half the footprint of your patch and applied at the very end of the release cycle; the latter was slightly larger and applied in August 2008, so considerably earlier in the cycle than this one could possibly be - and there were still things we did not catch before release. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Teodor Sigaev escribió: Actually, it's easy to split patch to several ones: - contrib/pg_trgm - contrib/btree_gist - knngist itself - planner changes +1 on the split patches. I wonder about the opr_sanity test change ... why is it necessary? -- Alvaro Herrerahttp://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
2009/12/30 Teodor Sigaev teo...@sigaev.ru: changes should be made. It does also need to be updated to CVS HEAD, as it no longer applies cleanly. The reason was a point_ops patch, some OIDs become duplicated. Both attached patches are synced with current CVS. Thanks! I will take a look. I tend to feel that we should probably target this for 8.6 rather than 8.5. We are down to the last CommitFest, and while we don't have a nailed-down criterion for what is too big for the last CommitFest of a given release cycle, this is definitely a big, invasive patch. This Is we really have rule to accept only small patches at last CommitFest? May be, FixFest name is better for it? :) See here and following for some of the previous discussion - which was not unanimous on all points: http://archives.postgresql.org/pgsql-hackers/2009-09/msg00139.php I think the intention is not to accept only bug fixes, but to limit large features to those that have already been through a CommitFest or two. Actually, it's easy to split patch to several ones: - contrib/pg_trgm - contrib/btree_gist - knngist itself - planner changes And knngist depends on rbtree and point_ops patch, in summary 6 dependent patches. Is it more comfortable? I'm not sure. One of the problems with separating out contrib module changes is that it tends to obscure the point of the changes to the core code. On the other hand if some of the core code changes can be split out into an infrastructure patch that is of some independent usefulness, that can certainly be worthwhile. It's not obvious to me without looking at this more than I have whether there is a possble split that makes sense here; I will read your updated patch. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
On Wed, Dec 30, 2009 at 12:16 PM, Robert Haas robertmh...@gmail.com wrote: 2009/12/30 Teodor Sigaev teo...@sigaev.ru: changes should be made. It does also need to be updated to CVS HEAD, as it no longer applies cleanly. The reason was a point_ops patch, some OIDs become duplicated. Both attached patches are synced with current CVS. Thanks! I will take a look. OK, I'm confused. First, there are two versions of the patch here, so I'm not sure which one I'm supposed to be looking at. Second, when I attempt to apply either one, I get: $ patch -p0 ~/Download/builtin_knngist-0.5 patching file src/backend/access/gist/gistget.c patching file src/backend/access/gist/gistproc.c Reversed (or previously applied) patch detected! Assume -R? [n] ...regardless of how I answer that question, it then goes on to apply most of the rest of the patch successfully. Help? ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
2009/11/26 Teodor Sigaev teo...@sigaev.ru: Hi! Contrib module is reworked as a patch for current GiST. Now GiST supports KNN-search, the query looks like SELECT * FROM point_tbl ORDER BY f1 - '0,1'; or SELECT * FROM point_tbl WHERE f1 @ '(-10,-10),(10,10)':: box ORDER BY f1 - '0,1'; Plans are: EXPLAIN (COSTS OFF) SELECT * FROM point_tbl ORDER BY f1 - '0,1'; QUERY PLAN - Index Scan using gpointind on point_tbl Index Cond: (f1 - '(0,1)'::point) EXPLAIN (COSTS OFF) SELECT * FROM point_tbl WHERE f1 @ '(-10,-10),(10,10)':: box ORDER BY f1 - '0,1'; QUERY PLAN -- Index Scan using gpointind on point_tbl Index Cond: ((f1 @ '(10,10),(-10,-10)'::box) AND (f1 - '(0,1)'::point)) pg_am now has new column amcanorderbyop (can order by operation), indexes with this flag enabled can be used to speedup operations, which returns non-boolean value, currently type of returned value should have default btree operator class to perform sort. Planner (find_usable_indexes function, actually) could push pathkey expression into restriction clauses of index. I'm not fully satisfied with this piece of code, but, may be, someone has a better idea. I though about adding separate indexorderquals in IndexPath structure... Both GiST's get methods are optimized and there is no overhead, since gistrescan method can choose what traversal algorithm to use using information about types of values returned by operations. If at least one of them returns non-boolean result, then KNN-search will be performed. The only change in interface of supporting functions is: consistentFn function could return float8 non-negative value and it's mandatory to perform KNN-search. Old-style consistent functions are supported. Patch contains (it still requires rbtree-0.5 and point_ops-0.4 patches): - GiST changes - changes in point_ops to support knn-search - contrib/pg_trgm now has new operation - returns distance between texts. This operation is supported in KNN-search - contrib/btree_gist provides - and its support for GiST for types int2, int4, int8, float4, float8, money, oid, interval, time, date, timestamp and timestamptz TODO: - selectivity of ordering operation should be 1.0 - current patch remove support of IndexScanDesc-kill_prior_tuple, it's needed to restore support if it will not create too big overhead - documentation Based on the feedback provided on this patch so far, it looks like some changes are probably needed, but it's not entirely clear whether the feedback provided is sufficient to provide guidance on what changes should be made. It does also need to be updated to CVS HEAD, as it no longer applies cleanly. I tend to feel that we should probably target this for 8.6 rather than 8.5. We are down to the last CommitFest, and while we don't have a nailed-down criterion for what is too big for the last CommitFest of a given release cycle, this is definitely a big, invasive patch. This patch weights in at over 2400 adds/removes, and it's not boilerplate stuff like updates to pg_proc entries, but real, significant changes. I'm worried that applying something like this late in the release cycle is just not a good idea, especially given the fact that it probably still needs significant revising. However, I'm fairly conservative by nature, so perhaps someone else will have a different opinion, or maybe there is a way to restructure it so that the needed changes are less invasive. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Planner (find_usable_indexes function, actually) could push pathkey expression into restriction clauses of index. I'm not fully satisfied with this piece of code, but, may be, someone has a better idea. I though about adding separate indexorderquals in IndexPath structure... Done, IndexScan and IndexPath have separate field to store order clauses. That's allowed to improve explain output: # EXPLAIN (COSTS OFF) SELECT * FROM point_tbl WHERE f1 @ '(-10,-10),(10,10)':: box ORDER BY f1 - '0,1'; QUERY PLAN Index Scan using gpointind on point_tbl Index Cond: (f1 @ '(10,10),(-10,-10)'::box) Sort Cond: (f1 - '(0,1)'::point) (3 rows) We are waiting feedback to choose a way of planner support of knn-search. Still TODO: - cost of index scan - Sort condition should not be ANDed in explain output - current patch remove support of IndexScanDesc-kill_prior_tuple, it's needed to restore support if it will not create too big overhead - documentation -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ builtin_knngist-0.4.1.gz Description: Unix tar archive -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Teodor Sigaev teo...@sigaev.ru writes: Planner (find_usable_indexes function, actually) could push pathkey expression into restriction clauses of index. I'm not fully satisfied with this piece of code, but, may be, someone has a better idea. I though about adding separate indexorderquals in IndexPath structure... Done, IndexScan and IndexPath have separate field to store order clauses. Why? Isn't that redundant with the pathkey structures? We generate enough paths during a complex planning problem that I'm not in favor of adding unnecessary structures to them. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Done, IndexScan and IndexPath have separate field to store order clauses. Why? Isn't that redundant with the pathkey structures? We generate enough paths during a complex planning problem that I'm not in favor of adding unnecessary structures to them. I found two ways to add support of knn-seaech to planner - 0.4 version: add sorting clauses to restrictclauses in find_usable_indexes, and there is two issues: - find_usable_indexes could not be used to find indexes for index and bitmap scans at once, because sorting clauses will be used in bitmap scan. Full scan of index with knn-ordering on large index is much more expensive. - implied/refused predicate machinery is teached to ignore sorting clauses, but it's not so obvious: it should ignore operation returning non-boolean values - 0.4.1 version: pull sort clauses separately and merge them with regular clauses at create_indexscan_plan function. That's solves problems above Do you suggest to construct that clauses from pathkey representation? And append constructed clauses to indexquals in create_indexscan_plan? -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Teodor Sigaev teo...@sigaev.ru writes: Do you suggest to construct that clauses from pathkey representation? And append constructed clauses to indexquals in create_indexscan_plan? I'd probably have to read the patch to make any intelligent suggestions ... and right now I'm busy with patches that are already in the commitfest. But usually it's a good idea to postpone work to createplan time if you can. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] KNNGiST for knn-search (WIP)
Hi! Contrib module is reworked as a patch for current GiST. Now GiST supports KNN-search, the query looks like SELECT * FROM point_tbl ORDER BY f1 - '0,1'; or SELECT * FROM point_tbl WHERE f1 @ '(-10,-10),(10,10)':: box ORDER BY f1 - '0,1'; Plans are: EXPLAIN (COSTS OFF) SELECT * FROM point_tbl ORDER BY f1 - '0,1'; QUERY PLAN - Index Scan using gpointind on point_tbl Index Cond: (f1 - '(0,1)'::point) EXPLAIN (COSTS OFF) SELECT * FROM point_tbl WHERE f1 @ '(-10,-10),(10,10)':: box ORDER BY f1 - '0,1'; QUERY PLAN -- Index Scan using gpointind on point_tbl Index Cond: ((f1 @ '(10,10),(-10,-10)'::box) AND (f1 - '(0,1)'::point)) pg_am now has new column amcanorderbyop (can order by operation), indexes with this flag enabled can be used to speedup operations, which returns non-boolean value, currently type of returned value should have default btree operator class to perform sort. Planner (find_usable_indexes function, actually) could push pathkey expression into restriction clauses of index. I'm not fully satisfied with this piece of code, but, may be, someone has a better idea. I though about adding separate indexorderquals in IndexPath structure... Both GiST's get methods are optimized and there is no overhead, since gistrescan method can choose what traversal algorithm to use using information about types of values returned by operations. If at least one of them returns non-boolean result, then KNN-search will be performed. The only change in interface of supporting functions is: consistentFn function could return float8 non-negative value and it's mandatory to perform KNN-search. Old-style consistent functions are supported. Patch contains (it still requires rbtree-0.5 and point_ops-0.4 patches): - GiST changes - changes in point_ops to support knn-search - contrib/pg_trgm now has new operation - returns distance between texts. This operation is supported in KNN-search - contrib/btree_gist provides - and its support for GiST for types int2, int4, int8, float4, float8, money, oid, interval, time, date, timestamp and timestamptz TODO: - selectivity of ordering operation should be 1.0 - current patch remove support of IndexScanDesc-kill_prior_tuple, it's needed to restore support if it will not create too big overhead - documentation -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ builtin_knngist-0.4.gz Description: Unix tar archive -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
