Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Jul 24, 2017 at 2:43 PM, Peter Geoghegan wrote: > On Mon, Jul 24, 2017 at 10:13 AM, Claudio Freire > wrote: >> Vacuum *might* be able to redistribute tuples too, while holding locks >> to all 3 pages (the two children and the parent page), since it

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Jul 24, 2017 at 10:13 AM, Claudio Freire wrote: > In most cases, the TID itself can be omitted when the key itself > differs already. > > When a split happens, a TID will be added referring to a real tid from > a child page iff necessary. > > This gives a lot of

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Jul 24, 2017 at 2:02 PM, Peter Geoghegan wrote: > On Mon, Jul 24, 2017 at 9:51 AM, Claudio Freire > wrote: >> My point was that the TID doesn't have to point to an actual tuple. >> >> It's more of a keyspace thing, so it doesn't need to match real

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Jul 24, 2017 at 9:51 AM, Claudio Freire wrote: > My point was that the TID doesn't have to point to an actual tuple. > > It's more of a keyspace thing, so it doesn't need to match real > tuples, it can just divide the keyspace with an arbitrary cutoff, and > should

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Wed, Nov 23, 2016 at 12:27 AM, Peter Geoghegan wrote: > On Mon, Nov 21, 2016 at 5:15 PM, Claudio Freire > wrote: >>> There are a couple >>> of tricky issues with that that you'd have to look out for, like >>> making sure that the high key continues to

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Fri, Jul 21, 2017 at 10:31 PM, Peter Geoghegan wrote: > On Wed, Aug 17, 2016 at 7:54 PM, Claudio Freire > wrote: >> The attached patch tries to maintain the initial status of B-Tree >> indexes, which are created with equal-key runs in physical order, >>

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Wed, Aug 17, 2016 at 7:54 PM, Claudio Freire wrote: > The attached patch tries to maintain the initial status of B-Tree > indexes, which are created with equal-key runs in physical order, > during the whole life of the B-Tree, and make key-tid pairs > efficiently

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Nov 21, 2016 at 5:15 PM, Claudio Freire wrote: >> There are a couple >> of tricky issues with that that you'd have to look out for, like >> making sure that the high key continues to hold a real TID, which at a >> glance looks like something that just happens

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Nov 21, 2016 at 5:42 PM, Peter Geoghegan wrote: >>> Or, you might want to make >>> sure that B-Tree tuple insertions still find that "first page" to >>> check, despite still generally treating heap item pointer as part of >>> the key proper (in unique indexes, it can

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Mon, Nov 21, 2016 at 9:42 AM, Claudio Freire wrote: >> I realized today, quite suddenly, why I disliked your original patch: >> it didn't go far enough with embracing the idea of >> heap-item-pointer-as-key. In other words, I didn't like that you >> didn't change

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Fri, Nov 18, 2016 at 11:09 PM, Peter Geoghegan wrote: > On Fri, Nov 18, 2016 at 5:27 PM, Claudio Freire > wrote: >> I've been changing the on-disk format considerably, to one that makes >> more sense. > > I can see how that would be necessary. I'm

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Fri, Nov 18, 2016 at 5:27 PM, Claudio Freire wrote: > I've been changing the on-disk format considerably, to one that makes > more sense. I can see how that would be necessary. I'm going to suggest some more things that need a new btree version number now, too. I

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Fri, Nov 18, 2016 at 10:05 PM, Peter Geoghegan wrote: > On Thu, Aug 18, 2016 at 2:15 PM, Peter Geoghegan wrote: >> I think that this is a bad idea. We need to implement suffix >> truncation of internal page index tuples at some point, to make them >> contain

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 2:15 PM, Peter Geoghegan wrote: > I think that this is a bad idea. We need to implement suffix > truncation of internal page index tuples at some point, to make them > contain less information from the original leaf page index tuple. > That's an important

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Sat, Aug 20, 2016 at 9:58 PM, Claudio Freire wrote: > On Sat, Aug 20, 2016 at 4:27 AM, Amit Kapila wrote: >> >> That makes sense, but this means there is a chance that the searches >> could lead to different buffers in case of uniqueness checks

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Sat, Aug 20, 2016 at 4:27 AM, Amit Kapila wrote: >> All uniqueness checks will find the same "nbuf" (read-locked), which >> is the first one that matches the key. >> >> They could have different "buf" buffers (the write-locked) one. But >> since read locks cannot be

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Sat, Aug 20, 2016 at 10:23 AM, Claudio Freire wrote: > On Sat, Aug 20, 2016 at 1:05 AM, Amit Kapila wrote: >> On Thu, Aug 18, 2016 at 8:24 AM, Claudio Freire >> wrote: >>> >>> A couple of points make me uneasy about

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Sat, Aug 20, 2016 at 1:53 AM, Claudio Freire wrote: > All uniqueness checks will try to read-lock nbuf > unless the uniqueness check for that insertion is done. That should read "all uniqueness checks will try to read-lock the buf unless the uniqueness check for that

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Sat, Aug 20, 2016 at 1:05 AM, Amit Kapila wrote: > On Thu, Aug 18, 2016 at 8:24 AM, Claudio Freire > wrote: >> >> A couple of points make me uneasy about this patch, yet I can think of >> no better alternative, so I seek feedback: >> >> -

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 8:24 AM, Claudio Freire wrote: > > A couple of points make me uneasy about this patch, yet I can think of > no better alternative, so I seek feedback: > > - introducing a different format for inner index tuples makes for an > invasive patch and

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:26 PM, Claudio Freire wrote: > On Thu, Aug 18, 2016 at 6:15 PM, Peter Geoghegan wrote: >> On Thu, Aug 18, 2016 at 1:41 PM, Claudio Freire >> wrote: >>> In fact, that's why non-leaf index tuples need a

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 5:04 PM, Claudio Freire wrote: > But the choice of split point may make a difference for future > insertions, so I'll look into that. A database product I worked on a long time ago had an interesting optimization for indexes that had multiple

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:38 PM, Peter Geoghegan wrote: > On Thu, Aug 18, 2016 at 2:26 PM, Claudio Freire > wrote: >> I see that. I could try to measure average depth to measure the impact >> this had on fan-in. >> >> While it should cut it in half for

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 2:26 PM, Claudio Freire wrote: > I see that. I could try to measure average depth to measure the impact > this had on fan-in. > > While it should cut it in half for narrow indexes, half of very high > is still high. Wide indexes, which are are the

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:27 PM, Tom Lane wrote: > Claudio Freire writes: >> On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner wrote: >>> Speaking of performance side effects, does this avoid O(N^2) >>> performance on index tuple

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

Claudio Freire writes: > On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner wrote: >> Speaking of performance side effects, does this avoid O(N^2) >> performance on index tuple insertion with duplicate values, for all >> insertion orderings? For example,

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:15 PM, Peter Geoghegan wrote: > On Thu, Aug 18, 2016 at 1:41 PM, Claudio Freire > wrote: >> In fact, that's why non-leaf index tuples need a different format, >> because while leaf index tuples contain the heap pointer already,

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

Claudio Freire wrote: > Unique indexes still need to scan all duplicates to check visibility > and will become O(N^2) there. That scenario doesn't matter, because on unique indexes there aren't many duplicate values anyway -- only one can be a live tuple. -- Álvaro Herrera

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 1:41 PM, Claudio Freire wrote: > In fact, that's why non-leaf index tuples need a different format, > because while leaf index tuples contain the heap pointer already, > non-leaf ones contain only the downlink, not the pointer into the > heap. To be

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:04 PM, Kevin Grittner wrote: > On Thu, Aug 18, 2016 at 3:41 PM, Claudio Freire > wrote: > >> It also makes index scans of the form >> >> SELECT * FROM t WHERE some_col = some_const; >> >> Scan the heap in sequential order,

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 3:41 PM, Claudio Freire wrote: > It also makes index scans of the form > > SELECT * FROM t WHERE some_col = some_const; > > Scan the heap in sequential order, even if some_col has low > cardinality (ie: the query returns lots of tuples), which is a

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 5:05 PM, Robert Haas wrote: > On Wed, Aug 17, 2016 at 10:54 PM, Claudio Freire > wrote: >> The attached patch tries to maintain the initial status of B-Tree >> indexes, which are created with equal-key runs in physical

Re: [HACKERS] [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Wed, Aug 17, 2016 at 10:54 PM, Claudio Freire wrote: > The attached patch tries to maintain the initial status of B-Tree > indexes, which are created with equal-key runs in physical order, > during the whole life of the B-Tree, and make key-tid pairs > efficiently