Re: Looking for keyed file package

Re: Looking for keyed file package

[Al Christians]

>> It would be interesting to understand why you are 
doing things "by hand" here at such a low level, 
rather than use a DB. <<

The appliction is to use the keyed file to collate 
data from multiple sources.  It's sort of a brief
holding tank for data.  Pick up a file here, a file
there, keep accumulating the information, then 
spit out sequential files for a different 
application to process on a different machine.
The total lifecycle of the application is just a
couple of weeks.  The number of simultaneous users
of the file will probably never exceed 1.  It's not
worth buying a database for, and the speed objectives,
processing hundreds of thousands of records in much 
less than an hour, and the large file sizes make me 
reluctant to try MS Access, the only database likely 
to be available on the target machines.  

All this data is going to come together next month at 
a site that I have not yet visited.  Simpler is better
when preparing to walk into a new location and run
from a cold start.  I don't know if their version of
Access is the same as the one I could use here to 
develop and test, what the differences might
be, or how much trouble they might cause.  I don't want
to find out.  I just need the simplest thing that will
work.  Low-cost doesn't hurt, either.     

I did try each of Pascal Obry's packages and the one 
from Ada-Belgium with no success.  I think that the 
Ada Belgium package has an off by one error that causes
a constraint error when there is an unfortunate 
coincidence of the start of a record with the start of
a block of data in the file.  It would load my data 
and let me access it, but about 1000 records into the
file, it would crash with  a subscript computed as
(something mod 512) being used as an index into an 
array(1..512).   

I'll have to go back and reconstruct my code to re-create
the problems I was getting with Pascal's modules.  That
won't be hard -- he's designed them with a very easy to 
use interface.  Unfortunately, I'm doing this under an
extreme time crunch, so I think I'm going to be going
even more toward the 'do-it-all-by-hand' position using
direct IO.  I'll just create the index in memory each 
time I run by reading the entire file.  Up to a million
records should fit fine. 


Al

Re: Looking for keyed file package

[Vladimir Olensky]

Al Christians wrote in message <37E8F0C1.A49C3E2D@easystreet.com>...

>The total lifecycle of the application is just a
>couple of weeks.  The number of simultaneous users
>of the file will probably never exceed 1.  It's not
>worth buying a database for, and the speed objectives,
>processing hundreds of thousands of records in much
>less than an hour, and the large file sizes make me
>reluctant to try MS Access, the only database likely
>to be available on the target machines.


Have you tried BDE (Borland Database Engine) using either  Paradox or Delphi
?
You can  create simple DB application with needed functionality in less than
hour using them.

I have very positive experience with Paradox and prefer it to MS Access.
I few years ago  I did  Call Accounting System for our Meridian 1 switches
that I maintain.
I did it using Paradox and it's Object  PAL.
It works efficiently with files which size is more than 20 Mbytes.


MS Access and it's VB is still  not up to the Paradox and BDE.

Another good example of using BDE that I would like to mention
is my City Address Book on a CD .
Primary DB is more that 40 Mbyts but  any query is done
in a few seconds.

Regards.

Re: Looking for keyed file package

[Al Christians]

Vladimir Olensky wrote:
> 
> Al Christians wrote in message <37E8F0C1.A49C3E2D@easystreet.com>...
> 
> 
> Have you tried BDE (Borland Database Engine) using either  Paradox or Delphi
> ?
> You can  create simple DB application with needed functionality in less than
> hour using them.
> 

Yes, but because I travel and work at various client sites here and 
there, I try to avoid using tools licensed per machine, which I think
Borland's are now.  I would have to be able to install Delphi and
BDE at each location for it to be a good solution for me.   Licensing is
much less problem with OSS, GPL, etc, etc, etc.  



Al

Re: Looking for keyed file package

[Al Christians]

Robert Dewar wrote:
> 
> 
> Well that's a non-technical objection, and a curious one,
> since there are as likely to be free software databases
> around as free software indexed file systems (indeed I
> know one of the former, none of the latter).
> 

I'm not aware of any 'free software database' that is down to 
my level of sophistication. What such animal can you recommend 
for use with GNAT Ada 3.11p under NT?  


I just fear out of pure ignorance that many of the things that
are available in database systems but unneeded in this application
-- locking, transactions, multi-user capabilities, joins, 
set-at-a-time processing, triggers, you-name-it -- carry a 
pretty heavy cost in performance and general bulk of the 
application, ie number of things that can go wrong.  What I 
got working today -- a direct_io file with a couple of indexes 
built in memory each time the application runs -- works fine and 
appears to be able to create a few thousand records per second 
and then read and update over 1000 per second.

It's also amusing to me that after my data is refined into its final
form, I will create an Ascii text file of it to pass to the next
application.  Using direct_io with a record padded with a crlf,
the step of creating the Ascii version of the file is null,  there's
nothing to do. This random access Ascii via direct_io matches Btrieve 
in speed, and I can view and patch my database with edlin.



Al

Re: Looking for keyed file package

[p.obry]

<<
I have tried first Pascal Obrey's adbm package, but it seems to hang
the first time I try to do an insert with insert mode set to insert
or update.  I suppose I'll try his gdbm package next, as it has almost
the same interface.
>>

Please report to me the problem you are having. Since I've used a lot
this package I'am pretty sure it is working pretty fine. You could have
found a bug or you did not use adbm right. I know that the documentation
is very thin... Anyway I'am willing to fix adbm if you found a bug.

BTW, it's Obry not Obrey :-)

Pascal.

Re: Looking for keyed file package

[David Botton]

I disagree, just like there are times to use assembly, there are times for
using an indexed file package. If your package was available for Ada, I for
one would be using it.

David Botton


Robert Dewar wrote in message <7saii8$5bl$1@nnrp1.deja.com>...
>P.S. As the author of the highly efficient indexed file package
>for Realia COBOL, I find this disappointing, it would have been
>fun to adapt this very interesting technology to Ada, but I am
>afraid no one would be interested in using it these days :-(

Re: Looking for keyed file package

[David Botton]

You could create a set of ADO bindings using BindCOM
(http://www.adapower.com/com - there is an example already on using ADO
there) and then use Access databases or even Paradox databases. ADO doesn't
have licensing restrictions to create a problem for you and if it isn't
already on the machine there is a simple install package available off the
MS web site. I have used ADO for a number of projects and found the
performance was on par with other solutions.

David Botton


Al Christians wrote in message <37E932C2.5EB97471@easystreet.com>...
>Yes, but because I travel and work at various client sites here and
>there, I try to avoid using tools licensed per machine, which I think
>Borland's are now.  I would have to be able to install Delphi and
>BDE at each location for it to be a good solution for me.   Licensing is
>much less problem with OSS, GPL, etc, etc, etc.
>

Re: Looking for keyed file package

[Robert Dewar]

In article <37E8F0C1.A49C3E2D@easystreet.com>,
  Al Christians <achrist@easystreet.com> wrote:
> >> It would be interesting to understand why you are
> doing things "by hand" here at such a low level,
> rather than use a DB.

> It's not worth buying a database for

Well that's a non-technical objection, and a curious one,
since there are as likely to be free software databases
around as free software indexed file systems (indeed I
know one of the former, none of the latter).

> and the speed objectives,
> processing hundreds of thousands of records in much
> less than an hour, and the large file sizes make me
> reluctant to try MS Access, the only database likely
> to be available on the target machines.

No, indeed I was talking about a real data base with efficient
processing, definitely you do not want Access which is really
a bit of a toy in this regard.


> All this data is going to come together next month at
> a site that I have not yet visited.  Simpler is better
> when preparing to walk into a new location and run
> from a cold start.  I don't know if their version of
> Access is the same as the one I could use here to
> develop and test, what the differences might
> be, or how much trouble they might cause.  I don't want
> to find out.  I just need the simplest thing that will
> work.  Low-cost doesn't hurt, either.

Well of course you would install the database at the target
site, just as you would have to install the indexed file
system. Alternatively you could statically link either into
your application.



Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Looking for keyed file package

[p.obry]

I do not agree here. For example for Information Retrieval a relational DB 
is not well suited at all.

You need to have very quick access (and walk through) to inverted index 
file. Using a DB is 
just a too big overhead.

Pascal.

Re: Looking for keyed file package

[Robert Dewar]

In article <7scrba$bdu$1@clnews.edf.fr>,
  p.obry@der.edf.fr wrote:
> I do not agree here. For example for Information Retrieval a
relational DB
> is not well suited at all.
>
> You need to have very quick access (and walk through) to
inverted index
> file. Using a DB is
> just a too big overhead.


A database like DB2 is well suited for this task ...


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[Robert Dewar]

In article <7semeb$69u$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:
> In article <7scrba$bdu$1@clnews.edf.fr>,
>   p.obry@der.edf.fr wrote:
> > I do not agree here. For example for Information Retrieval a
> relational DB
> > is not well suited at all.
> >
> > You need to have very quick access (and walk through) to
> inverted index
> > file.


One thing to be aware of here is that a naive implementation of
indexed files may well be slower than using a database built on
top of a sophisticated indexed file system.

It is quite surprising what can be done with good indexed
file systems. For example, the Realia COBOL compiler uses a
sophisticated form of leading/trailing key compression which
results in an average stored key length of about 16 bits,
regardless of the actual physical key length.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[Larry Kilgallen]

In article <7seobv$7ib$1@nnrp1.deja.com>, Robert Dewar <robert_dewar@my-deja.com> writes:

> One thing to be aware of here is that a naive implementation of
> indexed files may well be slower than using a database built on
> top of a sophisticated indexed file system.

I think the original poster said the project had a 4 week useful
lifespan, so it seems me Implementation Time would dominate.

> It is quite surprising what can be done with good indexed
> file systems. For example, the Realia COBOL compiler uses a
> sophisticated form of leading/trailing key compression which
> results in an average stored key length of about 16 bits,
> regardless of the actual physical key length.

The VMS implementation of RMS does key compression and data compression
as well, but I think that all started back when disk and memory space
were much more dear.  I/O bandwidth one area of computer performance
that does not seem to be advancing so much as the others, so these
days typical advice might be to engage in extensive caching of the
index data if performance is important.

Larry Kilgallen

Re: Looking for keyed file package

[Robert Dewar]

In article <1999Sep24.130829.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
ed key length of about 16 bits,
> > regardless of the actual physical key length.
>
> The VMS implementation of RMS does key compression and data
compression
> as well

Yes, but it uses a scheme basically similar to that used by
VSAM on IBM, the Realia COBOL scheme is significantly more
efficient, because it uses a single count to indicate both
the leading and trailing compression amounts.

> but I think that all started back when disk and memory space
> were much more dear.  I/O bandwidth one area of computer
> performance that does not seem to be advancing so much as the
> others, so these days typical advice might be to engage in
> extensive caching of the index data if performance is
> important.

The whole *point* of key compression is to allow this caching
to be more efficient. You want as much of the key index in main
memory as possible (and if you are really pushing things, in
cache as possible). Key compression is vitally important for
this, and in fact it is MORE important with modern architectures
than with older ones, precisely because of the increasing gap
between processor/memory speed and I/O speed.

Robert Dewar


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[Larry Kilgallen]

In article <7sijv6$tc8$1@nnrp1.deja.com>, Robert Dewar <robert_dewar@my-deja.com> writes:

>> but I think that all started back when disk and memory space
>> were much more dear.  I/O bandwidth one area of computer
>> performance that does not seem to be advancing so much as the
>> others, so these days typical advice might be to engage in
>> extensive caching of the index data if performance is
>> important.
> 
> The whole *point* of key compression is to allow this caching
> to be more efficient. You want as much of the key index in main
> memory as possible (and if you are really pushing things, in
> cache as possible). Key compression is vitally important for
> this, and in fact it is MORE important with modern architectures
> than with older ones, precisely because of the increasing gap
> between processor/memory speed and I/O speed.

Since you say "in main memory as possible (and ...in cache",
I gather you are talking about processor memory cache, whereas
what I meant was having the index in the caches created by the
indexed file system in main memory.

Presuming the actual data will likely require a disk read,
I think the difference between index data being in processor
cache and being in the file system cache in main memory is
not of consequence.

The data I have been dealing with this month have a maximum
of 16 bytes of key data for a record length of 600 bytes,
so the standard recommendation to set the cache size large
enough to hold the entire index tree in memory seems reasonable.
Memory is cheap enough, however, that even not having the
keys compressed would be acceptable in this setting. That
would be quite different with 584 bytes of key data for
a record length of 600 bytes.  Of course particular key
data can be more or less susceptible to compression.

Larry Kilgallen

Re: Looking for keyed file package

[Robert Dewar]

In article <1999Sep25.114101.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
> Since you say "in main memory as possible (and ...in cache",
> I gather you are talking about processor memory cache, whereas
> what I meant was having the index in the caches created by the
> indexed file system in main memory.

Yes, exactly

> Presuming the actual data will likely require a disk read,
> I think the difference between index data being in processor
> cache and being in the file system cache in main memory is
> not of consequence.

That's not necessarily the case, there can be substantial
processing involved in accessing the index, and processor
caching is a factor.

> The data I have been dealing with this month have a maximum
> of 16 bytes of key data for a record length of 600 bytes,
> so the standard recommendation to set the cache size large
> enough to hold the entire index tree in memory seems
> reasonable.

Sure if you have a small file where the indexes can fit in
main memory even if not compressed, that is a simple case
to deal with.

> Memory is cheap enough, however, that even not having the
> keys compressed would be acceptable in this setting. That
> would be quite different with 584 bytes of key data for
> a record length of 600 bytes.  Of course particular key
> data can be more or less susceptible to compression.

Actually that's wrong, with modern key compression techniques
you can get down to less than 16 bits per key on average quite
regardless of the distribution of key data.

This is a rather specialized area, and the techniques involved
are rather tricky. To get an intuitive feeling for why the above
is true, consider the following extremes

1. Keys are very very different, in this case you only need a
little bit of the key to differentiate them (this is trailing
key compression in action, discarding trailing data in the
key that is not significant).

2. Keys are very very similar, in this case leading key
compression becomes effective.

The combination is effective in all situations. As I mentioned
earlier, the technique used in the Realia COBOL compiler gets
down to about 16 bits per key, including control information,
pretty much regardless of key distribution.

Yes, of course for a small file, there is no issue, but the
point is that key compression greatly extends the size of
files that can be handled efficiently. Memory is cheap, but
files are in practice getting bigger at least as fast as
main memory size is increasing.

Consider as an example, the ebay files, do some simple
calculations here (remembering that you can do full searches
on titles and expect instant response). You will see that
files like this get pretty big, pretty quickly :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[David Botton]

If you ever have the time to put together and example of building these keys
in Ada, I'd love to get a copy (and publish it on AdaPower if possible :-)

David Botton


Robert Dewar wrote in message <7sju61$pdv$1@nnrp1.deja.com>...
>This is a rather specialized area, and the techniques involved
>are rather tricky. To get an intuitive feeling for why the above
>is true, consider the following extremes
>
>1. Keys are very very different, in this case you only need a
>little bit of the key to differentiate them (this is trailing
>key compression in action, discarding trailing data in the
>key that is not significant).
>
>2. Keys are very very similar, in this case leading key
>compression becomes effective.
>
>The combination is effective in all situations. As I mentioned
>earlier, the technique used in the Realia COBOL compiler gets
>down to about 16 bits per key, including control information,
>pretty much regardless of key distribution.

Re: Looking for keyed file package

[Robert Dewar]

In article <7smj11$fp2$1@news.gate.net>,
  "David Botton" <David@Botton.com> wrote:
> If you ever have the time to put together and example of
building these keys
> in Ada, I'd love to get a copy (and publish it on AdaPower if
possible :-)

