database,caching,memory,operating-system,b-tree , How is cache conscious B+tree stored?

How is cache conscious B+tree stored?


Tag: database,caching,memory,operating-system,b-tree

I am new to database and wish to implement a cache conscious B+tree. A lot of reading suggest storing nodes and leaves as continuous memory. Is this assuming that when B+tree is created, nodes and leaves are stored in the heap, and then copied into disk by read write operation? Does a cache conscious B+tree tell OS to give it a set of continuous physical pages? I think the answer is no b/c applications shouldn't know about how physical pages are allocated, and continuous memory is referring only to primary memory page?


The 'cache-consciousness' bit refers to a special discipline of page layout that tries to maximise the utilisation of the first-level data cache of the CPU, often optimised for a specific cache line size (e.g. 64 bytes).

One standard technique (independent of cache line size) is to use offset-value coding in the indirection vector, often combined with 'poor man's normalised keys' (e.g. typically two or four bytes of key material starting with the first byte that is not shared with the predecessor). This reduces the necessity of accessing data outside the indirection vector - i.e. the actual key data that is kept in a heap elsewhere on the page, and quite a few queries (failed seeks) can be done using only the data contained in the beefed-up indirection vector. This maximises cache utilisation and minimises thrashing.

Other schemes form the elements of the indirection vector into a mini-btree with 'page size' equal to the cache line size.

Yet another scheme divides the indirection vector into sub-blocks of one (or very few) cache lines in size, with prefix truncation (called 'front compression' in some papers) used only within these sub blocks but not across different blocks. Binary search among block 'leaders' is used to identify the target block, which is then scanned linearly in the manner that is typical for prefix-truncated key sequences.

A variation of this scheme stores the block leaders in a mini-index and keeps the sequential sub blocks elsewhere, to improve cache utilisation even further. Needless to say, intra-page space management is an absolute nightmare.

Many other variations are possible but publications seem to be limited to academic papers trying to prove academic points, and rare peeks into the page layouts used by important database systems.

Even for something as basic as key comparison in connection with prefix truncation, the only serious reference on the web that I could find dates back to 1990:

DDJ December 1990 - Supercharging Sequential Searches

Papers with good overviews of CPU cache issues with btrees:

Consciousness of the paged nature of the underlying storage - and differing characteristics of seek, page read/write and bulk read/write - is a different beast but also important. It often in results in surprising, innovative designs. One example is Berkeley DB's Java version, which persists only its log file to disk and reconstructs the in-memory btree from the log at startup.


Displaying MySQL results in a single table

I created an interface in which the user can choose which results are going to be displayed. The options selected by the user are saved in an array, so the MySQL query goes through the different elements of this array. So I want to display the results in a single...

If I export my database with phpmyadmin will it lock my tables or take my database down?

I want to create a backup of my database using the phpmyadmin export function. the database can't have any down time so I need to know if running a database export will take the database down? I've looked on-line but all I get is instructions on how to export. No...

How to call posts from PHP

