Sybase NNTP forums - End Of Life (EOL)

The NNTP forums from Sybase - forums.sybase.com - are now closed.

All new questions should be directed to the appropriate forum at the SAP Community Network (SCN).

Individual products have links to the respective forums on SCN, or you can go to SCN and search for your product in the search box (upper right corner) to find your specific developer center.

Would ASE implement BitMap index or BitWise index?

6 posts in Product Futures Discussion Last posting was on 2004-09-07 03:03:43.0Z
FlyBean Posted on 2004-08-25 11:40:53.0Z
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Would ASE implement BitMap index or BitWise index?
From: flybean <charity@163.net>
User-Agent: Xnews/06.07.17
NNTP-Posting-Host: 61.145.199.122
X-Original-NNTP-Posting-Host: 61.145.199.122
Message-ID: <412c7ac5@forums-1-dub>
Date: 25 Aug 2004 04:40:53 -0700
X-Trace: forums-1-dub 1093434053 61.145.199.122 (25 Aug 2004 04:40:53 -0700)
X-Original-Trace: 25 Aug 2004 04:40:53 -0700, 61.145.199.122
Lines: 10
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1597
Article PK: 96597

Hi,Sybaser:
Dose ASE has any plan to implement BitMap index?
Any what's the advantage of BitWise index. I just know it's a patent
technology of SYBASE while BitMap index is a all-known technology based on
RDBMS's theory.
Thanks a lot.


Flybean
2004.08.25


Jason L. Froebe [TeamSybase] Posted on 2004-08-26 02:49:17.0Z
From: "Jason L. Froebe [TeamSybase]" <jason@NOSPAMMY.froebe.net>
Reply-To: jason@NOSPAMMY.froebe.net
Organization: TeamSybase
User-Agent: Mozilla Thunderbird 0.7.3 (Windows/20040803)
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Re: Would ASE implement BitMap index or BitWise index?
References: <412c7ac5@forums-1-dub>
In-Reply-To: <412c7ac5@forums-1-dub>
Content-Type: multipart/mixed; boundary="------------080008090408020008010403"
NNTP-Posting-Host: d53-64-196-184.nap.wideopenwest.com
X-Original-NNTP-Posting-Host: d53-64-196-184.nap.wideopenwest.com
Message-ID: <412d4fad$1@forums-1-dub>
Date: 25 Aug 2004 19:49:17 -0700
X-Trace: forums-1-dub 1093488557 64.53.184.196 (25 Aug 2004 19:49:17 -0700)
X-Original-Trace: 25 Aug 2004 19:49:17 -0700, d53-64-196-184.nap.wideopenwest.com
Lines: 61
X-Authenticated-User: TeamSybase
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1601
Article PK: 96598


flybean wrote:

> Hi,Sybaser:
> Dose ASE has any plan to implement BitMap index?
> Any what's the advantage of BitWise index. I just know it's a patent
> technology of SYBASE while BitMap index is a all-known technology based on
> RDBMS's theory.
> Thanks a lot.
>
>
> Flybean
> 2004.08.25

Hi Flybean,

Take a look at Sybase's IQ data warehouse that has the bitwise index.
It is a very inefficient type of index for OLTP operations - which is
why it is not in ASE.

jason

--
Jason L. Froebe

"There is usually a balance between the left and the right... checks &
balances... the bane of the government but the boon of the people" -
Jason L. Froebe

