Thread

Re: ARC patent

John Hansen <john@geeknet.com.au> — 2005-01-17T08:04:49Z

> > FYI, IBM has applied for a patent on ARC (AFAICS the patent 
> > application is still pending, although the USPTO site is a 
> little hard to grok):
> 
> http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220040098541%22.PGNR.&OS=DN/20040098541&RS=DN/20040098541

How will this affect the release of 8.0?

Wasn't this implemented in the early stages of the 7.5 cycle, long before may 20?


... John

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T08:14:31Z

"John Hansen" <john@geeknet.com.au> writes:
> How will this affect the release of 8.0?

I don't think it needs to delay the release; the patent is only pending.
But we need to look into the problem.

			regards, tom lane

Re: ARC patent

Andrew Sullivan <ajs@crankycanuck.ca> — 2005-01-17T19:27:44Z

On Mon, Jan 17, 2005 at 03:14:31AM -0500, Tom Lane wrote:
> I don't think it needs to delay the release; the patent is only pending.
> But we need to look into the problem.

What will you do if the patent is granted, 8.0 is out there with the
offending code, and you get a cease-and-desist letter from IBM
demanding the removal of all offending code from the Net?  The code
would have to be yanked from CVS &c., in that case, no?  (IANAL, but
I think I may consult with one.)

A

-- 
Andrew Sullivan  | ajs@crankycanuck.ca
The fact that technology doesn't work is no bar to success in the marketplace.
		--Philip Greenspun

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-17T19:37:44Z

Andrew Sullivan wrote:
> On Mon, Jan 17, 2005 at 03:14:31AM -0500, Tom Lane wrote:
> > I don't think it needs to delay the release; the patent is only pending.
> > But we need to look into the problem.
> 
> What will you do if the patent is granted, 8.0 is out there with the
> offending code, and you get a cease-and-desist letter from IBM
> demanding the removal of all offending code from the Net?  The code
> would have to be yanked from CVS &c., in that case, no?  (IANAL, but
> I think I may consult with one.)

We can modify the code slightly to hopefully avoid the patent.  With the
US granting patents on even obvious ideas, I would think that most large
software projects, including commercial ones, already have tons of
patent violations in their code.  Does anyone think otherwise?

However, I will grant that ARC is not an obvious idea.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Joshua D. Drake <jd@commandprompt.com> — 2005-01-17T19:44:08Z

>We can modify the code slightly to hopefully avoid the patent.  With the
>US granting patents on even obvious ideas, I would think that most large
>software projects, including commercial ones, already have tons of
>patent violations in their code.  Does anyone think otherwise?
>
>However, I will grant that ARC is not an obvious idea.
>  
>

Speaking from a commercial perspective, if the community has
known patent violating code within its source tree, the community
needs to remove and or modify as to not violate that patent
before any continued release.

The last thing I am sure that:

RedHat
Pervasive
SRA
Fufitsu
PgSQL, Inc.
and of course
Command Prompt

want is a call from IBM saying... hey we aren't going to go
after the community but you need to pay up.

The patent risk is just entirely too great and it can greatly
hurt the community as a whole.

Sincerely,

Joshua D. Drake






-- 
Command Prompt, Inc., home of Mammoth PostgreSQL - S/ODBC and S/JDBC
Postgresql support, programming shared hosting and dedicated hosting.
+1-503-667-4564 - jd@commandprompt.com - http://www.commandprompt.com
PostgreSQL Replicator -- production quality replication for PostgreSQL

Re: ARC patent

Andrew Sullivan <ajs@crankycanuck.ca> — 2005-01-17T19:46:13Z

On Mon, Jan 17, 2005 at 02:37:44PM -0500, Bruce Momjian wrote:
> 
> We can modify the code slightly to hopefully avoid the patent.  With the

I guess what I'm very much worried about is that there is
potentially-infringing code there, we know about it, and we may press
ahead and release with it anyway.  IBM would justifiably jump on us
for that as a result.  What I simply don't know is what they can
require be done as a remedy.  If merely modifying the code is good
enough, fine.  But given how widely the code base will be
disseminated, I'm worried they might demand that we somehow track it
down and get rid of it.  That would be a significant distraction, I
think.

> US granting patents on even obvious ideas, I would think that most large
> software projects, including commercial ones, already have tons of
> patent violations in their code.  Does anyone think otherwise?

First, that's hardly a justification, and second, they're not all
subject to inspection.  Plus, this is a case where we _know_ about
the potential violation, and have had it pointed out to us, before
the code has been declared "released".

> However, I will grant that ARC is not an obvious idea.

Precisely, or we wouldn't be pleased with the implementation.

A

-- 
Andrew Sullivan  | ajs@crankycanuck.ca
I remember when computers were frustrating because they *did* exactly what 
you told them to.  That actually seems sort of quaint now.
		--J.D. Baldwin

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T19:48:46Z

Bruce Momjian <pgman@candle.pha.pa.us> writes:
> Andrew Sullivan wrote:
>> What will you do if the patent is granted, 8.0 is out there with the
>> offending code, and you get a cease-and-desist letter from IBM
>> demanding the removal of all offending code from the Net?

> We can modify the code slightly to hopefully avoid the patent.  With the
> US granting patents on even obvious ideas, I would think that most large
> software projects, including commercial ones, already have tons of
> patent violations in their code.  Does anyone think otherwise?

I think there is zero probability of being sued by IBM in the near
future.  They would instantly destroy the credibility and good
relationships they've worked so hard to build up with the entire
open source community.

However, I don't want to be beholden to IBM indefinitely --- in five
years their corporate strategy might change.  I think that a reasonable
response to this is to plan to get rid of ARC, or at least modify the
code enough to avoid the patent, in time for 8.1.  (It's entirely likely
that that will happen before the patent issues, anyway.)

			regards, tom lane

Re: ARC patent

Joshua D. Drake <jd@commandprompt.com> — 2005-01-17T19:57:33Z

>However, I don't want to be beholden to IBM indefinitely --- in five
>years their corporate strategy might change.  I think that a reasonable
>response to this is to plan to get rid of ARC, or at least modify the
>code enough to avoid the patent, in time for 8.1.  (It's entirely likely
>that that will happen before the patent issues, anyway.)
>
>			regards, tom lane
>  
>
IBM makes 20% of their money from licensing patents.

That alone makes this whole conversation scare the hell out of
me.

We should be as proactive as possible with this and remove
the code (or modify as required).

Sincerely,

Joshua D. Drake




>---------------------------(end of broadcast)---------------------------
>TIP 4: Don't 'kill -9' the postmaster
>  
>