I have a website, that uses WP Super Cache plugin. I need to recycle cache once a day and then I need to call 5 posts (URL adresses) so WP Super Cache put these posts into cache again (caching is quite time consuming so I'd like to have it precached...

Combining two select statements

I have two statements as such: var chgAssociationQuery1 = (from a in sostenuto.PROBLEMS join b in sostenuto.S_ASSOCIATION on a.SERVICEREQNO equals b.FROMSERVICEREQNO join c in sostenuto.Changes on b.TOSERVICEREQNO equals c.SERVICEREQNO where b.FROMSERVICEID == 101001110 && b.TOSERVICEID == 101001109 && a.NAME.Contains(name) select new { ProblemReqNo = a.SERVICEREQNO, ProblemId = a.SERVICEREQID, ChangeReqNo =...

In simple RESTful design, does PATCH imply mapping to CRUD's (ORM's) “update” and PUT to “destroy”+“create” (to replace a resource)?

I'm trying to create a simple REST API and map it to CRUD. I have an ORM (DataMapper) which has methods like create, update and destroy. If I get it right, given a resource {a:'foo',b:'bar',c:'baz'}, performing a PUT {b:'qux'} is supposed to replace the resource and result in the same...

MySQL: Select several rows based on several keys on a given column

I have this mysql table structure: ------------------------------------ | item_id | meta_key | meta_value | ------------------------------------ 159 category Bungalow 159 location Lagos 159 price 45000 160 category Bungalow 160 location Abuja 160 price 53500 ... 350 category Bungalow 350 location Lagos 350 price 32000 What I'd like to do is select...

Is there a way to create a primary key and have it cascade into other tables without re-entering data into the new tables?

I am working on setting up a database and have created tables that cascade out like using the cascade on update for the foreign key. I have two tables being worked with to try to solve this. My tables are like this: create table Item(Item int(4) not null, EquipName varchar(20),...

Check if value exists in MySQL DB in Java?

I'm creating a game right now that stores quest values into a DB when a player completes his or her quest. The issue I'm having right now is writing a method that searches the MySQL table for the player id and the quest id to check if he or she...

Why am getting this error?: Unknown column 'firstname' in 'field list'

if(isset($_POST["submit"])) { // Details for inserting into the database $id = htmlentities($_POST["id"]); $firstname = htmlspecialchars($_POST["firstname"]); $lastname = htmlspecialchars($_POST["lastname"]); $username = htmlspecialchars($_POST["username"]); $password = htmlspecialchars($_POST["password"]); // Dealing with inserting $query = "INSERT INTO `myDatabaseForAll`.`users` (`id`, `firstname`, `lastname`, `username`, `password`) VALUES (NULL, $firstname, $lastname,$username,$password)"; $result = mysqli_query($connection,$query);...

Foreign key in C#

I have two tables, A and B, in a dataset in SQL Server; I have created a connection to the dataset in a c# project in visual studio. How can I create a foreign key ( A is the parent) between my two tables ? I want to create the...

Creating a generic / abstract “DBContext” Class for shared functionality among different DBs

I am working on a C# project that is pulling data from SQL Server, ODBC data-sources and Oracle Databases at different times. At this point, I have created 3 different classes - Once for each type of DB access. However, I am seeing that 95% of the code is identical...

What type of database is the best for storing array or object like data [on hold]

I'm just curious what the best method would be if I'm trying to have a bot running on my Node server that I could play Blackjack against. But for multiple connected clients via sockets, each connected socket will have their own bot to play against but I need some way...

How do I access website databases? [closed]

I'm trying to better understand databases and networking. Basically my question is how do websites like these access player data from the game when they're not affiliated with the company? Do you have to have permission by the website to read their statistics? Are these databases private? What are different...

PHP How to not cache generated HTML but cache static data like images/js/css

Many PHP developers add the no-cache header on top of their PHP pages, so do I, for obvious reasons. Since PHP generated content is usually dynamic, having the browser cache them results in outdated data being presented to the user. To avoid this caching is usually disabled. <?php //no cache...

Pull information from SQL database and getting login errors

I am creating a very small, simple CRM for a company, they require the function to be able to view the last 25 orders via the dashboard. The orders are added via a Order-add form within the CRM. When adding the following code to the CRM I get an error:...

Angular ng-repeat cache (avoid re-rendering on state change)

We have huge rendering spikes with ng-repeat in Angular application. Main page shows a huge list of cover images ("::" and "track by" are in place). On first load it works acceptable. But if user changes the state (we use UI-Router) and goes back to the home page afterwards then...

SQL Server: checkident: “[S00014][2560] Parameter 3 is incorrect for this DBCC statement.”

Using an SQL Server database. A lookup table is having 50 new items added to it using a database versioning tool so the same script will be run on all three databases. There is a Dev, QA, and Prod version of the database and because of political reasons prod can't...

creating stored procedure in mysql calculate profit from product table

My following code show some error: 1064 - You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'BEGIN SET @v1:= (select sum( cost_price * current_stock) from product)' at line 2 CREATE PROCEDURE sp_profit BEGIN...

echo both users

The code at the bottom of this post currently echoes: Name: Spongebob Squarepants Description: I live in a pineapple under the sea. Role: editor But there are two users in "wp_usermeta". It's only echoing one. The result needs to look like this: Name: wp_dev_05 Description: My name is Chris Topher!...

PreparedStatement.executeUpdate() doesn't insert in sqlite database

i'm trying to make a DAO class for my Java project. I've a SQLite Database with only one table "USER". The schema is: CREATE TABLE USER( username VARCHAR(20) NOT NULL PRIMARY KEY, password VARCHAR NOT NULL, total_matches INTEGER DEFAULT 0, victories INTEGER DEFAULT 0, times_alien INTEGER DEFAULT 0, times_human INTEGER...

Complex SQL with Multiple Joins

I have a database of politicians, political parties and candidacies for a post in the election. The database consists of the following tables: People, Groups, Candidacies and Posts. The Candidacies table is a join relationship between People and Groups. Each record in the Candidacies table represents a candidacy in the...

How do I prevent MySQL Database Injection Attacks using

I am using in Visual Basic 2010 and using Query to edit my Online MySQL Database from the application (WinForms). Here is a sample to insert a new user into the database: MySQLCon.Open() Dim SQLADD As String = "INSERT INTO members(member,gamertag,role) VALUES('" & memberToAdd.Text & "','" & membersGamertag.Text &...

ODBC ISAM_EOF without any reason

I have a strange behavior with an ODBC Driver and the underlying COBOL database. The database driver is acuODBC of AcuCorp(now Microfocus), the database itself is a COBOL database. The DSN is a system DSN and works just fine. Via Access/Excel u can read/write data with the DSN successfully. In...

Id in database using qt

I am new to qt. I have created a table in sql, and what I'm trying to do is to give an id whenever user adds data. For the first thing inserted it will be 1, second 2 and so on. So how to check what number was the last...

SimpleMembershipProvider WebSecurity.InitializeDatabaseConnection The login from an untrusted domain,database,exception,model-view-controller
I export the database to the server and i've problem. When I start application i see this error An exception of type 'System.Data.SqlClient.SqlException' occurred in System.Data.dll but was not handled in user code Login failed. The login is from an untrusted domain and cannot be used with Windows authentication. WebSecurity.InitializeDatabaseConnection("DefaultConnection",...

App Not Downloading Newest Version Of File [Java]

Okay, I've been trying to figure this out for a few hours and it's starting to kill me. I wrote a primitive version checker for an app I work on every once and awhile. It's just a simple for fun project. The version checker has been a pain though. It...

How I could create a db with the messages that are saved in admin/reports/dblog?

I want to create a table in the db with the column message and with values from column message on admin/reports/dblog...Could someone help me? Or take the message from the db but in db the messages are with separated variables :/

select data according to Row in Sqlite

image i want to get the whole row i am using this code to get my desired data but its giving me null pointer exception at temp_address1 here is the code as in mentioned image i want to get the whole row matching phone number. how can i achive that...

How to get node.js to connect to mongolab using mongoose

I've been trying to use mongoose (module for node.js and mongodb). And tried to get a connection with mongolab up and running. I tried the following at the top of my app.js file, but I couldn't seem to enter the db.on function. global.mongoose = require('mongoose'); var uri = 'mongodb://'; global.db...

Why does the date doesn't match with what I have inserted into the database?

I tried to display the sqlcommand after I saved into the database. Everything seemed to work pretty fine, but when I opened my table from TOAD, the dates are wrong. Here is my sql command: INSERT INTO USERTASK (USERTASKKEY, USERID, TASKKEY, TASKDATE, CREATEDATE, CREATEUSERID) VALUES (USERTASKSEQUENCE.NEXTVAL, 'admin2', '1', TO_DATE('05-06-2015','yyyy/mm/dd HH24:MI:SS'),...

How to use a dynamic value for cache key with ActiveModel::Serializers (v0.10.0.rc1)

I am using a database-driven solution for labels and translations that I would like to cache at the serializer level. Here is my serializer. class AppLabelSerializer < ActiveModel::Serializer cache key: 'app_label', expires_in: 3.hours attributes :id, :key, :label, :label_plural def key object.app_label_dictionary.key end end The problem is that I need to...

Speeding up a SQL query with indexes

I have a table called Products. This table contains over 3 million entries. Every day there are approximately 5000 new entries. which only happens during the night in 2 minutes. But this table gets queried every night maybe over 20 000 times with this query. SELECT Price FROM Products WHERE...

SQLite: Individual tables per user or one table for them all?

I've already designed a website which uses an SQLite database. Instead of using one large table, I've designed it so that when a user signs up, a individual table is created for them. Each user will possibly use several hundreds of records. I done this because I thought it would...

Improving work with SQL DataTime

I have a business in my Date. I need change date below for each date before 25 of each month I want get 25 of month before and for each date after 25 of each month I want get 25 of the same month. Example : for 2015/06/24 (or 2015/06/06)...

Desktop Database with Server without installation

i have Java-Application that growth a lot over the past month. All configurations from the programm and all the logs are stored in .txt or .log files. The programm should change now. The user could install the programm on his own pc but the programm itself should get all the...

string split and subquery in mysql

first of all i have 1 table in database. 1)tags : id name 1 theme1=test1 2 theme1=test2 3 theme1=test3 4 theme2=test1 5 theme2=test2 6 theme2=test3 And i have bunch of id of tags in array. like 1,3. Now, 1)select name from tags where id=1 result: theme1=test1 (now using wildcard) 2)select...

Database only adds (x) amount of rows before error system resources exceeded

I am having a problem with my code where i am only able to add so many lines of text before i get an error "system resources exceeded". This is my code: Dim x As Integer = MsgBox("Update Record?", MsgBoxStyle.YesNo, "Are you sure?") If x = MsgBoxResult.Yes Then Dim accessconn...

Difference between dba_SEGMENTS and dba_data_files

Shouldn't these two queries give the same result? First is a sum of all segments while other is the sum of all data files. They are giving different results for me. While the first one gives me 149522MB, the other gives 214973.34 MB select sum(bytes)/1024/1024 MB from dba_segments; select sum(bytes)/1024/1024...

CakePHP Unable to insert to database (datetime format)

I was new to Cakephp and I actually following the tutorial of the Blog tutorial however I didn't follow their database and try my own. Currently my database: My Model: class FypCakephp extends AppModel { //Table Name public $useTable = 'Report'; public $primaryKey = 'report_id';} My Controller: public function add()...

ER diagram for booking database

I'm creating a database for booking apartments app. I have a question - it is allowable to keep user's passwords in DB (for example using BCrytp)? Another question - where is the best way to keep price if it may vary during several months?

Does Maria DB support ANSI-89 join syntax

Does Maria DB support ansi-89 join syntax? SELECT sites.site_id, sites.site_name, pages.page_id, pages.page_title FROM sites, pages WHERE sites.site_id = pages.site_id; or only ansi-92 syntax? SELECT sites.site_id, sites.site_name, pages.page_id, pages.page_title FROM sites INNER JOIN pages ON sites.site_id = pages.site_id; ...

Pandas sql update efficiently

I am using python pandas to load data from a MySQL database, change, then update another table. There are a 100,000+ rows so the UPDATE query's take some time. Is there a more efficient way to update the data in the database than to use the df.iterrows() and run an...

Database object with different data

I'm making a web page in ASP.NET MVC which compares prices from different shops. I have a one-to-many with products and the shops, where the SHOP has one PRODUCT and a PRODUCT has many SHOPs, the problem is that the product is the same but the price is different. Example:...

How to use existing SQLite database in swift?

I know there are some resources available for this but none of them clearly show the way how to do it properly. I have already populated .sqlite database (MTrader.db) and i want to connect it to my swift project and load the data from the database into spinner. I tried...

IBM Cognos _days_between function not working

I'm having an issue with Cognos 10. I'm trying to calculate the number of days between to dates so I use the _days_between( date1, date2 ) function. _days_between ([Derniere Date Changement diaphragme] , [Premiere Date Changement diaphragme]) I'm quite sure the two Dates are Date objects ( I set them...

Purging Database - Count purged/not-purged tables

So I am working with a database where I will be purging various tables that contain rows that are older than 30days. I have fairly limited knowledge of SQL and wanted to know if there was a certain way to select the row that will be purged and the rows...

How to omit creating static Map for data caching?

I want to know if it is possible to omit creating cache with static Map instance. Here is snippet of my class: public class XpathEvaluator { private DocumentBuilder builder; private XPath path; private Document document; private static Map<String, List<String>> cachedXpaths = new HashMap<>(); private XpathEvaluator() throws ParserConfigurationException { DocumentBuilderFactory factory...

ElasticSearch asynchronous post

I'm posting data on my ElasticSearch database. I've noticed that data is not immediately available, it requires some milliseconds to show up in a GET request. I can live with that (after all, the calls are asynchronous so this behavior is expected) but in my test code I need to...

sql script to find index's tablespace_name only

Trying to find the specific tablespace names that were created for indexes only. I don't want to see the tablespaces names that are already used for tables. Something like below, but i couldn't have it working due to syntax error. Can someone fix it? select tablespace_name from dba_indexes where tablespace_name...

Order by count not sorting the records correctly?

I am using MySQL. I have two table i have attached the images of the both tables? When i apply ORDER by Count then the query retrieving result's from database but not sorting them correctly, i don't know what wrong i am doing? i searched some similar question in stack...