Tree Indexes II

 So the last class, we have some things to handle duplicate keys. At a higher level how are we going to maintain these duplicate keys.

The first approach is to make every key unique automatically by appending the tuple's record id as part of the key to ensure that all keys are unique. We can also allow leaf nodes to spill into overflow nodes that contain the duplicate keys. The page id and offset is the identifier for every unique location in a tuple. 

The database stores the combination of the key and the record id. 

Let's see what happens when we insert an entry to the table. If we insert a 6, because we don't have overflow pages, I have to go in sorted over, so we need to slide everyone over and update pointers accordingly. 

Here's the tree after the first trial: 

The other way we can do it is to insert an overflow page. It's okay to leave things unsorted, but we have to do the linear search. 

I follow particular pointers if I need to go to the next page. I get the iterator and look for the element I want to find. I need to update if I want everything in proper sorter order. We can exploit record ids to faciitate operations that are otherwise not easy to do. To a certain point, you actually want to rebalance, though. 

For insertion, we want to see if the count in the internal nodes surpassing M or the count of the leaf nodes surpassing L. The rules are to first try to give and element to the left sibling, and then give an element to the right sibling. We split if neither of those work. We start with an empty tree. The elements in a leaf node are arranged in order from least to greatest. We look for left and right sibling, else we just split. We put more elements in the new leaf node if the root has split, which requires an internal node now to act as a parent, requiring the addition of a new root node. Look to left, look to right, split if no other choice, check if new root needed. New internal nodes are needed to be the parent of the node that just split. 

Here's how to create a B+ tree data structure: 

CREATE INDEX idx_emails_hash ON emails USING HASH(email); 

Using the EXPLAIN keyword, postgres will tell you what it will do. 

Here's what the EXPLAIN does: 

The bitmap sees the record map with the offset (2 lookups) and see what matches and what doesn't. It uses sequential scan when looking for a range, but uses a hash index when looking for something else. You have both a hash index and tree index for the quality predicate.

Table clustering uses the index to enforce the sort ordering of the tuples themselves. CLUSTER command forces Postgres to resort the entire table based on the sort ordering defined by an index. 

CLUSTER emails USING idx_emails_tree;

LIMIT 1 after cluster guarantees that things were in sorted order. For POSTGRES, you need to run clusters repeatedly. For any other language, you don't. By default you are always going to get a B+ tree but you can force some systems to convert to the hash index. Most DBMSs automatically create index to enforce integrity constraints but not referential constraints. 

Without index, you have to scan things all over again to make sure no 2 indexes as a unique key. However, foreign keys doesn't do this. A foreign key refers to the primary key in another table. If we try to do '

CREATE TABLE bar (

    id INT REFERENCES foo

    val VARCHAR(32)

); 

It doesn't work since you can't force an integrity constraint without an index. If we add a UNIQUE clause like this:

CREATE TABLE bar (

    id SERIAL PRIMARY KEY, 

    val INT NOT NULL UNIQUE,

    val2 VARCHAR(32) UNIQUE 

); 

it then builds an index automatically that we can then use to enforce this command: 

CREATE TABLE bar (

    id INT REFERENCES foo

    val VARCHAR(32)

); 

We can try to call a partial index.

When we normally do create index, it tries to look at every single tuple, and instead we can try to look at some subset of the data. We can add a where clause to add how to match the index. 

These are called partial indexes. This creates an index on a subset of the entire table, which potentially reduces its size and the amount of potential overhead. 

One use is to partition indexes by date ranges creating a separate index per month and per year. This reduces contention on the Databases' buffer pool resources. 

CREATE INDEX idx_foo ON 

foo(a, b) 

WHERE c = 'wuTang';

SELECT b from foo 

WHERE a = 123

AND c  = 'WuTang' 

It turns out that all the data you need is in the index itself.

In the covering index, all the fields that are necessary to answer the required result in the query can be found in the index itself.  I can get the b and a field with the index, and I will never need to look at the actual tuples. 

The include column say "for all the keys with a and b, include the additional attribute c." I can look at c in the leaf node as a result, and value my predicate and produce my output. 

CREATE INDEX idx_foo

    ON foo(a, b)

    INCLUDE (c); 

The extra columns are only stored in the leaf nodes. 

SELECT b FROM foo

WHERE a = 123

AND c = 'WuTang';

Although we can lookup C, we are not greatly increasing in size of the overall index. 

Another index to discuss is the functional and expression index. An index does not need to store keys in the same way that they appear inside of the base table. We want to do a lookup on a value that we derived from the key, not only some value.