-- 
Command Prompt, Inc., home of Mammoth PostgreSQL - S/ODBC and S/JDBC
Postgresql support, programming shared hosting and dedicated hosting.
+1-503-667-4564 - jd@commandprompt.com - http://www.commandprompt.com
PostgreSQL Replicator -- production quality replication for PostgreSQL

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T19:58:33Z

Andrew Sullivan <ajs@crankycanuck.ca> writes:
> I guess what I'm very much worried about is that there is
> potentially-infringing code there, we know about it, and we may press
> ahead and release with it anyway.  IBM would justifiably jump on us
> for that as a result.

With what?  They have no patent, yet, and may never have one.  If the
patent were already issued then I'd be much more concerned.

			regards, tom lane

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-17T20:01:39Z

Tom Lane wrote:
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Andrew Sullivan wrote:
> >> What will you do if the patent is granted, 8.0 is out there with the
> >> offending code, and you get a cease-and-desist letter from IBM
> >> demanding the removal of all offending code from the Net?
> 
> > We can modify the code slightly to hopefully avoid the patent.  With the
> > US granting patents on even obvious ideas, I would think that most large
> > software projects, including commercial ones, already have tons of
> > patent violations in their code.  Does anyone think otherwise?
> 
> I think there is zero probability of being sued by IBM in the near
> future.  They would instantly destroy the credibility and good
> relationships they've worked so hard to build up with the entire
> open source community.
> 
> However, I don't want to be beholden to IBM indefinitely --- in five
> years their corporate strategy might change.  I think that a reasonable
> response to this is to plan to get rid of ARC, or at least modify the
> code enough to avoid the patent, in time for 8.1.  (It's entirely likely
> that that will happen before the patent issues, anyway.)

We may already have modified the code enough to avoid the patent.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-17T20:05:20Z

Tom Lane wrote:
> Andrew Sullivan <ajs@crankycanuck.ca> writes:
> > I guess what I'm very much worried about is that there is
> > potentially-infringing code there, we know about it, and we may press
> > ahead and release with it anyway.  IBM would justifiably jump on us
> > for that as a result.
> 
> With what?  They have no patent, yet, and may never have one.  If the
> patent were already issued then I'd be much more concerned.

One big question is why we pulled so directly from ideas on an IBM web
site?  That is very atypical of us.

Because we used it, I assumed the ideas were available for all to use
without patent restriction.  Obviously not.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Andrew Dunstan <andrew@dunslane.net> — 2005-01-17T20:11:16Z


Tom Lane wrote:

>Bruce Momjian <pgman@candle.pha.pa.us> writes:
>  
>
>>Andrew Sullivan wrote:
>>    
>>
>>>What will you do if the patent is granted, 8.0 is out there with the
>>>offending code, and you get a cease-and-desist letter from IBM
>>>demanding the removal of all offending code from the Net?
>>>      
>>>
>
>  
>
>>We can modify the code slightly to hopefully avoid the patent.  With the
>>US granting patents on even obvious ideas, I would think that most large
>>software projects, including commercial ones, already have tons of
>>patent violations in their code.  Does anyone think otherwise?
>>    
>>
>
>I think there is zero probability of being sued by IBM in the near
>future.  They would instantly destroy the credibility and good
>relationships they've worked so hard to build up with the entire
>open source community.
>
>However, I don't want to be beholden to IBM indefinitely --- in five
>years their corporate strategy might change.  I think that a reasonable
>response to this is to plan to get rid of ARC, or at least modify the
>code enough to avoid the patent, in time for 8.1.  (It's entirely likely
>that that will happen before the patent issues, anyway.)
>
>
>  
>

There's a very recent paper at 
http://carmen.cs.uiuc.edu/~zchen9/paper/TPDS-final.ps on an alternative 
to ARC which claims superior performance ...

Maybe this will give us added impetus to make the 8.1 cycle short, as 
has been suggested previously.


cheers

andrew

Re: ARC patent

Andrew Sullivan <ajs@crankycanuck.ca> — 2005-01-17T20:16:49Z

On Mon, Jan 17, 2005 at 02:58:33PM -0500, Tom Lane wrote:
> Andrew Sullivan <ajs@crankycanuck.ca> writes:
> > ahead and release with it anyway.  IBM would justifiably jump on us
> > for that as a result.
> 
> With what?  They have no patent, yet, and may never have one.  If the
> patent were already issued then I'd be much more concerned.

With a team of lawyers which we can't match.  They may never have a
patent, or they may get it next month.  I'd feel more
comfortable if I knew what sort of remedies they could demand (I have
a call open to a lawyer I believe will give me a conservative answer
about that).  

What I can say, for sure, is that no responsible corporate user will
be able to use this code with the threat hanging over.  The recent
SCO stuff ought to be a lesson here: their claims appear to have been
completely baseless, but companies still spent a pile of time and
money on the issue.  It'll be far worse in a case where the
infringment is real and, yet worse, intentional.

A
-- 
Andrew Sullivan  | ajs@crankycanuck.ca
When my information changes, I alter my conclusions.  What do you do sir?
		--attr. John Maynard Keynes

Re: ARC patent

Andrew Sullivan <ajs@crankycanuck.ca> — 2005-01-17T20:17:35Z

On Mon, Jan 17, 2005 at 02:48:46PM -0500, Tom Lane wrote:
> I think there is zero probability of being sued by IBM in the near
> future.  

They won't sue the project.  They'll send corporate users a bill,
instead, for a license. 

A

-- 
Andrew Sullivan  | ajs@crankycanuck.ca
A certain description of men are for getting out of debt, yet are
against all taxes for raising money to pay it off.
		--Alexander Hamilton

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T20:18:15Z

Andrew Dunstan <andrew@dunslane.net> writes:
> There's a very recent paper at 
> http://carmen.cs.uiuc.edu/~zchen9/paper/TPDS-final.ps on an alternative 
> to ARC which claims superior performance ...

Personally, I'd prefer a very *old* paper ;-)

> Maybe this will give us added impetus to make the 8.1 cycle short, as 
> has been suggested previously.

Agreed.  If we have a plan to replace the code in three-to-six months
I think we are all right, especially seeing that this is only a pending
patent and not enforceable yet.

To those who say "you can't release with a potential patent problem"
I would say that we already have.  There are lots of people running
8.0 beta and RC releases --- if history is any guide, many of them
will continue running those releases for a long time, rather than
update to final.  We can never erase all trace that we ever touched
ARC (would you have us retroactively edit our CVS history?) and AFAIK
we would not be required to do so anyway.  The legal requirement would
be to cure the breach going forward, ie, get it out of our future
releases.  That we can and should do, but there's no need for panic.

			regards, tom lane

