From: Volkan YAZICI <yazicivo@ttnet.net.tr>
To: pgsql-general@postgresql.org
Subject: Re: intarray internals
Date: Sat, 6 May 2006 23:43:15 +0300
Message-ID: <20060506204315.GC202@alamut> (raw)
In-Reply-To: <20060506143824.GB202@alamut>
References: <20060505214601.GA208@alamut>
<20060506101303.GB4413@svana.org>
<20060506143824.GB202@alamut>
On May 06 05:38, Volkan YAZICI wrote:
> g_int_compress():
> if (integer array length > constant limit)
> {
> Transfrom {A, B, C, ..., Z} array into
> {A, A, B, B, ..., Z, Z}
>
> while (integer array length > constant limit)
> {
> Select two couples whose difference is minimum
> and remove them from the list.
> }
> }
>
> g_int_decompress():
> for (iterate over compressed array items)
> {
> Transform {..., 47, 50, ...} into {..., 47, 48, 49, 50, ...}
> }
>
> As you can see both compression and decompression methods are quite
> lossy. I'm not sure if this has any negative impact on the traversing
> of nodes stuff for more accurate predicates, but I am currently
> considering "performance gain * physical storage gain / cpu
> consumation loss" ratio if we'd instead use a lossless data
> compression method.
After considering the idea, I conclude up with that, current lossy
compression method seems like the best for now. But here goes my
proposal:
g_int_compress():
/* Input */
arr = {16, 20, 40, 52, 58}
len = 5
orig_len = len
while (len(arr) > LIM)
{
Find the couple with minimum diff: (16, 20)
Remove(arr, 20) /* Removing right bound. If it's the
last item of the list, remove
left item. */
--len
}
/*
* Suppose that, above function reduced array with below steps:
* 0: {16, 20, 40, 52, 58} (16, 20*)
* 1: {16, 40, 52, 58} (52*, 58)
* 2: {16, 40, 58}
*/
/* Prepend orig_len to array */
arr = {_5_, 16, 40, 58}
g_int_decompress():
/* Import info from input array. */
orig_len = 5
arr = {16, 40, 58}
len = 3
while (len < orig_len)
{
Divide every interval into two equal parts:
{16, 40, 58} -> {16, 28*, 40, 49*, 58}
}
I didn't test above method on real-world data chunks but, AFAIC, above
method would result with more accurate ranges in the decompressed arrays
and probably skip some redundant loop recursions when compared to
previous method.
Your comments?
Regards.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: yazicivo@ttnet.net.tr, pgsql-general@postgresql.org
Subject: Re: intarray internals
In-Reply-To: <20060506204315.GC202@alamut>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox