Psql regex is NFA or DFA?

On Tue, Sep 10, 2002 at 02:16:51AM -0500, Josh Jore wrote:

So I've finished reading Jeffery Friedl's _Mastering Regular Expressions_
and while I don't need regex in PostgreSQL I know I'll do it for something
- eventually. The book makes a distinction between DFA, POSIX NFA and
Traditional NFA and then ascribes some properties and behaviours to each.
So what sort does PostgreSQL have?

Regex in PostgreSQL code:

Copyright (c) 1992, 1993, 1994 Henry Spencer.
Copyright (c) 1992, 1993, 1994
The Regents of the University of California. All rights reserved.

I think it's:

POSIX 1003.2, section 2.8 (Regular Expression Notation)

--
Karel Zak <zakkr@zf.jcu.cz>
http://home.zf.jcu.cz/~zakkr/

C, PostgreSQL, PHP, WWW, http://docs.linux.cz, http://mape.jcu.cz

Josh Jore <josh@greentechnologist.org> writes:

So I've finished reading Jeffery Friedl's _Mastering Regular Expressions_
and while I don't need regex in PostgreSQL I know I'll do it for something
- eventually. The book makes a distinction between DFA, POSIX NFA and
Traditional NFA and then ascribes some properties and behaviours to each.
So what sort does PostgreSQL have?

Well, you could read the code (src/backend/regex), or you could apply
the tests that Friedl suggests to distinguish the type of an unknown
engine ...

My guess is that it's an NFA, but I dunno if Spencer did the POSIX
semantics or not.

regards, tom lane

Tom Lane wrote:

Josh Jore <josh@greentechnologist.org> writes:

So I've finished reading Jeffery Friedl's _Mastering Regular Expressions_
and while I don't need regex in PostgreSQL I know I'll do it for something
- eventually. The book makes a distinction between DFA, POSIX NFA and
Traditional NFA and then ascribes some properties and behaviours to each.
So what sort does PostgreSQL have?

Well, you could read the code (src/backend/regex), or you could apply
the tests that Friedl suggests to distinguish the type of an unknown
engine ...

My guess is that it's an NFA, but I dunno if Spencer did the POSIX
semantics or not.

I am continuing to talk to Henry about getting a newer version of his
regex library. He is working on it but is not yet finished.

-- 
  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

On Tue, 10 Sep 2002, Bruce Momjian wrote:

Tom Lane wrote:

Josh Jore <josh@greentechnologist.org> writes:

So I've finished reading Jeffery Friedl's _Mastering Regular Expressions_
and while I don't need regex in PostgreSQL I know I'll do it for something
- eventually. The book makes a distinction between DFA, POSIX NFA and
Traditional NFA and then ascribes some properties and behaviours to each.
So what sort does PostgreSQL have?

Well, you could read the code (src/backend/regex), or you could apply
the tests that Friedl suggests to distinguish the type of an unknown
engine ...

My guess is that it's an NFA, but I dunno if Spencer did the POSIX
semantics or not.

I am continuing to talk to Henry about getting a newer version of his
regex library. He is working on it but is not yet finished.

Do you have some details about the implementation itself? I would like
to work on implementing a regex engine using the Shift-And algorithm
families, and that can probably give a performance improvement over the
current engine.

--
Alvaro Herrera (<alvherre[@]dcc.uchile.cl>)

Alvaro Herrera wrote:

I am continuing to talk to Henry about getting a newer version of his
regex library. He is working on it but is not yet finished.

Do you have some details about the implementation itself? I would like
to work on implementing a regex engine using the Shift-And algorithm
families, and that can probably give a performance improvement over the
current engine.

[ CC'ing Henry Spencer. ]

No, I don't know any details except that his regex library is in the new
tcl code and has to repackaged as a separate library. Henry, could we
help you finish up your regex stuff?

Henry's regex work is the same code that is in *BSD regex (at least
BSD/OS, FreeBSD, NetBSD), which I have found to be pretty slow in
certain complex cases, so much so that I have moved to super-sed (ssed)
for use on my local machine where I have seen 100x speed improvements
with ssed.

I am not sure how slow our regex really is, but for the sake of
PostgreSQL and of the BSD regex library, I would love to see a newer
version.

In fact, I just had an email exchange with Henry about two weeks ago.

-- 
  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

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Henry's regex work is the same code that is in *BSD regex (at least
BSD/OS, FreeBSD, NetBSD), which I have found to be pretty slow in
certain complex cases,

You're speaking of his *old* package (the one we currently use), no?

Friedl seems to think that the current Tcl regex engine (Henry's new
code) is the most advanced thing on the planet.

regards, tom lane

Tom Lane wrote:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Henry's regex work is the same code that is in *BSD regex (at least
BSD/OS, FreeBSD, NetBSD), which I have found to be pretty slow in
certain complex cases,

You're speaking of his *old* package (the one we currently use), no?

Yes, that is the old stuff shipped with BSD 4.4 and included in all the
*BSD releases I have checked.

Friedl seems to think that the current Tcl regex engine (Henry's new
code) is the most advanced thing on the planet.

I have not heard that, but it is good to hear.

-- 
  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

Tom Lane dijo:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Henry's regex work is the same code that is in *BSD regex (at least
BSD/OS, FreeBSD, NetBSD), which I have found to be pretty slow in
certain complex cases,

You're speaking of his *old* package (the one we currently use), no?

Friedl seems to think that the current Tcl regex engine (Henry's new
code) is the most advanced thing on the planet.

Oh, so the TODO item "replace with newer code" is not just vaporware?
Well, I won't try to compete with Spencer's code in that case.

--
Alvaro Herrera (<alvherre[a]atentus.com>)
"Linux transform� mi computadora, de una `m�quina para hacer cosas',
en un aparato realmente entretenido, sobre el cual cada d�a aprendo
algo nuevo" (Jaime Salinas)

Alvaro Herrera <alvherre@atentus.com> writes:

Tom Lane dijo:

Friedl seems to think that the current Tcl regex engine (Henry's new
code) is the most advanced thing on the planet.

Oh, so the TODO item "replace with newer code" is not just vaporware?
Well, I won't try to compete with Spencer's code in that case.

The code is certainly not vaporware: Tcl's been using it for awhile.
But the code in a Tcl-independent package that we could easily use
is a different story. Perhaps you could offer Henry some help in
making it into a clean library package ...

regards, tom lane