Re: ARC patent

Jeff Trout <threshar@torgo.978.org> — 2005-01-17T20:21:59Z

On Jan 17, 2005, at 2:57 PM, Joshua D. Drake wrote:

>
> We should be as proactive as possible with this and remove
> the code (or modify as required).
>

Perhaps a member of -CORE should contact IBM.  The ball is out there 
now due to the discussion on this list that we know we might have 
infringing code.  Might as well try to play "good citizen" and talk 
with them, perhaps they'll give us some sort of indemnity for 8.0 so we 
can get something perhaps better for 8.1.

--
Jeff Trout <jeff@jefftrout.com>
http://www.jefftrout.com/
http://www.stuarthamm.net/

Re: ARC patent

Jeff Davis <jdavis-pgsql@empires.org> — 2005-01-17T20:22:30Z

> I think there is zero probability of being sued by IBM in the near
> future.  They would instantly destroy the credibility and good
> relationships they've worked so hard to build up with the entire
> open source community.
> 
> However, I don't want to be beholden to IBM indefinitely --- in five
> years their corporate strategy might change.  I think that a reasonable
> response to this is to plan to get rid of ARC, or at least modify the
> code enough to avoid the patent, in time for 8.1.  (It's entirely likely
> that that will happen before the patent issues, anyway.)
> 

If PostgreSQL 8.0 is released with ARC, and then PostgreSQL 8.1 is
released without ARC, and then the patent is granted to IBM, would
everyone be fine if they just all switched to 8.1 at that time? Or would
we have some kind of retroactive problem? Would people that are still
using 8.0 in production, but not distributing it, have difficulty?

Regards,
	Jeff

Re: ARC patent

Joshua D. Drake <jd@commandprompt.com> — 2005-01-17T20:30:39Z

>If PostgreSQL 8.0 is released with ARC, and then PostgreSQL 8.1 is
>released without ARC, and then the patent is granted to IBM, would
>everyone be fine if they just all switched to 8.1 at that time? Or would
>we have some kind of retroactive problem? Would people that are still
>using 8.0 in production, but not distributing it, have difficulty?
>  
>
The biggest problem is going to be that if we release 8 with
the patented stuff, then for a minimum of 3 years there will
be liability for anyone running 8.

We still have people running 7.1 and once you get something
into production you typically don't just "change" it.

Basically I think the fact that we are even considering leaving
the knowingly infringing code in 8 is presenting a horrible
face to the community.

Sincerely,

Joshua D. Drake



>Regards,
>	Jeff
>
>
>
>---------------------------(end of broadcast)---------------------------
>TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org
>  
>


-- 
Command Prompt, Inc., home of Mammoth PostgreSQL - S/ODBC and S/JDBC
Postgresql support, programming shared hosting and dedicated hosting.
+1-503-667-4564 - jd@commandprompt.com - http://www.commandprompt.com
PostgreSQL Replicator -- production quality replication for PostgreSQL

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-17T20:48:38Z

Andrew Sullivan wrote:
> With a team of lawyers which we can't match.  They may never have a
> patent, or they may get it next month.  I'd feel more
> comfortable if I knew what sort of remedies they could demand (I have
> a call open to a lawyer I believe will give me a conservative answer
> about that).  
> 
> What I can say, for sure, is that no responsible corporate user will
> be able to use this code with the threat hanging over.  The recent
> SCO stuff ought to be a lesson here: their claims appear to have been
> completely baseless, but companies still spent a pile of time and
> money on the issue.  It'll be far worse in a case where the
> infringment is real and, yet worse, intentional.

You want scarey --- forget the IBM patent.  Find an Oracle or Microsoft
patent that is similar to something in our code.  It will might not be
exact, but our ARC isn't exact either.

Basically any organization that wants to produce patent-free code would
need one lawyer for every five programmers, and even then it isn't 100%.
The method I have heard to find infringement sounds pretty imprecise.

The remedy for patent infringment I think is usually to stop using the
patented idea, rather than punitive damages, unlike copyright.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T20:57:53Z

"Joshua D. Drake" <jd@commandprompt.com> writes:
> The biggest problem is going to be that if we release 8 with
> the patented stuff, then for a minimum of 3 years there will
> be liability for anyone running 8.

Do you honestly think that this is the only patented algorithm anywhere
in there?

Now that we've been made aware that there is a pending (one more time:
pending, not issued) patent on it, we will work on removing the affected
code in an orderly fashion.  I don't think there is need for panic.

			regards, tom lane

Re: ARC patent

Marc G. Fournier <scrappy@postgresql.org> — 2005-01-17T21:04:36Z

On Mon, 17 Jan 2005, Andrew Sullivan wrote:

> On Mon, Jan 17, 2005 at 02:37:44PM -0500, Bruce Momjian wrote:
>>
>> We can modify the code slightly to hopefully avoid the patent.  With the
>
> I guess what I'm very much worried about is that there is
> potentially-infringing code there, we know about it, and we may press
> ahead and release with it anyway.  IBM would justifiably jump on us
> for that as a result.

I thought the patnt was only pending, not granted?


----
Marc G. Fournier           Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org           Yahoo!: yscrappy              ICQ: 7615664

Re: ARC patent

Andrew Sullivan <ajs@crankycanuck.ca> — 2005-01-17T21:05:54Z

On Mon, Jan 17, 2005 at 05:04:36PM -0400, Marc G. Fournier wrote:
> 
> I thought the patnt was only pending, not granted?

That's right, and it's what gives Tom's arguments some weight.

A

-- 
Andrew Sullivan  | ajs@crankycanuck.ca
Information security isn't a technological problem.  It's an economics
problem.
		--Bruce Schneier

Re: ARC patent

Jeff Davis <jdavis-pgsql@empires.org> — 2005-01-17T21:06:04Z

> You want scarey --- forget the IBM patent.  Find an Oracle or Microsoft
> patent that is similar to something in our code.  It will might not be
> exact, but our ARC isn't exact either.
> 
> Basically any organization that wants to produce patent-free code would
> need one lawyer for every five programmers, and even then it isn't 100%.
> The method I have heard to find infringement sounds pretty imprecise.
> 
> The remedy for patent infringment I think is usually to stop using the
> patented idea, rather than punitive damages, unlike copyright.
> 

Is that for all kinds of patent infringement, or only the
didn't-know-better kind? Right now I don't think we can claim
"didn't-know-better".

