Query execution for intervals

#21

Quote:

-- both indexes
select --+ index(i xi) index(i yi)
count(1)
from intervals i
where 500 between x and y;
18 sec

-- one index
select --+ index(i xi)
count(1)
from intervals i
where 500 between x and y;
16 sec

These queries actually have identical plans. The correct test is
select --+ index(i xi) index(i yi)
count(1)
from intervals i
where 50000 between x and y;
16 sec

select --+ index(i xi) no_index(i yi)
-----------------------------^^^^^^^^^^^^^^^^
count(1)
from intervals i
where 50000 between x and y;
21 sec

select --+full(i)
count(1)
from intervals i
where 50000 between x and y;
2.5 sec

These performance data are volatile, of course. Increasing number of
interval bondary collisions would favor bitmapped plans. Increasing the
number of colums in the table would slow down full table scan.
Therefore, it is possible that bitmapped plans might outperform FTS.
Still, querying intervals covering a point is nowhere as fast as
finding a (small) set of points which belongs to an interval via B-Tree
index scan. I assume this remains to be true even for fancier access
methods developed in spatial area (e.g. R-tree).

#22

<frebe73 (AT) gmail (DOT) com> wrote

Quote:

Your k is really a constant or is someting like log(n)/n ?
k is a constant. I don't claim that my assumption is correct. But until
someone else can give a motivation why the assumption is wrong, I have
to assume that it is correct.

You can also look at the actual query plan to see what operations would
be
performed.
Nobody here seem to be able to provide an answer. Just trial an error.

Well, somebody have to do trial and error :-)

You said you use Oracle DBMS. I hope you know what you paid for.
Look at the product documentation and experiment to know your product.

https://dpt-info.u-strasbg.fr/doc/or...que.htm#i10797
https://dpt-info.u-strasbg.fr/doc/or...b14211/toc.htm

https://dpt-info.u-strasbg.fr/doc/or...xpconcepts.htm

Oracle Spatial in https://dpt-info.u-strasbg.fr/doc/or...v/portal_7.htm

etc. etc. etc.

Otherwise you risk to employ an unlicensed patented algorithm and you don't
want to do that, don't you ?

#23

I would add that your interval is a set and you know the relational model
don't like sets as attributes.

#24

x wrote:

Quote:

I would add that your interval is a set and you know the relational model
don't like sets as attributes.

There is a certain truth in this proposition. If we consider an
interval as a set of points, then the set of all intervals covering a
given point (or, more generally, a set of points) is formally a
relational division. Relational division is a prominent example of set
join. Of course, the fact that an interval is an infinite set is very
inconvenient from technical perspective.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Query execution for intervals

comp.databases.theory comp.databases.theory

Re: Query execution for intervals - 02-09-2006 , 02:02 PM

Re: Query execution for intervals - 02-10-2006 , 01:56 AM

Re: Query execution for intervals - 02-10-2006 , 02:09 AM

Re: Query execution for intervals - 02-10-2006 , 02:23 PM