MySQL中的排序

MySQL中的排序

曾经以为filesort是文件排序，后来知道这仅仅是一个排序，文件只是路人甲而已
前些日子从china-pub上买了《Mysql核心内幕》，当浏览到第4章时，以前对MySQL的排序，join buffer不理解的地方，忽然觉得懂了，只是不知道这个懂了是真懂了还是假懂了。
就如当你从一个梦中醒来，难道你就确认你一定不是在做梦了吗？

说说看了什么吧，
filesort排序算法是将一组记录或元素按照快速排序算法放入到内存缓存，然后这几个内存缓存按合并排序算法排序。（摘自《Mysql核心内幕》第82页）
filesort有两种模式：
1、直接模式，将已经数据完全读取出来，然后进行排序
2、指针模式，先根据过滤条件取出排序字段(sort_key)和可以行指针信息(row_id)，根据sort_key排序后，再依据row_id取出取出查询中所请求的其他字段。
第一种算法的优势是减少了数据的二次访问，当然会消耗更多的内存，在算法上来讲是以空间换时间。
MySQL会尽量采用每一种方式，只有在每一种方式不行的情况下才会采用第二种方式（即指针模式）

然后是MySQL的三种排序方法：
1、使用索引排序
2、在单表上使用filesort排序
3、先使用临时表，再使用filesort排序
（摘自《Mysql核心内幕》第83页）

PHP源码阅读笔记四：count函数

PHP源码阅读笔记之count函数

在一些面试或考试中经常会看到count函数的身影，于是一探其究竟

对于非数组的count处理
在其代码中可以看到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

PHP_FUNCTION(count)
{
    zval *array;
    long mode = COUNT_NORMAL;
    if (zend_parse_parameters (ZEND_NUM_ARGS() TSRMLS_CC, "z|l", &array, &mode) == FAILURE)
        return;
    switch (Z_TYPE_P(array)) {
        case IS_NULL:    //    空值处理
            RETURN_LONG(0);
            break;
        case IS_ARRAY:    //    处理数组，包括其是递归
            RETURN_LONG (php_count_recursive (array, mode TSRMLS_CC));
            break;
        case IS_OBJECT: {    
    #ifdef HAVE_SPL
        /* it the object implements Countable we call its count() method */
            zval *retval;
 
            if (Z_OBJ_HT_P(array)->get_class_entry && instanceof_function(Z_OBJCE_P(array), spl_ce_Countable TSRMLS_CC)) {
                zend_call_method_with_0_params(&array, NULL, NULL, "count", &retval);
                if (retval) {
                    convert_to_long_ex(&retval);
                    RETVAL_LONG(Z_LVAL_P(retval));
                    zval_ptr_dtor(&retval);
                }
            return;
            }
    #endif
        /* if not we return the number of properties (not taking visibility into account) */
            if (Z_OBJ_HT_P(array)->count_elements) {
                RETVAL_LONG(1);
                if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_LVAL_P(return_value) TSRMLS_CC)) {
                    return;    
              }
            }
        }
    default:    //    其它情况，如考试中常见的字符串等
        RETURN_LONG(1);
        break;
    }
}

在手册中有说明：
此函数对于对象，如果安装了 SPL，可以通过实现 Countable 接口来调用 count()。该接口只有一个方法 count()，此方法返回 count() 函数的返回值。

对于数组长度的统计，如果mode使用默认值（0），则仅显示第一维数组的长度
如下所示代码

1
2
3
4
5
6
7
8

$arr = array(1, 2, 3);
$arr2 = array($arr, $arr);
echo count($arr2), '<br />';
echo count($arr2, 1);
/*   输出结果：
2
8
*/

如果只是显示第一维数组，则直接返回保存数组的HashTable的nNumOfElements属性即可
其实现的代码为：

1
2
3
4
5
6
7
8
9

//    php_count_recursive函数 array.c 251行
cnt = zend_hash_num_elements(Z_ARRVAL_P(array));
 
ZEND_API int zend_hash_num_elements(HashTable *ht)
{
    IS_CONSISTENT(ht);
 
    return ht->nNumOfElements;
}

如果想直接运行HashTable的一些简单操作，猛击PHP源码中HashTable的简单示例
如果想查看了解数组存储或遍历的方式，猛击鸟哥的深入理解PHP之数组(遍历顺序)

如果启动了递归，即使用count($arr, 1)
则程序会递归调用php_count_recursive函数
针对HashTable，程序会遍历包含这一维数组的双向链表，然后再递归遍历每个节点存储的pData，真到遍历完所有的节点

【感受】
HashTable很强大，如果要计算数组的长度还是调用count函数，重复发明轮子会是一种吃力不讨好的事情！

PHP源码阅读笔记三：strrchr, strstr, stristr函数

PHP源码阅读笔记三：strrchr, strstr, stristr函数

string strrchr ( string haystack, string needle )
返回haystack中最后一个needle（字符）所在位置以后的字符串
如果needle为数字，将这个数字转化为这个值所对应的字符
如果needle多于一个字符串，则取第一个字符
如果haystack为一个数字，会将这个数字直接转化成字符串
程序中调用convert_to_string_ex(haystack);

在此函数的实现中，基本上是对一些特殊情况的处理（如上），
到最后就是定位最后一个needle出现的位置，返回根据位置返回此位置以后的字符串，如果此位置不存在，同返回false

string strstr ( string haystack, string needle )
此函数功能与strrchr类似，只不过它的needle允许为字符串，并且是查找needle第一个出现的位置，根据此位置返回之后的字符串，如果不存在则返回FALSE

在其代码中有一些特别的细节值得学习，如下所示代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

static inline char *zend_memnstr(char *haystack, char *needle, int needle_len, char *end)
{
    char *p = haystack;
    char ne = needle[needle_len-1];
 
    if(needle_len > end-haystack) {
        return NULL;
    }
    end -= needle_len;   //    优化细节一，仅查找end-needle_len长度的字符串
 
    while (p <= end) {
        //    优化细节二，此处先判断字符串的开头和结尾的字符是否一样，如果一样则再判断整个字符串，提升性能
        if ((p = (char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {    
            if (!memcmp(needle, p, needle_len-1)) {
                return p;
            }
        }
 
        if (p == NULL) {
            return NULL;
        }
 
        p++;
    }
 
    return NULL;
}

以上代码是strstr和stristr函数实现的核心代码，功能：查找needle在haystack中首次出现的位置

string stristr ( string haystack, string needle )
stristr函数的功能与strstr类似，所不同的是其不区分大小写。
在PHP源码实现中主要区别是添加了将所有字符串转化为小写的操作，程序实现是在查找之前添加了如下代码：

1
2
3

php_strtolower(s, s_len);
php_strtolower(t, t_len);
return php_memnstr(s, t, t_len, s + s_len);

PS:在看源码的过程中，再次看了《再再认指针》的前面一段话，多了一些体会；
指针能够进行加减法，原因并不是因为它是指针，加减法则不是属于指针这种变量的，而是地址这种数据类型的本能，正是因为地址具有加减的能力，所以才使指针作为存放地址的变量能够进行加减运算。
这跟整数变量因为整数能够进行加减乘除因而它也能进行加减乘除一个道理。
查看《再再论指针》，请猛击再再论指针