Also, does "stop" mean stop distributing the patented process, or stop
using all installations?

Regards,
	Jeff Davis

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-17T21:09:29Z

Jeff Davis wrote:
> 
> > You want scarey --- forget the IBM patent.  Find an Oracle or Microsoft
> > patent that is similar to something in our code.  It will might not be
> > exact, but our ARC isn't exact either.
> > 
> > Basically any organization that wants to produce patent-free code would
> > need one lawyer for every five programmers, and even then it isn't 100%.
> > The method I have heard to find infringement sounds pretty imprecise.
> > 
> > The remedy for patent infringment I think is usually to stop using the
> > patented idea, rather than punitive damages, unlike copyright.
> > 
> 
> Is that for all kinds of patent infringement, or only the
> didn't-know-better kind? Right now I don't think we can claim
> "didn't-know-better".

Didn't know better has no status for patents.  Copyright stuff is pretty
easy to avoid --- just don't copy stuff and you are OK, and most
companies are good at enforcing that part.  

> Also, does "stop" mean stop distributing the patented process, or stop
> using all installations?

Not sure.  The PostgreSQL development group doesn't have installations,
do we?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-17T23:15:04Z

On Mon, 2005-01-17 at 12:30 -0800, Joshua D. Drake wrote:
> The biggest problem is going to be that if we release 8 with
> the patented stuff, then for a minimum of 3 years there will
> be liability for anyone running 8.
> 
> We still have people running 7.1 and once you get something
> into production you typically don't just "change" it.

Keep in mind that it would be conceivable to ship an 8.0.x release which
replaces ARC with another algorithm. That would be a somewhat
non-trivial change, but there's no reason we need to wait for a major
release (i.e. 8.1 or 8.2) to replace ARC.

> Basically I think the fact that we are even considering leaving
> the knowingly infringing code in 8 is presenting a horrible
> face to the community.

I agree with Tom -- this shouldn't be an impediment to releasing 8.0,
but it definitely warrants attention in the future.

-Neil

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-17T23:43:28Z

Neil Conway <neilc@samurai.com> writes:
> Keep in mind that it would be conceivable to ship an 8.0.x release which
> replaces ARC with another algorithm. That would be a somewhat
> non-trivial change, but there's no reason we need to wait for a major
> release (i.e. 8.1 or 8.2) to replace ARC.

It's not that we couldn't fold a non-ARC algorithm into the 8.0.x
release series, it's that it'd be a fairly fundamental change in
some critical code.  Critical from both the reliability and performance
standpoints.  I would be comfortable with developing a replacement
algorithm as part of the 8.1 development cycle, and then considering
a back-patch after 8.1 is out and has shown that it's not completely
broken.  But to replace it with less testing than that would be
irresponsible, at least by the standards we have customarily used for
minor releases.

This is assuming that we conclude we need a whole new algorithm to
dodge the patent.  Another line of attack should be to see whether we
can make minor tweaks to avoid it.  I'm pessimistic about that, but
it deserves some amount of investigation before we go down the wholesale
replacement path.

We already had been considering a short development cycle for 8.1, and
I think that this issue will set that decision in stone.  What I'm
currently thinking about is a couple of months development and the same
for beta, which would allow a release in June or so.  I have already
suggested to core that we should insist on 8.1 not requiring an initdb,
so as to ensure that people will migrate up to it easily from 8.0.
Aside from the ARC issue, we have already one significant Windows
porting issue (%$n in message strings) and I'm sure we will find more
once 8.0 is out and getting some real use.  I would expect us to focus
on fixing issues of that caliber and probably being pretty stingy on
new features.

(Of course, if we do take this approach, it's questionable whether we'd
need to bother with a back-patch.)

			regards, tom lane

Re: ARC patent

Simon Riggs <simon@2ndquadrant.com> — 2005-01-17T23:56:35Z

On Tue, 2005-01-18 at 10:15 +1100, Neil Conway wrote:
> On Mon, 2005-01-17 at 12:30 -0800, Joshua D. Drake wrote:
> > The biggest problem is going to be that if we release 8 with
> > the patented stuff, then for a minimum of 3 years there will
> > be liability for anyone running 8.
> > 
> > We still have people running 7.1 and once you get something
> > into production you typically don't just "change" it.
> 
> Keep in mind that it would be conceivable to ship an 8.0.x release which
> replaces ARC with another algorithm. That would be a somewhat
> non-trivial change, but there's no reason we need to wait for a major
> release (i.e. 8.1 or 8.2) to replace ARC.

Agreed.

> > Basically I think the fact that we are even considering leaving
> > the knowingly infringing code in 8 is presenting a horrible
> > face to the community.
> 
> I agree with Tom -- this shouldn't be an impediment to releasing 8.0,
> but it definitely warrants attention in the future.
> 

Agreed.

-- 
Best Regards, Simon Riggs

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-18T22:33:49Z

On Mon, 2005-01-17 at 15:11 -0500, Andrew Dunstan wrote:
> There's a very recent paper at 
> http://carmen.cs.uiuc.edu/~zchen9/paper/TPDS-final.ps on an alternative 
> to ARC which claims superior performance ...

>From a quick glance, this doesn't look applicable. The authors are
discussing buffer replacement strategies for a multi-level cache
hierarchy (e.g. they would call the DBMS buffer cache "L1", and the
kernel I/O cache "L2" -- note that despite the terminology, this has
little in common with L1/L2 caches in processors). They don't really
address caching for the L1-only case -- they're concerned with proposing
algorithms to manage the L2 cache (with or without explicit knowledge
about the content of the L1 cache).

A few years ago Tom implemented the LRU-K replacement policy[1], but
AFAIK the performance results from that weren't very positive (since the
implementation of LRU-K requires a heap and is therefore logarithmic
rather than constant time, that makes sense). The 2Q algorithm looks
like it might be worth investigating[2].

-Neil

[1] http://citeseer.ist.psu.edu/16869.html
[2] http://citeseer.ist.psu.edu/63909.html

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-18T23:48:00Z

On Mon, 2005-01-17 at 18:43 -0500, Tom Lane wrote:
> I have already
> suggested to core that we should insist on 8.1 not requiring an initdb,
> so as to ensure that people will migrate up to it easily from 8.0.

So is it firm policy that changes that require a catversion update
cannot be made during the 8.1 cycle?

(Needless to say, it would be good to get this sorted out early on in
the 8.1 development cycle, to avoid the need to revert patches at some
point down the line. For those of us working on large projects that will
definitely require an initdb, it would also be good to know -- as this
policy will likely prevent that work from getting into 8.1)

