анализатор логических выражений

pachanga

Новичок
анализатор логических выражений

В начале немного предыстории:

У нас в конторе возникла задача кэшировать sql запрос, но не в файл, а просто в самый обычный хеш массив.

А затем необходимо перенаправлять последущие sql запросы уже не к базе данных, а к этому самому массиву.

Отсюда возникает задача анализировать сколь угодно сложные логические выражения...

Никто не подскажет, гже можно поискать инфу по этой теме?
 

young

Новичок
Для каждого сложного SQL запроса мною писалась отделная функция, которая уже и занималась кешированием.

По другому... Если узнаешь - расскажи и мне
 

young

Новичок
Например мне надо по ID OWNER получить статиску по владельцу за последний месяц

Я делаю
function SELECT_STAT_BY_OWNER($id_owner) {
}

И там реализовую выборку и хеш
 

Crazy

Developer
Я для решение задачи "кэширование sql-запросов" делал класс CacheableSQL с единственным методом: select($querySQL). При этом в объекте содержался массив, где ключом были тексты sql-запросов, в значениями -- массивы результирующих строк.

Понятно, что для больших текстов запросов это требует определенной оптимизации. :)

Вот мне и непонятно: зачем отдельную функцию на каждый запрос. Какие задачи при этом решаются?
 

pachanga

Новичок
Ну вы и любители уйти от темы :)

А все же, никто не реализовывал сабж?
 

si

Administrator
Вы хотите как я понял реализовать SQL в РНР. Вопрос зачем если его знает ваш SQL сервер ?

То что предложил Crazy очень логично и правильно.
 

ForJest

- свежая кровь
А я то дурак хранил запросы в сессиях :) И горя не знал - 1 юзверь, 1 сессия, 1 набор запросов.
Pacha - а ты очень туманно выразился по поводу анализатора - не понятно чего тебе надо. Вообще это задача вроде для конечных автоматов, если я не ошибаюсь. yacc в Unix есть :)
 

.des.

Поставил пиво кому надо ;-)
Совсем небольшое улучшение.. хотя может быть у Crazy так и было.
1. Хранить хеши от запросов.
2. Если речь идет о мускл.. то можно дополнительно обрабатывать лимиты. Если было выбрано раннее 1, 100 то незачем выбирать 20,40

А теперь что касается целесообразности.. - а нужно ли? не затормозит ли это и без того не быстрый пхп? ведь база по идее тоже эффективно должна кэшировать запросы.
 

pachanga

Новичок
Si, да, именно этого я бы и хотел, однако этот самый 'SQL' был бы очень ограниченным, по сути, все сводится к правильному анализу условия where.

Вариант Crazy не подходит, потому что хотелось бы сделать следущее:

Пусть имеется много запросов по выборке информации из базы данных. Причем некоторые из этих запросов отличаются друг от друга только условием where. Поэтому было бы здорово самым первым запросом загнать вообще всю информацию во внутренние массивы без использования where. И остальные запросы прозрачно делать именно к этим массивам.

Скажем, у нас есть 3 запроса:

1)
SELECT * FROM item_type INNER JOIN tree_item
ON item_type.id = tree_item.item_type_id
WHERE (tree_item.id = 3);

2)
SELECT * FROM item_type INNER JOIN tree_item
ON item_type.id = tree_item.item_type_id
WHERE (tree_item.id = 67);

3)
SELECT * FROM item_type INNER JOIN tree_item
ON item_type.id = tree_item.item_type_id
WHERE (tree_item.id = 38);

Так вот во время первого запроса делается кеширование следующего запроса в массивы:

SELECT * FROM item_type INNER JOIN tree_item
ON item_type.id = tree_item.item_type_id

Пусть это будет некий 'схожий источник данных'.

Дальше скрипт анализирует последующие запросы и если выявляет 'схожий источник данных', то делает выборку из массива, а не из бд. Естеснно, если опять встречается уникальный 'схожий источник данных', то вновь делается его кеширование.

На самом деле у нас всего около 50 различных запросов, из которых вот так можно выделить порядка 10 'схожих источников данных'.
Обращения к бд делаются из малосвязанных подмодулей программы, поэтому как-то централизовать и оптимизировать без основательной(и ненужной) переработки кода невозможно.
 

.des.

Поставил пиво кому надо ;-)
2pacha
Некоторые соображения.

насчет схожего источника данных.