Well it is not something that just an example can show, it is
a very complex algorithm, involving some tricky data structures.
The current implementation is thousands of lines of x86
assembly language :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[Ted Dennison]

In article <7sphpe$10ra$1@news.gate.net>,
  "David Botton" <David@Botton.com> wrote:
> Well, if you ever get bored.... :-)
>
> Robert Dewar wrote in message <7sp9e0$aru$1@nnrp1.deja.com>...
> >In article <7smj11$fp2$1@news.gate.net>,
> >Well it is not something that just an example can show, it is
> >a very complex algorithm, involving some tricky data structures.
> >The current implementation is thousands of lines of x86
> >assembly language :-)

Yeah, you can do it in your spare time, while Nick's writing that
garbage-collecting Ada compiler. ;-)

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[Robert Dewar]

In article <7sqs1l$ei7$1@nnrp1.deja.com>,
  Ted Dennison <dennison@telepath.com> wrote:
> In article <7sphpe$10ra$1@news.gate.net>,
>   "David Botton" <David@Botton.com> wrote:
> > Well, if you ever get bored.... :-)
> >
> > Robert Dewar wrote in message
<7sp9e0$aru$1@nnrp1.deja.com>...
> > >In article <7smj11$fp2$1@news.gate.net>,
> > >Well it is not something that just an example can show, it
is
> > >a very complex algorithm, involving some tricky data
structures.
> > >The current implementation is thousands of lines of x86
> > >assembly language :-)
>
> Yeah, you can do it in your spare time, while Nick's writing
that
> garbage-collecting Ada compiler. ;-)


Maybe he can just include a special tool for converting
x86 assembly language to well commented, well structured
Ada, which his optimizing compiler will then convert back
to exactly equivalent assembly language :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Looking for keyed file package

[David Botton]

Well, if you ever get bored.... :-)

David Botton

Robert Dewar wrote in message <7sp9e0$aru$1@nnrp1.deja.com>...
>In article <7smj11$fp2$1@news.gate.net>,
>Well it is not something that just an example can show, it is
>a very complex algorithm, involving some tricky data structures.
>The current implementation is thousands of lines of x86
>assembly language :-)