-Neil

Re: ARC patent

Alvaro Herrera <alvherre@dcc.uchile.cl> — 2005-01-19T00:10:29Z

On Wed, Jan 19, 2005 at 10:48:00AM +1100, Neil Conway wrote:
> On Mon, 2005-01-17 at 18:43 -0500, Tom Lane wrote:
> > I have already
> > suggested to core that we should insist on 8.1 not requiring an initdb,
> > so as to ensure that people will migrate up to it easily from 8.0.
> 
> So is it firm policy that changes that require a catversion update
> cannot be made during the 8.1 cycle?

Hmm.  That means my shared dependency patch cannot go in, nor anything
I do about shared row locking.  Fortunately that leaves the multitable
truncate and the C "install" replacement free to be applied.

-- 
Alvaro Herrera (<alvherre[@]dcc.uchile.cl>)
You liked Linux a lot when he was just the gawky kid from down the block
mowing your lawn or shoveling the snow. But now that he wants to date
your daughter, you're not so sure he measures up. (Larry Greenemeier)

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-19T04:26:14Z

Neil Conway <neilc@samurai.com> writes:
> On Mon, 2005-01-17 at 18:43 -0500, Tom Lane wrote:
>> I have already
>> suggested to core that we should insist on 8.1 not requiring an initdb,
>> so as to ensure that people will migrate up to it easily from 8.0.

> So is it firm policy that changes that require a catversion update
> cannot be made during the 8.1 cycle?

Not yet --- I suggested it but didn't get any yeas or nays.  I don't
feel this is solely core's decision anyway ... what do the assembled
hackers think?

> (Needless to say, it would be good to get this sorted out early on in
> the 8.1 development cycle, to avoid the need to revert patches at some
> point down the line. For those of us working on large projects that will
> definitely require an initdb, it would also be good to know -- as this
> policy will likely prevent that work from getting into 8.1)

Yes, it has to be decided one way or the other soon.

One way to have our cake and eat it too would be for someone to
resurrect pg_upgrade during this devel cycle.  Anyone feel like
working on that?

			regards, tom lane

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-19T05:25:43Z

On Tue, 2005-01-18 at 23:26 -0500, Tom Lane wrote:
> Not yet --- I suggested it but didn't get any yeas or nays.  I don't
> feel this is solely core's decision anyway ... what do the assembled
> hackers think?

I'm not sure it's a great idea.

I'm not aware of a recent example of short development cycles working
well in this project. That isn't to say we *can't* do one effectively,
just that history is not on our side (does anyone recall the plans to
finish off Win32 in 7.5 and get it out the door quickly?)

The primary justification I've heard for the no-initdb policy is that it
would provide a smooth upgrade path for 8.0 users if/when the ARC patent
is granted. I don't think this is the best way to deal with the ARC
issue: it seems silly to handicap an entire development cycle because of
one (potential) problem. Not to mention that it's not even certain
whether an ARC replacement will be needed: we might be able to adapt the
existing code to workaround the patent, the patent might not be granted,
or IBM might grant us a license to use it. It's also worth emphasizing
that this would be a rather severe limitation on what kind of new
developments can go into 8.1.

I think the proper fix for the ARC issue is an 8.0.x release with a new
replacement policy. To avoid introducing instability into 8.0, we should
obviously test the new buffer replacement policy *very* carefully.
However, I think the ARC replacement should *not* be a fundamental
change in behavior: the algorithm should still attempt to balance
recency and frequency, to adjust dynamically to changes in workload, to
avoid "sequential flooding", and to allow constant-time page
replacement. Ideally the ARC replacement would do something similar to
ARC but via a different means. If such a patch were developed, I don't
think it would be a herculean task to include it in an 8.0.x release
after a lot of careful testing and code review.

-Neil

Re: ARC patent

Tom Lane <tgl@sss.pgh.pa.us> — 2005-01-19T05:39:28Z

Neil Conway <neilc@samurai.com> writes:
> On Tue, 2005-01-18 at 23:26 -0500, Tom Lane wrote:
>> Not yet --- I suggested it but didn't get any yeas or nays.  I don't
>> feel this is solely core's decision anyway ... what do the assembled
>> hackers think?

> I'm not aware of a recent example of short development cycles working
> well in this project.

Granted, but we haven't tried very hard either.

> I think the proper fix for the ARC issue is an 8.0.x release with a new
> replacement policy. To avoid introducing instability into 8.0, we should
> obviously test the new buffer replacement policy *very* carefully.

That testing isn't going to magically appear from somewhere.  Unless the
proposed fix is only a very small variation on what we have (which seems
unlikely to get around the patent), I wouldn't have any confidence in it
until it's at least survived an 8.1 beta cycle.  So I don't believe in
the concept of a near-term 8.0.x fix while 8.1 slides along on a slow
devel schedule.

What this really boils down to is whether we think we have
order-of-a-year before the patent is issued.  I'm nervous about
assuming that.  I'd like to have a plan that will produce a tested,
credible patch in less than six months.

			regards, tom lane

Re: ARC patent

Simon Riggs <simon@2ndquadrant.com> — 2005-01-19T08:20:16Z

On Wed, 2005-01-19 at 16:25 +1100, Neil Conway wrote:
> On Tue, 2005-01-18 at 23:26 -0500, Tom Lane wrote:
> > Not yet --- I suggested it but didn't get any yeas or nays.  I don't
> > feel this is solely core's decision anyway ... what do the assembled
> > hackers think?
> 
> I'm not sure it's a great idea.

It's not, but may still be required. We should defer any changes for a
month, just to see if its feasible to do that.

> I think the proper fix for the ARC issue is an 8.0.x release with a new
> replacement policy. To avoid introducing instability into 8.0, we should
> obviously test the new buffer replacement policy *very* carefully.

Agreed.

I prefer a plan that, if required, back ports NewStrategy to 8.0.x than
one that hobbles 8.1, just in case.

> However, I think the ARC replacement should *not* be a fundamental
> change in behavior: the algorithm should still attempt to balance
> recency and frequency, to adjust dynamically to changes in workload, to
> avoid "sequential flooding", and to allow constant-time page
> replacement. 

Agreed: Those are the requirements. It must also scale better as well.

All of which have sufficient prior art that they could never be seen to
in-themselves form the basis of a patent.

> If such a patch were developed, I don't
> think it would be a herculean task to include it in an 8.0.x release
> after a lot of careful testing and code review.

Agreed.

-- 
Best Regards, Simon Riggs

Re: ARC patent

Andreas Pflug <pgadmin@pse-consulting.de> — 2005-01-19T11:33:15Z