Let's say 0 is Sunday, Monday 1, Tuesday 2, etc. 

We want to do a lookup to a value that is derived from the key. 

We can try to build an index on anything we have a WHERE clause on. We can try to find all of the elements on how we want. We can do partial index, or we can use something on the where clause where the extracted element produces. 2. 

SELECT * FROM users

WHERE EXTRACT (dow

    FROM login) = 2

To create index, we do the following: 

CREATE INDEX idx_user_login

    ON foo(login)

WHERE EXTRACT(dow FROM login) = 2, which is a partial index. 

A partial index is an index built over a subset of a table; the subset is defined by a conditional expression.

A functional index is one in which all keys derive from the results of a function.

We can first use the expression index which is built. 

Let's first create a table after setting off parallel workers (to accurately measure complexity). 

Here are the commands in order

SET max_parallel_workers_per_gather = 0;

CREATE TABLE users (id SERIAL PRIMARY KEY, login TIMESTAMP NOT NULL)

INSERT INTO users (login) SELECT * FROM generate_series('2015-01-01'::timestamp, NOW()::timestamp, '1 minute'::interval); 

SELECT pg_prewarm('users');

SELECT AVG(id) FROM users where EXTRACT(dow FROM login) = 2

EXPSELECT AVG(id) FROM users WHERE EXTRACT(dow FROM login) = 2

We try to try to do the lookup where the extract value equals to 2. 

The partial index will only contains the records where the partial function equals to 2. 

Now let's create an index on the partial function: 

CREATE INDEX idx_user_login_partial ON users(login) WHERE EXTRACT(dow FROM login) = 2; 

In a partial index, the index contains entries for only those table rows that satisfy the predicate. Partial index avoid indexing common values. You can create an index that specializes in something.

Here, it runs the NOW function once, and the NOW() is not dynamic so if I insert something again, it should use the current now, but if it's smart it can detect the NOW() at the time building the index. 

CREATE INDEX idx_user_login_expr ON users (login - NOW()); 

You can also drop an index by DROP INDEX idx_user_login_expr; 

When we create an index, the index that the command that it will create is a B+ tree. If we do

CREATE INDEX idx_emails_hash ON emails USING HASH (email); then this indicates that you want to use a hash index. 

The inner node keys in a B+ tree cannot tell you whether a key exists in an index, you must traverse to a leaf node, meaning you could have one buffer pool page miss just to find out that a key does not exist. 

Radix tree is a spexialization of a Trie. A trie is a tree data structure where we store digits of a key, an atomic subset of a key, for example, a byte, or a single bit, store the digits of a key down different levels, and we only need to store this once at each level. We use digital representation of keys to compare prefixes, in contrast to comparing the entire key. 

Trie distribution only depends on the key spaces and their length. It's a deterministic data structure, no matter what order we enter the keys, it's gonna be the same vs a B+ tree, which may end up in different layouts. Tries also don't require any rebalancing like in the B+ tree. The fact that the complexity is based on the key we're trying to look up in regards to the length is interesting. 

Tries are going to be faster for point queries, but will be slower for scans. The span of a trie level is the number of bits that each partial key or digit represents, determining the fanpout of each node and the physical height of the tree. Here's what a 1-bit span trie looks like. 

Theres bit 0 and bit 1 and the number of times where we repeat a number of times with a value after null or pointer. The "devil" signs represent a pointer. 

A radix tree omits all nodes with only a single child. 

How do we do modifications? There is no standard way to do a trie in the same way to do a B+ tree. 

Radix tree is when we remove all of the paths. Radix tree is a subset of a trie. 

Last thing we're going to talk about is inverted indexes. No commercial database system supports tries out of the box. Hyper is on trie, but right now the B+ tree is still the dominant data structure that everyone uses. 

B+ tree are good for "point" and "range" queries, but not good for keyword searches, since you're trying to find the subelement for the value for the attribute. 

We should not create an index on the content attribute, this would be super stupid. 

An inverted index stores a mapping of words to records that contain them. It will allow to do lookups like "find me all the keywords that match to the certain property). 

These are called accordances in theoretical literature. All the major database indexes vary interally and vary in the sophistication in the indexes. Lucene is a library that does the search and indexing and elastic search provides a server interface to the index. 

I can do regular expressions and complex pattern matching to find things that I am looking for. 

Decision 1 is what to store where the index needs to store at least the words contained in each record and frequency. Decision 2 maintains auxillary data structures to stage updates and update the index batches. 

B+ trees are still the way to go for tree indexes.