http://www.froebe.net
Bookcrossing (http://www.bookcrossing.com)
WebBlog http://www.livejournal.com/users/jfroebe

TeamSybase (http://www.teamsybase.com)
ISUG member (http://www.isug.com)
Chicago Sybase Tools User Group (http://www.cpbug.com)


Download VCard jason.vcf


FlyBean Posted on 2004-08-27 07:10:21.0Z
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Re: Would ASE implement BitMap index or BitWise index?
From: flybean <charity@163.net>
References: <412c7ac5@forums-1-dub> <412d4fad$1@forums-1-dub>
User-Agent: Xnews/06.07.17
X-Original-NNTP-Posting-Host: 61.145.199.121
Message-ID: <412edfd1@forums-2-dub>
X-Original-Trace: 27 Aug 2004 00:16:33 -0700, 61.145.199.121
Lines: 30
X-Original-NNTP-Posting-Host: forums-2-dub.sybase.com
X-Original-Trace: 27 Aug 2004 00:00:06 -0700, forums-2-dub.sybase.com
NNTP-Posting-Host: forums-master.sybase.com
X-Original-NNTP-Posting-Host: forums-master.sybase.com
Date: 27 Aug 2004 00:10:21 -0700
X-Trace: forums-1-dub 1093590621 10.22.108.75 (27 Aug 2004 00:10:21 -0700)
X-Original-Trace: 27 Aug 2004 00:10:21 -0700, forums-master.sybase.com
X-Authenticated-User: ngsysop
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1604
Article PK: 96601

"Jason L. Froebe [TeamSybase]" <jason@NOSPAMMY.froebe.net> wrote in
news:412d4fad$1@forums-1-dub:

> flybean wrote:
>
>> Hi,Sybaser:
>> Dose ASE has any plan to implement BitMap index?
>> Any what's the advantage of BitWise index. I just know it's a
>> patent
>> technology of SYBASE while BitMap index is a all-known technology
>> based on RDBMS's theory.
>> Thanks a lot.
>>
>>
>> Flybean
>> 2004.08.25
>
> Hi Flybean,
>
> Take a look at Sybase's IQ data warehouse that has the bitwise index.
> It is a very inefficient type of index for OLTP operations - which is
> why it is not in ASE.
>
> jason
>

So, how about bitmap index?

Flybean
2004.08.27


Jeff Tallman Posted on 2004-08-27 12:14:10.0Z
From: Jeff Tallman <tallman@sybase.com>
User-Agent: Mozilla Thunderbird 0.6 (Windows/20040502)
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Re: Would ASE implement BitMap index or BitWise index?
References: <412c7ac5@forums-1-dub> <412d4fad$1@forums-1-dub> <412edfd1@forums-2-dub>
In-Reply-To: <412edfd1@forums-2-dub>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
NNTP-Posting-Host: vpn-concord-020.sybase.com
X-Original-NNTP-Posting-Host: vpn-concord-020.sybase.com
Message-ID: <412f2592$1@forums-1-dub>
Date: 27 Aug 2004 05:14:10 -0700
X-Trace: forums-1-dub 1093608850 158.159.8.20 (27 Aug 2004 05:14:10 -0700)
X-Original-Trace: 27 Aug 2004 05:14:10 -0700, vpn-concord-020.sybase.com
Lines: 60
X-Authenticated-User: techsupp
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1605
Article PK: 96600

As Oracle has and others have found out, the bitmap index doesn't help
that much in row-based stored systems except in covered queries (i.e. no
datapage access) and only works when the covered queries can be
effectively handled by the bitmap index - which supports extremely low
cardinality (<100 distinct values). The reason for this is that the
incidence of low cardinality is usually fairly high which gets into the
whole problem of whether it becomes cheaper to table scan or walk the
index. While, yes, it does aid in that very limited aspect (covered
queries) - as with all gazillion neat features - it is looked at in
light of what features customers are asking for the most as well as if a
solution already exists (in this case Sybase IQ).

In column-based stored systems (Sybase IQ), bitmap indices can not only
be used effectively, but they also can shring the storage space by
orders of magnitude over row-based systems (in which bitmapped indexes
just generally add to the space explosion). In IQ, it is as much the
physical storage of the data (column vs. row - all transparent to
app/user/dba) that contributes to the speed and parallelism it can
achieve - as it is the indexing technology.

Consequently, in order for ASE to effectively implement bitmap indexes,
it would have to first implement column-wise table storage - a merging
of ASE and ASIQ - something many people would like to see.

flybean wrote:

> "Jason L. Froebe [TeamSybase]" <jason@NOSPAMMY.froebe.net> wrote in
> news:412d4fad$1@forums-1-dub:
>
>
>>flybean wrote:
>>
>>
>>>Hi,Sybaser:
>>> Dose ASE has any plan to implement BitMap index?
>>> Any what's the advantage of BitWise index. I just know it's a
>>> patent
>>>technology of SYBASE while BitMap index is a all-known technology
>>>based on RDBMS's theory.
>>> Thanks a lot.
>>>
>>>
>>>Flybean
>>>2004.08.25
>>
>>Hi Flybean,
>>
>>Take a look at Sybase's IQ data warehouse that has the bitwise index.
>>It is a very inefficient type of index for OLTP operations - which is
>>why it is not in ASE.
>>
>>jason
>>
>
>
> So, how about bitmap index?
>
> Flybean
> 2004.08.27


FlyBean Posted on 2004-09-01 16:28:48.0Z
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Re: Would ASE implement BitMap index or BitWise index?
From: FlyBean <flybean_zhou@163.com>
References: <412c7ac5@forums-1-dub> <412d4fad$1@forums-1-dub> <412edfd1@forums-2-dub> <412f2592$1@forums-1-dub>
Organization: Free
User-Agent: Xnews/4.06.22
X-Original-NNTP-Posting-Host: 61.144.97.89
Message-ID: <4135fa48@forums-2-dub>
X-Original-Trace: 1 Sep 2004 09:35:20 -0700, 61.144.97.89
Lines: 54
X-Original-NNTP-Posting-Host: forums-2-dub.sybase.com
X-Original-Trace: 1 Sep 2004 09:18:03 -0700, forums-2-dub.sybase.com
NNTP-Posting-Host: forums-master.sybase.com
X-Original-NNTP-Posting-Host: forums-master.sybase.com
Date: 1 Sep 2004 09:28:48 -0700
X-Trace: forums-1-dub 1094056128 10.22.108.75 (1 Sep 2004 09:28:48 -0700)
X-Original-Trace: 1 Sep 2004 09:28:48 -0700, forums-master.sybase.com
X-Authenticated-User: ngsysop
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1612
Article PK: 96610


Jeff Tallman <tallman@sybase.com> wrote in news:412f2592$1@forums-1-dub:

>
> As Oracle has and others have found out, the bitmap index doesn't help
> that much in row-based stored systems except in covered queries (i.e. no
> datapage access) and only works when the covered queries can be
> effectively handled by the bitmap index - which supports extremely low
> cardinality (<100 distinct values). The reason for this is that the
> incidence of low cardinality is usually fairly high which gets into the
> whole problem of whether it becomes cheaper to table scan or walk the
> index. While, yes, it does aid in that very limited aspect (covered
> queries) - as with all gazillion neat features - it is looked at in
> light of what features customers are asking for the most as well as if a
> solution already exists (in this case Sybase IQ).
>

Why only covered queries?
Let's suppose a relation R like the following:
R( colA, colB, some other columns )
And suppose: T(R)>30000, V(R,colA)=20, V(R,colB)=30
Query is : retrieve all records where colA=some value and colB=some value
(In my env, it's very common)

Sample 1: has seprate bitmap indices on colA and colB
Read bitmap indices into memory;(less I/Os)
de-compress them;
calculate the intersection;
read each row from datapage;( max to the size of intersection )

Sample 2: has two normal indices on colA and colB
estimate which value of colA/colB may cause small resultset using
statistics;
walk through the index tree of the selected col, while found one matchs,
read the row and check if another condition matchs ( max to 1+1 I/O, while
the rows retrieved by selected index may more bigger than the real result )

Sample 2 should cost more I/Os than sample 1.

> In column-based stored systems (Sybase IQ), bitmap indices can not only
> be used effectively, but they also can shring the storage space by
> orders of magnitude over row-based systems (in which bitmapped indexes
> just generally add to the space explosion). In IQ, it is as much the
> physical storage of the data (column vs. row - all transparent to
> app/user/dba) that contributes to the speed and parallelism it can
> achieve - as it is the indexing technology.
>
I think in IQ, the data of the column is just stored in the index page, the
same as some file manage systems which hold small files directly in the FAT.
But column-based stored systems is not suit for normal OLTP applications,
which a relation should has some columns with other types, such as
char,varchar,datetime.

Flybean
2004.09.02


Jeff Tallman Posted on 2004-09-07 03:03:43.0Z
From: Jeff Tallman <tallman@sybase.com>
User-Agent: Mozilla Thunderbird 0.6 (Windows/20040502)
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: sybase.public.ase.product_futures_discussion
Subject: Re: Would ASE implement BitMap index or BitWise index?
References: <412c7ac5@forums-1-dub> <412d4fad$1@forums-1-dub> <412edfd1@forums-2-dub> <412f2592$1@forums-1-dub> <4135fa48@forums-2-dub>
In-Reply-To: <4135fa48@forums-2-dub>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Original-NNTP-Posting-Host: pcp03383846pcs.potshe01.pa.comcast.net
Message-ID: <413d26aa@forums-2-dub>
X-Original-Trace: 6 Sep 2004 20:10:34 -0700, pcp03383846pcs.potshe01.pa.comcast.net
Lines: 96
X-Original-NNTP-Posting-Host: forums-2-dub.sybase.com
X-Original-Trace: 6 Sep 2004 19:52:25 -0700, forums-2-dub.sybase.com
NNTP-Posting-Host: forums-master.sybase.com
X-Original-NNTP-Posting-Host: forums-master.sybase.com
Date: 6 Sep 2004 20:03:43 -0700
X-Trace: forums-1-dub 1094526223 10.22.108.75 (6 Sep 2004 20:03:43 -0700)
X-Original-Trace: 6 Sep 2004 20:03:43 -0700, forums-master.sybase.com
X-Authenticated-User: ngsysop
Path: forums-1-dub!not-for-mail
Xref: forums-1-dub sybase.public.ase.product_futures_discussion:1613
Article PK: 96609

Your example is exactly what I was saying - a covered query is one in
which all SARGS are covered by the index....additionally, I note that
your columns are extremely low cardinality and that while you attempt to
use set notation to describe the cardinality, the distribution
apparently is assumed equal.

Now then, try this:

select *
from R
where colA in (value1,value2,value3,value4)
and colD in (something1, something2, something3)

Since colA only has 20 distinct values, the optimizer - even if it used
the index - would have to consider whether it is worth identifying the
1/5 of the table only to have to read all the pages to look at colD

Interesting note by the way - when IBM DB2 UDB speaks of bitmapped
indices they really refer to the ability to calculate the intersection
of two other indices (non-bitmapped) as you did - however, I am not sure
that Oracle can intersections - be silly not to, so they should.

On the IQ standpoint, I am not sure what you are getting at - it seems
you have a very narrow view of IQ's indexing capabilities. First,
analogy of files stored in FAT is not exactly relevant - be like saying
the data was stored in the space allocation map and ignoring the
linkage, data ordering (i.e. indices are ordered), etc. Additionally,
while IQ does store data in column-wise format, it is well capable of
handling varchar, binary, datetime and other datatypes - rather than the
simplistic bitmapped indices of Oracle, IQ supports bitwise indices -
which not only handles non-numeric datatypes (as it appears you assume
it cannot) with much greater efficiency than any RDBMS alive, it also
includes semantic indexes including special date/time indices that allow
rapid queries based on dateparts (i.e. quarters). While it is not
intended for OLTP, one could argue quite easily that the types of
queries that benefit from bitmapped indices (typically aggregation)
don't happen as much in OLTP systems either.

FlyBean wrote:
> Jeff Tallman <tallman@sybase.com> wrote in news:412f2592$1@forums-1-dub:
>
>
>>As Oracle has and others have found out, the bitmap index doesn't help
>>that much in row-based stored systems except in covered queries (i.e. no
>>datapage access) and only works when the covered queries can be
>>effectively handled by the bitmap index - which supports extremely low
>>cardinality (<100 distinct values). The reason for this is that the
>>incidence of low cardinality is usually fairly high which gets into the
>>whole problem of whether it becomes cheaper to table scan or walk the
>>index. While, yes, it does aid in that very limited aspect (covered
>>queries) - as with all gazillion neat features - it is looked at in
>>light of what features customers are asking for the most as well as if a
>>solution already exists (in this case Sybase IQ).
>>
>
>
> Why only covered queries?
> Let's suppose a relation R like the following:
> R( colA, colB, some other columns )
> And suppose: T(R)>30000, V(R,colA)=20, V(R,colB)=30
> Query is : retrieve all records where colA=some value and colB=some value
> (In my env, it's very common)
>
> Sample 1: has seprate bitmap indices on colA and colB
> Read bitmap indices into memory;(less I/Os)
> de-compress them;
> calculate the intersection;
> read each row from datapage;( max to the size of intersection )
>
> Sample 2: has two normal indices on colA and colB
> estimate which value of colA/colB may cause small resultset using
> statistics;
> walk through the index tree of the selected col, while found one matchs,
> read the row and check if another condition matchs ( max to 1+1 I/O, while
> the rows retrieved by selected index may more bigger than the real result )
>
> Sample 2 should cost more I/Os than sample 1.
>
>
>>In column-based stored systems (Sybase IQ), bitmap indices can not only
>>be used effectively, but they also can shring the storage space by
>>orders of magnitude over row-based systems (in which bitmapped indexes
>>just generally add to the space explosion). In IQ, it is as much the
>>physical storage of the data (column vs. row - all transparent to
>>app/user/dba) that contributes to the speed and parallelism it can
>>achieve - as it is the indexing technology.
>>
>
> I think in IQ, the data of the column is just stored in the index page, the
> same as some file manage systems which hold small files directly in the FAT.
> But column-based stored systems is not suit for normal OLTP applications,
> which a relation should has some columns with other types, such as
> char,varchar,datetime.
>
> Flybean
> 2004.09.02