Tom Lane wrote:

> 
> What this really boils down to is whether we think we have
> order-of-a-year before the patent is issued.  I'm nervous about
> assuming that.  I'd like to have a plan that will produce a tested,
> credible patch in less than six months.

Why not having a beta on an 8.0.x version if ARC replacement has to be 
released shortly?

Regards,
Andreas

Re: ARC patent

Stephen Frost <sfrost@snowman.net> — 2005-01-19T14:20:13Z

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> Neil Conway <neilc@samurai.com> writes:
> > So is it firm policy that changes that require a catversion update
> > cannot be made during the 8.1 cycle?
> 
> Not yet --- I suggested it but didn't get any yeas or nays.  I don't
> feel this is solely core's decision anyway ... what do the assembled
> hackers think?

Don't know if I count, but I've noticed a number of things that people
are working on that require initdb's and I think they'd be nice to allow
in 8.1 unless the 8.1 cycle is *very* short.  I'd also like to get group
ownership & roles in soon, if possible (and if I find enough time to
finish and properly test it).

> One way to have our cake and eat it too would be for someone to
> resurrect pg_upgrade during this devel cycle.  Anyone feel like
> working on that?

Of course, this would be really nice too..

	Stephen

Re: ARC patent

Matthew T. O'Connor <matthew@zeut.net> — 2005-01-19T16:50:33Z

Tom Lane wrote:

>Neil Conway <neilc@samurai.com> writes:
>  
>
>>So is it firm policy that changes that require a catversion update
>>cannot be made during the 8.1 cycle?
>>    
>>
>
>Not yet --- I suggested it but didn't get any yeas or nays.  I don't
>feel this is solely core's decision anyway ... what do the assembled
>hackers think?
>

My personal goal for 8.1 is to get autovacuum integrated into the 
backend.  The patch I submitted during the 8.0 dev cycle required a new 
system table for autovacuum data.  Anyway we could get around that 
without bumping catversion?  Perhaps the vacuum daemon could add the 
table if it's not found?

Re: ARC patent

Hannu Krosing <hannu@tm.ee> — 2005-01-20T00:06:03Z

Ühel kenal päeval (kolmapäev, 19. jaanuar 2005, 00:39-0500), kirjutas
Tom Lane:
> What this really boils down to is whether we think we have
> order-of-a-year before the patent is issued.  I'm nervous about
> assuming that.  I'd like to have a plan that will produce a tested,
> credible patch in less than six months.

Can't this thing be abstracted out like so many other things are (types,
functions, pl-s) or should be/were once (storage managers) ?

Like different scheduling algorithms in the linux kernel ?

What makes this inherently so difficult to do ? 

Is it just testing or something for fundamental?

Most likely also the gathering of information needed to decide on
replacement policy.

If just testing, we could move fast to supplying two algos LRU/ARC ,
selectable at startup. 

This has extra benefit of allowing easily testing other algorithms - I
guess that for unpredictable workloads a random policy in 80% tail of
LRU cache should not do too badly, probably better than 7.x's seqscan
polluteable LRU ;)


-- 
Hannu Krosing <hannu@tm.ee>

Re: ARC patent

Hannu Krosing <hannu@tm.ee> — 2005-01-20T00:34:17Z

Ühel kenal päeval (esmaspäev, 17. jaanuar 2005, 11:57-0800), kirjutas
Joshua D. Drake:
> >However, I don't want to be beholden to IBM indefinitely --- in five
> >years their corporate strategy might change.  I think that a reasonable
> >response to this is to plan to get rid of ARC, or at least modify the
> >code enough to avoid the patent, in time for 8.1.  (It's entirely likely
> >that that will happen before the patent issues, anyway.)
> >
> >			regards, tom lane
> >  
> >
> IBM makes 20% of their money from licensing patents.

OTOH they make >80% of their goodwill in OS community out of being nice
to opensource projects. Or at least avoiding being seen as downright
unfair. So I expect at least some civility from them if and when thei
get the patent.

I'm also suspect that PG "possibly infringes" on enough already granted
patents (some likely owned by IBM) to at least get it into as much
trouble as SCO has caused to IBM. 

The reason we havent seen any IBM lawyers is that demanding royalties
from "PostgreSQL Global Development Group" would be bad publicity, not
thet they could not have done it if PG were a product of "Mom&Pop
Software Startup Co".

What comes to companies that take PG source, rebrand it and sell as
closed-source product, then they have several options :
 1) just wait and hope that the public version evolves past ARC patent
    before the patent is granted.
 2) licence the patent from IBM, if and when it is granted
 3) rewrite the part that uses ARC (and if they're really paranoid, 
    then parts bordering it) in their commercial version.
 4) hire some core developers to do 3) in the public version

-- 
Hannu Krosing <hannu@tm.ee>

Re: ARC patent

Hannu Krosing <hannu@tm.ee> — 2005-01-20T00:54:27Z

Ühel kenal päeval (esmaspäev, 17. jaanuar 2005, 14:48-0500), kirjutas
Tom Lane:
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Andrew Sullivan wrote:
> >> What will you do if the patent is granted, 8.0 is out there with the
> >> offending code, and you get a cease-and-desist letter from IBM
> >> demanding the removal of all offending code from the Net?
> 
> > We can modify the code slightly to hopefully avoid the patent.  With the
> > US granting patents on even obvious ideas, I would think that most large
> > software projects, including commercial ones, already have tons of
> > patent violations in their code.  Does anyone think otherwise?
> 
> I think there is zero probability of being sued by IBM in the near
> future.  They would instantly destroy the credibility and good
> relationships they've worked so hard to build up with the entire
> open source community.

Agreed

> However, I don't want to be beholden to IBM indefinitely --- in five
> years their corporate strategy might change.  I think that a reasonable
> response to this is to plan to get rid of ARC, or at least modify the
> code enough to avoid the patent, in time for 8.1.  (It's entirely likely
> that that will happen before the patent issues, anyway.)

I'd rather like a solution where the cache replacement policy has clean-
enough interface to have many competing algorithms/implementations,
probably even selactable at startup (or even runtime ;).

Firstly, I'm sure that there is no single best strategy (even ARC) for
all kinds of workloads  - think OLTP v.s.OLAP.

Secondly, some people might want to use ARC even if and when IBM gets
the patent, even badly enough to license it from IBM. (We are not
obliged to design an interfaces that prevents usage of patented stuff as
this is generally impossible.)

Thirdly, having it as a well-defined component/API might encourage more
research on different algorithms - see how many schedulers linux 2.6
has, both for processes and disk io.

-- 
Hannu Krosing <hannu@tm.ee>

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-20T12:17:13Z

Simon Riggs wrote:
>>However, I think the ARC replacement should *not* be a fundamental
>>change in behavior: the algorithm should still attempt to balance
>>recency and frequency, to adjust dynamically to changes in workload, to
>>avoid "sequential flooding", and to allow constant-time page
>>replacement.
> 
> Agreed: Those are the requirements. It must also scale better as well.

On thinking about this more, I'm not sure these are the right goals for 
an 8.0.x replacement algorithm. For 8.1 we should definitely Do The 
Right Thing and develop a complete ARC replacement. For 8.0.x, I wonder 
if it would be better to just replace ARC with LRU. The primary 
advantage to doing this is LRU's simplicity -- if we're concerned about 
introducing regressions in stability into 8.0, this is likely the best 
way to reduce the chance of that happening. Furthermore, LRU's behavior 
with PostgreSQL is well-known and has been extensively tested. A complex 
ARC replacement would receive even less testing than ARC itself has 
received -- which isn't a whole lot, in comparison with LRU.

Of course, the downside is that we lose the benefits of ARC or an 
ARC-like algorithm in 8.0. That would be unfortunate, but I don't think 
it is a catastrophe. The other bufmgr-related changes (vacuum hints, 
bgwriter and vacuum delay) should ensure that VACUUM still has a much 
reduced impact on system performance. Sequential scans will still flood 
the cache, but I don't view that as an enormous problem. In other words, 
I think a more intelligent replacement policy would be nice to have, but 
at this point in the 8.0 development cycle we should go with the 
simplest solution that we know is likely to work -- namely, LRU.

-Neil

Re: ARC patent

Hannu Krosing <hannu@tm.ee> — 2005-01-21T00:31:40Z

Ühel kenal päeval (neljapäev, 20. jaanuar 2005, 23:17+1100), kirjutas
Neil Conway:
> Simon Riggs wrote:
> >>However, I think the ARC replacement should *not* be a fundamental
> >>change in behavior: the algorithm should still attempt to balance
> >>recency and frequency, to adjust dynamically to changes in workload, to
> >>avoid "sequential flooding", and to allow constant-time page
> >>replacement.
> > 
> > Agreed: Those are the requirements. It must also scale better as well.
> 
> On thinking about this more, I'm not sure these are the right goals for 
> an 8.0.x replacement algorithm. For 8.1 we should definitely Do The 
> Right Thing and develop a complete ARC replacement. For 8.0.x, I wonder 
> if it would be better to just replace ARC with LRU. The primary 
> advantage to doing this is LRU's simplicity -- if we're concerned about 
> introducing regressions in stability into 8.0, this is likely the best 
> way to reduce the chance of that happening. Furthermore, LRU's behavior 
> with PostgreSQL is well-known and has been extensively tested. 

If we are going the "simple" way, i have two simple suggestions:

1) We should do something about seqscans polluting LRU - perhaps insert
pages brought into memory by seqscan near the end of LRU list. Or just
swich off postgresqls internal cachin alltogether when doing seqscans
and rely on underlying systems caching entirely (as we cant switch it
off anyway)

2) Another simple, but nondeterministic, hack would be using randomness,
i.e. 

  2.1) select a random buffer in LR side half (or 30% or 60%) of 
       for replacement. 

  2.2) dont last accessed pages to top of LRU list immediately, 
       just push them uphill some amount, either random, or 
       perhaps 1/2 the way to top at each access.

This should be quite qood strategy for avoiding disastrous failings on
specific pathological workloads, at the cost of less than optimal
behaviour in easily analysed standard cases.

> Of course, the downside is that we lose the benefits of ARC or an 
> ARC-like algorithm in 8.0. That would be unfortunate, but I don't think 
> it is a catastrophe. 

The only case this would be a catastrophe, is for production OLTP
workloads that did fine with ARC but get overloaded when using LRU.

> The other bufmgr-related changes (vacuum hints, 
> bgwriter and vacuum delay) should ensure that VACUUM still has a much 
> reduced impact on system performance. Sequential scans will still flood 
> the cache, but I don't view that as an enormous problem. 

Has anobody some insight, how does linux kernel level disk cache solve
this "sequencial scan/read pollutes cache" problem ?

-- 
Hannu Krosing <hannu@tm.ee>

Re: ARC patent

Simon Riggs <simon@2ndquadrant.com> — 2005-01-21T01:26:21Z

On Thu, 2005-01-20 at 23:17 +1100, Neil Conway wrote:
> Simon Riggs wrote:
> >>However, I think the ARC replacement should *not* be a fundamental
> >>change in behavior: the algorithm should still attempt to balance
> >>recency and frequency, to adjust dynamically to changes in workload, to
> >>avoid "sequential flooding", and to allow constant-time page
> >>replacement.
> > 
> > Agreed: Those are the requirements. It must also scale better as well.
> 
> For 8.1 we should definitely Do The 
> Right Thing and develop a complete ARC replacement. 

Agreed. That would be my focus.

> For 8.0.x, I wonder 
> if it would be better to just replace ARC with LRU. The primary 
> advantage to doing this is LRU's simplicity -- if we're concerned about 
> introducing regressions in stability into 8.0, this is likely the best 
> way to reduce the chance of that happening. Furthermore, LRU's behavior 
> with PostgreSQL is well-known and has been extensively tested. A complex 
> ARC replacement would receive even less testing than ARC itself has 
> received -- which isn't a whole lot, in comparison with LRU.
> 
> Of course, the downside is that we lose the benefits of ARC or an 
> ARC-like algorithm in 8.0. That would be unfortunate, but I don't think 
> it is a catastrophe. The other bufmgr-related changes (vacuum hints, 
> bgwriter and vacuum delay) should ensure that VACUUM still has a much 
> reduced impact on system performance. Sequential scans will still flood 
> the cache, but I don't view that as an enormous problem. In other words, 
> I think a more intelligent replacement policy would be nice to have, but 
> at this point in the 8.0 development cycle we should go with the 
> simplest solution that we know is likely to work -- namely, LRU.

Agree with everything apart from the idea that seq scan flooding isn't
an issue. I definitely think it is.

-- 
Best Regards, Simon Riggs

Re: ARC patent

Neil Conway <neilc@samurai.com> — 2005-01-21T02:52:28Z

On Fri, 2005-01-21 at 01:26 +0000, Simon Riggs wrote:
> Agree with everything apart from the idea that seq scan flooding isn't
> an issue. I definitely think it is.

