Greg Stark wrote:
Tom Lane [EMAIL PROTECTED] writes:
In any case, this discussion is predicated on the assumption that the
operations involving the bitmap are a significant fraction of the total
time, which I think is quite uncertain. Until we build it and profile
it, we won't know
Bruce Momjian [EMAIL PROTECTED] writes:
Also, what does an in-memory bitmapped index look like?
One idea that might work: a binary search tree in which each node
represents a single page of the table, and contains a bit array with
one bit for each possible item number on the page. You could not
On Fri, Jan 30, 2004 at 09:48:19AM -0500, Tom Lane wrote:
A variant is to make the per-page bit arrays be entries in a hash table
with page number as hash key. This would reduce insertion to a nearly
constant-time operation, but the drawback is that you'd need an explicit
sort at the end to
Alvaro Herrera wrote:
On Fri, Jan 30, 2004 at 09:48:19AM -0500, Tom Lane wrote:
A variant is to make the per-page bit arrays be entries in a hash table
with page number as hash key. This would reduce insertion to a nearly
constant-time operation, but the drawback is that you'd need an
Bruce Momjian [EMAIL PROTECTED] writes:
Alvaro Herrera wrote:
Is there a reason sort the pages before scanning them? The result won't
come out sorted one way or the other.
I think the goal would be to hit the heap in sequential order as much as
possible.
Exactly. Also, it'll be harder to
On Jan 30, 2004, at 6:31 AM, Bruce Momjian wrote:
I like the idea of building in-memory bitmapped indexes.
Me too (FWIW)! This thread is really interesting as the whole idea
would help to solve the biggest issue with my (currently stalled)
project to integrate Xapian as a full-text search
Tom Lane kirjutas R, 30.01.2004 kell 16:48:
Bruce Momjian [EMAIL PROTECTED] writes:
Also, what does an in-memory bitmapped index look like?
One idea that might work: a binary search tree in which each node
represents a single page of the table, and contains a bit array with
one bit for
Hannu Krosing [EMAIL PROTECTED] writes:
Another idea would be using bitmaps where we have just one bit per
database page and do a seq scan but just over marked pages.
That seems a bit too lossy for me, but I really like your later idea
about folding. Generalizing that a little, we can choose
Tom Lane kirjutas L, 31.01.2004 kell 01:02:
Hannu Krosing [EMAIL PROTECTED] writes:
Another idea would be using bitmaps where we have just one bit per
database page and do a seq scan but just over marked pages.
That seems a bit too lossy for me,
I originally thought of it in context of
Tom Lane [EMAIL PROTECTED] writes:
That seems a bit too lossy for me, but I really like your later idea
about folding. Generalizing that a little, we can choose any fold point
we like. We could allocate, say, one 32-bit word per page and set the
(i mod 32) bit when item i is fingered by
Greg Stark [EMAIL PROTECTED] writes:
Tom Lane [EMAIL PROTECTED] writes:
ORing and ANDing of such bitmaps still works, with the understanding
that it's lossy and you have to double check each retrieved tuple.
That would make it really hard to ever clear the bits.
We're speaking of in-memory
A small comment on Oracle's implementation of persistent bitmap indexes:
Oracle's bitmap index is concurently locked by DML, i.e. it suites for OLAP
(basically read only data warehouses) but in no way for OLTP.
IMHO,
Laimis
Maybe the lack of heap/btree consistent ordering in Oracle
and
Tom Lane [EMAIL PROTECTED] writes:
In any case, this discussion is predicated on the assumption that the
operations involving the bitmap are a significant fraction of the total
time, which I think is quite uncertain. Until we build it and profile
it, we won't know that.
The other thought I
Tom Lane [EMAIL PROTECTED] writes:
Greg Stark [EMAIL PROTECTED] writes:
I would see that as the next step, But it seems to me it would be only a small
set of queries where it would really help enough to outweigh the extra work of
the sort.
What sort?
To build the in-memory bitmap
Greg Stark [EMAIL PROTECTED] writes:
Tom Lane [EMAIL PROTECTED] writes:
What sort?
To build the in-memory bitmap you effectively have to do a sort.
Hm, you're thinking that the operation of inserting a bit into a bitmap
has to be at least O(log N). Seems to me that that depends on the data
Some potentially helpful background comments on the discussion so far...
Tom Lane writes
Greg Stark writes
Note that the space saving of bitmap indexes is still a substantial
factor.
I think you are still confusing what I'm talking about with a bitmap
index, ie, a persistent structure on-disk.
How feasible would it be to have a btree index on ctid? I'm thinking it ought
to work simply enough for the normal case of insert/delet/update, but I'm not
completely certain how vacuum, vacuum full, and cluster would interact.
You may think this would be utterly useless, but I have a cunning
Greg Stark [EMAIL PROTECTED] writes:
How feasible would it be to have a btree index on ctid?
Why would you want one? Direct access by ctid beats out an index lookup
every time. In any case, vacuum and friends would break such an index
entirely.
regards, tom lane
Tom Lane [EMAIL PROTECTED] writes:
Greg Stark [EMAIL PROTECTED] writes:
How feasible would it be to have a btree index on ctid?
Why would you want one? Direct access by ctid beats out an index lookup
every time.
Of course. But as I mentioned, I have a cunning plan.
If you have two
Greg Stark [EMAIL PROTECTED] writes:
If you have two indexes (a,ctid) and (b,ctid) and do a query where a=1 and b=2
then it would be particularly easy to combine the two efficiently.
If specially marked btree indexes -- or even all btree indexes -- implicitly
had ctid as a final sort order
Tom Lane [EMAIL PROTECTED] writes:
I don't think so. You are thinking only of exact-equality queries ---
as soon as the WHERE clause describes a range of index entries, the
readout wouldn't be sorted by ctid anyway.
But then even bitmap indexes would fail in that way too, or at least have a
Greg Stark [EMAIL PROTECTED] writes:
Combining indexes via a bitmap intermediate step (which is not really
the same thing as bitmap indexes, IIUC) seems like a more robust
approach than relying on the index entries to be in ctid order.
I would see that as the next step, But it seems to me it
22 matches
Mail list logo