Дальше скрипт анализирует последующие запросы и если выявляет 'схожий источник данных', то делает выборку из массива, а не из бд. Естеснно, если опять встречается уникальный 'схожий источник данных', то вновь делается его кеширование.
Если ты имеешь ввиду делать выборку - это поиск по массиву средствами самого пхп то учти только очень ограниченный ряд операций не приведет к бОльшим тормозам. В основном это работа с числовыми значениями!
То есть если вдруг в запросе окажется что то вроде LOCATE("aaa",field); А ты его заменишь на strpos() по каждому элементу кэшированного массива "необходимого источника данных", то ты не только не выиграешь, но и замедлишь работу.
К тому же скрипт будет требовать не мало памяти. Точнее так НЕ МАЛО!

Если же все таки выборки подобные приведенным тобой
или таким MOD(id,2)=0
или таким id<10000 and id>670

То поиск по массиву php будет проводить быстрее. Опять же тут есть и обратная сторона - баланс в ресурсозатратах между бд и php

Да спешу обрадовать :) при совпадении запроса например запросе одного и того же 100 раз подряд и кэш система это распознает - то выигрыши будут ощутимые.. на порядок и более.

Да скорее всего мы откланяемся от изначального вопроса - как осуществить разбор выражения?.. Но ForJest тебе выше ответил, задача для конечных автоматов.
 

clevel

Новичок
а зачем такие сложности? сейчас мускул сделал кеш запросов.. правда релиз этой версии либо скоро выйдет либо только что вышел (не знаю, не отслеживал ситуацию)... и все...
в чем плюсы - не надо кодить, бинарник(мускул) будет это делать быстрее, можно настроить опции кеширования при компиляции мускула (увеличение производительности)..
 

.des.

Поставил пиво кому надо ;-)
Тут я сделал.. некоторые выкладки.. в виде небольших тестов.
В качестве пример взял две таблицы со структурой подходящим к твоим таблицы d1,d2.

CREATE TABLE dN (
id int(11) NOT NULL auto_increment,
name char(20) NOT NULL default '',
uq_field bigint(20) NOT NULL default '0',
note char(250) NOT NULL default '',
PRIMARY KEY (id)
) TYPE=MyISAM;

d1 данные 9,935 кБ индекс 296,960 Байт (35,949 записей)
d2 данные 10,025 кБ индекс 299,008 Байт (36,273 записей)

Итак.
1. Просто выборка из базы.. запрос за запросом. - 101 запрос.
PHP:
$qbase="SELECT d1.id,d1.name, d2.id , d2.name 
                FROM d1 d1 INNER JOIN d2 d2 ON d1.id=d2.id
                WHERE d1.id<10000";

$res=mysql_query($qbase);
echo "Total - ".mysql_num_rows($res)." records<br>\n";

for($i=0;$i<100;$i++)
{
	$qadd=" AND d1.id<5000";
	$res=mysql_query($qbase.$qadd);
	echo "Total - in query qbase - ".$qadd." - ".mysql_num_rows($res)." records<br>\n";
}
Output :
Total - 2490 records
Total - in query qbase - AND d1.id<5000 - 1244 records
.....
.....
вся пpогpамма pаботала 15.0083 сек
PHP:
$cache=array();
$cache_add=array();

function cachesql($query)
{
	static $sbase=0;	
	global $cache;
	global $cache_add;
// Определяем схожий источник данных sbase.
// Упрощая тест, полагаем, что первым запросом идет именно он.
	if ($sbase==0)
	{
		
		$res=mysql_query($query);
		$i=0;
		while($row=mysql_fetch_row($res))
		{
			$cache[$i++]=$row;
		}
		$sbase++;
		return $cache;
	}//if
	else
	{
// Здесь будет проводиться синтаксический разбор. 
// Для упрощения - мы его опускаем. 
			$res=array();
			for($i=0,$c=sizeof($cache);$i<$c;$i++)
			{
				if($cache[$i][0]<5000)
					$cache_add[$i]=$cache[$i];
			}
			$sadd++;
			return $cache_add;
	}//else
}//f cachesql


$qbase="SELECT d1.id,d1.name, d2.id , d2.name FROM d1 d1 INNER JOIN d2 d2 ON d1.id=d2.id WHERE d1.id<10000";

$res=cachesql($qbase);
echo "Total - in query qbase - ".$qadd." - ".sizeof($res)."records <br>\n";

for($i=0;$i<100;$i++)
{
	$qadd=" AND d1.id>5000";
	$res=cachesql($qbase.$qadd);
	echo "Total - in query qbase - ".$qadd." - ".sizeof($res)." records<br>\n";
}
Output:
Total - in query qbase - - 2490 records
Total - in query qbase - AND d1.id<5000 - 1244 records
вся пpогpамма pаботала 5.3017 сек



Соотвественно. Приведу результаты для других типов запросов.

--------------------------------------------------------------
PHP:
 AND MOD(d1.id,2)=0
Total - 2490
Total - in query qbase - AND MOD(d1.id,2)=0 - 1233
вся пpогpамма pаботала 20.2367 сек

PHP:
$cache[$i][0]%2==0
Total - in query qbase - - 2490records
Total - in query qbase - AND d1.id>5000 - 1233 records
вся пpогpамма pаботала 5.6057 сек
--------------------------------------------------------------

--------------------------------------------------------------
PHP:
LOCATE('а',d1.name)>0  (и это без индекса по полю name)
Total - 2490 records
Total - in query qbase - AND LOCATE('а',d1.name)>0 - 1178 records
вся пpогpамма pаботала 20.2786 сек

PHP:
strpos($cache[$i][1],'а')!==FALSE
Total - in query qbase - - 2490records
Total - in query qbase - LOCATE('а',d1.name)>0 - 1178 records
вся пpогpамма pаботала 10.1678 сек
--------------------------------------------------------------

Краткие итоги.
В принципе ускорение выполнения запросов в несколько раз можно назвать приемлемым результатом.
Однако если просто делать return из функции без какого либо разбора выражения то вариант с кэшем выполняется меньше секунды.. оно и понятно он же ничего не делает.

Лично мое мнение писать "разбор запроса" - не стоит оно того. А вдвойне не стоит делать это на пхп.

Изобретать SQL оно тебе надо?
Вот если запросы очень часто повторяются, то как выход написать экстеншин к пхп (реализацию класса Crazy на c :).
И без всякого разбора производительность возрастет.

Если честно мне немного непонятно поведение мускла - абсолютно никакого кэширования :( Если не ошибаюсь это обещали поправить. вроде с 4.1. будет кэширование запросов
 

pachanga

Новичок
Вот спасибо, тов. .des!
Так основательно подошел, спасибо за выкладки и потраченное время!

Теперь по порядку:

1)ну вот тот самый запрос, который я привел, он совершенно искуственный, в жизни сам знаешь как все навороченно бывает. И в тесте вообще-то надо было привести несколько вообще разных 'схожих источников данных'.
mysql, по-моему, какую никакую оптимизацию все же делает: замерь исполнение самого первого запроса и всех последующих.

2)будут использоваться самые базовые SQL операции, для написания безопасного SQL совместимого с популярными бд, т.е. LOCATE вычеркиваем сразу

3)возрастание скорости в ~3.5 раза, хм, не так уж и плохо, учитывая тот факт, что борешься за доли секунды, чтобы сохранить приемлимое время ответной реакции приложения(у нас сейчас страница собирается за 0.9 сек -- 0.3 разница ощутима).
Однако ты прав, сколько займет парсинг логического выражения и представления его неким внутренним образом?
(мне все чудится, что как-то здесь eval можно поюзать)

4)extension - это никак :( , в нашей конторе основным хостером заказчика считается тот, у которого вообще сервак без наворотов

5)то что все это связано с теорией конечных автоматов, я знал в самом начале, когда активно пропускал пары "Теории построения компиляторов" :)

6)такая неприятная вещь как рассинхронизация кеша и оригинала, ведь пока делаются запросы к кешу, оригинал может измениьтся и как это отследить...

7)надо еще не забыть и про order

И все же при всех трудностях реализации, согласись, нестандартная и интересная задача.

Все же, народ, может кто что-то подобное делал?
 

clevel

Новичок
насчет eval - считаю его опасным делом и не использую... мало ли чего в скрипте может оказаться...
 

kvn

programmer
Советую поискать в и-нете такую штуку как textDB, эмуляция SQL DB на файлах, дык там есть этот хлополучный SQL Parser, который делает, как ты сказал "синтаксический анализ логических выражений", причем для SELECT-ов довольно неплохо работает..

Удачи.
 

si

Administrator
Изобретание велосипеда 100%ное. SQL запросы должен выполнять SQL сервер а не PHP. Втягивать все записи в PHP тоже не хорошо, память будет кушать сильно, скорее всего привысит memory limit. Результаты тестов очень сомнительные. Про индексы никто не не помнит чтоли ? в MySQL 4.0.x есть QUERY CACHE который работать будет (и работает) очень быстро

P.S. использую 4.0 уже 2-3 месяца, вполне stable
 

Eugene_E

Guest
Pacha,
если тебе действительно необходим разбор выражений в _общем_ случае,
то самый единственный :) вариант - написать компилятор этих выражений.

Сделать это очень просто! Есть такой инструмент The Lemon Parser Generator, на вход ему подается грамматика в БНФ, на выходе имеется парсер, руками необходимо дописать только семантику и токенайзер. Очень удобное отличие от Яка: Токенайзер вызывает парсер.
 
Сверху