I agree it's an issue, I just don't think it's an issue of sufficient
importance that it needs to be solved in the 8.0.x timeframe.

In any case, I'll take a look at developing a patch to replace ARC with
LRU. If it's possible to solve sequential flooding (e.g. via some kind
of hint-based approach) without too much complexity, we could add that
to the patch down the line.

-Neil

Re: ARC patent

Mark Kirkwood <markir@coretech.co.nz> — 2005-01-21T02:55:06Z

Simon Riggs wrote:
> On Thu, 2005-01-20 at 23:17 +1100, Neil Conway wrote:
> (snippage)
>>For 8.0.x, I wonder 
>>if it would be better to just replace ARC with LRU.
>>
>> Sequential scans will still flood 
>>the cache, but I don't view that as an enormous problem. 
> 
> Agree with everything apart from the idea that seq scan flooding isn't
> an issue. I definitely think it is.
> 
Is it feasible to consider LRU + a free-behind or seqscan hint type of 
replacement policy?

regards

Mark

Re: ARC patent

Manfred Koizar <mkoi-pg@aon.at> — 2005-01-21T14:42:38Z

On Fri, 21 Jan 2005 02:31:40 +0200, Hannu Krosing <hannu@tm.ee> wrote:
>2) Another simple, but nondeterministic, hack would be using randomness,
>i.e. 
>
>  2.1) select a random buffer in LR side half (or 30% or 60%) of 
>       for replacement. 
>
>  2.2) dont last accessed pages to top of LRU list immediately, 
>       just push them uphill some amount, either random, or 
>       perhaps 1/2 the way to top at each access.

Sounds good, but how do find the middle of a linked list?  Or the other
way round:  Given a list element, how do you find out its position in a
linked list?  So the only approach that is easily implementable is

2.3) If a sequential scan hint flag is set, put the buffer into the
     free list at a random position.

Servus
 Manfred

Re: ARC patent

Kenneth Marshall <ktm@it.is.rice.edu> — 2005-01-21T14:57:28Z

On Fri, Jan 21, 2005 at 03:42:38PM +0100, Manfred Koizar wrote:
> On Fri, 21 Jan 2005 02:31:40 +0200, Hannu Krosing <hannu@tm.ee> wrote:
> >2) Another simple, but nondeterministic, hack would be using randomness,
> >i.e. 
> >
> >  2.1) select a random buffer in LR side half (or 30% or 60%) of 
> >       for replacement. 
> >
> >  2.2) dont last accessed pages to top of LRU list immediately, 
> >       just push them uphill some amount, either random, or 
> >       perhaps 1/2 the way to top at each access.
> 
> Sounds good, but how do find the middle of a linked list?  Or the other
> way round:  Given a list element, how do you find out its position in a
> linked list?  So the only approach that is easily implementable is
> 
> 2.3) If a sequential scan hint flag is set, put the buffer into the
>      free list at a random position.
> 

If we use the clock algorithm as an approximation to LRU, we can avoid
a lot of the MRU/LRU churn. Then the seq. scan hint could just be another
type of clock bit.

Ken

Re: ARC patent

Bruce Momjian <pgman@candle.pha.pa.us> — 2005-01-21T17:59:01Z

Tom Lane wrote:
> Neil Conway <neilc@samurai.com> writes:
> > On Mon, 2005-01-17 at 18:43 -0500, Tom Lane wrote:
> >> I have already
> >> suggested to core that we should insist on 8.1 not requiring an initdb,
> >> so as to ensure that people will migrate up to it easily from 8.0.
> 
> > So is it firm policy that changes that require a catversion update
> > cannot be made during the 8.1 cycle?
> 
> Not yet --- I suggested it but didn't get any yeas or nays.  I don't
> feel this is solely core's decision anyway ... what do the assembled
> hackers think?

I am not in favor of adjusting the 8.1 release based solely on this
patent issue.  I think the probability of the patent being accepted and
enforced against anyone using PostgreSQL to be very unlikely.  I would
also like to come up with a procedure that would scale to any other
patent problems we might have.  What if someone finds another patent
problem during 8.1 beta?  Do we shorten the 8.2 development cycle too?

What I would like to do is to pledge that we will put out an 8.0.X to
address any patent conflict experienced by our users.  This would
include ARC or anything else.  This way we don't focus just on ARC but
have a plan for any patent issues that appear, and we don't have to
adjust our development cycle until an actual threat appears.

One advantage we have is that we can easily adjust our code to work
around patented code by just installing a new binary.  (Patents that
affect our storage format would be more difficult.  A fix would have to
perhaps rewrite the on-disk data.)

One problem in working around the GIF format patent is that you had to
create a file that was readable by many of the existing GIF readers. 
With PostgreSQL, only we read our own data files so we can more easily
make adjustments to avoid patents.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: ARC patent

Hannu Krosing <hannu@tm.ee> — 2005-01-23T10:27:32Z

Ühel kenal päeval (reede, 21. jaanuar 2005, 15:42+0100), kirjutas
Manfred Koizar:
> On Fri, 21 Jan 2005 02:31:40 +0200, Hannu Krosing <hannu@tm.ee> wrote:
> >2) Another simple, but nondeterministic, hack would be using randomness,
> >i.e. 
> >
> >  2.1) select a random buffer in LR side half (or 30% or 60%) of 
> >       for replacement. 
> >
> >  2.2) dont last accessed pages to top of LRU list immediately, 
> >       just push them uphill some amount, either random, or 
> >       perhaps 1/2 the way to top at each access.
> 
> Sounds good, but how do find the middle of a linked list?

Ok, we are back to using 2 lists - one for 1st and one for 2nd half and
spill the tail of 1st list over to 2nd when it growns.
But the fundamental fact of using two lists seems to be the first claim
in IBM's patent ;(
Not that I think that using 2 lists to know where the midpoint of linked
list is is patentable, but if we deside start acting scared of all
things in patent applications then we should be aware of it.

>   Or the other
> way round:  Given a list element, how do you find out its position in a
> linked list?  

To know an *approximate* position, we could 
1) have an independent periodic process that just scans the list and
records the position
2) each node inserted at head or tail is recorded true position
3) each node inserted in middle is given the same position as its
predecessor.
This would not be too expensive, but OTOH I can't think of a way to use
this onfo right now. An additional array of node pointers in list order
populated in step 1) could have more use.

> So the only approach that is easily implementable is
> 
> 2.3) If a sequential scan hint flag is set, put the buffer into the
>      free list at a random position.

-- 
Hannu Krosing <hannu@tm.ee>