Ok...let's talk compression...

Posted by b0b0rama on 26-Oct-2011 14:37

I'm looking at the INDEX blocks of a progress database which are "compressed".

I'd describe the general leaf node organizations as having the usual index block header properties... which include the block address, block type, index number, number of indexes etc.  Followed by  repeating segements of  rowid, compression key, index delta.

The indexes appear to be organized as a delta value from the previous index...   thus for a given unique primary index...with keys like 12345, 12346, 12347,...

The FIRST key is written in entirety, and the following keys are written as a DELTA from the previous key.... thus to generate 12346 you keep the first 4 digits and replace only the last digit.   The "compression key" tells you which digits to keep...and which ones to replace with the delta values.

Does anyone have any ideas on the structure of the compression algorithm?

I noticed for an index with a NINE character key...the following compression codes seem to apply.

0c 08 01 = keep the first 8 replace the last character.

0b 09 01 = keep the first 7 replace the last two characters.

0a 0a 01 = keep the first 6 replace the last 3 characters.

OK...how about an easier question.  Does a Binary Dump on a Table dump the entire table (including "deleted" records that exist in a block....or does it only dump valid active records? 

Why are some of the record offsets in the record offset directory "nibble swapped"   I noted that some records are identified in the directory offset of a record block by their offset withing the record block, but some record offsets appear to point outside the current block..thse records have certain high order and low order nibbles swapped around so that the offset  hex "43 20" actually refers to  offset 03 24.   And  "42 50" refers to  02 54.  This is not simply a little/big endian system byte swap. It is swapping around nibbles. I theorized this may be how the internally mark a record as "deleted" and can then roll-back the record if the transactuion is not committed..but it's just a guess.

Don't you hate it when your data gets trapped in a proprietary database and because your version is so old...buying a new license won't even help you extract it anymore because the current release is not backward compatible far enough for your existing database.  Bummer.

I don't really expect anyone to be able to answer these questions. This forum is filled with Progress Database experts, but not low level Progress database architects.

I just submit them here on the off chance that one person may have some clue about the architecture.

All Replies

Posted by gus on 26-Oct-2011 15:22

0) If in an index you have the ordered key values

0: Bologne

1: Bolton

2: Bonn

3: Boston

4: Boston

5: Boston

in a block, the leaf node compression drops those bytes of an entry where the entry has leading bytes that are the same value as in the preceding entry. Here, entry no 1 has the first 3 characters the same as the preceding entry (entry 0). We can leave them out and replace them with a number that tells us how many characters were dropped. Entry 2 has 2 characters the same as the preceding entry, etc. So we get:

0: 0, Bologne

1: 3, ton

2: 2, nn

3: 2, ston

4: 6

5: 6

1) Binary dump does not dump deleted rows.

2) In the row data blocks, the row offset directory has entries that have 4 status bits and 12 bits of offset.

Posted by b0b0rama on 26-Oct-2011 16:45

Thank you Gus for your timely response. I suspected this is what is occuring, but I'm still not ceretain about how the "number" of characters is being encoded in the data. I have nine character keys.....and when the last digit changes.... The single character is preceded by  "0c 08 01".   When the first 7 characters stay the same...and the last two digits change...the "code"  appears to be 0b 09 01.  Example:

File: general.d1 (0x1bd4000 bytes)

Byte: 0xf0800 Rec: 963

Dec : 985088 Pos: 0

00 40 78 00 00 02 7f 01 00 00 00 00 00 d7 06 00 00 @x..............

10 00 01 15 00 00 00 00 00 52 00 e3 03 00 00 00 00 ........R.......

20 14 01 00 00 00 15 39 30 30 30 30 30 30 30 31 00 ......900000001. 

30 01 f0 00 00 00 b9 88 0c 08 01 32 00 01 f0 00 00 ..........2.....   0c 08 01 means keep 8?

40 00 b9 60 0c 08 01 33 00 01 f0 00 00 00 b9 61 0c ..`...3.......a.

50 08 01 34 00 01 f0 00 00 00 b9 62 0c 08 01 35 00 ..4.......b...5.

60 01 f0 00 00 00 b9 63 0c 08 01 36 00 01 f0 00 00 ......c...6.....

70 00 b9 40 0c 08 01 37 00 01 f0 00 00 00 b9 41 0c ..@...7.......A.

80 08 01 38 00 01 f0 00 00 00 b9 42 0c 08 01 39 00 ..8.......B...9.

90 01 f0 00 00 00 b9 43 0b 09 01 31 30 00 01 f0 00 ......C...10....   0b 09 01 means keep 7?

a0 00 00 b8 80 0c 08 01 31 00 01 f0 00 00 00 b8 81 .......1........

b0 0c 08 01 32 00 01 f0 00 00 00 b8 82 0c 08 01 33 ...2...........3

c0 00 01 f0 00 00 00 b7 40 0c 08 01 34 00 01 f0 00 .......@...4....

d0 00 00 b7 41 0c 08 01 35 00 01 f0 00 00 00 b7 42 ...A...5.......B

e0 0c 08 01 36 00 01 f0 00 00 00 b7 43 0c 08 01 37 ...6.......C...7

f0 00 01 f0 00 00 00 b7 20 0c 08 01 38 00 01 f0 00 ....... ...8....

Posted by b0b0rama on 27-Oct-2011 11:06

Gus,

I would like to say that I really do appreciate your technical expertise and the time you took to answer my question. Optimally, I'd like to just "ignore" index blocks and root blocks and leaf blocks...and just look at RECORD blocks (type 3).  My goal then was just to "sort" the records into separate files according to their Table "number".   My initial investigation seemed to demonstrate that the "table number" was located in each records "header".  After following the record directory offset....I arrive at a location that appears to contain the Length of the record and the Table number associated with that record.  Perhaps the missing piece of my puzzle is how to identify and assemble records that were split into segments.  I would expect to find a rowid for the (block and slot number) in records identified as fragments.  I expect this may be one of the things indicated by the four status bits in the offset directory.  Asembling the fragments may mean "jumping about" between record blocks....so I can no longer process the blocks sequentially. That's why I started looking to the indexes.  I've traversed a fair number of Btrees in my day. Again, I would like to thank you for your assistance with these technical details. It is most appreciated.

Posted by gus on 27-Oct-2011 14:13

You are correct, one of the status bits indicates fragmentation.

The leftmost status bit indicates the row slot is reserved for a deleted row (by a possibly still active transaction).

The next status bit indicates that another fragment follows this one.

The next status bit indicates that this fragment is not the first.

The last stauts bit indicates a reserved rowid for a deleted row.

When there is another fragment following the current one, the rowid of the next fragment comes after the two byte row length.

Posted by Thomas Mercer-Hursh on 29-Oct-2011 16:16

See the other thread.  There is no reason to go through this to get the data unless it is purely an intellectual exercise.

Posted by b0b0rama on 31-Oct-2011 10:37

Gus,

Can you confirm that the "table number" is stored with each record in a record block and where?   When I follow the Record Offset Directory pointers I read the first 4 bytes and containing first...the "length" (2 bytes) of the data record and second (next 2 bytes), the "table number"  the record belongs to.  Can I reliably get the table number out of the records themselves?  Do fragmented records and record fragments share the same structure?

Thank you so much for your invaluable insight into the low level internal structure of the database.

It is most appreciated.  I am simultaneously investigating migrating these databases to an install of  Progress 10.2 as an alternate (easier?) means of exporting the data.

R Bednar

Posted by b0b0rama on 31-Oct-2011 12:28

I also noted that according to your brief bio on blogs.progress.com -- you like using Linux and Mac OS X.   I know that OpenEdge will run on Unix, and that Mac OS X is of course built on a foundation of UNIX.  I don't suppose it's possible to install and run OpenEdge on Mac OS X?  Hmmmm.... searched the discussions...looks like there is currently no way to run the Progress database natively on Mac OS X.  It can run on Windows...and hence the Mac through virtualization. Darn. I realize that most desktop clients are Windows based, wish they supported more flavors of Unix for the backend database.

Posted by gus on 31-Oct-2011 13:12

I run Centos in vmware on my mac and run openedge databases in that.

We used to support more than 100 different UNIX flavors. Over time most of them have disappeared, along with the hardware they ran on. SCO OpenServer was quite popular amongst our customers before SCO discovered the business strategy of suing their current and former customers.

Posted by gus on 31-Oct-2011 13:33

Yes, the table number will always be there, in the first (and often the only) fragment.

The fragment structure looks like this:

[ Rowid of next fragment: 4 octets, if present ]

Fragment length: 2 octets

Fragment data: variable

When the fragments are assembled, the complete row looks like this

Row length: 2 octets

Skip table: variable, not present if row has less than 16 data values

Table number: variable length integer

First data value: variable

   . . .

Last data value: variable

The skip table starts with a prefix octet of 0xE7, followed by a two octet table length, followed by two octet entries. Each entry contains the offset to the 16th, 32nd, 48th, 64th, etc. data value. All data values are variable length.

Each data value consists of a prefix octet followed by zero or more data bytes. If the prefix octet is less than 0xE6, it indicates the data length in octets. 0 is used for integers whose value is zero and booleans whose values is "false". Prefix values in the range 0xE6 through 0xFF have various special meanings, such as a NULL value (0xFD) or that a data value is longer than 229 octets (0xE6) in which case the next two octets contain the length.

Edit: forgot to mention that the table number is stroed in one of two forms: either as a variable length integer, or as an octet value of 0xFA followed by an element array where the first element contains the table number.

This thread is closed